Principles of Sequencing and Scheduling

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. 

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 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

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.