Recent developments in scheduling

Authors Ulrich Dorndorf, Erwin Pesch, Toàn Phan-Huy

Publication date 5 February 2002

branch-and-bound algorithm consistency test job shop local search resource constrained project scheduling survey tabu search

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Deterministic scheduling theory in operations research (90B35) Search theory (90B40) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Review text

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].

Recommendations

Cited in

(10)

This page was built for publication: Recent developments in scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4494435)