Scheduling
Theory, Algorithms, and Systems
2nd Edition
Published on 12. December 2001
Book
Hardback
586 pages
978-0-13-028138-8 (ISBN)
Description
Efficient scheduling of resources is critical to the proper functioning of businesses in today's competitive environment. Scheduling focuses on theoretical as well as applied aspects of the scheduling of resources. It is unique in the range of problems and issues that it covers. The book consists of three parts. The first part focuses on deterministic scheduling and deals with the combinational problems that arise in deterministic scheduling. The second part covers probabilistic scheduling models. In this part it is assumed that processing times and other problem data are not known in advance with certainty. The third part deals with scheduling in practice. It covers heuristics that are popular with practitioners and also delves into system design and developmental issues. INCLUDES: *Discussion of the basic properties of scheduling models. *Computational as well as theoretical exercises at the end of each chapter. *Thorough examination of numerous applications. *Investigation of the latest developments in the field. *Discussion of future research developments. A software package especially designed for the readers of this text is available free of charge on the web.Known as LEKIN, this system covers most of the machine environments discussed in this book and enables the user to test many of the algorithms and heuristics described.
This book is of interest to theoreticians and practitioners alike. Graduate students in operations research, industrial engineering, and computer science will find the book to be an accessible and invaluable resource. Scheduling will serve as an essential reference for professionals working on scheduling problems in manufacturing and computing environments.
This book is of interest to theoreticians and practitioners alike. Graduate students in operations research, industrial engineering, and computer science will find the book to be an accessible and invaluable resource. Scheduling will serve as an essential reference for professionals working on scheduling problems in manufacturing and computing environments.
More details
Edition
2nd edition
Language
English
Place of publication
United States
Publishing group
Pearson Education (US)
Target group
College/higher education
Dimensions
Height: 240 mm
Width: 182 mm
Thickness: 26 mm
Weight
1036 gr
ISBN-13
978-0-13-028138-8 (9780130281388)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Other editions
Previous edition
Book
01/1995
Pearson
€54.46
Article exhausted; check for reprint
Person
Michael Pinedo is a research professor with the Stern School of Business, New York University. His research interests lie in the theoretical and applied aspects of scheduling. He has written numerous papers on the theory of deterministic and stochastic scheduling. He has also consulted extensively in industry and has been actively involved in the development of several large industrial scheduling systems.
Content
1. Introduction.
The Role of Scheduling. The Scheduling Function in an Enterprise. Outline of the Book.
I. DETERMINISTIC MODELS.
2. Deterministic Models: Preliminaries.
Framework and Notation. Examples. Classes of Schedules. Complexity Hierarchy.
3. Single Machine Models (Deterministic).
The Total Weighted Completion Time. The Maximum Lateness. The Number of Tardy Jobs. The Total Tardiness. The Total Weighted Tardiness. Discussion.
4. More Advanced Single Machine Models (Deterministic).
The Total Tardiness: An Approximation Scheme. The Total Earliness and Tardiness. Primary and Secondary Objectives. Multiple Objectives: A Parametric Analysis. The Makespan with Sequence-Dependent Setup Times. Discussion.
5. Parallel Machine Models (Deterministic).
The Makespan without Preemptions. The Makespan with Preemptions. The Total Completion Time without Preemptions. The Total Completion Time with Preemptions. Due Date-Related Objectives. Discussion.
6. Flow Shops and Flexible Flow Shops (Deterministic).
Flow Shops with Unlimited Intermediate Storage. Flow Shops with Limited Intermediate Storage. Flexible Flow Shops with Unlimited Intermediate Storage.
7. Job Shops (Deterministic).
Disjunctive Programming and Branch and Bound. The Shifting Bottleneck Heuristic and the Makespan. The Shifting Bottleneck Heuristic and the Total Weighted Tardiness. Discussion.
8. Open Shops (Deterministic).
The Makespan without Preemptions. The Makespan with Preemptions. The Maximum Lateness without Preemptions. The Maximum Lateness with Preemptions. The Number of Tardy Jobs. Discussion.
II. STOCHASTIC MODELS.
9. Stochastic Models: Preliminaries.
Framework and Notation. Distributions and Classes of Distributions. Stochastic Dominance. Impact of Randomness on Fixed Schedules. Classes of Policies.
10. Single Machine Models (Stochastic).
Arbitrary Distributions without Preemptions. Arbitrary Distributions with Preemptions: The Gittins Index. Likelihood Ratio Ordered Distributions. Exponential Distributions.
11. Single Machine Models with Release Dates (Stochastic).
Arbitrary Releases and Arbitrary Processing Times. Priority Queues, Work Conservation, and Poisson Releases. Arbitrary Releases and Exponential Processing Times. Poisson Releases and Arbitrary Processing Times. Discussion.
12. Parallel Machine Models (Stochastic).
The Makespan with Preemptions. The Makespan and Total Completion Time with Preemptions. Due-Date Related Objectives.
13. Flow Shops, Job Shops, and Open Shops (Stochastic).
Stochastic Flow Shops with Unlimited Intermediate Storage. Stochastic Flow Shops with Blocking. Stochastic Job Shops. Stochastic Open Shops.
III. SCHEDULING IN PRACTICE.
14. General Purpose Procedures for Scheduling in Practice.
Dispatching Rules. Composite Dispatching Rules. Filtered Beam Search. Local Search: Simulated Annealing and Tabu-Search. Local Search: Genetic Algorithms. Discussion.
15. More Advanced General Purpose Procedures.
Decomposition Methods and Rolling Horizon Procedures. Constraint Guided Heuristic Search. Market-Based and Agent-Based Procedures. Procedures for Scheduling Problems with Multiple Objectives. Discussion.
16. Modeling and Solving Scheduling Problems in Practice.
Scheduling Problems in Practice. Cyclic Scheduling of a Flow Line. Flexible Flow Line with Limited Buffers and Bypass. Flexible Flow Line with Unlimited Buffers and Setups. Bank of Parallel Machines with Release Dates and Due Dates. Discussion.
17. Design, Development, and Implementation of Scheduling Systems.
Systems Architecture. Databases and Knowledge-Bases. Schedule Generation Issues. User Interfaces and Interactive Optimization. Generic Systems Versus Application-Specific Systems. Implementation and Maintenance Issues.
18. Advanced Concepts in Scheduling System Design.
Robustness and Reactive Scheduling. Machine Learning Mechanisms. Design of Scheduling Engines and Algorithm Libraries. Reconfigurable Systems. Scheduling Systems on the Internet. Discussion.
19. Examples of System Designs and Implementations.
The SAP-APO System. IBM's Independent Agents Architecture. i2's TradeMatrix Production Scheduler. An Implementation of Cybertec's Cyberplan. Synquests's Virtual Production Engine. The LEKIN System for Research and Teaching. Discussion.
20. What Lies Ahead?
Theoretical Research. Applied Research. Systems Development and Integration.
APPENDICES.
Appendix A: Mathematical Programming: Formulations and Applications.
Linear Programming Formulations. Integer Programming Formulations. Disjunctive Programming Formulations.
Appendix B: Deterministic and Stochastic Dynamic Programming.
Deterministic Dynamic Programming. Stochastic Dynamic Programming.
Appendix C: Complexity Theory.
Preliminaries. Polynomial Time Solutions Versus NP-Hardness. Examples.
Appendix D: Complexity Classification of Deterministic Scheduling Problems.
Appendix E: Overview of Stochastic Scheduling Problems.
Appendix F: Selected Scheduling Systems.
REFERENCES.
The Role of Scheduling. The Scheduling Function in an Enterprise. Outline of the Book.
I. DETERMINISTIC MODELS.
2. Deterministic Models: Preliminaries.
Framework and Notation. Examples. Classes of Schedules. Complexity Hierarchy.
3. Single Machine Models (Deterministic).
The Total Weighted Completion Time. The Maximum Lateness. The Number of Tardy Jobs. The Total Tardiness. The Total Weighted Tardiness. Discussion.
4. More Advanced Single Machine Models (Deterministic).
The Total Tardiness: An Approximation Scheme. The Total Earliness and Tardiness. Primary and Secondary Objectives. Multiple Objectives: A Parametric Analysis. The Makespan with Sequence-Dependent Setup Times. Discussion.
5. Parallel Machine Models (Deterministic).
The Makespan without Preemptions. The Makespan with Preemptions. The Total Completion Time without Preemptions. The Total Completion Time with Preemptions. Due Date-Related Objectives. Discussion.
6. Flow Shops and Flexible Flow Shops (Deterministic).
Flow Shops with Unlimited Intermediate Storage. Flow Shops with Limited Intermediate Storage. Flexible Flow Shops with Unlimited Intermediate Storage.
7. Job Shops (Deterministic).
Disjunctive Programming and Branch and Bound. The Shifting Bottleneck Heuristic and the Makespan. The Shifting Bottleneck Heuristic and the Total Weighted Tardiness. Discussion.
8. Open Shops (Deterministic).
The Makespan without Preemptions. The Makespan with Preemptions. The Maximum Lateness without Preemptions. The Maximum Lateness with Preemptions. The Number of Tardy Jobs. Discussion.
II. STOCHASTIC MODELS.
9. Stochastic Models: Preliminaries.
Framework and Notation. Distributions and Classes of Distributions. Stochastic Dominance. Impact of Randomness on Fixed Schedules. Classes of Policies.
10. Single Machine Models (Stochastic).
Arbitrary Distributions without Preemptions. Arbitrary Distributions with Preemptions: The Gittins Index. Likelihood Ratio Ordered Distributions. Exponential Distributions.
11. Single Machine Models with Release Dates (Stochastic).
Arbitrary Releases and Arbitrary Processing Times. Priority Queues, Work Conservation, and Poisson Releases. Arbitrary Releases and Exponential Processing Times. Poisson Releases and Arbitrary Processing Times. Discussion.
12. Parallel Machine Models (Stochastic).
The Makespan with Preemptions. The Makespan and Total Completion Time with Preemptions. Due-Date Related Objectives.
13. Flow Shops, Job Shops, and Open Shops (Stochastic).
Stochastic Flow Shops with Unlimited Intermediate Storage. Stochastic Flow Shops with Blocking. Stochastic Job Shops. Stochastic Open Shops.
III. SCHEDULING IN PRACTICE.
14. General Purpose Procedures for Scheduling in Practice.
Dispatching Rules. Composite Dispatching Rules. Filtered Beam Search. Local Search: Simulated Annealing and Tabu-Search. Local Search: Genetic Algorithms. Discussion.
15. More Advanced General Purpose Procedures.
Decomposition Methods and Rolling Horizon Procedures. Constraint Guided Heuristic Search. Market-Based and Agent-Based Procedures. Procedures for Scheduling Problems with Multiple Objectives. Discussion.
16. Modeling and Solving Scheduling Problems in Practice.
Scheduling Problems in Practice. Cyclic Scheduling of a Flow Line. Flexible Flow Line with Limited Buffers and Bypass. Flexible Flow Line with Unlimited Buffers and Setups. Bank of Parallel Machines with Release Dates and Due Dates. Discussion.
17. Design, Development, and Implementation of Scheduling Systems.
Systems Architecture. Databases and Knowledge-Bases. Schedule Generation Issues. User Interfaces and Interactive Optimization. Generic Systems Versus Application-Specific Systems. Implementation and Maintenance Issues.
18. Advanced Concepts in Scheduling System Design.
Robustness and Reactive Scheduling. Machine Learning Mechanisms. Design of Scheduling Engines and Algorithm Libraries. Reconfigurable Systems. Scheduling Systems on the Internet. Discussion.
19. Examples of System Designs and Implementations.
The SAP-APO System. IBM's Independent Agents Architecture. i2's TradeMatrix Production Scheduler. An Implementation of Cybertec's Cyberplan. Synquests's Virtual Production Engine. The LEKIN System for Research and Teaching. Discussion.
20. What Lies Ahead?
Theoretical Research. Applied Research. Systems Development and Integration.
APPENDICES.
Appendix A: Mathematical Programming: Formulations and Applications.
Linear Programming Formulations. Integer Programming Formulations. Disjunctive Programming Formulations.
Appendix B: Deterministic and Stochastic Dynamic Programming.
Deterministic Dynamic Programming. Stochastic Dynamic Programming.
Appendix C: Complexity Theory.
Preliminaries. Polynomial Time Solutions Versus NP-Hardness. Examples.
Appendix D: Complexity Classification of Deterministic Scheduling Problems.
Appendix E: Overview of Stochastic Scheduling Problems.
Appendix F: Selected Scheduling Systems.
REFERENCES.