Skip to main content
main-content

Inhaltsverzeichnis

Frontmatter

1. Introduction

Abstract
Let us start with the description of the purpose of this book. Firstly we should explain how we understand its title. In general, scheduling problems can be understood very broadly as the problems of the allocation of resources over time to perform a set of tasks. By resources we understand arbitrary means tasks compete for. They can be of a very different nature, e.g. manpower, money, processors (machines), energy, tools. Also tasks can have a variety of interpretations starting from machining parts in manufacturing systems up to processing information in computer systems. The same is true for task characteristics, e. g. ready times, due dates, relative urgency weights, functions describing task processing in relation to allotted resources. Moreover, a structure of a set of tasks, reflecting precedence contraints among them, can be defined in different ways. In addition, different criteria which measure the quality of the performance of a set of tasks can be taken into account.
Jacek Blazewicz, Klaus Ecker, Günter Schmidt, Jan Wȩglarz

2. Preliminaries

Abstract
In this chapter we provide the reader with basic notions used throughout the book. After a short introduction into sets and relations, decision problems, optimization problems and the encoding of problem instances are discussed. The way algorithms will be represented, and problem membership of complexity classes are other issues that are essential because algorithms for scheduling problems and their properties will be discussed from the complexity point of view. Afterwards graphs, especially certain types such as precedence graphs and networks that are important for scheduling problems, are presented. The last two sections deal with algorithmic methods used in scheduling such as enumerative algorithms (e. g. dynamic programming and branch and bound) and heuristic approaches.
Jacek Blazewicz, Klaus Ecker, Günter Schmidt, Jan Wȩglarz

3. Formulation of Scheduling Problems

Abstract
In general, scheduling problems considered in this book are characterized by three sets: set T of n tasks T = {T 1, T 2,...,T n }, set P of m processors (machines) P = {P 1, P 2,...,P m } and set R of s types of additional resources R = {R 1, R 2,...,R S }. Scheduling, generally speaking, means to assign processors from P and (possibly) resources from R , to tasks from T in order to complete all tasks under the imposed constraints. There are two general constraints in classical scheduling theory. Each task is to be processed by at most one processor at a time (plus possibly specified amounts of additional resources) and each processor is capable of processing at most one task at a time. In Sections 5.4 and 7.2 we will show some new applications in which the first constraint will be relaxed.
Jacek Blazewicz, Klaus Ecker, Günter Schmidt, Jan Wȩglarz

4. Single Processor Scheduling

Abstract
Single machine scheduling (SMS) problems seem to have received substantial attention because of several reasons. These type of problems are important both because of their own intrinsic value, as well as their role as building blocks for more generalized and complex problems. In a multi-processor environment single processor schedules may be used in bottlenecks, or to organize task assignment to an expensive processor, sometimes an entire production line may be treated as a single processor for scheduling purposes. Also, compared to multiple processor scheduling, SMS problems are mathematically more tractable. Hence more problem classes can be solved in polynomial time, and a larger variety of model parameters, such as various types of cost functions, or an introduction of change-over cost, can be analyzed. Single processor problems are thus of rather fundamental character and allow for some insight and development of ideas when treating more general scheduling problems.
Jacek Blazewicz, Klaus Ecker, Günter Schmidt, Jan Wȩglarz

5. Parallel Processor Scheduling

Abstract
This chapter is devoted to the analysis of scheduling problems in parallel processor environment. As before the three main criteria to be analyzed are schedule length, mean flow time and lateness. Then, some more developed models of multiprocessor systems are described, including semi-identical processors and uniform k-processor systems. Corresponding results are presented in the four following sections.
Jacek Blazewicz, Klaus Ecker, Günter Schmidt, Jan Wȩglarz

6. Static Shop Scheduling

Abstract
In this chapter we will consider scheduling tasks on dedicated processors (machines). As we said in Section 3.1 we assume that tasks form n subsets (or jobs), belonging to set j, and two adjacent tasks of a job are to be performed on different machines. Unfortunately, most scheduling problems of this kind are NP-hard, which is especially true for optimality criteria other than Cmax. In the first two sections we will concentrate first on polynomial time algorithms, where special cases of flow shop and open shop scheduling problems will be considered. Then the job shop scheduling problem will be discussed and two approaches, a heuristic based on simulated annealing and an exact based on branch and bound will be presented.
Jacek Blazewicz, Klaus Ecker, Günter Schmidt, Jan Wȩglarz

7. Resource Constrained Scheduling

Abstract
The scheduling model we consider now is more complicated than the previous ones, because any task, besides processors, may require for its processing some additional scarce resources. Resources, depending on their nature, may be classified into types and categories. The classification into types takes into account only the functions resources fulfill: resources of the same type are assumed to fulfill the same functions. The classification into categories will concern two points of view. First, we differentiate three categories of resources from the viewpoint of resource constraints. We will call a resource renewable,if only its total usage i.e. temporary availability at every moment is constrained (in other words this resource can be used once more when returned by a task currently using it). A resource is called nonrenewable,if only its total consumption, i.e. integral availability up to any given moment is constrained (in other words this resource once used by some task cannot be assigned to any other task). A resource is called doubly constrained,if both total usage and total consumption are constrained. Secondly, we distinguish two resource categories from the viewpoint of resource divisibility: discrete (i.e. discretely-divisible) and continuous (i.e. continuously-divisible) resources. In other words, by a discrete resource we will understand a resource which can be allocated to tasks in discrete amounts from a finite set of possible allocations, which in particular may consist of only one unit per task. Continuous resources, on the other hand, can be allocated in arbitrary a priori unknown amounts less than or equal to some given maximum value.
Jacek Blazewicz, Klaus Ecker, Günter Schmidt, Jan Wȩglarz

8. Scheduling in Flexible Manufacturing Systems

Abstract
A new application area for machine scheduling theory comes from Flexible Manufacturing Systems (FMSs). This relatively new technology was introduced to improve the efficiency of a job shop while retaining its flexibility. An FMS can be defined as an integrated manufacturing system consisting of flexible machines equipped with tool magazines and linked by a material handling system, where all system components are under computer control [BY86a]. Existing FMSs mainly differ by the installed hardware concerning machine types, tool changing devices and material handling systems. Instances of machine types are dedicated machines or parallel multi-purpose ones. Tool changing devices can be designed to render automatic online tool transportation and assignment to the machines’ magazines while the system is running. In other cases tool changes are only possible if the operations of the system are stopped. Most of the existing FMSs have automatic part transportation capabilities.
Jacek Blazewicz, Klaus Ecker, Günter Schmidt, Jan Wȩglarz

9. Knowledge-Based Scheduling

Abstract
Within all activities of production management, production scheduling is a major part of production planning and control. By production management we mean all activities which are necessary to carry out production. The two main activities in this field are production planning and production control. Production scheduling is a common activity of these two areas because scheduling is needed not only on the planning level — as mainly treated in the preceding chapters — but also on the control level. From the different aspects of production scheduling problems we can further distinguish predictive production scheduling or offline planning (OFP) and reactive production scheduling or online-control (ONC). Predictive production scheduling serves to provide guidance in achieving global coherence in the process of local decision making. Reactive production scheduling is concerned with revising predictive schedules when unexpected events force changes. OFP generates the requirements for ONC and ONC creates feedback to OW. The relationship between these functions are shown in Figure 9.0.1.
Jacek Blazewicz, Klaus Ecker, Günter Schmidt, Jan Wȩglarz

Backmatter

Weitere Informationen