Scheduling Algorithms

Besides scheduling problems for single and parallel machines and shop scheduling problems the book covers advanced models involving due-dates, sequence dependent changeover times and batching. Also multiprocessor task scheduling and problems with multipurpose machines are discussed. The methods used to solve these problems are linear programming, dynamic programming, branch-and-bound algorithms, and local search heuristics. Complexity results for the different classes of deterministic scheduling problems are summarized. Front Matter....Pages i-xii Classification of Scheduling Problems....Pages 1-10 Some Problems in Combinatorial Optimization....Pages 11-35 Computational Complexity....Pages 36-60 Single Machine Scheduling Problems....Pages 61-100 Parallel Machines....Pages 101-144 Shop Scheduling Problems....Pages 145-228 Due-Date Scheduling....Pages 229-251 Batching Problems....Pages 252-263 Changeover Times and Transportation Times....Pages 264-273 Multi-Purpose Machines....Pages 274-297 Multiprocessor Tasks....Pages 298-320 Back Matter....Pages 321-342