zbMATH — the first resource for mathematics

Scheduling algorithms. 3rd ed. (English) Zbl 1051.90011
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.

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