TABLE OF CONTENTS:

Chapter 1. Introduction.

1.1. The Role of Scheduling
1.2. The Place of Scheduling within an Organization
1.3. Outline of the Book.

PART I: DETERMINISTIC MODELS

Chapter 2. Deterministic Models Preliminaries.

2.1. Framework and Notation
2.2. Examples
2.3. Classes of Schedules
2.4. Complexity Hierarchy

Chapter 3. Single Machine Deterministic Models.

3.1. The Total Weighted Completion Time
3.2. The Maximum Lateness
3.3. The Number of Tardy Jobs
3.4. The Total Tardiness
3.5. The Total Weighted Tardiness

Chapter 4. More Advanced Single Machine Deterministic Models.

4.1. The Total Tardiness Revisited
4.2. The Total Earliness and Tardiness
4.3. Bicriteria Problems
4.4. Parametric Analysis and Trade-Off Curves
4.5. The Makespan with Sequence Dependent Setup Times

Chapter 5. Parallel Machines Deterministic Models.

5.1. The Makespan without Preemptions
5.2. The Makespan with Preemptions
5.3. The Total Completion Time without Preemptions
5.4. The Total Completion Time with Preemptions
5.5. Due Date Related Objectives

Chapter 6. Deterministic Flow Shops and Flexible Flow Shops.

6.1. Flow Shops with Unlimited Intermediate Storage
6.2. Flow Shops with Limited Intermediate Storage
6.3. Flexible Flow Shops with Unlimited Intermediate Storage

Chapter 7. Deterministic Open Shops and Job Shops.

7.1. Open Shops
7.2. Job Shops
7.3. The Shifting Bottleneck Heuristic
7.4. Discussion

PART II STOCHASTIC MODELS

Chapter 8. Stochastic Models Preliminaries

8.1. Framework and Notation
8.2. Distributions and Classes of Distributions
8.3. Stochastic Dominance
8.4. Impact of Randomness on Fixed Schedules
8.5. Classes of Policies

Chapter 9. Single Machine Stochastic Models.

9.1. Arbitrary Distributions without Preemptions
9.2. Arbitrary Distributions with Preemptions: the Gittins Index
9.3. Likelihood Ratio Ordered Distributions
9.4. Exponential Distributions

Chapter 10. Single Machine Stochastic Models with Release Dates

10.1. Stochastic Scheduling and Priority Queues
10.2. Work Conservation
10.3. Arbitrary Release Dates and Exponential Processing Times
10.4. Arbitrary Release Dates and Arbitrary Processing Times
10.5. Poisson Release Dates and Arbitrary Processing Times

Chapter 11. Parallel Machines Stochastic Models

11.1. The Makespan without Preemptions
11.2. The Makespan and Total Completion Time with Preemptions
11.3. Due Date Related Objectives

Chapter 12. Stochastic Flows Shops, Open Shops and Job Shops.

12.1. Stochastic Flow Shops with Unlimited Intermediate Storage
12.2. Stochastic Flow Shops with Blocking
12.3. Stochastic Open Shops
12.4. Stochastic Job Shops

PART III APPLICATIONS

Chapter 13. Examples of Models of Scheduling Problems in Practice

13.1. Scheduling Problems in Practice
13.2. Cyclic Scheduling of a Flow Line
13.3. Scheduling of a Flexible Flow line with Limited Buffers and Bypass
13.4. Scheduling of a Flexible Flow Line with Unlimited Buffers and Setups
13.5. Scheduling of a Bank of Parallel Machines with Release and Due Dates
13.6. Discussion

Chapter 14. General Purpose Procedures in Practice

14.1. Dispatching rules
14.2. Branch and Bound
14.3. Beam Search
14.4. Dynamic Programming
14.5. Local Search: Simulated Annealing and Tabu-Search
14.6. Local Search: Genetic Algorithms
14.7. Discussion

Chapter 15. More Advanced General Purpose Procedures

15.1. Decomposition Methods and Rolling Horizon Procedures
15.2. Pricing and Auction Based Mechanisms
15.3. Constraint Guided Heuristic Search
15.4. Machine Learning Mechanisms
15.5. Discussion

Chapter 16. Design and Implementation of Scheduling Systems: Basic Concepts

16.1. Systems Architecture
16.2. Databases and Knowledge-Bases
16.3. Schedule Generation Issues
16.4. User Interfaces
16.5. Generic Systems versus Application-Specific Systems
16.6. Implementation Issues

Chapter 17. Design and Implementation of Scheduling Systems: More Advanced Concepts

17.1. Reconfigurable Systems
17.2. Randomness, Robustness, and Reactive Scheduling
17.3. Multiple Objectives
17.4. Market Based Designs
17.5. Scheduling Systems on the Internet
17.6. Discussion

Chapter 18. Scheduling Systems: Examples of Implementations

18.1. I2 Rhythm: a Commercial Generic System
18.2. BPSS: an Application-Specific System Based on an Algorithmic Approach
18.3. GATES: an Application-Specific System Based on a Knowledge-Based Approach
18.4. Lekin: an Academic Prototype
18.5. Discussion

APPENDICES

Appendix A. Mathematical Programming: Formulations and Applications

A.1. Linear Programming Formulations
A.2. Integer Programming Formulations
A.3. Disjunctive Programming Formulations

Appendix B. Deterministic and Stochastic Dynamic Programming

B.1. Deterministic Dynamic Programming
B.2. Stochastic Dynamic Programming

Appendix C. Complexity Theory

C.1. Preliminaries
C.2. Polynomial Time Solutions versus NP-Hardness
C.3. Examples

Appendix D. Complexity Classification of Scheduling Problems

D.1. Problems Solvable in Polynomial Time
D.2. Problems Solvable in Pseudo-Polynomial Time
D.3. Strongly NP-Hard problems

Appendix E. Overview of Stochastic Scheduling Problems

E.1. Tractable Stochastic Scheduling Problems
E.2. Comparisons of Stochastic Scheduling Problems to their Deterministic Counterparts

Appendix F. Selected Scheduling Systems

F.1. Generic Systems
F.2. Application-Specific Systems
F.3. Academic Prototypes

REFERENCES