An updated edition of the text that explores the core topics in scheduling theory
The second edition of Principles of Sequencing and Scheduling has been revised and updated to provide comprehensive coverage of sequencing and scheduling topics as well as emerging developments in the field. The text offers balanced coverage of deterministic models and stochastic models and includes new developments in safe scheduling and project scheduling, including coverage of project analytics. These new topics help bridge the gap between classical scheduling and actual practice. The authors—noted experts in the field—present a coherent and detailed introduction to the basic models, problems, and methods of scheduling theory.
This book offers an introduction and overview of sequencing and scheduling and covers such topics as single-machine and multi-machine models, deterministic and stochastic problem formulations, optimization and heuristic solution approaches, and generic and specialized software methods. This new edition adds coverage on topics of recent interest in shop scheduling and project scheduling. This important resource:
- Offers comprehensive coverage of deterministic models as well as recent approaches and developments for stochastic models
- Emphasizes the application of generic optimization software to basic sequencing problems and the use of spreadsheet-based optimization methods
- Includes updated coverage on safe scheduling, lognormal modeling, and job selection
- Provides basic coverage of robust scheduling as contrasted with safe scheduling
- Adds a new chapter on project analytics, which supports the PERT21 framework for project scheduling in a stochastic environment.
- Extends the coverage of PERT 21 to include hierarchical scheduling
- Provides end-of-chapter references and access to advanced Research Notes, to aid readers in the further exploration of advanced topics
Written for upper-undergraduate and graduate level courses covering such topics as scheduling theory and applications, project scheduling, and operations scheduling, the second edition of Principles of Sequencing and Scheduling is a resource that covers scheduling techniques and contains the most current research and emerging topics.
Table of Contents:
Preface xiii
Acknowledgments xvii
1 Introduction 1
1.1 Introduction to Sequencing and Scheduling 1
1.2 Scheduling Theory 4
1.3 Philosophy and Coverage of the Book 6
Bibliography 8
2 Single-machine Sequencing 11
2.1 Introduction 11
2.2 Preliminaries 12
2.3 Problems Without Due Dates: Elementary Results 15
2.3.1 Flowtime and Inventory 15
2.3.2 Minimizing Total Flowtime 17
2.3.3 Minimizing Total Weighted Flowtime 20
2.4 Problems with Due Dates: Elementary Results 22
2.4.1 Lateness Criteria 22
2.4.2 Minimizing the Number of Tardy Jobs 25
2.4.3 Minimizing Total Tardiness 26
2.5 Flexibility in the Basic Model 30
2.5.1 Due Dates as Decisions 30
2.5.2 Job Selection Decisions 32
2.6 Summary 34
Exercises 35
Bibliography 37
3 Optimization Methods for the Single-machine Problem 39
3.1 Introduction 39
3.2 Adjacent Pairwise Interchange Methods 41
3.3 A Dynamic Programming Approach 42
3.4 Dominance Properties 48
3.5 A Branch-and-bound Approach 52
3.6 Integer Programming 59
3.6.1 Minimizing the Weighted Number of Tardy Jobs 60
3.6.2 Minimizing Total Tardiness 63
3.7 Summary 65
Exercises 67
Bibliography 68
4 Heuristic Methods for the Single-machine Problem 71
4.1 Introduction 71
4.2 Dispatching and Construction Procedures 72
4.3 Random Sampling 77
4.4 Neighborhood Search Techniques 81
4.5 Tabu Search 85
4.6 Simulated Annealing 87
4.7 Genetic Algorithms 89
4.8 The Evolutionary Solver 91
4.9 Summary 96
Exercises 100
Bibliography 103
5 Earliness and Tardiness Costs 105
5.1 Introduction 105
5.2 Minimizing Deviations from a Common Due Date 107
5.2.1 Four Basic Results 107
5.2.2 Due Dates as Decisions 112
5.3 The Restricted Version 113
5.4 Asymmetric Earliness and Tardiness Costs 116
5.5 Quadratic Costs 118
5.6 Job-dependent Costs 120
5.7 Distinct Due Dates 120
5.8 Summary 124
Exercises 125
Bibliography 126
6 Sequencing for Stochastic Scheduling 129
6.1 Introduction 129
6.2 Basic Stochastic Counterpart Models 130
6.3 The Deterministic Counterpart 137
6.4 Minimizing the Maximum Cost 139
6.5 The Jensen Gap 144
6.6 Stochastic Dominance and Association 145
6.7 Using Analytic Solver Platform 149
6.8 Non-probabilistic Approaches: Fuzzy and Robust Scheduling 154
6.9 Summary 161
Exercises 163
Bibliography 166
7 Safe Scheduling 167
7.1 Introduction 167
7.2 Meeting Service Level Targets 169
7.2.1 Sample-based Analysis 169
7.2.2 The Normal Model 172
7.3 Trading Off Tightness and Tardiness 174
7.3.1 An Objective Function for the Trade-off 174
7.3.2 The Normal Model 175
7.3.3 A Branch-and-bound Solution 178
7.4 The Stochastic E/T Problem 184
7.5 Using the Lognormal Distribution 190
7.6 Setting Release Dates 194
7.7 The Stochastic U-problem: A Service-level Approach 197
7.8 The Stochastic U-problem: An Economic Approach 204
7.9 Summary 208
Exercises 210
Bibliography 213
8 Extensions of the Basic Model 215
8.1 Introduction 215
8.2 Nonsimultaneous Arrivals 216
8.2.1 Minimizing the Makespan 219
8.2.2 Minimizing Maximum Tardiness 221
8.2.3 Other Measures of Performance 223
8.3 Related Jobs 225
8.3.1 Minimizing Maximum Tardiness 226
8.3.2 Minimizing Total Flowtime with Strings 226
8.3.3 Minimizing Total Flowtime with Parallel Chains 229
8.4 Sequence-Dependent Setup Times 232
8.4.1 Dynamic Programming Solutions 234
8.4.2 Branch-And-Bound Solutions 235
8.4.3 Heuristic Solutions 240
8.5 Stochastic Traveling Salesperson Models 242
8.6 Summary 247
Exercises 248
Bibliography 251
9 Parallel-machine Models 255
9.1 Introduction 255
9.2 Minimizing the Makespan 255
9.2.1 Nonpreemptable Jobs 257
9.2.2 Nonpreemptable Related Jobs 263
9.2.3 Preemptable Jobs 267
9.3 Minimizing Total Flowtime 268
9.4 Stochastic Models 274
9.4.1 The Makespan Problem with Exponential Processing Times 274
9.4.2 Safe Scheduling with Parallel Machines 276
9.5 Summary 277
Exercises 279
Bibliography 280
10 Flow Shop Scheduling 283
10.1 Introduction 283
10.2 Permutation Schedules 286
10.3 The Two-machine Problem 288
10.3.1 Johnson’s Rule 288
10.3.2 A Proof of Johnson’s Rule 290
10.3.3 The Model with Time Lags 293
10.3.4 The Model with Setups 294
10.4 Special Cases of the Three-machine Problem 294
10.5 Minimizing the Makespan 296
10.5.1 Branch-and-Bound Solutions 297
10.5.2 Integer Programming Solutions 300
10.5.3 Heuristic Solutions 306
10.6 Variations of the m-Machine Model 308
10.6.1 Ordered Flow Shops 308
10.6.2 Flow Shops with Blocking 309
10.6.3 No-Wait Flow Shops 310
10.7 Summary 313
Exercises 313
Bibliography 315
11 Stochastic Flow Shop Scheduling 319
11.1 Introduction 319
11.2 Stochastic Counterpart Models 320
11.3 Safe Scheduling Models with Stochastic Independence 327
11.4 Flow Shops with Linear Association 330
11.5 Empirical Observations 331
11.6 Summary 336
Exercises 337
Bibliography 339
12 Lot Streaming Procedures for the Flow Shop 341
12.1 Introduction 341
12.2 The Basic Two-machine Model 342
12.2.1 Preliminaries 342
12.2.2 The Continuous Version 345
12.2.3 The Discrete Version 348
12.2.4 Models with Setups 350
12.3 The Three-machine Model with Consistent Sublots 352
12.3.1 The Continuous Version 352
12.3.2 The Discrete Version 355
12.4 The Three-machine Model with Variable Sublots 355
12.4.1 Item and Batch Availability 355
12.4.2 The Continuous Version 357
12.4.3 The Discrete Version 359
12.4.4 Computational Experiments 360
12.5 The Fundamental Partition 363
12.5.1 Defining the Fundamental Partition 364
12.5.2 A Heuristic Procedure for s Sublots 367
12.6 Summary 367
Exercises 369
Bibliography 371
13 Scheduling Groups of Jobs 373
13.1 Introduction 373
13.2 Scheduling Job Families 374
13.2.1 Minimizing Total Weighted Flowtime 375
13.2.2 Minimizing Maximum Lateness 377
13.2.3 Minimizing Makespan in the Two-Machine Flow Shop 379
13.3 Scheduling with Batch Availability 383
13.4 Scheduling with a Batch Processor 387
13.4.1 Minimizing the Makespan with Dynamic Arrivals 387
13.4.2 Minimizing Makespan in the Two-Machine Flow Shop 389
13.4.3 Minimizing Total Flowtime with Dynamic Arrivals 390
13.4.4 Batch-Dependent Processing Times 392
13.5 Summary 394
Exercises 395
Bibliography 397
14 The Job Shop Problem 399
14.1 Introduction 399
14.2 Types of Schedules 402
14.3 Schedule Generation 407
14.4 The Shifting Bottleneck Procedure 412
14.4.1 Bottleneck Machines 412
14.4.2 Heuristic and Optimal Solutions 414
14.5 Neighborhood Search Heuristics 417
14.6 Summary 421
Exercises 422
Bibliography 424
15 Simulation Models for the Dynamic Job Shop 427
15.1 Introduction 427
15.2 Model Elements 428
15.3 Types of Dispatching Rules 430
15.4 Reducing Mean Flowtime 432
15.5 Meeting Due Dates 436
15.5.1 Background 436
15.5.2 Some Clarifying Experiments 441
15.5.3 Experimental Results 443
15.6 Summary 449
Bibliography 451
16 Network Methods for Project Scheduling 453
16.1 Introduction 453
16.2 Logical Constraints And Network Construction 454
16.3 Temporal Analysis of Networks 458
16.4 The Time/Cost Trade-off 463
16.5 Traditional Probabilistic Network Analysis 467
16.5.1 The PERT Method 467
16.5.2 Theoretical Limitations of PERT 472
16.6 Summary 476
Exercises 478
Bibliography 481
17 Resource-Constrained Project Scheduling 483
17.1 Introduction 483
17.2 Extending the Job Shop Model 484
17.3 Extending the Project Model 490
17.4 Heuristic Construction and Search Algorithms 493
17.4.1 Construction Heuristics 493
17.4.2 Neighborhood Search Improvement Schemes 496
17.4.3 Selecting Priority Lists 499
17.5 Stochastic Sequencing with Limited Resources 501
17.6 Summary 503
Exercises 505
Bibliography 508
18 Project Analytics 511
18.1 Introduction 511
18.2 Basic Partitioning 513
18.3 Correcting for Rounding 515
18.4 Accounting for the Parkinson Effect 516
18.5 Identifying Mixtures 521
18.6 Addressing Subjective Estimation Bias 524
18.7 Linear Association 526
18.7.1 Systemic Bias 526
18.7.2 Cross-Validation 530
18.7.3 Using Nonparametric Bootstrap Sampling 531
18.8 Summary 534
Bibliography 536
19 PERT 21: Analytics-Based Safe Project Scheduling 537
19.1 Introduction 537
19.2 Stochastic Balance Principles for Activity Networks 539
19.2.1 The Assembly Coordination Model 540
19.2.2 Balancing a General Project Network 547
19.2.3 Additional Examples 550
19.3 Hierarchical Balancing and Progress Payments 557
19.4 Crashing Stochastic Activities 560
19.5 Summary 565
Exercises 567
Bibliography 569
Appendix A: Practical Processing Time Distributions 571
Appendix B: The Critical Ratio Rule 597
Index 613
About the Author :
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.
