TABLE OF CONTENTS

PREFACE

Introduction

1.1 The Role of Scheduling
1.2 The Scheduling Function in an Enterprise
1.3 Outline of the Book

PART I: DETERMINISTIC MODELS

Deterministic Models: Preliminaries

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

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

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

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

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

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

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 II: STOCHASTIC MODELS

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

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

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

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

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 III: SCHEDULING IN PRACTICE

General Purpose Proceedures 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

More Advanced General Purpose Proceedures

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

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 ParallelMachines with Release Dates and Due Dates
16.6 Discussion

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

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

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

What Lies Ahead?

20.1 Theoretical Research
20.2 Applied Research
20.3 Systems Development and Integration

PART IV: APPENDIXES

Mathematical Programming: Formulations and Applications

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

Michael Pinedo