zbMATH — the first resource for mathematics

Scheduling algorithms. 4th edition. (English) Zbl 1060.90034
Berlin: Springer (ISBN 3-540-20524-1/hbk). xii, 367 p. (2004).
This is a book about scheduling algorithms. Most parts of it are devoted to the discussion of polynomial algorithms. In addition, enumerative procedures based on branch-and-bound concepts and dynamic programming, as well as local search algorithms, are presented. The book contains eleven chapters.
In Chapter 1 a basic traditional classification for the scheduling problems is given. (In later chapters this classification scheme is extended to involve advanced scheduling problems.) In Chapter 2 the author gives a survey of well-known combinatorial optimization problems to which some scheduling problems can be reduced. Besides, the dynamic programming method is discussed. In Chapter 3 the main points of the computational complexity theory are described. Simple reductions between scheduling problems are shown. In addition, the methods of attacking hard combinatorial optimization problems (local search techniques, branch-and-bound algorithms) are considered. Chapters 4 through 6 cover classical scheduling algorithms for solving single machine problems, parallel machine problems and shop scheduling problems.
The final part of the book (Chapters 7 through 11) is devoted to problems discussed in the more recent literature in connection with flexible manufacturing. The algorithms for single machine due-date scheduling problems are presented in Chapter 7. In Chapter 8 single machine batching problems are discussed. In Chapter 9 machine scheduling problems with changeover times are considered. Besides, shop problems with transportation times are introduced. Chapter 10 is devoted to Multi-Purpose Machine (MPM) model. MPM problems with identical and uniform machines as well as MPM shop problems are discussed. Finally, in Chapter 11 single-stage and multi-stage problems with multiprocessor tasks are considered. Moreover, multi-mode multiprocessor-task scheduling problems are discussed.
Most of chapters contain the summarized complexity results. In this edition the complexity columns have been updated. The book is completed by the bibliography which also has been updated and now contains 198 references. The book is well organized. It will be useful for specialists in scheduling theory and in combinatorial optimization.

90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C05 Linear programming
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
90C10 Integer programming
90C27 Combinatorial optimization
90C39 Dynamic programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C59 Approximation methods and heuristics in mathematical programming
90C60 Abstract computational complexity for mathematical programming problems
90C90 Applications of mathematical programming