Scheduling : theory, algorithms, and systems

This new edition provides an up-to-date coverage of important theoretical models in the scheduling literature as well as significant scheduling problems that occur in the real world. It again includes supplementary material in the form of slide-shows from industry and movies that show 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. The references have been made completely 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. Preface Preface to the First Edition Preface to the Second Edition Preface to the Third Edition Preface to the Fourth Edition Preface to the Fifth Edition Contents Supplementary Electronic Material 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 SetupTimes 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 Flexible Flow Shops with Unlimited Intermediate Storage 6.5 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 withoutPreemptions 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 AlgorithmLibraries 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 System 19.2 IBM's Independent Agents Architecture 19.3 Real Time Dispatching and Agent Scheduling at AMD 19.4 ASPROVA Advanced Planning and Scheduling 19.5 Preactor Planning and Scheduling Systems 19.6 ORTEMS' Agile Manufacturing Suite 19.7 LEKIN - A System Developed in Academia 19.8 Discussion 20 What Lies Ahead? 20.1 Theoretical Research 20.2 Applied Research 20.3 Systems Development Appendices 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 Deterministic and Stochastic Dynamic Programming B.1 Deterministic Dynamic Programming B.2 Stochastic Dynamic Programming 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 Complexity Theory D.1 Preliminaries D.2 Polynomial Time Solutions versus NP-Hardness D.3 Examples D.4 Approximation Algorithms and Schemes Complexity Classification of Deterministic SchedulingProblems Overview of Stochastic Scheduling Problems Selected Scheduling Systems The Lekin System H.1 Formatting of Input and Output Files H.2 Linking Scheduling Programs References Author Index Subject Index This new edition of the well-established text Scheduling: Theory, Algorithms, and Systems provides an up-to-date coverage of important theoretical models in the scheduling literature as well as important scheduling problems that appear in the real world. The accompanying website includes supplementary material in the form of slide-shows from industry as well as movies that show actual implementations of scheduling systems. The main structure of the book, as per previous editions, 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, streamlined, and extended. The references have been made completely 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. Review of third edition: "This well-established text covers both the theory and practice of scheduling. The book begins with motivating examples and the penultimate chapter discusses some commercial scheduling systems and examples of their implementations." (Mathematical Reviews, 2009)