Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2016 | Book

Introduction Read chapter Read first chapter

Scheduling

Theory, Algorithms, and Systems

Author: Michael L. Pinedo

Publisher: Springer International Publishing

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

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.

Table of Contents

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 focused on deterministic scheduling. The number and variety of models considered is 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, but 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
This chapter deals with multi-operation models that are different from the job shop models considered in the previous chapter. In a job shop each job has a fixed route that is predetermined. In practice, it often occurs that the route of the job is immaterial and up to the scheduler to decide. When the routes of the jobs are open, the model is referred to as an open shop.
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 non-preemptive 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 Chapter 5 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 can 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 types of scheduling systems. The variety of available platforms, databases, Graphic User Interfaces (GUI’s), 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
Backmatter
Metadata
Title
Scheduling
Author
Michael L. Pinedo
Copyright Year
2016
Electronic ISBN
978-3-319-26580-3
Print ISBN
978-3-319-26578-0
DOI
https://doi.org/10.1007/978-3-319-26580-3