Handbook on Scheduling

Scheduling problems can be understood in general as the problems of allocating resources over time to perform a set of tasks being parts of some processes, among which computational and manufacturing ones are most important. Tasks individually compete for resources which can be of a very different nature, e.g. manpower, money, processors (machines), energy, tools. 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 relations 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.

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 essential issues which will be discussed. 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 (e. g. tabu search, simulated annealing, ejection chains, and genetic algorithms).

Throughout this book we are concerned with scheduling computer and manufacturing processes. Despite the fact that we deal with two different areas of applications, the same model could be applied. This is because the above processes consist of complex activities to be scheduled, which can be modeled by means of tasks (or jobs), relations among them, processors, sometimes additional resources (and their operational functions), and parameters describing all these items in greater detail. The purpose of the modeling is to find optimal or sub-optimal schedules in the sense of a given criterion, by applying best suited algorithms. These schedules are then used for the original setting to carry out the various activities. In this chapter we introduce basic notions used for such a modeling of computer and manufacturing processes.

Single machine scheduling (SMS) problems seem to have received substantial attention because of several reasons. These types 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.

This chapter is devoted to the analysis of scheduling problems in a 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, imprecise computations and lot size scheduling. Corresponding results are presented in the four following sections.

One of the assumptions imposed in Chapter 3 was that each task is processed on at most one processor at a time. However, in recent years, with the rapid development of manufacturing as well as microprocessor and especially multi-microprocessor systems, the above assumption has ceased to be justified in some important applications. There are, for example, self-testing multi-microprocessor systems in which one processor is used to test others, or diagnostic systems in which testing signals stimulate the tested elements and their corresponding outputs are simultaneously analyzed [Avi78, DD81]. When formulating scheduling problems in such systems, one must take into account the fact that some tasks have to be processed on more than one processor at a time. On the other hand, communication issues must be also taken into account in systems where tasks (e.g. program modules) are assigned to different processors and exchange information between each other.

In Chapters 4 and 5 we analyzed scheduling problems in which the task performance is subject to temporal restrictions such as release times or deadlines. The present chapter deals with a similar problem, but where the tasks are to be processed repeatedly, and each execution is restricted by release times and deadlines. The release times are regularly distributed over time with equal distances called the task period. Such tasks are called periodic. The deadline is usually assumed to coincide with the release time of the next period. In many applications such as real-time systems we find problems where sets of periodic tasks are to be processed on a single processor or on a distributed or parallel processor system.

The formulation of an open shop scheduHng problem is the same as for the flow shop problem except that the order of processing tasks comprising one job may be arbitrary.

In this chapter we continue scheduUng of tasks on dedicated processors or machines. We assume that tasks belong to a set of jobs, each of which is characterized by its own machine sequence. We will assume that any two consecutive tasks of the same job are to be processed on different machines. The type of factory layout is the job shop. It provides the most flexible form of manufacturing, however, frequently accepting unsatisfactory machine utilization and a large amount of work-in-process. Hence, makespan minimization is one of the objectives in order to schedule job shops effectively, see e.g. [Pin95].

In scheduling theory the basic model assumes that all machines are continuously available for processing throughout the planning horizon. This assumption might be justified in some cases but it does not apply if certain maintenance requirements, breakdowns or other constraints that cause the machines not to be available for processing have to be considered. In this chapter we discuss results related to deterministic scheduling problems where machines are not continuously available for processing.

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. A resource is called non-renewable, 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 given finite set of possible allocations, which in particular may consist of one element only. Continuous resources, on the other hand, can be allocated in arbitrary, a priori unknown, amounts from given intervals.

Constraint propagation is an elementary method for reducing the search space of combinatorial search and optimization problems which has become more and more important in the last decades. The basic idea of constraint propagation is to detect and remove inconsistent variable assignments that cannot participate in any feasible solution through the repeated analysis and evaluation of the variables, domains and constraints describing a specific problem instance.

Within all activities of production management, production scheduling is a major part covering planning and control functions. By production management we mean all activities which are necessary to carry out production. The two main decisions to be taken 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 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 un-expected events force changes. OFP generates the requirements for ONC, and ONC creates feedback to OFP.