Principles of Sequencing and Scheduling (Hardcover, 2)

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.5. Flexibility in the Basic Model

2.5.1. Due Dates as Decisions

2.5.1. Job Selection Decisions

2.6. 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. Integer Programming

3.7. 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 Analytic Solver Platform

6.8. Non-Probabilistic Approaches: Fuzzy and Robust Scheduling

6.9. Summary

7. Safe Scheduling

7.1. Introduction

7.2. Basic Stochastic Counterpart Models

7.2.1. Sample-Based Analysis

7.2.2. The Normal Model

7.3. Trading Off Tightness and Tardiness

7.3.1. An Objective Function for the Trade-Off

7.3.2. The Normal Model

7.3.3. A Branch and Bound Solution

7.4. The Stochastic E/T Problem

7.5. Using the Lognormal Distribution

7.6. Setting Release Dates

7.7. The Stochastic U-problem: A Service-Level Approach

7.8. The Stochastic U-problem: An Economic Approach

7.9. 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 Traveling Salesperson Models

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. Integer Programming Solutions

10.5.3. 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.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.4.4. Computational Experiments

12.5. The Fundamental Partition

12.5.1. Defining the Fundamental Partition

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

17.5. Stochastic Sequencing with Limited Resources

17.6. Summary

18. Project Analytics

18.1. Introduction

18.2. Basic Partitioning

18.3. Correcting for Rounding

18.4. Accounting for the Parkinson Effect

18.5. Identifying Mixtures

18.6. Addressing Subjective Estimation Bias

18.7. Linear Association

18.7.1. Systemic Bias

18.7.2. Cross-Validation

18.7.3. Using Nonparametric Bootstrap Sampling

18.8. Summary

19. PERT21: Analytics-Based Safe Project Scheduling

19.1. Introduction

19.2. Stochastic Balance Principles for Activity Networks

19.2.1. The Assembly Coordination Model

19.2.2. Balancing a General Project Network

19.2.3. Additional Examples

19.3. Hierarchical Balancing and Progress Payments

19.4. Crashing Stochastic Activities

19.5. 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. Mixtures of Distributions

A.3. Increasing and Decreasing Completion Rates

A.4. Stochastic Dominance

A.5. 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

B.7. Calculations for the Lognormal Distribution

Index