Machine Scheduling Problems: Classification, Complexity and Computations

ISBN-13: 9789024718481 / Angielski / Miękka / 1976 / 190 str.

A. H. G. Rinnooy Kan

Opis

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.

Spis treści

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].- 3.3.3. [Wagner 1959].- 3.3.4. [Manne 1960].- 3.3.5. [Nepomiastchy 1973].- 3.4. Branch-and-bound.- 3.5. Dynamic programming.- 3.5.1. [Held and Karp 1962; Lawler 1964].- 3.5.2. [Lawler and Moore 1969].- 3.6. Complexity theory.- 3.7. Heuristic methods.- 3.7.1. Priority rules.- 3.7.2. Bayesian analysis.- 4. One-Machine Problems.- 4.1. n|1?cmax problems.- 4.1.1. The n|1?Cmax problem.- 4.1.2. The n|1?Lmax problem.- 4.1.3. The general n|1?cmax problem.- 4.2. n|1|i|Cmax problems.- 4.2.1. The n|1|ri0|cmax problem.- 4.2.1.1. Lower bound by job splitting.- 4.2.1.2. The algorithm of McMahon and Florian 62.- 4.2.1.3. Precedence constraints.- 4.2.2. The n|1|seq dep|cmax problem.- 4.2.3. The n|1|prec|cmax problem.- 4.3. n|1??ci problems.- 4.3.1. The n|1??wiCi problem.- 4.3.2. The n|1??wiTi problem.- 4.3.3. The general n|1??Ci problem.- 4.3.3.1. Elimination criteria.- 4.3.3.2. A branch-and-bound algorithm.- 4.4. n|1|?|?Ci problems.- 4.4.1. The n|1|ri ? 0|?Ci problem.- 4.4.2. The n|1|seq dep|?Ci problem.- 4.4.3. The n|1|prec|?Ci problem.- 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.1.1. Elimination criteria for the n|m|P|Cmax problem.- 6.1.2. Lower bounds for the n|m|P|cmax problem.- 6.2. The n|m|F|? problem.- 6.3. The n|m|G|? problem.- 6.3.1. Lower bounds.- 6.3.2. Branching rules.- 6.3.2.1. The procedure ‘actsched’.- 6.3.2.2. Branching on disjunctive arcs.- 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.