Cover
Preface
1. Coverage of the Text
2. Historical Background
3. New in the Second Edition
1 Introduction
1. 1.1 Introduction to Sequencing and Scheduling
2. 1.2 Scheduling Theory
3. 1.3 Philosophy and Coverage of the Book
4. Bibliography
2 Single‐machine Sequencing
1. 2.1 Introduction
2. 2.2 Preliminaries
3. 2.3 Problems Without Due Dates: Elementary Results
4. 2.4 Problems with Due Dates: Elementary Results
5. 2.5 Flexibility in the Basic Model
6. 2.6 Summary
7. Exercises
8. Bibliography
3 Optimization Methods for the Single‐machine Problem
1. 3.1 Introduction
2. 3.2 Adjacent Pairwise Interchange Methods
3. 3.3 A Dynamic Programming Approach
4. 3.4 Dominance Properties
5. 3.5 A Branch‐and‐bound Approach
6. 3.6 Integer Programming
7. 3.7 Summary
8. Exercises
9. Bibliography
4 Heuristic Methods for the Single‐machine Problem
1. 4.1 Introduction
2. 4.2 Dispatching and Construction Procedures
3. 4.3 Random Sampling
4. 4.4 Neighborhood Search Techniques
5. 4.5 Tabu Search
6. 4.6 Simulated Annealing
7. 4.7 Genetic Algorithms
8. 4.8 The Evolutionary Solver
9. 4.9 Summary
10. Exercises
11. Bibliography
5 Earliness and Tardiness Costs
1. 5.1 Introduction
2. 5.2 Minimizing Deviations from a Common Due Date
3. 5.3 The Restricted Version
4. 5.4 Asymmetric Earliness and Tardiness Costs
5. 5.5 Quadratic Costs
6. 5.6 Job‐dependent Costs
7. 5.7 Distinct Due Dates
8. 5.8 Summary
9. Exercises
10. Bibliography
6 Sequencing for Stochastic Scheduling
1. 6.1 Introduction
2. 6.2 Basic Stochastic Counterpart Models
3. 6.3 The Deterministic Counterpart
4. 6.4 Minimizing the Maximum Cost
5. 6.5 The Jensen Gap
6. 6.6 Stochastic Dominance and Association
7. 6.7 Using Analytic Solver Platform
8. 6.8 Non‐probabilistic Approaches: Fuzzy and Robust Scheduling
9. 6.9 Summary
10. Exercises
11. Bibliography
7 Safe Scheduling
1. 7.1 Introduction
2. 7.2 Meeting Service Level Targets
3. 7.3 Trading Off Tightness and Tardiness
4. 7.4 The Stochastic E/T Problem
5. 7.5 Using the Lognormal Distribution
6. 7.6 Setting Release Dates
7. 7.7 The Stochastic U‐problem: A Service‐level Approach
8. 7.8 The Stochastic U‐problem: An Economic Approach
9. 7.9 Summary
10. Exercises
11. Bibliography
8 Extensions of the Basic Model
1. 8.1 Introduction
2. 8.2 Nonsimultaneous Arrivals
3. 8.3 Related Jobs
4. 8.4 Sequence‐Dependent Setup Times
5. 8.5 Stochastic Traveling Salesperson Models
6. 8.6 Summary
7. Exercises
8. Bibliography
9 Parallel‐machine Models
1. 9.1 Introduction
2. 9.2 Minimizing the Makespan
3. 9.3 Minimizing Total Flowtime
4. 9.4 Stochastic Models
5. 9.5 Summary
6. Exercises
7. Bibliography
10 Flow Shop Scheduling
1. 10.1 Introduction
2. 10.2 Permutation Schedules
3. 10.3 The Two‐machine Problem
4. 10.4 Special Cases of the Three‐machine Problem
5. 10.5 Minimizing the Makespan
6. 10.6 Variations of the m‐Machine Model
7. 10.7 Summary
8. Exercises
9. Bibliography
11 Stochastic Flow Shop Scheduling
1. 11.1 Introduction
2. 11.2 Stochastic Counterpart Models
3. 11.3 Safe Scheduling Models with Stochastic Independence
4. 11.4 Flow Shops with Linear Association
5. 11.5 Empirical Observations
6. 11.6 Summary
7. Exercises
8. Bibliography
12 Lot Streaming Procedures for the Flow Shop
1. 12.1 Introduction
2. 12.2 The Basic Two‐machine Model
3. 12.3 The Three‐machine Model with Consistent Sublots
4. 12.4 The Three‐machine Model with Variable Sublots
5. 12.5 The Fundamental Partition
6. 12.6 Summary
7. Exercises
8. Bibliography
13 Scheduling Groups of Jobs
1. 13.1 Introduction
2. 13.2 Scheduling Job Families
3. 13.3 Scheduling with Batch Availability
4. 13.4 Scheduling with a Batch Processor
5. 13.5 Summary
6. Exercises
7. Bibliography
14 The Job Shop Problem
1. 14.1 Introduction
2. 14.2 Types of Schedules
3. 14.3 Schedule Generation
4. 14.4 The Shifting Bottleneck Procedure
5. 14.5 Neighborhood Search Heuristics
6. 14.6 Summary
7. Exercises
8. Bibliography
15 Simulation Models for the Dynamic Job Shop
1. 15.1 Introduction
2. 15.2 Model Elements
3. 15.3 Types of Dispatching Rules
4. 15.4 Reducing Mean Flowtime
5. 15.5 Meeting Due Dates
6. 15.6 Summary
7. Bibliography
16 Network Methods for Project Scheduling
1. 16.1 Introduction
2. 16.2 Logical Constraints And Network Construction
3. 16.3 Temporal Analysis of Networks
4. 16.4 The Time/Cost Trade‐off
5. 16.5 Traditional Probabilistic Network Analysis
6. 16.6 Summary
7. Exercises
8. Bibliography
17 Resource‐Constrained Project Scheduling
1. 17.1 Introduction
2. 17.2 Extending the Job Shop Model
3. 17.3 Extending the Project Model
4. 17.4 Heuristic Construction and Search Algorithms
5. 17.5 Stochastic Sequencing with Limited Resources
6. 17.6 Summary
7. Bibliography
18 Project Analytics
1. 18.1 Introduction
2. 18.2 Basic Partitioning
3. 18.3 Correcting for Rounding
4. 18.4 Accounting for the Parkinson Effect
5. 18.5 Identifying Mixtures
6. 18.6 Addressing Subjective Estimation Bias
7. 18.7 Linear Association
8. 18.8 Summary
9. Bibliography
19 PERT 21
1. 19.1 Introduction
2. 19.2 Stochastic Balance Principles for Activity Networks
3. 19.3 Hierarchical Balancing and Progress Payments
4. 19.4 Crashing Stochastic Activities
5. 19.5 Summary
6. Exercises
7. Bibliography
Appendix A: Practical Processing Time Distributions
1. A.1 Important Processing Time Distributions
2. A.2 Mixtures of Distributions
3. A.3 Increasing and Decreasing Completion Rates
4. A.4 Stochastic Dominance
5. A.5 Linearly Associated Processing Times
6. Bibliography
Appendix B: The Critical Ratio Rule
1. B.1 A Basic Trade‐off Problem
2. B.2 Optimal Policy for Discrete Probability Models
3. B.3 A Special Discrete Case: Equally Likely Outcomes
4. B.4 Optimal Policy for Continuous Probability Models
5. B.5 A Special Continuous Case: The Normal Distribution
6. B.6 Calculating d + γE(T) for the Normal Distribution
7. B.7 Calculations for the Lognormal Distribution
8. Bibliography
Index
End User License Agreement

List of Tables

Chapter 03
1. Table 3.1
2. Table 3.2
3. Table 3.3
4. Table 3.4
Chapter 04
1. Table 4.1
2. Table 4.2
3. Table 4.3
4. Table 4.4
5. Table 4.5
6. Table 4.6
7. Table 4.7
8. Table 4.8 Twelve test problems for the T_w‐problem.
Chapter 05
1. Table 5.1
2. Table 5.2
3. Table 5.3
4. Table 5.4
Chapter 06
1. Table 6.1
2. Table 6.2
3. Table 6.3
4. Table 6.4
5. Table 6.5
6. Table 6.6
7. Table 6.7
8. Table 6.8
9. Table 6.9
10. Table 6.10
Chapter 08
1. Table 8.1
2. Table 8.2
3. Table 8.3
4. Table 8.4
5. Table 8.5
6. Table 8.6
Chapter 09
1. Table 9.1
2. Table 9.2
Chapter 10
1. Table 10.1
2. Table 10.2
Chapter 11
1. Table 11.1
Chapter 12
1. Table 12.1
2. Table 12.2
3. Table 12.3
4. Table 12.4
5. Table 12.5
6. Table 12.6
Chapter 13
1. Table 13.1
Chapter 14
1. Table 14.1
Chapter 15
1. Table 15.1
2. Table 15.2
3. Table 15.3
4. Table 15.4
5. Table 15.5
6. Table 15.6
7. Table 15.7
8. Table 15.8
9. Table 15.9
10. Table 15.10
Chapter 16
1. Table 16.1
2. Table 16.2
Chapter 17
1. Table 17.1
2. Table 17.2
3. Table 17.3
Chapter 18
1. Table 18.1
Chapter 19
1. Table 19.1
2. Table 19.2
3. Table 19.3
4. Table 19.4
Appendix A
1. Table A.1 A simulated normal random sample.
2. Table A.2 Comparing the mean and the median for the lognormal distribution.
3. Table A.3 Calculated values for Example A.1.

List of Illustrations

Chapter 01
1. Figure 1.1 A Gantt chart.
Chapter 02
1. Figure 2.1 The J(t) function.
2. Figure 2.2 An alternative view of the J(t) function.
3. Figure 2.3 The J(t) function for a schedule and its Gantt chart.
4. Figure 2.4 A pairwise interchange of adjacent jobs.
5. Figure 2.5 The V(t) function.
6. Figure 2.6 The form of a sequence that minimizes U.
Chapter 03
1. Figure 3.1 Inserting job i into the last position.
2. Figure 3.2 Feasible sequences for the three‐job example.
3. Figure 3.3 The form of a sequence in dynamic programming.
4. Figure 3.4 A branching scheme for single‐machine problems.
5. Figure 3.5 The branching tree for the example problem.
6. Figure 3.6 Spreadsheet layout for the IP solution to Example 3.5.
7. Figure 3.7 Spreadsheet layout for the IP solution to Example 3.6.
Chapter 04
1. Figure 4.1 Improvement of the objective function in neighborhood search.
2. Figure 4.2 Improvement of the objective function with simulated annealing.
3. Figure 4.3 Spreadsheet layout for the T‐problem example.
4. Figure 4.4 Specifying the objective and direction of optimization.
5. Figure 4.5 Specifying the alldifferent constraint.
6. Figure 4.6 The problem specification.
7. Figure 4.7 Information on the Engine tab.
Chapter 05
1. Figure 5.1 Optimal total cost as a function of the due date.
2. Figure 5.2 Layout for the heuristic procedure.
Chapter 06
1. Figure 6.1 Depicting the expected value as an area above the cdf.
2. Figure 6.2 E[(p₁ − t)⁺] and E[(p₂ − t)⁺] as areas.
3. Figure 6.3 Comparing two sequences with stochastic dominance.
4. Figure 6.4 Spreadsheet layout for the deterministic counterpart.
5. Figure 6.5 Lognormal probability distribution function.
6. Figure 6.6 Simulation options in ASP.
7. Figure 6.7 Summary of simulation results.
8. Figure 6.8 Displaying the simulation results on the spreadsheet.
9. Figure 6.9 Calculations for Example 6.7, showing results for the sequence (1‐3‐2‐4‐5).
Chapter 07
1. Figure 7.1 Detailed calculations for Example 7.1.
2. Figure 7.2 Detailed calculations for Example 7.2.
3. Figure 7.3 Detailed calculations for the jobs in Example 7.3.
4. Figure 7.4 A portion of the branching scheme (B&B tree) for an n‐job problem.
5. Figure 7.5 Lower bound calculation for partial sequence P(2).
6. Figure 7.6 The B&B tree for Example 7.3.
7. Figure 7.7 Detailed calculations for the jobs in Example 7.4.
8. Figure 7.8 The branch‐and‐bound tree for Example 7.4.
9. Figure 7.9 Detailed calculations for Example 7.2 with lognormal processing times.
10. Figure 7.10 The form of a sequence that maximizes the number of stochastically feasible jobs.
11. Figure 7.11 Summary of calculations for Example 7.7.
12. Figure 7.12 Graph for Example 7.8: (a) sequence 1‐2 and (b) sequence 2‐1.
13. Figure 7.13 Spreadsheet model and calculations for Example 7.10.
14. Figure 7.14 Spreadsheet model and calculations for Example 7.11.
Chapter 08
1. Figure 8.1 Three schedules for the two‐job example.
2. Figure 8.2 The example problem in (a) and after applying Step 2 in (b).
3. Figure 8.3 An eight‐job example.
4. Figure 8.4 A decomposition tree for the example in Figure 8.3.
5. Figure 8.5 The partial tree for the example problem.
6. Figure 8.6 The final tree for the example problem.
7. Figure 8.7 The complete set of mean–variance pairs for Example 8.7.
8. Figure 8.8 Nine‐job example.
Chapter 09
1. Figure 9.1 An optimal schedule for the eight‐job example.
2. Figure 9.2 A list schedule for the seven‐job example.
3. Figure 9.3 An example of implementing Algorithm 9.2.
4. Figure 9.4 An example of implementing Algorithm 9.3.
5. Figure 9.5 A seven‐job example in (a) and its preemptable representation in (b).
6. Figure 9.6 A schedule for the job set in Figure 9.5b.
7. Figure 9.7 An optimal schedule for the example with preemptable jobs.
8. Figure 9.8 An optimal solution to the six‐job F‐problem.
9. Figure 9.9 Schedules for the example problem from (a) H_m and (b) H₁.
Chapter 10
1. Figure 10.1 The precedence structure of a job in a flow shop.
2. Figure 10.2 Workflow in a pure flow shop.
3. Figure 10.3 Workflow in a general flow shop.
4. Figure 10.4 Three schedules for Example 10.1.
5. Figure 10.5 A pairwise interchange of two adjacent operations on machine 1.
6. Figure 10.6 The schedule produced by Algorithm 10.1 for Example 10.2.
7. Figure 10.7 Spreadsheet layout for the IP model of Example 10.5.
8. Figure 10.8 Flow shop layout for synchronous transfers.
9. Figure 10.9 Spreadsheet layout for the IP model of Example 10.6.
Chapter 11
1. Figure 11.1 Comparison of the cdfs for two sequences in Example 11.5.
2. Figure 11.2 The Jensen gap as a function of the nominal makespan.
3. Figure 11.3 The mean makespan as a function of the nominal makespan.
4. Figure 11.4 The standard deviation as a function of the expected makespan.
5. Figure 11.5 Some dominance relationships among schedules.
6. Figure 11.6 The Jensen gap of the two sequences as a function of the number of jobs.
7. Figure 11.7 The standard deviation of the two makespans.
Chapter 12
1. Figure 12.1 A solution to Example 12.1 with two equal sublots.
2. Figure 12.2 The continuous solution for Example 12.2.
3. Figure 12.3 The discrete solution for Example 12.2.
4. Figure 12.4 A counterexample to the optimality of geometric sublots.
5. Figure 12.5 Solutions with consistent sublots and variable sublots.
6. Figure 12.6 The continuous solution to the Example 12.3 with variable sublots.
7. Figure 12.7 Optimal solution to Example 12.4 (with machine 2 dominated).
8. Figure 12.8 Optimal solution to Example 12.1.
Chapter 13
1. Figure 13.1 A two‐machine schedule for a family containing four jobs.
2. Figure 13.2 Three schedules for Example 13.3.
3. Figure 13.3 Optimal schedule for Example 13.6.
Chapter 14
1. Figure 14.1 Workflow in a job shop.
2. Figure 14.2 Job and machine requirements in Example 14.1.
3. Figure 14.3 Two views of a feasible schedule for Example 14.1.
4. Figure 14.4 Network representation of Example 14.2.
5. Figure 14.5 Alternative resolutions of disjunctive arcs in Example 14.2.
6. Figure 14.6 Four feasible schedules for Example 14.1.
7. Figure 14.7 A partial schedule for Example 14.1.
8. Figure 14.8 Heuristic solution for Example 14.1.
9. Figure 14.9 Performing API on the heuristic result.
Chapter 15
1. Figure 15.1 Hypothetical distributions of job lateness for four priority rules.
2. Figure 15.2 Mean tardiness performance for allowance‐based rules.
3. Figure 15.3 Mean tardiness performance for slack‐based rules.
4. Figure 15.4 Mean tardiness performance for critical ratio rules and S/OPN.
5. Figure 15.5 Mean tardiness performance for selected rules.
Chapter 16
1. Figure 16.1 Activity A directly precedes B, in an AOA representation.
2. Figure 16.2 Activities C and D directly precede E, in an AOA representation.
3. Figure 16.3 Activity F directly precedes G and H, in an AOA representation.
4. Figure 16.4 An AOA network for Example 16.1.
5. Figure 16.5 Revision of Figure 16.4, using a dummy arc.
6. Figure 16.6 AON network for the activities in Example 16.1.
7. Figure 16.7 Network model for the example project.
8. Figure 16.8 Network for the example project with ET and LT shown for each event.
9. Figure 16.9 Three different ways of scheduling activities G and I.
10. Figure 16.10 The time/cost function for an individual activity.
11. Figure 16.11 A sequence of schedule modifications in Example 16.3.
12. Figure 16.12 The total cost curve.
13. Figure 16.13 The density functions of two beta distributions, (a) skewed to the right and (b) skewed to the left.
14. Figure 16.14 Deterministic analysis using mean values, for Example 16.4.
15. Figure 16.15 Distribution of individual paths in a network for two hypothetical projects.
16. Figure 16.16 The interdictive graph.
17. Figure 16.17 Network representation for Example 16.5.
Chapter 17
1. Figure 17.1 A partial schedule for Example 17.1.
2. Figure 17.2 The conditional project network given PS(2).
3. Figure 17.3 Scheduling Example 17.2 by the parallel approach.
4. Figure 17.4 Scheduling Example 17.2 by the serial approach.
5. Figure 17.5 A project network for Example 17.3.
Chapter 18
1. Figure 18.1 ln(p_j/e_j) as a function of planned duration.
2. Figure 18.2 Q–Q charts before and after correcting for rounding.
3. Figure 18.3 Normal Q–Q plot of ln(p_j/e_j) for a development project before (left) and after correcting for rounding (right).
4. Figure 18.4 Normal Q–Q plot of ln(p_j/e_j) for a development project with partial Parkinson correction before (left) and after correcting for rounding (right).
5. Figure 18.5 Normal Q–Q plot of ln(p_j) for project C2014‐03 where e_j = 1, with the on‐time activities included (left) and after correcting for the Parkinson effect (right).
6. Figure 18.6 Normal Q–Q plot of ln(p_j) for project C2014‐03 where e_j = 1 and p_j > 1 before (left) and after correcting for rounding (right).
7. Figure 18.7 Normal Q–Q plot of the residuals of the Hill et al. (2000) estimates by regression (left) and subjective estimates (right), with log‐transformed data.
8. Figure 18.8 Normal Q–Q plot for durations (left) and expenditures (right) for 12 projects as reported by Lipke et al. (2009).
9. Figure 18.9 P–P charts for a family of nine projects based on the PERT independence assumption (left) and on cross‐validation of linear association by nonparametric bootstrap (right) (Trietsch et al. 2012).
10. Figure 18.10 Cross‐validation of nine Armenian projects by nonparametric bootstrap, with correction for average bias only (left) and accounting for the variance of the bias by linear association (right).
Chapter 19
1. Figure 19.1 The ACM network structure.
2. Figure 19.2 The interdictive graph with release dates.
3. Figure 19.3 The bus scheduling problem as a project.
4. Figure 19.4 A stochastic Gantt chart for Example 19.3.
5. Figure 19.5 The optimal solution of Example 19.4 as a stochastic Gantt chart.
6. Figure 19.6 A stochastic Gantt chart for Example 19.8.
Appendix A
1. Figure A.1 A normal Q–Q chart for Table A.1.
2. Figure A.2 Comparing the basic lognormal distribution to the exponential.
3. Figure A.3 Normal Q–Q plot of ln(p_j/e_j) for machine breakdown mixture models with large infrequent repairs (left) and small frequent repairs (right).
4. Figure A.4 Depicting the expected value as an area over the cdf.
Appendix B
1. Figure B.1 Finding d* for a discrete distribution.
2. Figure B.2 Finding d* for a continuous distribution.

Wiley Series in Operations Research and Management Science

Operations Research and Management Science (ORMS) is a broad, interdisciplinary branch of applied mathematics concerned with improving the quality of decisions and processes and is a major component of the global modern movement towards the use of advanced analytics in industry and scientific research. The Wiley Series in Operations Research and Management Science features a broad collection of books that meet the varied needs of researchers, practitioners, policy makers, and students who use or need to improve their use of analytics. Reflecting the wide range of current research within the ORMS community, the Series encompasses application, methodology, and theory and provides coverage of both classical and cutting edge ORMS concepts and developments. Written by recognized international experts in the field, this collection is appropriate for students as well as professionals from private and public sectors including industry, government, and nonprofit organization who are interested in ORMS at a technical level. The Series is comprised of four sections: Analytics; Decision and Risk Analysis; Optimization Models; and Stochastic Models.

Advisory Editors • Optimization Models
Lawrence V. Snyder, Lehigh University
Ya‐xiang Yuan, Chinese Academy of Sciences

Founding Series Editor
James J. Cochran, University of Alabama

Analytics
Yang and Lee • Healthcare Analytics: From Data to Knowledge to Healthcare Improvement

Attoh‐Okine • Big Data and Differential Privacy: Analysis Strategies for Railway Track Engineering

Kong and Zhang • Decision Analytics and Optimization in Disease Prevention and Treatment

Forthcoming Titles

Dai • Handbook of Healthcare Analytics: Theoretical Minimum for Conducting 21st Century Research on Healthcare Operations

Decision and Risk Analysis
Barron • Game Theory: An Introduction, Second Edition

Brailsford, Churilov, and Dangerfield • Discrete‐Event Simulation and System Dynamics for Management Decision Making

Johnson, Keisler, Solak, Turcotte, Bayram, and Drew • Decision Science for Housing and Community Development: Localized and Evidence‐Based Responses to Distressed Housing and Blighted Communities

Mislick and Nussbaum • Cost Estimation: Methods and Tools

Forthcoming Titles
Aleman and Carter • Healthcare Engineering

Optimization Models
Ghiani, Laporte, and Musmanno • Introduction to Logistics Systems Management, Second Edition

Bozorg‐Haddad • Meta‐heuristic and Evolutionary Algorithms for Engineering Optimization

Baker and Trietsch • Principles of Sequencing and Scheduling, Second Edition

Forthcoming Titles
Smith • Learning Operations Research Through Puzzles and Games

Tone • Advances in DEA Theory and Applications: With Examples in Forecasting Models

Stochastic Models
Ibe • Random Walk and Diffusion Processes

Forthcoming Titles
Donohue, Katok, and Leider • The Handbook of Behavioral Operations

Matis • Applied Markov Based Modelling of Random Processes

This edition first published 2019
© 2019 John Wiley & Sons, Inc.

Edition History
John Wiley & Sons, Inc. (1e, 2009)

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by law. Advice on how to obtain permission to reuse material from this title is available at http://www.wiley.com/go/permissions.

The right of Kenneth R. Baker and Dan Trietsch to be identified as the authors of the material in this work has been asserted in accordance with law.

Registered Office
John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, USA

Editorial Office
111 River Street, Hoboken, NJ 07030, USA

For details of our global editorial offices, customer services, and more information about Wiley products visit us at www.wiley.com.

Wiley also publishes its books in a variety of electronic formats and by print‐on‐demand. Some content that appears in standard print versions of this book may not be available in other formats.

Limit of Liability/Disclaimer of Warranty
In view of ongoing research, equipment modifications, changes in governmental regulations, and the constant flow of information relating to the use of experimental reagents, equipment, and devices, the reader is urged to review and evaluate the information provided in the package insert or instructions for each chemical, piece of equipment, reagent, or device for, among other things, any changes in the instructions or indication of usage and for added warnings and precautions. While the publisher and authors have used their best efforts in preparing this work, they make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives, written sales materials or promotional statements for this work. The fact that an organization, website, or product is referred to in this work as a citation and/or potential source of further information does not mean that the publisher and authors endorse the information or services the organization, website, or product may provide or recommendations it may make. This work is sold with the understanding that the publisher is not engaged in rendering professional services. The advice and strategies contained herein may not be suitable for your situation. You should consult with a specialist where appropriate. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

Library of Congress Cataloging‐in‐Publication Data

Names: Baker, Kenneth R., 1943– author. | Trietsch, Dan, author.
Title: Principles of sequencing and scheduling / Kenneth R Baker, Dan Trietsch.
Description: Second edition. | Hoboken, NJ, USA : John Wiley & Sons, Inc., [2019] | Series: Wiley series in operations research and management science | Includes bibliographical references and index. |
Identifiers: LCCN 2018019714 (print) | LCCN 2018021976 (ebook) | ISBN 9781119262589 (Adobe PDF) | ISBN 9781119262596 (ePub) | ISBN 9781119262565 (hardcover)
Subjects: LCSH: Production scheduling.
Classification: LCC TS157.5 (ebook) | LCC TS157.5 .B35 2019 (print) | DDC 658.5/3–dc23
LC record available at https://lccn.loc.gov/2018019714

Preface

This textbook provides an introduction to the concepts, methods, and results of scheduling theory. It is written for graduate students and advanced undergraduates who are studying scheduling, as well as for practitioners who are interested in the knowledge base on which modern scheduling applications have been built. The coverage assumes no background in scheduling, and for stochastic scheduling topics, we assume only a familiarity with basic probability concepts. Among other things, our first appendix summarizes the important properties of the probability distributions we use.

We view scheduling theory as practical theory, and we have made sure to emphasize the practical aspects of our topic coverage. Thus, we provide algorithms that implement some of the solution concepts we describe, and we use spreadsheet models where appropriate to calculate solutions to scheduling problems. Especially when tackling stochastic scheduling problems, we must balance the need for tractability and the need for realism. Thus, we stress heuristics and simulation‐based approaches when optimization methods and analytic tools fall short. We also provide many examples in the text along with computational exercises among our end‐of‐chapter problems.

Coverage of the Text

The material in this book can support a variety of course designs. An introductory‐level course covering only deterministic scheduling can draw from Chapters 1–5, 8–10, 12–14, and 16–17. A one‐quarter course that covers both deterministic and stochastic topics can use Chapters 1–11 and possibly 15. Our own experience suggests that the entire book can support a two‐quarter sequence, especially with supplementary material we provide online.

The book contains two appendices. The first reviews the salient properties of well‐known probability distributions, as background for our coverage of stochastic models. It also covers selected topics on which some of our advanced coverage is based. The second appendix includes background derivations related to the “critical ratio rule,” which arises frequently in safe scheduling models.

Our coverage is substantial compared with that in other scheduling textbooks, but it is not encyclopedic. Our goal is to enable the reader to delve into the research literature (or in some cases, the practice literature) with enough background to appreciate the contributions of state‐of‐the‐art papers.

For the reader who is interested in a more comprehensive link to the research literature than our text covers, we provide a set of online Research Notes. The Research Notes represent unique material that expands the book’s coverage and builds an intellectual bridge to the research literature on sequencing and scheduling. In organizing the text, we wanted to proceed from simple to complex and to maintain technological order. As much as possible, each new result is based only on previous coverage. As a secondary guiding principle, the text minimizes any discussion of connections between models, thus keeping the structure simple. Scheduling theory did not develop along these same lines, however, so research‐oriented readers may wish to look at the bigger picture without adhering to these principles with the same fidelity. One purpose of our Research Notes is to offer such a picture. Another purpose is to provide some historical background. We also mention open research questions that we believe should be addressed by future research. Occasionally, we provide more depth on topics that are not sufficiently central to justify inclusion in the text itself. Finally, for readers who will be reading research papers directly from the source, we occasionally need to discuss topics that are not crucial to the text but arise frequently in the literature.

Historical Background

This book is an updated version of Baker’s text, so some historical background is appropriate at the outset. Introduction to Sequencing and Scheduling (ISS) was published by John Wiley & Sons in 1973 and became the dominant textbook in scheduling theory. A generation of instructors and graduate students relied on this book as the key source of information for advanced work in sequencing and scheduling. Later books stayed abreast of developments in the field, but as references in journal articles would indicate, most of those books were never treated as fundamental to the study of scheduling.

Sales of ISS slowed by 1980, and Wiley eventually gave up the copyright. Although they found a publishing house interested in buying the title, Baker took back the copyright. For several years, he provided generous photocopying privileges to instructors who were still interested in using the material, even though some of it had become outdated. Finally, in the early 1990s, Baker revised the book. The sequel was Elements of Sequencing and Scheduling (ESS), self‐published in 1992 and expanded in 1995. Less encyclopedic than its predecessor, ESS was rewritten to be readable and accessible to the student while still providing an intellectual springboard to the field of scheduling theory. Without advertising or sales reps, and without any association with a textbook publishing house, ESS sold several hundred copies in paperback through 2007. Another generation of advanced undergraduate and graduate students used the book in courses, while other graduate students were simply assigned the book as a required reading for independent studies or qualifying exams. Current research articles in scheduling continue to cite ISS and/or ESS as the source of basic knowledge on which today’s research is being built.

Perhaps the most important topic not covered in ESS was stochastic scheduling. With the exception of the chapter on job shop simulations, almost all the coverage in ESS dealt with deterministic models. In the last 15 years, research has focused as much on stochastic models as on deterministic models, and stochastic scheduling has become a significant part of the field. But traditional approaches to stochastic scheduling have their limitations, and new approaches are currently being developed. One important line of work introduces the notion of safe scheduling, an approach pioneered by Trietsch and others, and more recently extended in joint work by Baker and Trietsch. This book updates the coverage of ESS and adds coverage of safe scheduling as well as traditional stochastic scheduling. Because the new material comes from active researchers, the book surpasses competing texts in terms of its timeliness. And because the book retains the readability of its earlier versions, it should be the textbook of choice for instructors of scheduling courses. Finally, its title reinforces the experiences of two generations of students and scholars, providing a thread that establishes this volume, now in its second edition, as the latest update of a classic text.

New in the Second Edition

The second edition adds coverage of two major advances in stochastic scheduling and also addresses a few other new topics. One major development involves the application of branch and bound techniques and mathematical programming models to some safe scheduling problems. That new work, incorporated in Chapters 7 and 8 shows that the toolkit developed for deterministic scheduling can be applied to safe scheduling as well. The second major development builds on the validation of lognormal distributions for various empirical data sets. That new work implies that we can implement the full spectrum of analytics and modeling to scheduling, most importantly in project scheduling. Accordingly, Chapter 18 is a new chapter devoted to project analytics. The previous Chapter 18 is now Chapter 19, with an expanded coverage of hierarchical safe scheduling for projects. We also expanded Appendix A to include project analytics background material, including coverage of mixtures, which occur often, especially in projects. We also added a section on the lognormal tail distribution to Appendix B. Chapter 6 now includes a section on fuzzy scheduling and on robust scheduling. These approaches have been promoted as alternatives to stochastic scheduling that ostensibly avoid the need to fit stochastic distributions to observed processing times, but we argue that the distribution‐based approach remains the most useful one. That argument is especially valid now that stochastic scheduling models in general, and safe scheduling models in particular, can rely on validated distribution models.