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.

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)

##### 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 |