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 1. Introduction.- 2. Problem Formulation.- 2.1. Notations and representations.- 2.2. Restrictive assumptions.- 2.3. Optimality criteria.- 2.3.1. Regular measures.- 2.3.1.1. Criteria based on completion times.- 2.3.1.2. Criteria based on due dates.- 2.3.1.3. Criteria based on inventory cost and utilization.- 2.3.2. Relations between criteria.- 2.3.3. Analysis of scheduling costs.- 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.3.1. [Bowman 1959].- 3.3.2. [Pritsker et al. 1969] Front Matter....Pages I-IX Introduction....Pages 1-4 Problem formulation....Pages 5-29 Methods of solution....Pages 30-55 One-machine problems....Pages 56-88 Two-machine and three-machine problems....Pages 89-105 General flow-shop and job-shop problems....Pages 106-130 Concluding remarks....Pages 131-142 Back Matter....Pages 143-180