Principles of Sequencing and Scheduling

KENNETH R. BAKER, PHD, is Nathaniel Leverone Professor of Management at the Tuck School of Business and INFORMS Fellow. He is a Founding Associate Editor for the International Journal of Planning and Scheduling. DAN TRIETSCH, PHD, is an independent researcher and consultant in scheduling and project analytics, with extensive teaching experience, mostly at the graduate level. He is an Area Editor for the International Journal of Information Technology Project Management and a Board Member of the International Journal of Planning and Scheduling.

• Preface xiiiAcknowledgments xvii1 Introduction 11.1 Introduction to Sequencing and Scheduling 11.2 Scheduling Theory 41.3 Philosophy and Coverage of the Book 6Bibliography 82 Single-machine Sequencing 112.1 Introduction 112.2 Preliminaries 122.3 Problems Without Due Dates: Elementary Results 152.3.1 Flowtime and Inventory 152.3.2 Minimizing Total Flowtime 172.3.3 Minimizing Total Weighted Flowtime 202.4 Problems with Due Dates: Elementary Results 222.4.1 Lateness Criteria 222.4.2 Minimizing the Number of Tardy Jobs 252.4.3 Minimizing Total Tardiness 262.5 Flexibility in the Basic Model 302.5.1 Due Dates as Decisions 302.5.2 Job Selection Decisions 322.6 Summary 34Exercises 35Bibliography 373 Optimization Methods for the Single-machine Problem 393.1 Introduction 393.2 Adjacent Pairwise Interchange Methods 413.3 A Dynamic Programming Approach 423.4 Dominance Properties 483.5 A Branch-and-bound Approach 523.6 Integer Programming 593.6.1 Minimizing the Weighted Number of Tardy Jobs 603.6.2 Minimizing Total Tardiness 633.7 Summary 65Exercises 67Bibliography 684 Heuristic Methods for the Single-machine Problem 714.1 Introduction 714.2 Dispatching and Construction Procedures 724.3 Random Sampling 774.4 Neighborhood Search Techniques 814.5 Tabu Search 854.6 Simulated Annealing 874.7 Genetic Algorithms 894.8 The Evolutionary Solver 914.9 Summary 96Exercises 100Bibliography 1035 Earliness and Tardiness Costs 1055.1 Introduction 1055.2 Minimizing Deviations from a Common Due Date 1075.2.1 Four Basic Results 1075.2.2 Due Dates as Decisions 1125.3 The Restricted Version 1135.4 Asymmetric Earliness and Tardiness Costs 1165.5 Quadratic Costs 1185.6 Job-dependent Costs 1205.7 Distinct Due Dates 1205.8 Summary 124Exercises 125Bibliography 1266 Sequencing for Stochastic Scheduling 1296.1 Introduction 1296.2 Basic Stochastic Counterpart Models 1306.3 The Deterministic Counterpart 1376.4 Minimizing the Maximum Cost 1396.5 The Jensen Gap 1446.6 Stochastic Dominance and Association 1456.7 Using Analytic Solver Platform 1496.8 Non-probabilistic Approaches: Fuzzy and Robust Scheduling 1546.9 Summary 161Exercises 163Bibliography 1667 Safe Scheduling 1677.1 Introduction 1677.2 Meeting Service Level Targets 1697.2.1 Sample-based Analysis 1697.2.2 The Normal Model 1727.3 Trading Off Tightness and Tardiness 1747.3.1 An Objective Function for the Trade-off 1747.3.2 The Normal Model 1757.3.3 A Branch-and-bound Solution 1787.4 The Stochastic E/T Problem 1847.5 Using the Lognormal Distribution 1907.6 Setting Release Dates 1947.7 The Stochastic U-problem: A Service-level Approach 1977.8 The Stochastic U-problem: An Economic Approach 2047.9 Summary 208Exercises 210Bibliography 2138 Extensions of the Basic Model 2158.1 Introduction 2158.2 Nonsimultaneous Arrivals 2168.2.1 Minimizing the Makespan 2198.2.2 Minimizing Maximum Tardiness 2218.2.3 Other Measures of Performance 2238.3 Related Jobs 2258.3.1 Minimizing Maximum Tardiness 2268.3.2 Minimizing Total Flowtime with Strings 2268.3.3 Minimizing Total Flowtime with Parallel Chains 2298.4 Sequence-Dependent Setup Times 2328.4.1 Dynamic Programming Solutions 2348.4.2 Branch-And-Bound Solutions 2358.4.3 Heuristic Solutions 2408.5 Stochastic Traveling Salesperson Models 2428.6 Summary 247Exercises 248Bibliography 2519 Parallel-machine Models 2559.1 Introduction 2559.2 Minimizing the Makespan 2559.2.1 Nonpreemptable Jobs 2579.2.2 Nonpreemptable Related Jobs 2639.2.3 Preemptable Jobs 2679.3 Minimizing Total Flowtime 2689.4 Stochastic Models 2749.4.1 The Makespan Problem with Exponential Processing Times 2749.4.2 Safe Scheduling with Parallel Machines 2769.5 Summary 277Exercises 279Bibliography 28010 Flow Shop Scheduling 28310.1 Introduction 28310.2 Permutation Schedules 28610.3 The Two-machine Problem 28810.3.1 Johnson’s Rule 28810.3.2 A Proof of Johnson’s Rule 29010.3.3 The Model with Time Lags 29310.3.4 The Model with Setups 29410.4 Special Cases of the Three-machine Problem 29410.5 Minimizing the Makespan 29610.5.1 Branch-and-Bound Solutions 29710.5.2 Integer Programming Solutions 30010.5.3 Heuristic Solutions 30610.6 Variations of the m-Machine Model 30810.6.1 Ordered Flow Shops 30810.6.2 Flow Shops with Blocking 30910.6.3 No-Wait Flow Shops 31010.7 Summary 313Exercises 313Bibliography 31511 Stochastic Flow Shop Scheduling 31911.1 Introduction 31911.2 Stochastic Counterpart Models 32011.3 Safe Scheduling Models with Stochastic Independence 32711.4 Flow Shops with Linear Association 33011.5 Empirical Observations 33111.6 Summary 336Exercises 337Bibliography 33912 Lot Streaming Procedures for the Flow Shop 34112.1 Introduction 34112.2 The Basic Two-machine Model 34212.2.1 Preliminaries 34212.2.2 The Continuous Version 34512.2.3 The Discrete Version 34812.2.4 Models with Setups 35012.3 The Three-machine Model with Consistent Sublots 35212.3.1 The Continuous Version 35212.3.2 The Discrete Version 35512.4 The Three-machine Model with Variable Sublots 35512.4.1 Item and Batch Availability 35512.4.2 The Continuous Version 35712.4.3 The Discrete Version 35912.4.4 Computational Experiments 36012.5 The Fundamental Partition 36312.5.1 Defining the Fundamental Partition 36412.5.2 A Heuristic Procedure for s Sublots 36712.6 Summary 367Exercises 369Bibliography 37113 Scheduling Groups of Jobs 37313.1 Introduction 37313.2 Scheduling Job Families 37413.2.1 Minimizing Total Weighted Flowtime 37513.2.2 Minimizing Maximum Lateness 37713.2.3 Minimizing Makespan in the Two-Machine Flow Shop 37913.3 Scheduling with Batch Availability 38313.4 Scheduling with a Batch Processor 38713.4.1 Minimizing the Makespan with Dynamic Arrivals 38713.4.2 Minimizing Makespan in the Two-Machine Flow Shop 38913.4.3 Minimizing Total Flowtime with Dynamic Arrivals 39013.4.4 Batch-Dependent Processing Times 39213.5 Summary 394Exercises 395Bibliography 39714 The Job Shop Problem 39914.1 Introduction 39914.2 Types of Schedules 40214.3 Schedule Generation 40714.4 The Shifting Bottleneck Procedure 41214.4.1 Bottleneck Machines 41214.4.2 Heuristic and Optimal Solutions 41414.5 Neighborhood Search Heuristics 41714.6 Summary 421Exercises 422Bibliography 42415 Simulation Models for the Dynamic Job Shop 42715.1 Introduction 42715.2 Model Elements 42815.3 Types of Dispatching Rules 43015.4 Reducing Mean Flowtime 43215.5 Meeting Due Dates 43615.5.1 Background 43615.5.2 Some Clarifying Experiments 44115.5.3 Experimental Results 44315.6 Summary 449Bibliography 45116 Network Methods for Project Scheduling 45316.1 Introduction 45316.2 Logical Constraints And Network Construction 45416.3 Temporal Analysis of Networks 45816.4 The Time/Cost Trade-off 46316.5 Traditional Probabilistic Network Analysis 46716.5.1 The PERT Method 46716.5.2 Theoretical Limitations of PERT 47216.6 Summary 476Exercises 478Bibliography 48117 Resource-Constrained Project Scheduling 48317.1 Introduction 48317.2 Extending the Job Shop Model 48417.3 Extending the Project Model 49017.4 Heuristic Construction and Search Algorithms 49317.4.1 Construction Heuristics 49317.4.2 Neighborhood Search Improvement Schemes 49617.4.3 Selecting Priority Lists 49917.5 Stochastic Sequencing with Limited Resources 50117.6 Summary 503Exercises 505Bibliography 50818 Project Analytics 51118.1 Introduction 51118.2 Basic Partitioning 51318.3 Correcting for Rounding 51518.4 Accounting for the Parkinson Effect 51618.5 Identifying Mixtures 52118.6 Addressing Subjective Estimation Bias 52418.7 Linear Association 52618.7.1 Systemic Bias 52618.7.2 Cross-Validation 53018.7.3 Using Nonparametric Bootstrap Sampling 53118.8 Summary 534Bibliography 53619 PERT 21: Analytics-Based Safe Project Scheduling 53719.1 Introduction 53719.2 Stochastic Balance Principles for Activity Networks 53919.2.1 The Assembly Coordination Model 54019.2.2 Balancing a General Project Network 54719.2.3 Additional Examples 55019.3 Hierarchical Balancing and Progress Payments 55719.4 Crashing Stochastic Activities 56019.5 Summary 565Exercises 567Bibliography 569Appendix A: Practical Processing Time Distributions 571Appendix B: The Critical Ratio Rule 597Index 613