Scheduling Algorithms

The theory of scheduling is characterized by a virtually unlimited number of problem types (see, e.g. Baker [11], Blazewicz et al. [24], Coffman [63], Conway et al. [66], French [86], Lenstra [144], Pinedo [172], Rinnooy Kan [173], Tanaev et al. [185], Tanaev et al. [186]). In this chapter, a basic classification for the scheduling problems covered in the first part of this book will be given. This classification is based on a classification scheme widely used in the literature (see, e.g. Lawler et al. [138]). In later chapters we will extend this classification scheme.

Some scheduling problems can be solved efficiently by reducing them to well-known combinatorial optimization problems, such as linear programs, maximum flow problems, or transportation problems. Others can be solved by using standard techniques, such as dynamic programming and branch-and-bound methods. In this chapter we will give a brief survey of these combinatorial optimization problems. We will also discuss some of the methods.

Practical experience shows that some computational problems are easier to solve than others. Complexity theory provides a mathematical framework in which computational problems are studied so that they can be classified as “easy” or “hard”. In this chapter we will describe the main points of such a theory. A more rigorous presentation can be found in the fundamental book of Carey & Johnson [92].

The single machine case has been the subject of extensive research ever since the early work of Jackson [111] and Smith [180]. In this chapter, we will present algorithms for single machine scheduling problems which are polynomial or pseudopolynomial. It is useful to note the following general result which holds for single machine problems: if all r _j = 0 and if the objective function is a monotone function of the finishing times of the jobs, then only schedules without preemption and without idle time need to be considered. This follows from the fact that the optimal objective value does not improve if preemption is allowed. To see this, consider a schedule in which some job i is preempted, i.e.

In this chapter, we discuss the problem of scheduling jobs on parallel machines. Problem P ‖ Σ C _i and, more generally, problem R ‖ Σ C _i are the only nonpreemptive problems with arbitrary processing times known to be known polynomially solvable. Problems P2 ‖ C _max and P2 ‖ Σ w _i C _i are NP-hard. For these reasons, we essentially discuss problems in which preemption is possible or in which all jobs have unit processing times. In the first section of this chapter, problems with independent jobs are discussed. In the second section, we permit precedence relations between jobs.

New production technologies like “just-in-time” production lead to special scheduling problems involving due dates d _i . Contrary to classical scheduling problems where the objective function simply involves lateness L _i = C _i − d _i or tardiness T _i = max{0, C _i − d _i } penalties, earliness E _i = max{0, d _i − C _i } is now also of importance. Objective functions such as Σ w _i | L _i | and Σ w _i L _i ² are typical of “just-in-time” situations. Note that L _i = T _i + E _i and L _i ² = T _i ² + E _i ². From the practical and theoretical point of view, situations in which all due dates are equal are of importance. This due date d may be a given parameter of the problem or it may be a variable, i.e. we are interested in an optimal due date d _opt with respect to the objective function. To indicate these special situations we add d or d _opt to the job characteristics of the problem. If the due date is a variable, then we may add due-date assignment costs w _d · d to the objective function.

Batching means that sets of jobs which are processed on the same machine must be grouped into batches. A batch is a set of jobs which must be processed jointly. The finishing time of all jobs in a batch is defined to be equal to the finishing time of the last job in the batch. There is a setup time s for each batch, which is assumed to be the same for all batches. A batching problem is to group the jobs on each machine into batches and to schedule these batches. Depending on the calculation of the length of a batch, two types of batching problems have been considered. For sbatching (p-batching) problems the length is the sum (maximum) of the processing times of the jobs in the batch. Batching problems have been identified by adding the symbol “s-batch” or “p-batch” to the β-field of our classification scheme.

In this chapter we consider scheduling problems in which the set I of all jobs or all operations (in connection with shop problems) is partitioned into disjoint sets I _l,... , I _r called groups, i.e. I = I _l ∪ I ₂ ∪ ... ∪ I _r and I _f ∩ I _g = Ø for f, g ∈ {1,... , r},f ≠ g. Let N _j be the number of jobs in I _j . Furthermore, we have the additional restrictions that for any two jobs (operations) i, j with i ∈ I _f and j ∈ I _g to be processed on the same machine M _k , job (operation) j cannot be started until s _fgk time units after the finishing time of job (operation) i, or job (operation) i cannot be started until s _gfk time units after the finishing time of job (operation) j. In a typical application, the groups correspond to different types of jobs (operations) and s _fgk may be interpreted as a machine dependent changeover time. During the changeover period, the machine cannot process another job. We assume that s _fgk = 0 for all f, g ∈ {1,... ,r}, k ∈ {1,... , m} with f = g,and that the triangle inequality holds:

In a multi-purpose machine (MPM) model there is a set of machines µ _i (µ _ij ) ⊆ {M ₁,... , M _m } associated with a job J _i (operation O _ij ). J _i (O _ij ) has to be processed by one machine in the set µ _i (µ _ij ). Thus, scheduling problems with multi-purpose machines combine assignment and scheduling problems: we have to schedule each job J _i (operation O _ij ) on exactly one machine from the set µ _i (µ _ij ).

Contrary to the scheduling problems discussed thus far in which each job (or task) is processed by at the most one machine (processor) at a time, in a system with multiprocessor tasks (MPT) tasks require one or more processors at a time.