Table of Contents
Preface vii CD-ROM Contents xvii
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 I Deterministic Models
2 Deterministic Models: Preliminaries 13
2.1 Framework and Notation 13
2.2 Examples 20
2.3 Classes of Schedules 21
2.4 Complexity Hierarchy 26
3 Single Machine Models (Deterministic) 35
3.1 The Total Weighted Completion Time 36
3.2 The Maximum Lateness 42
3.3 The Number of Tardy Jobs 47
3.4 The Total Tardiness - Dynamic Programming 50
3.5 The Total Tardiness - An Approximation Scheme 54
3.6 The Total Weighted Tardiness 57
3.7 Discussion 61
4 Advanced Single Machine Models (Deterministic) 69
4.1 The Total Earliness and Tardiness 70
4.2 Primary and Secondary Objectives 78
4.3 Multiple Objectives: A Parametric Analysis 80
4.4 The Makespan with Sequence Dependent Setup Times 84
4.5 Job Families with Setup Times 92
4.6 Batch Processing 99
4.7 Discussion 106
5 Parallel Machine Models (Deterministic) 111
5.1 The Makespan without Preemptions 112
5.2 The Makespan with Preemptions 122
5.3 The Total Completion Time without Preemptions 130
5.4 The Total Completion Time with Preemptions 134
5.5 Due Date Related Objectives 136
5.6 Online Scheduling 138
5.7 Discussion 142
6 Flow Shops and Flexible Flow Shops (Deterministic) 151
6.1 Flow Shops with Unlimited Intermediate Storage 152
6.2 Flow Shops with Limited Intermediate Storage 163
6.3 Flexible Flow Shops with Unlimited Intermediate Storage 171
6.4 Discussion 172
7 Job Shops (Deterministic) 179
7.1 Disjunctive Programming and Branch-and-Bound179
7.2 The Shifting Bottleneck Heuristic and the Makespan 189
7.3 The Shifting Bottleneck Heuristic and the Total Weighted Tardiness 197
7.4 Constraint Programming and the Makespan 203
7.5 Discussion 211
8 Open Shops (Deterministic) 217
8.1 The Makespan without Preemptions 217
8.2 The Makespan with Preemptions 221
8.3 The Maximum Lateness without Preemptions 224
8.4 The Maximum Lateness with Preemptions 229
8.5 The Number of Tardy Jobs 233
8.6 Discussion 234 Part II Stochastic Models
9 Stochastic Models: Preliminaries 243
9.1 Framework and Notation 243
9.2 Distributions and Classes of Distributions 244
9.3 Stochastic Dominance 248
9.4 Impact of Randomness on Fixed Schedules 251
9.5 Classes of Policies 255
10 Single Machine Models (Stochastic) 263
10.1 Arbitrary Distributions without Preemptions 263
10.2 Arbitrary Distributions with Preemptions: the Gittins Index 270
10.3 Likelihood Ratio Ordered Distributions 275
10.4 Exponential Distributions 278
10.5 Discussion 285
11 Single Machine Models with Release Dates (Stochastic) 291
11.1 Arbitrary Release Dates and Arbitrary Processing Times without Preemptions 292
11.2 Priority Queues, Work Conservation and Poisson Releases 294
11.3 Arbitrary Releases and Exponential Processing Times with Preemptions 298
11.4 Poisson Releases and Arbitrary Processing Times without Preemptions 304
11.5 Discussion 310
12 Parallel Machine Models (Stochastic) 317
12.1 The Makespan without Preemptions 317
12.2 The Makespan and Total Completion Time with Preemptions 327
12.3 Due Date Related Objectives 335
12.4 Bounds Obtained through Online Scheduling 336
12.5 Discussion 339
13 Flow Shops, Job Shops and Open Shops (Stochastic) 345
13.1 Stochastic Flow Shops with Unlimited Intermediate Storage 346
13.2 Stochastic Flow Shops with Blocking 352
13.3 Stochastic Job Shops 357
13.4 Stochastic Open Shops 358
13.5 Discussion 364 Part III Scheduling in Practice
14 General Purpose Procedures for Deterministic Scheduling 371
14.1 Dispatching Rules 372
14.2 Composite Dispatching Rules 373
14.3 Local Search: Simulated Annealing and Tabu-Search 378
14.4 Local Search: Genetic Algorithms 385
14.5 Ant Colony Optimization 387
14.6 Discussion 389
15 More Advanced General Purpose Procedures 395
15.1 Beam Search 396
15.2 Decomposition Methods and Rolling Horizon Procedures 398
15.3 Constraint Programming 403
15.4 Market-Based and Agent-Based Procedures 407
15.5 Procedures for Scheduling Problems with Multiple Objectives 414
15.6 Discussion 420
16 Modeling and Solving Scheduling Problems in Practice 427
16.1 Scheduling Problems in Practice 428
16.2 Cyclic Scheduling of a Flow Line 431
16.3 Scheduling of a Flexible Flow Line with Limited Buffers and Bypass 436
16.4 Scheduling of a Flexible Flow Line with Unlimited Buffers and Setups 441
16.5 Scheduling a Bank of Parallel Machines with Jobs having Release Dates and Due Dates 448
16.6 Discussion 450
17 Design and Implementation of Scheduling Systems: Basic Concepts 455
17.1 Systems Architecture 456
17.2 Databases, Object Bases, and Knowledge-Bases 458
17.3 Modules for Generating Schedules 463
17.4 User Interfaces and Interactive Optimization 466
17.5 Generic Systems vs. Application-Specific Systems 472
17.6 Implementation and Maintenance Issues 475
18 Design and Implementation of Scheduling Systems: More Advanced Concepts 481
18.1 Robustness and Reactive Decision Making 482
18.2 Machine Learning Mechanisms 487
18.3 Design of Scheduling Engines and Algorithm Libraries 492
18.4 Reconfigurable Systems 496
18.5 Web-Based Scheduling Systems 498
18.6 Discussion 501
19 Examples of System Designs and Implementations 507
19.1 SAP's Production Planning and Detailed Scheduling System 508
19.2 IBM's Independent Agents Architecture 511
19.3 i2's Production Scheduler 515
19.4 Taylor Scheduling Software 523
19.5 Real Time Dispatching and Agent Scheduling at AMD 528
19.6 An Implementation of Cybertec's Cyberplan 533
19.7 LEKIN - A System Developed in Academia 537
19.8 Discussion 544
20 What Lies Ahead? 547
20.1 Theoretical Research 547
20.2 Applied Research 550
20.3 Systems Development 553 Appendices A Mathematical Programming: Formulations and Applications 559 A.1 Linear Programming Formulations 559 A.2 Integer Programming Formulations 563 A.3 Bounds, Approximations and Heuristics Based on Linear Programming 567 A.4 Disjunctive Programming Formulations 569 B Deterministic and Stochastic Dynamic Programming 573 B.1 Deterministic Dynamic Programming 573 B.2 Stochastic Dynamic Programming 577 C Constraint Programming 581 C.1 Constraint Satisfaction 581 C.2 Constraint Programming 583 C.3 An Example of a Constraint Programming Language 585 C.4 Constraint Programming vs. Mathematical Programming 586 D Complexity Theory 589 D.1 Preliminaries 589 D.2 Polynomial Time Solutions versus NP-Hardness 592 D.3 Examples 595 D.4 Approximation Algorithms and Schemes 598 E Complexity Classification of Deterministic Scheduling Problems 603 F Overview of Stochastic Scheduling Problems 607 G Selected Scheduling Systems 611 H The Lekin System 615 H.1 Formatting of Input and Output Files 615 H.2 Linking Scheduling Programs 617 References 623 Subject Index 659 Name Index 665
