Recent developments in scheduling (Q4494435)

This paper is a survey of the methods developed for solving intractable scheduling problems. In the first section the authors consider a job shop scheduling problem and its representation by the disjunctive graph model. They give a survey of branch-and-bound algorithms constructed for the job shop problem. Approximation algorithms for this problem are also considered. Here the importance of the local search technique is stressed. The various neighbourhood structures and the resulting efficient tabu search implementations are discussed. The purpose of the second section is to present a class of logical tests called interval capacity consistency tests. These tests have been applied frequently and with great success in branch-and-bound and local search algorithms for solving the job shop problem. The authors also discuss the results on the application of the consistency tests for the resource-constrained project scheduling problem (or so called cumulative scheduling problem). The survey includes about 60 references to the recent publications. For the entire collection see [Zbl 0937.00057].