Machine Scheduling Problems: Classification, complexity and computations

This book is the result of a doctoral dissertation written under the super- vision of professor dr. G. de Leve of the University of Amsterdam. I am very grateful to him for suggesting the subject and for his guidance and support during the preparation. Professor dr. ir. J. S. Folkers has carefully read various drafts of the manuscript; I would like to thank him for his many helpful comments and suggestions. I have also greatly benefited from the advice of Gene Lawler, who spent the summer of 1975 in Amsterdam at the invitation of the Stichting Mathematisch Centrum. A quick glance at the bibliography already indicates how much lowe to the extensive cooperation with Jan Karel Lenstra. Many of the results in this book are the outcome of our joint research. I am similarly grateful to Ben Lageweg, who actively participated in many projects and who was in charge of all computational experiments. The Graduate School of Management in Delft provided a stimulating professional environment. In particular I want to acknowledge the inspiring advice of David Bree and the useful contributions by Erik de Leede, Hans Geilenkirchen, Jaap Galjaard and Jan Knipscheer. I would like to thank Peter Brucker, Robbert Peters, K. Boskma, Michael Florian and Graham McMahon for their valuable written reactions. I am also grateful to Hendrik Lenstra II and Peter van Emde Boas for various illuminating conversations and to Bernard Dorhout for his kind cooperation.

Table of Contents:
1. Introduction.- 2. Problem Formulation.- 2.1. Notations and representations.- 2.2. Restrictive assumptions.- 2.3. Optimality criteria.- 2.4. Classification of problems.- 3. Methods of Solution.- 3.1. Complete enumeration.- 3.2. Combinatorial analysis.- 3.3. Mixed integer and non-linear programming.- 3.4. Branch-and-bound.- 3.5. Dynamic programming.- 3.6. Complexity theory.- 3.7. Heuristic methods.- 4. One-Machine Problems.- 4.1. n|1?cmax problems.- 4.2. n|1|i|Cmax problems.- 4.3. n|1??ci problems.- 4.4. n|1|?|?Ci problems.- 5. Two-Machine and Three-Machine Problems.- 5.1. The n|2|?,?|cmax and n|3|?,?|cmax problem.- 5.2. The n|2|F|?Ci problem.- 5.3. The n|2|P|Cmax problem with time lags.- 6. General Flow-Shop and Job-Shop Problems.- 6.1. The n|m|P|? problem.- 6.2. The n|m|F|? problem.- 6.3. The n|m|G|? problem.- 6.4. The n|m|?, no wait|? problem.- 7. Concluding Remarks.- 7.1. Complexity of scheduling problems.- 7.2. Practical scheduling problems.- 7.3. Conclusions.- List Of Notations.- References.- Author Index.