Machine Scheduling Problems

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.