Scheduling : Theory, Algorithms, and Systems

by Pinedo, Michael L.

• ISBN13: 9780387789347
• ISBN10: 0387789340
• Edition: 3rd
• Format: Hardcover
• Copyright: 2008-08-01
• Publisher: Springer Verlag

Summary

This book on scheduling covers both theoretical models as well as scheduling problems in the real world. Author Michael L. Pinedo also includes a CD that contains slide-shows from industry and movies dealing with implementations of scheduling systems.

Author Biography

Michael L. Pinedo is the Julius Schlesinger Professor of Operations Management at New York University

Table of Contents

Preface	p. vii
CD-ROM Contents	p. xvii
Introduction	p. 1
The Role of Scheduling	p. 1
The Scheduling Function in an Enterprise	p. 4
Outline of the Book	p. 6
Deterministic Models
Deterministic Models: Preliminaries	p. 13
Framework and Notation	p. 13
Examples	p. 20
Classes of Schedules	p. 21
Complexity Hierarchy	p. 26
Single Machine Models (Deterministic)	p. 35
The Total Weighted Completion Time	p. 36
The Maximum Lateness	p. 42
The Number of Tardy Jobs	p. 47
The Total Tardiness - Dynamic Programming	p. 50
The Total Tardiness - An Approximation Scheme	p. 54
The Total Weighted Tardiness	p. 57
Discussion	p. 61
Advanced Single Machine Models (Deterministic)	p. 69
The Total Earliness and Tardiness	p. 70
Primary and Secondary Objectives	p. 78
Multiple Objectives: A Parametric Analysis	p. 80
The Makespan with Sequence Dependent Setup Times	p. 84
Job Families with Setup Times	p. 92
Batch Processing	p. 99
Discussion	p. 106
Parallel Machine Models (Deterministic)	p. 111
The Makespan without Preemptions	p. 112
The Makespan with Preemptions	p. 122
The Total Completion Time without Preemptions	p. 130
The Total Completion Time with Preemptions	p. 134
Due Date Related Objectives	p. 136
Online Scheduling	p. 138
Discussion	p. 142
Flow Shops and Flexible Flow Shops (Deterministic)	p. 151
Flow Shops with Unlimited Intermediate Storage	p. 152
Flow Shops with Limited Intermediate Storage	p. 163
Flexible Flow Shops with Unlimited Intermediate Storage	p. 171
Discussion	p. 172
Job Shops (Deterministic)	p. 179
Disjunctive Programming and Branch-and-Bound	p. 179
The Shifting Bottleneck Heuristic and the Makespan	p. 189
The Shifting Bottleneck Heuristic and the Total Weighted Tardiness	p. 197
Constraint Programming and the Makespan	p. 203
Discussion	p. 211
Open Shops (Deterministic)	p. 217
The Makespan without Preemptions	p. 217
The Makespan with Preemptions	p. 221
The Maximum Lateness without Preemptions	p. 224
The Maximum Lateness with Preemptions	p. 229
The Number of Tardy Jobs	p. 233
Discussion	p. 234
Stochastic Models
Stochastic Models: Preliminaries	p. 243
Framework and Notation	p. 243
Distributions and Classes of Distributions	p. 244
Stochastic Dominance	p. 248
Impact of Randomness on Fixed Schedules	p. 251
Classes of Policies	p. 255
Single Machine Models (Stochastic)	p. 263
Arbitrary Distributions without Preemptions	p. 263
Arbitrary Distributions with Preemptions: the Gittins Index	p. 270
Likelihood Ratio Ordered Distributions	p. 275
Exponential Distributions	p. 278
Discussion	p. 285
Single Machine Models with Release Dates (Stochastic)	p. 291
Arbitrary Release Dates and Arbitrary Processing Times without Preemptions	p. 292
Priority Queues, Work Conservation and Poisson Releases	p. 294
Arbitrary Releases and Exponential Processing Times with Preemptions	p. 298
Poisson Releases and Arbitrary Processing Times without Preemptions	p. 304
Discussion	p. 310
Parallel Machine Models (Stochastic)	p. 317
The Makespan without Preemptions	p. 317
The Makespan and Total Completion Time with Preemptions	p. 327
Due Date Related Objectives	p. 335
Bounds Obtained through Online Scheduling	p. 336
Discussion	p. 339
Flow Shops, Job Shops and Open Shops (Stochastic)	p. 345
Stochastic Flow Shops with Unlimited Intermediate Storage	p. 346
Stochastic Flow Shops with Blocking	p. 352
Stochastic Job Shops	p. 357
Stochastic Open Shops	p. 358
Discussion	p. 364
Scheduling in Practice
General Purpose Procedures for Deterministic Scheduling	p. 371
Dispatching Rules	p. 372
Composite Dispatching Rules	p. 373
Local Search: Simulated Annealing and Tabu-Search	p. 378
Local Search: Genetic Algorithms	p. 385
Ant Colony Optimization	p. 387
Discussion	p. 389
More Advanced General Purpose Procedures	p. 395
Beam Search	p. 396
Decomposition Methods and Rolling Horizon Procedures	p. 398
Constraint Programming	p. 403
Market-Based and Agent-Based Procedures	p. 407
Procedures for Scheduling Problems with Multiple Objectives	p. 414
Discussion	p. 420
Modeling and Solving Scheduling Problems in Practice	p. 427
Scheduling Problems in Practice	p. 428
Cyclic Scheduling of a Flow Line	p. 431
Scheduling of a Flexible Flow Line with Limited Buffers and Bypass	p. 436
Scheduling of a Flexible Flow Line with Unlimited Buffers and Setups	p. 441
Scheduling a Bank of Parallel Machines with Jobs having Release Dates and Due Dates	p. 448
Discussion	p. 450
Design and Implementation of Scheduling Systems: Basic Concepts	p. 455
Systems Architecture	p. 456
Databases, Object Bases, and Knowledge-Bases	p. 458
Modules for Generating Schedules	p. 463
User Interfaces and Interactive Optimization	p. 466
Generic Systems vs. Application-Specific Systems	p. 472
Implementation and Maintenance Issues	p. 475
Design and Implementation of Scheduling Systems: More Advanced Concepts	p. 481
Robustness and Reactive Decision Making	p. 482
Machine Learning Mechanisms	p. 487
Design of Scheduling Engines and Algorithm Libraries	p. 492
Reconfigurable Systems	p. 496
Web-Based Scheduling Systems	p. 498
Discussion	p. 501
Examples of System Designs and Implementations	p. 507
SAP's Production Planning and Detailed Scheduling System	p. 508
IBM's Independent Agents Architecture	p. 511
i2's Production Scheduler	p. 515
Taylor Scheduling Software	p. 523
Real Time Dispatching and Agent Scheduling at AMD	p. 528
An Implementation of Cybertec's Cyberplan	p. 533
LEKIN - A System Developed in Academia	p. 537
Discussion	p. 544
What Lies Ahead?	p. 547
Theoretical Research	p. 547
Applied Research	p. 550
Systems Development	p. 553
Appendices
Mathematical Programming: Formulations and Applications	p. 559
Linear Programming Formulations	p. 559
Integer Programming Formulations	p. 563
Bounds, Approximations and Heuristics Based on Linear Programming	p. 567
Disjunctive Programming Formulations	p. 569
Deterministic and Stochastic Dynamic Programming	p. 573
Deterministic Dynamic Programming	p. 573
Stochastic Dynamic Programming	p. 577
Constraint Programming	p. 581
Constraint Satisfaction	p. 581
Constraint Programming	p. 583
An Example of a Constraint Programming Language	p. 585
Constraint Programming vs. Mathematical Programming	p. 586
Complexity Theory	p. 589
Preliminaries	p. 589
Polynomial Time Solutions versus NP-Hardness	p. 592
Examples	p. 595
Approximation Algorithms and Schemes	p. 598
Complexity Classification of Deterministic Scheduling Problems	p. 603
Overview of Stochastic Scheduling Problems	p. 607
Selected Scheduling Systems	p. 611
The Lekin System	p. 615
Formatting of Input and Output Files	p. 615
Linking Scheduling Programs	p. 617
References	p. 623
Subject Index	p. 659
Name Index	p. 665
Table of Contents provided by Ingram. All Rights Reserved.