Principles of Sequencing and Scheduling

An up-to-date and comprehensive treatment of the fundamentals of scheduling theory, including recent advances and state-of-the-art topics

Principles of Sequencing and Scheduling strikes a unique balance between theory and practice, providing an accessible introduction to the concepts, methods, and results of scheduling theory and its core topics. With real-world examples and up-to-date modeling techniques, the book equips readers with the basic knowledge needed for understanding scheduling theory and delving into its applications. The authors begin with an introduction and overview of sequencing and scheduling, including single-machine sequencing, optimization and heuristic solution methods, and models with earliness and tardiness penalties. The most current material on stochastic scheduling, including correct scheduling of safety time and the use of simulation for optimization, is then presented and integrated with deterministic models. Additional topical coverage includes:

* Extensions of the basic model
* Parallel-machine models
* Flow shop scheduling
* Scheduling groups of jobs
* The job shop problem
* Simulation models for the dynamic job shop
* Network methods for project scheduling
* Resource-constrained project scheduling
* Stochastic and safe scheduling

Extensive end-of-chapter exercises are provided, some of which are spreadsheet-oriented, and link scheduling theory to the most popular analytic platform among today's students and practitioners-the Microsoft Office Excel(r) spreadsheet. Extensive references direct readers to additional literature, and the book's related Web site houses material that reinforces the book's concepts, including research notes, data sets, and examples from the text.

Principles of Sequencing and Scheduling is an excellent book for courses on sequencing and scheduling at the upper-undergraduate and graduate levels. It is also a valuable reference for researchers and practitioners in the fields of statistics, computer science, operations research, and engineering.

This book is an expanded, thoroughly updated, and more comprehensive version of Kenneth Baker's previous works, Introduction to Sequencing and Scheduling (published by Wiley in 1973) and Elements of Sequencing and Scheduling (self-published in 1992).  While the earlier texts focused mainly on deterministic methods, the authors have added recent developments and topics in the field, including stochastic scheduling and safe scheduling.  Chapters 1-7 provide an introduction and overview of sequencing and scheduling, including single-machine sequencing, optimization and heuristics methods for the single-machine problem, and earliness and tardiness penalties.  Chapter 4 (Sequencing for Stochastic Scheduling) and Chapter 7 (Safe Scheduling) represent new material on stochastic scheduling, and these chapters have been integrated with the remaining five introductory chapters.  The additional eleven chapters discuss topics in stochastic scheduling and have all been integrated with deterministic models.  Additional topical coverage includes: extensions of the basic model, parallel-machine models, flow shop scheduling; lot streaming procedures for the flow shop; scheduling groups of jobs; the job shop problem; simulation models for the dynamic job shop; network methods for project scheduling; and resource-constrained project scheduling.

1. Introduction. 1.1. Introduction to Sequencing and Scheduling. 1.2. Scheduling Theory. 1.3. Philosophy and Coverage of the Book. 2. Single-Machine Sequencing. 2.1. Introduction. 2.2. Preliminaries. 2.3. Problems without Due Dates: Elementary Results. 2.3.1 Flowtime and Inventory. 2.3.2 Minimizing Total Flowtime. 2.3.3 Minimizing Total Weighted Flowtime. 2.4. Problems with Due Dates: Elementary Results. 2.4.1 Lateness Criteria. 2.4.2 Minimizing the Number of Tardy Jobs. 2.4.3 Minimizing Total Tardiness. 2.4.4 Due Dates as Decisions. 2.5. Summary. 3. Optimization Methods for the Single-Machine Problem. 3.1. Introduction. 3.2. Adjacent Pairwise Interchange Methods. 3.3. A Dynamic Programming Approach. 3.4. Dominance Properties. 3.5. A Branch and Bound Approach. 3.6. Summary. 4. Heuristic Methods for the Single-Machine Problem. 4.1. Introduction. 4.2. Dispatching and Construction Procedures. 4.3. Random Sampling. 4.4. Neighborhood Search Techniques. 4.5. Tabu Search. 4.6. Simulated Annealing. 4.7. Genetic Algorithms. 4.8. The Evolutionary Solver. 4.9. Summary. 5. Earliness and Tardiness Costs. 5.1. Introduction. 5.2. Minimizing Deviations from a Common Due Date. 5.2.1. Four Basic Results. 5.2.2. Due Dates as Decisions. 5.3. The Restricted Version. 5.4. Asymmetric Earliness and Tardiness Costs. 5.5. Quadratic Costs. 5.6. Job-Dependent Costs. 5.7. Distinct Due Dates. 5.8. Summary. 6. Sequencing for Stochastic Scheduling. 6.1. Introduction. 6.2. Basic Stochastic Counterpart Models. 6.3. The Deterministic Counterpart . 6.4. Minimizing the Maximum Cost . 6.5. The Jensen Gap. 6.6. Stochastic Dominance and Association. 6.7. Using Risk Solver. 6.8. Summary. 7. Safe Scheduling. 7.1. Introduction. 7.2. Meeting Service-Level Targets. 7.3. Trading Off Tightness and Tardiness. 7.4. The Stochastic E/T Problem. 7.5. Setting Release Dates. 7.6. The Stochastic U-problem: A Service-Level Approach. 7.7. The Stochastic U-problem: An Economic Approach. 7.8. Summary. 8. Extensions of the Basic Model. 8.1. Introduction. 8.2. Nonsimultaneous Arrivals. 8.2.1. Minimizing the Makespan. 8.2.2. Minimizing Maximum Tardiness. 8.2.3. Other Measures of Performance. 8.3. Related Jobs. 8.3.1. Minimizing Maximum Tardiness. 8.3.2. Minimizing Total Flowtime with Strings. 8.3.3. Minimizing Total Flowtime with Parallel Chains. 8.4. Sequence-Dependent Setup Times. 8.4.1. Dynamic Programming Solutions. 8.4.2. Branch and Bound Solutions. 8.4.3. Heuristic Solutions. 8.5. Stochastic Models with Sequence-Dependent Setup Times. 8.5.1. Setting Tight Due Dates . 8.5.2. Revisiting the Tightness-Tardiness Trade Off. 8.6. Summary. 9. Parallel-Machine Models. 9.1. Introduction. 9.2. Minimizing the Makespan. 9.2.1. Nonpreemptable Jobs. 9.2.2. Nonpreemptable Related Jobs. 9.2.3. Preemptable Jobs. 9.3. Minimizing Total Flowtime. 9.4. Stochastic Models. 9.4.1. The Makespan Problem with Exponential Processing Times. 9.4.2. Safe Scheduling with Parallel Machines. 9.5. Summary. 10. Flow Shop Scheduling. 10.1. Introduction. 10.2. Permutation Schedules. 10.3. The Two-Machine Problem. 10.3.1. Johnson's Rule. 10.3.2. A Proof of Johnson's Rule. 10.3.3. The Model with Time Lags. 10.3.4. The Model with Setups. 10.4. Special Cases of the Three-Machine Problem. 10.5. Minimizing the Makespan. 10.5.1. Branch and Bound Solutions. 10.5.2. Heuristic Solutions. 10.6. Variations of the m-Machine Model. 10.6.1. Ordered Flow Shops. 10.6.2. Flow Shops with Blocking. 10.6.3. No-Wait Flow Shops. 10.7. Summary. 11. Stochastic Flow Shop Scheduling. 11.1. Introduction. 11.2. Stochastic Counterpart Models. 11.2.1 The Two-Machine Model. 11.2.2 The m-Machine Model . 11.3. Safe Scheduling Models with Stochastic Independence. 11.4. Flow Shops with Linear Association. 11.5. Empirical Observations. 11.6. Summary. 12. Lot Streaming Procedures for the Flow Shop. 12.1. Introduction. 12.2. The Basic Two-Machine Model. 12.2.1. Preliminaries. 12.2.2. The Continuous Version. 12.2.3. The Discrete Version. 12.2.4. Models with Setups. 12.3. The Three-Machine Model with Consistent Sublots. 12.3.2. The Continuous Version. 12.3.3. The Discrete Version. 12.4. The Three-Machine Model with Variable Sublots. 12.4.1. Item and Batch Availability. 12.4.2. The Continuous Version. 12.4.3. The Discrete Version. 12.5. The m-Machine Model with Consistent Sublots. 12.5.1. The Two-Sublot Solution. 12.5.2. A Heuristic Procedure for s Sublots. 12.6. Summary. 13. Scheduling Groups of Jobs. 13.1. Introduction. 13.2. Scheduling Job Families. 13.2.1. Minimizing Total Weighted Flowtime. 13.2.2. Minimizing Maximum Lateness. 13.2.3. Minimizing Makespan in the Two-Machine Flow Shop. 13.3. Scheduling with Batch Availability. 13.4. Scheduling with a Batch Processor. 13.4.1. Minimizing the Makespan with Dynamic Arrivals. 13.4.2. Minimizing Makespan in the Two-Machine Flow Shop. 13.4.3. Minimizing Total Flowtime with Dynamic Arrivals. 13.4.4. Batch Dependent Processing Times. 13.5. Summary. 14. The Job Shop Problem. 14.1. Introduction. 14.2. Types of Schedules. 14.3. Schedule Generation . 14.4. The Shifting Bottleneck Procedure . 14.4.1. Bottleneck Machines . 14.4.2. Heuristic and Optimal Solutions. 14.5. Neighborhood Search Heuristics. 14.6. Summary. 15. Simulation Models for the Dynamic Job Shop. 15.1. Introduction. 15.2. Model Elements. 15.3. Types of Dispatching Rules. 15.4. Reducing Mean Flowtime. 15.5. Meeting Due Dates. 15.5.1. Background. 15.5.2. Some Clarifying Experiments. 15.5.3. Experimental Results. 15.6. Summary. 16. Network Methods for Project Scheduling. 16.1. Introduction. 16.2. Logical Constraints and Network Construction. 16.3. Temporal Analysis of Networks. 16.4. The Time/Cost Trade-off. 16.5. Traditional Probabilistic Network Analysis. 16.5.1. The PERT Method. 16.5.2. Theoretical Limitations of PERT. 16.6 Summary. 17. Resource-Constrained Project Scheduling. 17.1. Introduction. 17.2. Extending the Job Shop Model. 17.3. Extending the Project Model. 17.4 Heuristic Construction and Search Algorithms. 17.4.1. Construction Heuristics. 17.4.2. Neighborhood Search Improvement Schemes. 17.4.3. Selecting Priority Lists and Tie-Breakers. 17.5 Summary. 18. Safe Scheduling for Projects. 18.1. Introduction. 18.2. Stochastic Balance Principles for Activity Networks. 18.2.1. The Assembly Coordination Model . 18.2.2. Balancing General Project Networks. 18.2.3. Additional Examples. 18.2.4. Hierarchical Balancing. 18.3. Crashing Stochastic Activities. 18.4. Summary. Appendices. A. Practical Processing Time Distributions. A.1. Important Processing Time Distributions. A.1.1 The Uniform Distribution. A.1.2 The Exponential Distribution. A.1.3 The Normal Distribution. A.1.4 The Lognormal Distribution. A.1.5 The Parkinson Distribution . A.2. Increasing and Decreasing Completion Rates. A.3. Stochastic Dominance. A.4 . Linearly-Associated Processing Times. B. The Critical Ratio Rule. B.1. A Basic Trade-Off Problem. B.2. Optimal Policy for Discrete Probability Models. B.3. A Special Discrete Case: Equally-likely Outcomes. B.4. Optimal Policy for Continuous Probability Models. B.5. A Special Continuous Case: The Normal Distribution. B.6. Calculating d + E(T) for the Normal Distribution. C. Integer Programming Models for Sequencing. C.1. Introduction. C.2. The Single-Machine Model. C.2.1 Sequence-position Decisions. C.2.2 Precedence Decisions. C.2.3 Time-indexed Decisions. C.3. The Flow Shop Model. Index.