1 INTRODUCTION 1
1.1 The Role of Scheduling 1
1.2 The Scheduling Function in an Enterprise 4
1.3 Outline of the Book 6
Part 1 Deterministic Models 11
2 DETERMINISTIC MODELS:PRELIMINARIES 13
2.1 Framework and Notation 14
2.2 Examples 20
2.3 Classes of Schedules 21
2.4 Complexity Hierarchy 26
3 SINGLE MACHINE MODELS(DETERMINISTIC） 33
3.1 The Total Weighted Completion Time 34
3.2 The Maximum Lateness 40
3.3 The Number of Tardy Jobs 46
3.4 The Total Tardiness 49
3.5 The Total Weighted Tardiness 53
3.6 Discussion 57
4 MORE ADVANCED SINGLE MACHINE MODELS(DETERMINISTIC） 62
4.1 The Total Tardiness:An Approximation Scheme 63
4.2 The Total Earliness and Tardiness 66
4.3 Primary and Secondary Objectives 74
4.4 Multiple Objectives:A Parametric Analysis 76
4.5 The Makespan with Sequence-Dependent Setup Times 79
4.6 Discussion 88
5 PARALLEL MACHINE MODELS(DETERMINISTIC) 93
5.1 The Makespan without Preemptions 94
5.2 The Makespan with Preemptions 105
5.3 The Total Completion Time without Preemptions 112
5.4 The Total Completion Time with Preemptions 116
5.5 Due Date-Related Objectives 119
5.6 Discussion 121
6 FLOW SHOPS AND FLEXIBLE FLOW SHOPS(DETERMINISTIC) 129
6.1 Flow Shops with Unlimited Intermediate Storage 130
6.2 Flow Shops with Limited Intermediate Storage 142
6.3 Flexible Flow Shops with Unlimited Intermediate Storage 150
7 JOB SHOPS(DETERMINISTIC) 156
7.1 Disjunctive Programming and Branch and Bound 157
7.2 The Shifting Bottleneck Heuristic and the Makespan 167
7.3 The Shifting Bottleneck Heuristic and the Total Weighted Tardiness 174
7.4 Discussion 181
8 OPEN SHOPS(DETERMINISTIC) 186
8.1 The Makespan without Preemptions 187
8.2 The Makespan with Preemptions 191
8.3 The Maximum Lateness without Preemptions 193
8.4 The Maximum Lateness with Preemptions 198
8.5 The Number of Tardy Jobs 203
8.6 Discussion 204
Part 2 Stochastic Models 209
9 STOCHASTIC MODELS:PRELIMINARIES 211
9.1 Framework and Notation 212
9.2 Distributions and Classes of Distributions 212
9.3 Stochastic Dominance 217
9.4 Impact of Randomness on Fixed Schedules 220
9.5 Classes of Policies 223
10 SINGLE MACHINE MODELS(STOCHASTIC) 231
10.1 Arbitrary Distributions without Preemptions 231
10.2 Arbitrary Distributions with Preemptions:The Gittins Index 238
10.3 Likelihood Ratio Ordered Distributions 243
10.4 Exponential Distributions 247
11 SINGLE MACHINE MODELS WITH RELEASE DATES(STOCHASTIC) 258
11.1 Arbitrary Releases and Arbitrary Processing Times 259
11.2 Priority Queues,Work Conservation,and Poisson Releases 261
11.3 Arbitrary Releases and Exponential Processing Times 266
11.4 Poisson Releases and Arbitrary Processing Times 272
11.5 Discussion 278
12 PARALLEL MACHINE MODELS(STOCHASTIC) 283
12.1 The Makespan without Preemptions 284
12.2 The Makespan and Total Completion Time with Preemptions 293
12.3 Due Date-Related Objectives 302
13 FLOW SHOPS,JOB SHOPS,AND OPEN SHOPS(STOCHASTIC) 308
13.1 Stochastic Flow Shops with Unlimited Intermediate Storage 309
13.2 Stochastic Flow Shops with Blocking 316
13.3 Stochastic Job Shops 321
13.4 Stochastic Open Shops 322
Part 3 Scheduling in Practice 333
14 GENERAL PURPOSE PROCEDURES FOR SCHEDULING IN PRACTICE 335
14.1 Dispatching Rules 336
14.2 Composite Dispatching Rules 338
14.3 Filtered Beam Search 342
14.4 Local Search:Simulated Annealing and Tabu-Search 345
14.5 Local Search:Genetic Algorithms 352
14.6 Discussion 353
15 MORE ADVANCED GENERAL PURPOSE PROCEDURES 359
15.1 Decomposition Methods and Rolling Horizon Procedures 360
15.2 Constraint Guided Heuristic Search 364
15.3 Market-Based and Agent-Based Procedures 373
15.4 Procedures for Scheduling Problems with Multiple Objectives 380
15.5 Discussion 386
16 MODELING AND SOLVING SCHEDULING PROBLEMS IN PRACTICE 391
16.1 Scheduling Problems in Practice 392
16.2 Cyclic Scheduling of a Flow Line 396
16.3 Flexible Flow Line with Limited Buffers and Bypass 401
16.4 Flexible Flow Line with Unlimited Buffers and Setups 407
16.5 Bank of Parallel Machines with Release Dates and Due Dates 413
16.6 Discussion 414
17 DESIGN,DEVELOPMENT,AND IMPLEMENTATION OF SCHEDULING SYSTEMS 419
17.1 Systems Architecture 420
17.2 Databases and Knowledge-Bases 421
17.3 Schedule Generation Issues 426
17.4 User Interfaces and Interactive Optimization 429
17.5 Generic Systems Versus Application-Specific Systems 435
17.6 Implementation and Maintenance Issues 438
18 ADVANCED CONCEPTS IN SCHEDULING SYSTEM DESIGN 444
18.1 Robustness and Reactive Scheduling 445
18.2 Machine Learning Mechanisms 450
18.3 Design of Scheduling Engines and Algorithm Libraries 455
18.4 Reconfigurable Systems 459
18.5 Scheduling Systems on the Internet 461
18.6 Discussion 464
19 EXAMPLES OF SYSTEM DESIGNS AND IMPLEMENTATIONS 468
19.1 The SAP-APO System 469
19.2 IBM's Independent Agents Architecture 472
19.3 i2's TradeMatrix Production Scheduler 476
19.4 An Implementation of Cybertec's Cyberplan 483
19.5 Synquest's Virtual Production Engine 488
19.6 The LEKIN System for Research and Teaching 493
19.7 Discussion 500
20 WHAT LIES AHEAD? 502
20.1 Theoretical Research 503
20.2 Applied Research 505
20.3 Systems Development and Integration 507
APPENDIXES 511
A MATHEMATICAL PROGRAMMING:FORMULATIONS AND APPLICATIONS 513
A.1 Linear Programming Formulations 513
A.2 Integer Programming Formulations 518
A.3 Disjunctive Programming Formulations 522
B DETERMINISTIC AND STOCHASTIC DYNAMIC PROGRAMMING 525
B.1 Deterministic Dynamic Programming 525
B.2 Stochastic Dynamic Programming 529
C COMPLEXITY THEORY 533
C.1 Preliminaries 533
C.2 Polynomial Time Solutions Versus NP-Hardness 536
C.3 Examples 539
D COMPLEXITY CLASSIFICATION OF DETERMINISTIC SCHEDULING PROBLEMS 543
E OVERVIEW OF STOCHASTIC SCHEDULING PROBLEMS 547
F SELECTED SCHEDULING SYSTEMS 551
REFERENCES 555
NAME INDEX 577
SUBJECT INDEX 582