Brucker, Peter 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. Reviewer: I. N. Lushchakova (Minsk) Cited in 1 ReviewCited in 63 Documents MSC: 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 Keywords:scheduling; polynomial algorithms; computational complexity; linear programming; dynamic programming; branch-and-bound; heuristics Citations:Zbl 0914.90157; Zbl 0839.90059; Zbl 1051.90011 PDFBibTeX XMLCite \textit{P. Brucker}, Scheduling algorithms. 4th edition. Berlin: Springer (2004; Zbl 1060.90034)