Principles of Sequencing and SchedulingISBN: 9780470391655
512 pages
April 2009

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 realworld examples and uptodate 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 singlemachine 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

Parallelmachine models

Flow shop scheduling

Scheduling groups of jobs

The job shop problem

Simulation models for the dynamic job shop

Network methods for project scheduling

Resourceconstrained project scheduling

Stochastic and safe scheduling
Extensive endofchapter exercises are provided, some of which are spreadsheetoriented, 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 upperundergraduate and graduate levels. It is also a valuable reference for researchers and practitioners in the fields of statistics, computer science, operations research, and engineering.
1 Introduction.
1.1 Introduction to Sequencing and Scheduling.
1.2 Scheduling Theory.
1.3 Philosophy and Coverage of the Book.
References.
2 SingleMachine 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 SingleMachine 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 SingleMachine 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 JobDependent 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 ServiceLevel Targets.
7.3 Trading Off Tightness and Tardiness.
7.4 The Stochastic E/T Problem.
7.5 Setting Release Dates.
7.6 The Stochastic UProblem: A ServiceLevel Approach.
7.7 The Stochastic UProblem: 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 SequenceDependent Setup Times.
8.5 Stochastic Models with SequenceDependent Setup Times.
8.6 Summary.
References.
Exercises.
9 ParallelMachine 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 TwoMachine Problem.
10.4 Special Cases of The ThreeMachine Problem.
10.5 Minimizing the Makespan.
10.6 Variations of the mMachine 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 TwoMachine Model.
12.3 The ThreeMachine Model with Consistent Sublots.
12.4 The ThreeMachine 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 Tradeoff.
16.5 Traditional Probabilistic Network Analysis.
16.6 Summary.
References.
Exercises.
17 ResourceConstrained 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 Tradeoff 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 SingleMachine Model.
C.2.1 SequencePosition Decisions.
C.2.2 Precedence Decisions.
C.2.3 TimeIndexed Decisions.
C.3 The Flow Shop Model.
References.
Name Index.
Subject Index.

Updated coverage of research results that have appeared in the last few years

Integrated coverage of stochastic scheduling and safe scheduling

Stochastic solutions using samplebased methods and Risk Solver

Project scheduling analysis

Extensive sets of exercises are provided at the end of every chapter. Some of the exercises are spreadsheetoriented and link scheduling theory to the most popular analytic platform among today's students and practitioners  the Microsoft Office Excel® spreadsheet.

In addition to thorough coverage of deterministic models, recent developments and approaches of stochastic models are also provided

The book minimizes any discussion of connections between the presented models, which allows for structural independence for classroom use

A Research Supplement is also available via the book's FTP site. This supplement includes research notes and additional material that expands on the coverage in the book and represents an intellectual bridge to the research literature on sequencing and scheduling