Skip to main content
main-content

Über dieses Buch

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 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. Reviews 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)

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract
Scheduling is a decision making process that is used on a regular basis in many manufacturing and services industries. It deals with the allocation of resources to tasks over given time periods and its goal is to optimize one or more objectives
Michael L. Pinedo

Deterministic Models

Frontmatter

Chapter 2. Deterministic Models:Preliminaries

Abstract
Over the last fifty years a considerable amount of research effort has been focusedon deterministic scheduling. The number and variety of models consideredis astounding. During this time a notation has evolved that succinctly captures the structure of many (but for sure not all) deterministic models that have been considered in the literature
Michael L. Pinedo

Chapter 3. Single Machine Models (Deterministic)

Abstract
Single machine models are important for various reasons. The single machine environment is very simple and a special case of all other environments. Single machine models often have properties that neither machines in parallel nor machines in series have. The results that can be obtained for single machine models not only provide insights into the single machine environment, they also provide a basis for heuristics that are applicable to more complicated machine environments. In practice, scheduling problems in more complicated machine environments are often decomposed into subproblems that deal with single machines. For example, a complicated machine environment with a single bottleneck may give rise to a single machine model.
Michael L. Pinedo

Chapter 4. Advanced Single Machine Models (Deterministic)

Abstract
This chapter covers several more advanced topics in single machine scheduling.Some of these topics are important because of the theoretical insights they provide, others are important because of their applications in practice.
Michael L. Pinedo

Chapter 5. Parallel Machine Models (Deterministic)

Abstract
A bank of machines in parallel is a setting that is important from both a theoretical and a practical point of view. From a theoretical point of view it is a generalization of the single machine, and a special case of the flexible flow shop. From a practical point of view, it is important because the occurrence of resources in parallel is common in the real world. Also, techniques for machines in parallel are often used in decomposition procedures for multi-stage systems.
Michael L. Pinedo

Chapter 6. Flow Shops and Flexible Flow Shops (Deterministic)

Abstract
In many manufacturing and assembly facilities each job has to undergo a series of operations. Often, these operations have to be done on all jobs in the same order implying that the jobs have to follow the same route. The machines are then assumed to be set up in series and the environment is referred to as a flow shop
Michael L. Pinedo

Chapter 7. Job Shops (Deterministic)

Abstract
This chapter deals with multi operation models that are different from the flow shop models discussed in the previous chapter. In a flow shop model all jobs follow the same route. When the routes are fixed, but not necessarily the same for each job, the model is called a job shop. If a job in a job shop has to visit certain machines more than once, the job is said to recirculate. Recirculation is a common phenomenon in the real world. For example, in semiconductor manufacturing jobs have to recirculate several times before they complete all their processing.
Michael L. Pinedo

Chapter 8. Open Shops (Deterministic)

Abstract
A bank of machines in parallel is a setting that is important from both a theoretical and a practical point of view. From a theoretical point of view it is a generalization of the single machine, and a special case of the flexible flow shop. From a practical point of view, it is important because the occurrence of resources in parallel is common in the real world. Also, techniques for machines in parallel are often used in decomposition procedures for multi-stage systems.
Michael L. Pinedo

Stochastic Models

Frontmatter

Chapter 9. Stochastic Models: Preliminaries

Abstract
Production environments in the real world are subject to many sources of uncertainty or randomness. Sources of uncertainty that may have a major impact include machine breakdowns and unexpected releases of high priority jobs. Another source of uncertainty lies in the processing times, which are often not precisely known in advance. A good model for a scheduling problem should address these forms of uncertainty.
Michael L. Pinedo

Chapter 10. Single Machine Models (Stochastic)

Abstract
Stochastic models, especially with exponential processing times, may often contain more structure than their deterministic counterparts and may lead to results which, at first sight, seem surprising. Models that are NP hard in a deterministic setting often allow a simple priority policy to be optimal in a stochastic setting
Michael L. Pinedo

Chapter 11. Single Machine Models with Release Dates (Stochastic)

Abstract
In many stochastic environments job releases occur at random points in time. This chapter focuses on single machine stochastic models with the jobs having besides random processing times also random release dates. The objective is the total expected weighted completion time. Preemptive as well as nonpreemptive models are considered.
Michael L. Pinedo

Chapter 12. Parallel Machine Models (Stochastic)

Abstract
This chapter deals with parallel machine models that are stochastic counterparts of models discussed in The body of knowledge in the stochastic case is somewhat less extensive than in the deterministic case
Michael L. Pinedo

Chapter 13. Flow Shops, Job Shops and Open Shops (Stochastic)

Abstract
The results for stochastic flow shops, job shops, and open shops are somewhat less extensive than those for their deterministic counterparts
Michael L. Pinedo

Scheduling in Practice

Frontmatter

Chapter 14. General Purpose Procedures for Deterministic Scheduling

Abstract
This chapter describes a number of general purpose procedures that are useful in dealing with scheduling problems in practice and that can be implemented with relative ease in industrial scheduling systems. All the techniques described are heuristics that do not guarantee an optimal solution; they instead aim at finding reasonably good solutions in a relatively short time. The heuristics tend to be fairly generic and can be adapted easily to a large variety of scheduling problems
Michael L. Pinedo

Chapter 15. More Advanced General Purpose Procedures

Abstract
The previous chapter covered the more established and the more widely used generic procedures. This chapter focuses on techniques that are more specialized and not as widely used.
Michael L. Pinedo

Chapter 16. Modeling and Solving Scheduling Problems in Practice

Abstract
In Parts I and II a number of stylized and (supposedly) elegant mathematical models are discussed in detail. The deterministic models have led to a number of simple priority rules as well as to many algorithmic techniques and heuristic procedures. The stochastic models have provided some insight into the robustness of the priority rules. The results for the stochastic models have led to the conclusion that the more randomness there is in a system, the less advisable it is to use very sophisticated optimization techniques. Or, equivalently, the more randomness the system is subject to, the simpler the scheduling rules ought to be.
Michael L. Pinedo

Chapter 17. Design and Implementation of Scheduling Systems: Basic Concepts

Abstract
Analyzing a scheduling problem and developing a procedure for dealing with it on a regular basis is, in the real world, only part of the story. The procedure has to be embedded in a system that enables the decision-maker to actually use it. The system has to be integrated into the information system of the enterprise, which can be a formidable task. This chapter focuses on system design and implementation issues.
Michael L. Pinedo

Chapter 18. Design and Implementation of Scheduling Systems: More Advanced Concepts

Abstract
This chapter focuses on a number of issues that have come up in recent years in the design, development, and implementation of scheduling systems. The first section discusses issues concerning uncertainty, robustness and reactive decision making. In practice, schedules often have to be changed because of random events. The more robust the original schedule is, the easier the rescheduling is. This section focuses on the generation of robust schedules as well as on the measurement of their robustness. The second section considers machine learning mechanisms. No system can consistently generate good solutions that are to the liking of the user. The decision-maker often has to tweak the schedule generated by the system in order to make it usable. A well-designed system can learn from past adjustments made by the user the mechanism that enables the system to do this is called a learning mechanism. The third section focuses on the design of scheduling engines. An engine often contains an entire library of algorithms
Michael L. Pinedo

Chapter 19. Examples of System Designs and Implementations

Abstract
From the previous chapters it is evident that there are many different types of scheduling problems. It is not likely that a system can be designed in such a way that it could be made applicable to any scheduling problem with only minor customization. This suggests that there is room as well as a need for many different scheduling systems. The variety of available platforms, databases, Graphic User Interfaces (GUIs) and networking capabilities enlarges the number of possibilities even more
Michael L. Pinedo

Chapter 20. What Lies Ahead?

Abstract
This chapter describes various research and development topics that are likely to receive attention in the near future. A distinction is made between theoretical research, applied research, and developments in system design
Michael L. Pinedo

Appendices

Frontmatter

Appendix A. Mathematical Programming: Formulations and Applications

Abstract
This appendix gives an overview of the types of problems that can be formulated as mathematical programs. All the applications discussed concern scheduling problems. In order to understand these examples the reader should be familiar with the notation introduced in Chapter 2.This appendix is aimed at people who are already familiar with elementary Operations Research techniques. It makes an attempt to put various notions and problem definitions in perspective. Relatively little will be said about the standard solution techniques for dealing with such problems
Michael L. Pinedo

Appendix B. Deterministic and Stochastic Dynamic Programming

Abstract
Dynamic programming is one of the more widely used techniques for dealing with combinatorial optimization problems. Dynamic Programming can be applied to problems that are solvable in polynomial time, as well as problems that cannot be solved in polynomial time (see Appendix C). It has proven to be very useful for stochastic problems as well
Michael L. Pinedo

Appendix C. Constraint Programming

Abstract
In contrast to mathematical programming, which has its roots in the Operations Research community, constraint programming has its origins in the Artificial Intelligence and Computer Science communities. Constraint programming can be traced back to the constraint satisfaction problems studied in the 1970s. A constraint satisfaction problem requires a search for a feasible solution that satisfies all given constraints. To facilitate the search for a solution to such a problem various special purpose languages have been developed, e.g., Prolog. However, during the last decade of the twentieth century, constraint programming has not only been used for solving feasibility problems, but also for solving optimization problems. Several approaches have been developed that facilitate the application of constraint programming to optimization problems. One such approach is via the Optimization Programming Language (OPL), which was designed for modeling and solving optimization problems through both constraint programming techniques and mathematical programming procedures
Michael L. Pinedo

Appendix D. Complexity Theory

Abstract
Dynamic programming is one of the more widely used techniques for dealing with combinatorial optimization problems. Dynamic Programming can be applied to problems that are solvable in polynomial time, as well as problems that cannot be solved in polynomial time (see Appendix C). It has proven to be very useful for stochastic problems as well
Michael L. Pinedo

Appendix E. Complexity Classification of Deterministic Scheduling Problems

Abstract
Complexity theory is based on a mathematical framework developed by logicians and computer scientists. This theory was developed to study the intrinsic difficulty of algorithmic problems and has proven very useful for combinatorial optimization. This appendix presents a brief overview of this theory and its ramifications for scheduling
Michael L. Pinedo

Appendix F. Overview of Stochastic Scheduling Problems

Abstract
No framework or classification scheme has ever been introduced for stochastic scheduling problems. It is more difficult to develop such a scheme for stochastic scheduling problems than for deterministic scheduling problems. In order to characterize a stochastic scheduling problem more information is required. For example, the distributions of the processing times have to be specified as well as the distributions of the due dates (which may be different). It has to be specified whether the processing times of the n jobs are independent or correlated (e.g., equal to the same random variable) and also which class of policies is considered. For these reasons no framework has been introduced in this book either
Michael L. Pinedo

Appendix G. Selected Scheduling Systems

Abstract
Over the last three decades hundreds of scheduling systems have been developed. These developments have taken place in industry and in academia in many countries. An up-to-date list or annotated bibliography of all systems most likely does not exist. However, several survey papers have been written describing a number of systems
Michael L. Pinedo

Appendix H. The Lekin System

Abstract
This appendix provides examples of the formats of files that contain workstation information and job information. It also gives an example that illustrates how input data are read and how output data are written by a program that is linked to the LEKIN system.
Michael L. Pinedo

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise