The sixth edition provides expanded Discussion and Comments and References sections at the end of each chapter, creating a spotlight on practical applications of the theory presented in that chapter. New topics include rules for stochastic parallel machine scheduling and for stochastic online scheduling, models of flow shops with reentry, fixed parameter tractability, and new designs and implementations of scheduling systems.
The main structure of the book as per previous edition consists of three parts. The first part focuses on deterministic scheduling and the related combinatorial problems. The second part covers probabilistic scheduling models; in this part it is assumed that processing times and other problem data are random and not known in advance. The third part deals with scheduling in practice; it covers heuristics that are popular with practitioners and discusses system design and implementation issues. All three parts of this new edition have been revamped and streamlined and the references have been made up-to-date.
Theoreticians and practitioners alike will find this book of interest. Graduate students in operations management, operations research, industrial engineering, and computer science will find the book an accessible and invaluable resource. Scheduling - Theory, Algorithms, and Systems will serve as an essential reference for professionals working on scheduling problems in manufacturing, services, and other environments.
Michael L. Pinedo is the Julius Schlesinger Professor of Operations Management in the Stern School of Business at New York University.
Author(s): Michael L. Pinedo
Edition: 6
Publisher: Springer
Year: 2022
Language: English
Pages: 690
City: Cham
Preface to the Sixth Edition
The Gantt Chart: Its Originators
Supplementary Electronic Material
Contents
1 Introduction
1.1 The Role of Scheduling
1.2 The Scheduling Function in an Enterprise
1.3 Outline of the Book
Part I Deterministic Models
2 Deterministic Models: Preliminaries
2.1 Framework and Notation
2.2 Examples
2.3 Classes of Schedules
2.4 Complexity Hierarchy
3 Single Machine Models (Deterministic)
3.1 The Total Weighted Completion Time
3.2 The Maximum Lateness
3.3 The Number of Tardy Jobs
3.4 The Total Tardiness—Dynamic Programming
3.5 The Total Tardiness—An Approximation Scheme
3.6 The Total Weighted Tardiness
3.7 Online Scheduling
3.8 Discussion
4 Advanced Single Machine Models (Deterministic)
4.1 The Total Earliness and Tardiness
4.2 Primary and Secondary Objectives
4.3 Multiple Objectives: A Parametric Analysis
4.4 The Makespan with Sequence Dependent Setup Times
4.5 Job Families with Setup Times
4.6 Batch Processing
4.7 Discussion
5 Parallel Machine Models (Deterministic)
5.1 The Makespan without Preemptions
5.2 The Makespan with Preemptions
5.3 The Total Completion Time without Preemptions
5.4 The Total Completion Time with Preemptions
5.5 Due Date Related Objectives
5.6 Online Scheduling
5.7 Discussion
6 Flow Shops and Flexible Flow Shops (Deterministic)
6.1 Flow Shops with Unlimited Intermediate Storage
6.2 Flow Shops with Limited Intermediate Storage
6.3 Proportionate Flow Shops with Unlimited and Limited Intermediate Storage
6.4 Proportionate Flow Shops with Reentry
6.5 Flexible Flow Shops with Unlimited Intermediate Storage
6.6 Discussion
7 Job Shops (Deterministic)
7.1 Disjunctive Programming and Branch and Bound
7.2 The Shifting Bottleneck Heuristic and the Makespan
7.3 The Shifting Bottleneck Heuristic and the Total Weighted Tardiness
7.4 Constraint Programming and the Makespan
7.5 Discussion
8 Open Shops (Deterministic)
8.1 The Makespan without Preemptions
8.2 The Makespan with Preemptions
8.3 The Maximum Lateness without Preemptions
8.4 The Maximum Lateness with Preemptions
8.5 The Number of Tardy Jobs
8.6 Discussion
Part II Stochastic Models
9 Stochastic Models: Preliminaries
9.1 Framework and Notation
9.2 Distributions and Classes of Distributions
9.3 Stochastic Dominance
9.4 Impact of Randomness on Fixed Schedules
9.5 Classes of Policies
10 Single Machine Models (Stochastic)
10.1 Arbitrary Distributions without Preemptions
10.2 Arbitrary Distributions with Preemptions: the Gittins Index
10.3 Likelihood Ratio Ordered Distributions
10.4 Exponential Distributions
10.5 Discussion
11 Single Machine Models with Release Dates (Stochastic)
11.1 Arbitrary Release Dates and Arbitrary Processing Times without Preemptions
11.2 Priority Queues, Work Conservation, and Poisson Releases
11.3 Arbitrary Releases and Exponential Processing Times with Preemptions
11.4 Poisson Releases and Arbitrary Processing Times without Preemptions
11.5 Discussion
12 Parallel Machine Models (Stochastic)
12.1 The Makespan and Total Completion Time without Preemptions
12.2 The Makespan and Total Completion Time with Preemptions
12.3 Due Date Related Objectives
12.4 Bounds Obtained through Online Scheduling
12.5 Discussion
13 Flow Shops, Job Shops, and Open Shops (Stochastic)
13.1 Stochastic Flow Shops with Unlimited Intermediate Storage
13.2 Stochastic Flow Shops with Blocking
13.3 Stochastic Job Shops
13.4 Stochastic Open Shops
13.5 Discussion
Part III Scheduling in Practice
14 General Purpose Procedures for Deterministic Scheduling
14.1 Dispatching Rules
14.2 Composite Dispatching Rules
14.3 Local Search: Simulated Annealing and Tabu-Search
14.4 Local Search: Genetic Algorithms
14.5 Ant Colony Optimization
14.6 Discussion
15 More Advanced General Purpose Procedures
15.1 Beam Search
15.2 Decomposition Methods and Rolling Horizon Procedures
15.3 Constraint Programming
15.4 Market-Based and Agent-Based Procedures
15.5 Procedures for Scheduling Problems with Multiple Objectives
15.6 Discussion
16 Modeling and Solving Scheduling Problems in Practice
16.1 Scheduling Problems in Practice
16.2 Cyclic Scheduling of a Flow Line
16.3 Scheduling of a Flexible Flow Line with Limited Buffers and Bypass
16.4 Scheduling of a Flexible Flow Line with Unlimited Buffers and Setups
16.5 Scheduling a Bank of Parallel Machines with Jobs having Release Dates and Due Dates
16.6 Discussion
17 Design and Implementation of Scheduling Systems: Basic Concepts
17.1 Systems Architecture
17.2 Databases, Object Bases, and Knowledge-Bases
17.3 Modules for Generating Schedules
17.4 User Interfaces and Interactive Optimization
17.5 Generic Systems vs. Application-Specific Systems
17.6 Implementation and Maintenance Issues
18 Design and Implementation of Scheduling Systems: More Advanced Concepts
18.1 Robustness and Reactive Decision Making
18.2 Machine Learning Mechanisms
18.3 Design of Scheduling Engines and Algorithm Libraries
18.4 Reconfigurable Systems
18.5 Web-Based Scheduling Systems
18.6 Discussion
19 Examples of System Designs and Implementations
19.1 SAP's Production Planning and Detailed Scheduling
19.2 IBM's Independent Agents Architecture
19.3 AMD's Real Time Dispatching and Agent Scheduling
19.4 ASPROVA Advanced Planning and Scheduling
19.5 SIEMENS Opcenter APS
19.6 DELMIA Ortems Production Scheduler
19.7 CYBERPLAN - A System Developed by Cybertec
19.8 LEKIN - A System Developed in Academia
19.9 Discussion
20 What Lies Ahead?
20.1 Theoretical Research
20.2 Applied Research
20.3 Systems Development
Appendices
A Mathematical Programming: Formulations and Applications
A.1 Linear Programming Formulations
A.2 Integer Programming Formulations
A.3 Bounds, Approximations, and Heuristics Based on Linear Programming
A.4 Disjunctive Programming Formulations
B Deterministic and Stochastic Dynamic Programming
B.1 Deterministic Dynamic Programming
B.2 Stochastic Dynamic Programming
C Constraint Programming
C.1 Constraint Satisfaction
C.2 Constraint Programming
C.3 An Example of a Constraint Programming Language
C.4 Constraint Programming vs. Mathematical Programming
D Complexity Theory
D.1 Preliminaries
D.2 Polynomial Time Solutions versus NP-Hardness
D.3 Examples
D.4 Fixed Parameter Tractability
D.5 Approximation Algorithms and Schemes
E Complexity Classification of Deterministic Scheduling Problems
F Overview of Stochastic Scheduling Problems
G Selected Scheduling Systems
H The Lekin System
H.1 Formatting of Input and Output Files
H.2 Linking Scheduling Programs
References
Subject Index
Name Index
