This chapter of the Handbook of Combinatorial Optimization surveys research on deterministic machine scheduling. Special attention has been focused on single machine, parallel machine, open shop, flow shop and job shop models. This includes statement of complexity results (polynomial, NP-hard, strongly NP-hard, or open), description of enumerative algorithms together with an indication of the size of instances that they might be expected to solve efficiently, the main features of local search methods including an indication of their ability to generate near-optimal solutions, and details of performance guarantee for approximation algorithms. The chapter is accompanied by a list of 574 references.
The two-stage contents of the chapter is as follows:
1) Introduction,
2) Scheduling Models: Machine Environments, Job Characteristics, Optimality Criteria, Three-Field Representation.
3) Methodology: Computational Complexity, Enumerative Algorithms, Local Search, Approximation Algorithms.
4) Single Machine Problems: Maximum Lateness, Total Weighted Completion Time, Total Weighted Tardiness, Weighted Tardiness, Weighted Number of Late Jobs, Total Weighted Earliness and Tardiness, Other Criteria.
5) Parallel Machine Problems: Unit-Length Jobs a Preemption: Minmax Criteria, Minsum Criteria, Precedence Constraints, On-Line Algorithms.
6) Parallel Machine Problems: No Preemption: Minmax Criteria, Minsum Criteria, Precedence Constraint, On-Line Algorithms.
7) Multi-Stage Problems: The Open Shop, The Flow Shop, The Job Shop, Other Multi-Stage Problems.
8) Further Scheduling Models:
Family Scheduling, Scheduling Multiprocessor Jobs, Scheduling with Communication Delays, Resource Constrained Scheduling, Scheduling with Controllable Processing Times.
Concluding Remarks.
For the entire collection see [Zbl 0914.90002].