1. Introduction. The Role of Scheduling. The Scheduling Function in an Enterprise. Outline of the Book.
I. DETERMINISTIC MODELS.
2. Deterministic Models: Preliminaries. Framework and Notation. Examples. Classes of Schedules. Complexity Hierarchy.
3. Single Machine Models (Deterministic). The Total Weighted Completion Time. The Maximum Lateness. The Number of Tardy Jobs. The Total Tardiness. The Total Weighted Tardiness. Discussion.
4. More Advanced Single Machine Models (Deterministic). The Total Tardiness: An Approximation Scheme. The Total Earliness and Tardiness. Primary and Secondary Objectives. Multiple Objectives: A Parametric Analysis. The Makespan with Sequence-Dependent Setup Times. Discussion.
5. Parallel Machine Models (Deterministic). The Makespan without Preemptions. The Makespan with Preemptions. The Total Completion Time without Preemptions. The Total Completion Time with Preemptions. Due Date-Related Objectives. Discussion.
6. Flow Shops and Flexible Flow Shops (Deterministic). Flow Shops with Unlimited Intermediate Storage. Flow Shops with Limited Intermediate Storage. Flexible Flow Shops with Unlimited Intermediate Storage.
7. Job Shops (Deterministic). Disjunctive Programming and Branch and Bound. The Shifting Bottleneck Heuristic and the Makespan. The Shifting Bottleneck Heuristic and the Total Weighted Tardiness. Discussion.
8. Open Shops (Deterministic). The Makespan without Preemptions. The Makespan with Preemptions. The Maximum Lateness without Preemptions. The Maximum Lateness with Preemptions. The Number of Tardy Jobs. Discussion.
II. STOCHASTIC MODELS.
9. Stochastic Models: Preliminaries. Framework and Notation. Distributions and Classes of Distributions. Stochastic Dominance. Impact of Randomness on Fixed Schedules. Classes of Policies.
10. Single Machine Models (Stochastic). Arbitrary Distributions without Preemptions. Arbitrary Distributions with Preemptions: The Gittins Index. Likelihood Ratio Ordered Distributions. Exponential Distributions.
11. Single Machine Models with Release Dates (Stochastic). Arbitrary Releases and Arbitrary Processing Times. Priority Queues, Work Conservation, and Poisson Releases. Arbitrary Releases and Exponential Processing Times. Poisson Releases and Arbitrary Processing Times. Discussion.
12. Parallel Machine Models (Stochastic). The Makespan with Preemptions. The Makespan and Total Completion Time with Preemptions. Due-Date Related Objectives.
13. Flow Shops, Job Shops, and Open Shops (Stochastic). Stochastic Flow Shops with Unlimited Intermediate Storage. Stochastic Flow Shops with Blocking. Stochastic Job Shops. Stochastic Open Shops.
III. SCHEDULING IN PRACTICE.
14. General Purpose Procedures for Scheduling in Practice. Dispatching Rules. Composite Dispatching Rules. Filtered Beam Search. Local Search: Simulated Annealing and Tabu-Search. Local Search: Genetic Algorithms. Discussion.
15. More Advanced General Purpose Procedures. Decomposition Methods and Rolling Horizon Procedures. Constraint Guided Heuristic Search. Market-Based and Agent-Based Procedures. Procedures for Scheduling Problems with Multiple Objectives. Discussion.
16. Modeling and Solving Scheduling Problems in Practice. Scheduling Problems in Practice. Cyclic Scheduling of a Flow Line. Flexible Flow Line with Limited Buffers and Bypass. Flexible Flow Line with Unlimited Buffers and Setups. Bank of Parallel Machines with Release Dates and Due Dates. Discussion.
17. Design, Development, and Implementation of Scheduling Systems. Systems Architecture. Databases and Knowledge-Bases. Schedule Generation Issues. User Interfaces and Interactive Optimization. Generic Systems Versus Application-Specific Systems. Implementation and Maintenance Issues.
18. Advanced Concepts in Scheduling System Design. Robustness and Reactive Scheduling. Machine Learning Mechanisms. Design of Scheduling Engines and Algorithm Libraries. Reconfigurable Systems. Scheduling Systems on the Internet. Discussion.
19. Examples of System Designs and Implementations. The SAP-APO System. IBM's Independent Agents Architecture. i2's TradeMatrix Production Scheduler. An Implementation of Cybertec's Cyberplan. Synquests's Virtual Production Engine. The LEKIN System for Research and Teaching. Discussion.
20. What Lies Ahead? Theoretical Research. Applied Research. Systems Development and Integration.
APPENDICES.
Appendix A: Mathematical Programming: Formulations and Applications. Linear Programming Formulations. Integer Programming Formulations. Disjunctive Programming Formulations.
Appendix B: Deterministic and Stochastic Dynamic Programming. Deterministic Dynamic Programming. Stochastic Dynamic Programming.
Appendix C: Complexity Theory. Preliminaries. Polynomial Time Solutions Versus NP-Hardness. Examples.
Appendix D: Complexity Classification of Deterministic Scheduling Problems. Appendix E: Overview of Stochastic Scheduling Problems. Appendix F: Selected Scheduling Systems. REFERENCES.