Scheduling algorithms. 3rd ed. (English) Zbl 1051.90011

Brucker, Peter

Berlin: Springer (ISBN 3-540-41510-6/hbk). xii, 365 p. (2001).

For a review of the first edition see Zbl 0839.90059, of the second edition see Zbl 0914.90157.
Publisher’s description: Besides scheduling problems for single and parallel machines and shop scheduling problems the book covers advanced models involving due-dates, sequence dependent changeover times and batching. Also multiprocessor task scheduling and problems with multipurpose machines are discussed. The methods used to solve these problems are linear programming, dynamic programming, branch-and-bound algorithms, and local search heuristics. Complexity results for the different classes of deterministic scheduling problems are summarized.
In the third edition of the book the complexity status of the different classes of scheduling problems is updated and corresponding references are added. New polynomial algorithms for single machine problems with release times and constant processing times are added.

MSC:

90B35	Deterministic scheduling theory in operations research
90C60	Abstract computational complexity for mathematical programming problems
68M20	Performance evaluation, queueing, and scheduling in the context of computer systems
90C27	Combinatorial optimization
90-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
90C57	Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59	Approximation methods and heuristics in mathematical programming
90C05	Linear programming
90C39	Dynamic programming