Principles of Sequencing and Scheduling

An up–to–date and comprehensive treatment of the fundamentals of scheduling theory, including recent advances and state–of–the–art topics Principles of Sequencing and Scheduling strikes a unique balance between theory and practice, providing an accessible introduction to the concepts, methods, and results of scheduling theory and its core topics. With real–world examples and up–to–date modeling techniques, the book equips readers with the basic knowledge needed for understanding scheduling theory and delving into its applications. The authors begin with an introduction and overview of sequencing and scheduling, including single–machine sequencing, optimization and heuristic solution methods, and models with earliness and tardiness penalties. The most current material on stochastic scheduling, including correct scheduling of safety time and the use of simulation for optimization, is then presented and integrated with deterministic models. Additional topical coverage includes: Extensions of the basic model Parallel–machine models Flow shop scheduling Scheduling groups of jobs The job shop problem Simulation models for the dynamic job shop Network methods for project scheduling Resource–constrained project scheduling Stochastic and safe scheduling Extensive end–of–chapter exercises are provided, some of which are spreadsheet–oriented, and link scheduling theory to the most popular analytic platform among today′s students and practitioners—the Microsoft Office Excel® spreadsheet. Extensive references direct readers to additional literature, and the book′s related Web site houses material that reinforces the book′s concepts, including research notes, data sets, and examples from the text. Principles of Sequencing and Scheduling is an excellent book for courses on sequencing and scheduling at the upper–undergraduate and graduate levels. It is also a valuable reference for researchers and practitioners in the fields of statistics, computer science, operations research, and engineering.  

Preface. 1 Introduction. 1.1 Introduction to Sequencing and Scheduling. 1.2 Scheduling Theory. 1.3 Philosophy and Coverage of the Book. References. 2 Single–Machine Sequencing. 2.1 Introduction. 2.2 Preliminaries. 2.3 Problems Without Due Dates: Elementary Results. 2.4 Problems with Due Dates: Elementary Results. 2.5 Summary. References. Exercises. 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. References. Exercises. 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. References. Exercises. 5 Earliness and Tardiness Costs. 5.1 Introduction. 5.2 Minimizing Deviations from a Common Due Date. 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. References. Exercises. 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. References. Exercises. 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. References. Exercises. 8 Extensions of the Basic Model. 8.1 Introduction. 8.2 Nonsimultaneous Arrivals. 8.3 Related Jobs. 8.4 Sequence–Dependent Setup Times. 8.5 Stochastic Models with Sequence–Dependent Setup Times. 8.6 Summary. References. Exercises. 9 Parallel–Machine Models. 9.1 Introduction. 9.2 Minimizing the Makespan. 9.3 Minimizing Total Flowtime. 9.4 Stochastic Models. 9.5 Summary. References. Exercises. 10 Flow Shop Scheduling. 10.1 Introduction. 10.2 Permutation Schedules. 10.3 The Two–Machine Problem. 10.4 Special Cases of The Three–Machine Problem. 10.5 Minimizing the Makespan. 10.6 Variations of the m –Machine Model. 10.7 Summary. References. Exercises. 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. References. Exercises. 12 Lot Streaming Procedures for the Flow Shop. 12.1 Introduction. 12.2 The Basic Two–Machine Model. 12.3 The Three–Machine Model with Consistent Sublots. 12.4 The Three–Machine Model with Variable Sublots. 12.5 The Fundamental Partition. 12.5.1 Defining the Fundamental Partition. 12.5.2 A Heuristic Procedure for s Sublots. 12.6 Summary. References. Exercises. 13 Scheduling Groups of Jobs. 13.1 Introduction. 13.2 Scheduling Job Families. 13.3 Scheduling with Batch Availability. 13.4 Scheduling with a Batch Processor. 13.5 Summary. References. Exercises. 14 The Job Shop Problem. 14.1 Introduction. 14.2 Types of Schedules. 14.3 Schedule Generation. 14.4 The Shifting Bottleneck Procedure. 14.5 Neighborhood Search Heuristics. 14.6 Summary. References. Exercises. 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.6 Summary. References. 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.6 Summary. References. Exercises. 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.5 Summary. References. Exercises. 18 Safe Scheduling for Projects. 18.1 Introduction. 18.2 Stochastic Balance Principles For Activity Networks. 18.3 Crashing Stochastic Activities. 18.4 Summary. References. Exercises. Appendix A Practical Processing Time Distributions. A.1 Important Processing Time Distributions. A.2 Increasing and Decreasing Completion Rates. A.3 Stochastic Dominance. A.4 Linearly Associated Processing Times. References. Appendix 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. References. Appendix 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. References. Name Index. Subject Index.