1;FOREWORD;6 2;Contents;7 3;1 Introduction;13 4;2 Basics;21 4.1;2.1 Sets and Relations;21 4.2;2.2 Problems, Algorithms, Complexity;23 4.3;2.3 Graphs and Networks;33 4.4;2.4 Enumerative Methods;44 4.5;2.5 Heuristic and Approximation Algorithms;47 5;3 Definition, Analysis and Classification of Scheduling Problems;69 5.1;3.1 Definition of Scheduling Problems;69 5.2;3.2 Analysis of Scheduling Problems and Algorithms;74 5.3;3.3 Motivations for Deterministic Scheduling Problems;77 5.4;3.4 Classification of Deterministic Scheduling Problems;80 6;4 Scheduling on One Processor;85 6.1;4.1 Minimizing Schedule Length;85 6.2;4.2 Minimizing Mean Weighted Flow Time;95 6.3;4.3 Minimizing Due Date Involving Criteria;107 6.4;4.4 Minimizing Change-Over Cost;126 6.5;4.5 Other Criteria;134 7;5 Scheduling on Parallel Processors;149 7.1;5.1 Minimizing Schedule Length;149 7.2;5.2 Minimizing Mean Flow Time;180 7.3;5.3 Minimizing Due Date Involving Criteria;185 7.4;5.4 Other Models;194 8;6 Communication Delays and Multiprocessor Tasks;210 8.1;6.1 Introductory Remarks;210 8.2;6.2 Scheduling Multiprocessor Tasks;216 8.3;6.3 Scheduling Uniprocessor Tasks with Communication Delays;232 8.4;6.4 Scheduling Divisible Tasks;239 9;7 Scheduling in Hard Real-Time Systems;253 9.1;7.1 Introduction;253 9.2;7.2 Basic Notions;258 9.3;7.3 Single Processor Scheduling;262 9.4;7.4 Scheduling Periodic Tasks on Parallel Processors;274 9.5;7.5 Resources;275 9.6;7.6 Variations of the Periodic Task Model;276 10;8 Flow Shop Scheduling;280 10.1;8.1 Introduction;280 10.2;8.2 Exact Methods;283 10.3;8.3 Approximation Algorithms;291 10.4;8.4 Scheduling Flexible Flow Shops;300 11;9 Open Shop Scheduling;330 11.1;9.1 Complexity Results;330 11.2;9.2 A Branch and Bound Algorithm for Open Shop ScheduUng;332 12;10 Scheduling in Job Shops;353 12.1;10.1 Introduction;353 12.2;10.2 Exact Methods;360 12.3;10.3 Approximation Algorithms;368 12.4;10.4 Conclusions;395 13;11 Scheduling with Limited Processor Availability;405 13.1;11.1 Problem Definition;406 13.2;11.2 One Machine Problems;409 13.3;11.3 Parallel Machine Problems;411 13.4;11.4 Shop Problems;422 13.5;11.5 Conclusions;425 14;12 Scheduling under Resource Constraints;433 14.1;12.1 Classical Model;433 14.2;12.2 Scheduling Multiprocessor Tasks;444 14.3;12.3 Scheduling with Continuous Resources;458 15;13 Constraint Programming and Disjunctive Scheduling;484 15.1;13.1 Introduction;484 15.2;13.2 Constraint Satisfaction;486 15.3;13.3 The Disjunctive Scheduling Problem;500 15.4;13.4 Constraint Propagation and the DSP;504 15.5;13.5 Conclusions;537 15.6;13.6 Appendix: Bound Consistency Revisited;538 16;14 Scheduling in Flexible Manufacturing Systems;546 16.1;14.1 Introductory Remarks;546 16.2;14.2 Scheduling Dynamic Job Shops;549 16.3;14.3 Simultaneous Scheduling and Routing in some FMS;557 16.4;14.4 Batch Scheduling in Flexible Flow Shops under Resource Constraints;566 17;15 Computer Integrated Production Scheduling;590 17.1;15.1 Scheduling in Computer Integrated Manu-facturing;591 17.2;15.2 A Reference Model for Production Scheduling;596 17.3;15.3 IPS: An Intelligent Production Scheduling System;604 18;Index;638