An environment-driven, function-based approach to dynamic single-machine scheduling

In this paper, the dynamic single-machine scheduling problem with a sequence-dependent setup time and with minimising total weighted tardiness of jobs as the objective is investigated. Due to the dynamic nature of the problem, a function-based approach is developed that can capture dynamic characteristics associated with the environment. In order to find a function which maps the environment's states to an action at each decision point, a combination of simulated annealing and a multi-layer feed-forward neural network is employed in an algorithm named SANN. The efficiency of the proposed function-based approach is compared with the most commonly used dispatching rules and with an agent-based approach, which employs the Q-learning algorithm to develop a decision-making policy. Numerical results reveal that the proposed approach outperforms dispatching rules and the Q-learning algorithm. The mean value of the results is about 93% better than the mean of the best results obtained with dispatching rules. [Received 4 January 2010; Revised 28 September 2010, 22 February 2011, 6 June 2011, 28 June 2011; Accepted 3 July 2011].