Principles of Sequencing and 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.