Current trends in deterministic scheduling

Scheduling is concerned with allocating limited resources to tasks to optimize certain objective functions. Due to the popularity of the Total Quality Management concept, on-time delivery of jobs has become one of the crucial factors for customer satisfaction. Scheduling plays an important role in achieving this goal. Recent developments in scheduling theory have focused on extending the models to include more practical constraints. Furthermore, due to the complexity studies conducted during the last two decades, it is now widely understood that most practical problems are NP-hard. This is one of the reasons why local search methods have been studied so extensively during the last decade. In this paper, we review briefly some of the recent extensions of scheduling theory, the recent developments in local search techniques and the new developments of scheduling in practice. Particularly, we survey two recent extensions of theory: scheduling with a 1-job-on-r-machine pattern and machine scheduling with availability constraints. We also review several local search techniques, including simulated annealing, tabu search, genetic algorithms and constraint guided heuristic search. Finally, we study the robotic cell scheduling problem, the auto-mated guided vehicles scheduling problem, and the hoist scheduling problem. Copyright Kluwer Academic Publishers 1997