1 INTRODUCTION

1.1 The Role of Scheduling

1.2 The Scheduling Function in an Enterprise

1.3 Outline of the Book

Part 1 Deterministic Models

2 DETERMINISTIC MODELS:PRELIMINARIES

2.1 Framework and Notation

2.2 Examples

2.3 Classes of Schedules

2.4 Complexity Hierarchy

3 SINGLE MACHINE MODELS(DETERMINISTIC）

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

3.6 Discussion

4 MORE ADVANCED SINGLE MACHINE MODELS(DETERMINISTIC）

4.1 The Total Tardiness:An Approximation Scheme

4.2 The Total Earliness and Tardiness

4.3 Primary and Secondary Objectives

4.4 Multiple Objectives:A Parametric Analysis

4.5 The Makespan with Sequence-Dependent Setup Times

4.6 Discussion

5 PARALLEL MACHINE MODELS(DETERMINISTIC)

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

5.6 Discussion

6 FLOW SHOPS AND FLEXIBLE FLOW SHOPS(DETERMINISTIC)

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

7 JOB SHOPS(DETERMINISTIC)

7.1 Disjunctive Programming and Branch and Bound

7.2 The Shifting Bottleneck Heuristic and the Makespan

7.3 The Shifting Bottleneck Heuristic and the Total Weighted Tardiness

7.4 Discussion

8 OPEN SHOPS(DETERMINISTIC)

8.1 The Makespan without Preemptions

8.2 The Makespan with Preemptions

8.3 The Maximum Lateness without Preemptions

8.4 The Maximum Lateness with Preemptions

8.5 The Number of Tardy Jobs

8.6 Discussion

Part 2 Stochastic Models

9 STOCHASTIC MODELS:PRELIMINARIES

9.1 Framework and Notation

9.2 Distributions and Classes of Distributions

9.3 Stochastic Dominance

9.4 Impact of Randomness on Fixed Schedules

9.5 Classes of Policies

10 SINGLE MACHINE MODELS(STOCHASTIC)

10.1 Arbitrary Distributions without Preemptions

10.2 Arbitrary Distributions with Preemptions:The Gittins Index

10.3 Likelihood Ratio Ordered Distributions

10.4 Exponential Distributions

11 SINGLE MACHINE MODELS WITH RELEASE DATES(STOCHASTIC)

11.1 Arbitrary Releases and Arbitrary Processing Times

11.2 Priority Queues,Work Conservation,and Poisson Releases

11.3 Arbitrary Releases and Exponential Processing Times

11.4 Poisson Releases and Arbitrary Processing Times

11.5 Discussion

12 PARALLEL MACHINE MODELS(STOCHASTIC)

12.1 The Makespan without Preemptions

12.2 The Makespan and Total Completion Time with Preemptions

12.3 Due Date-Related Objectives

13 FLOW SHOPS,JOB SHOPS,AND OPEN SHOPS(STOCHASTIC)

13.1 Stochastic Flow Shops with Unlimited Intermediate Storage

13.2 Stochastic Flow Shops with Blocking

13.3 Stochastic Job Shops

13.4 Stochastic Open Shops

Part 3 Scheduling in Practice

14 GENERAL PURPOSE PROCEDURES FOR SCHEDULING IN PRACTICE

14.1 Dispatching Rules

14.2 Composite Dispatching Rules

14.3 Filtered Beam Search

14.4 Local Search:Simulated Annealing and Tabu-Search

14.5 Local Search:Genetic Algorithms

14.6 Discussion

15 MORE ADVANCED GENERAL PURPOSE PROCEDURES

15.1 Decomposition Methods and Rolling Horizon Procedures

15.2 Constraint Guided Heuristic Search

15.3 Market-Based and Agent-Based Procedures

15.4 Procedures for Scheduling Problems with Multiple Objectives

15.5 Discussion

16 MODELING AND SOLVING SCHEDULING PROBLEMS IN PRACTICE

16.1 Scheduling Problems in Practice

16.2 Cyclic Scheduling of a Flow Line

16.3 Flexible Flow Line with Limited Buffers and Bypass

16.4 Flexible Flow Line with Unlimited Buffers and Setups

16.5 Bank of Parallel Machines with Release Dates and Due Dates

16.6 Discussion

17 DESIGN,DEVELOPMENT,AND IMPLEMENTATION OF SCHEDULING SYSTEMS

17.1 Systems Architecture

17.2 Databases and Knowledge-Bases

17.3 Schedule Generation Issues

17.4 User Interfaces and Interactive Optimization

17.5 Generic Systems Versus Application-Specific Systems

17.6 Implementation and Maintenance Issues

18 ADVANCED CONCEPTS IN SCHEDULING SYSTEM DESIGN

18.1 Robustness and Reactive Scheduling

18.2 Machine Learning Mechanisms

18.3 Design of Scheduling Engines and Algorithm Libraries

18.4 Reconfigurable Systems

18.5 Scheduling Systems on the Internet

18.6 Discussion

19 EXAMPLES OF SYSTEM DESIGNS AND IMPLEMENTATIONS

19.1 The SAP-APO System

19.2 IBM's Independent Agents Architecture

19.3 i2's TradeMatrix Production Scheduler

19.4 An Implementation of Cybertec's Cyberplan

19.5 Synquest's Virtual Production Engine

19.6 The LEKIN System for Research and Teaching

19.7 Discussion

20 WHAT LIES AHEAD?

20.1 Theoretical Research

20.2 Applied Research

20.3 Systems Development and Integration

APPENDIXES

A MATHEMATICAL PROGRAMMING:FORMULATIONS AND APPLICATIONS

A.1 Linear Programming Formulations

A.2 Integer Programming Formulations

A.3 Disjunctive Programming Formulations

B DETERMINISTIC AND STOCHASTIC DYNAMIC PROGRAMMING

B.1 Deterministic Dynamic Programming

B.2 Stochastic Dynamic Programming

C COMPLEXITY THEORY

C.1 Preliminaries

C.2 Polynomial Time Solutions Versus NP-Hardness

C.3 Examples

D COMPLEXITY CLASSIFICATION OF DETERMINISTIC SCHEDULING PROBLEMS

E OVERVIEW OF STOCHASTIC SCHEDULING PROBLEMS

F SELECTED SCHEDULING SYSTEMS

REFERENCES

NAME INDEX

SUBJECT INDEX