Scheduling : theory, algorithms, and systems

Description

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