251 pág.


DisciplinaPlanejamento da Producao27 materiais261 seguidores
Pré-visualização50 páginas
being subject to deadlines (this prob-
lem is strongly NP-hard). Chen and Bul\ufb01n (1993) present a detailed overview
of the state of the art in multi-objective single machine scheduling. The book by
T\u2019kindt and Billaut (2002, 2006) is entirely focused on multi-objective schedul-
The material in Section 4.4 dealing with the Travelling Salesman Problem
is entirely based on the famous paper by Gilmore and Gomory (1964). For
more results on scheduling with sequence dependent setup times see Bianco,
Ricciardelli, Rinaldi and Sassano (1988), Tang (1990) and Wittrock (1990).
Scheduling with the jobs belonging to a given (\ufb01xed) number of families
has received a fair amount of attention in the literature. At times, these types
of models have also been referred to as batch scheduling models (since the
consecutive processing of a set of jobs from the same family may be regarded as
a batch). Monma and Potts (1989) discuss the complexity of these scheduling
problems. An excellent overview of the literature on this topic is presented in the
paper by Potts and Kovalyov (2000). Brucker (2004) in his book also considers
this class of models and refers to it as s-batching (batching with jobs processed
in series).
When the machine is capable of processing multiple jobs in parallel, the
machine is often referred to as a batching machine. An important paper con-
cerning batch processing and batching machines is the one by Brucker, Gladky,
Hoogeveen, Kovalyov, Potts, Tautenhahn, and van de Velde (1998). Potts and
Kovalyov (2000) provides for this class of models also an excellent survey.
Brucker (2004) considers this class of models as well and refers to them as
p-batching (batching with jobs processed in parallel).
Chapter 5
Parallel Machine Models
5.1 The Makespan without Preemptions . . . . . . . . . . . . . . . 112
5.2 The Makespan with Preemptions . . . . . . . . . . . . . . . . . . 122
5.3 The Total Completion Time without Preemptions . . . 130
5.4 The Total Completion Time with Preemptions . . . . . . 134
5.5 Due Date Related Objectives . . . . . . . . . . . . . . . . . . . . . 136
5.6 Online Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
5.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
A bank of machines in parallel is a setting that is important from both a the-
oretical 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 \ufb02exible \ufb02ow
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.
In this chapter several objectives are considered. The three principal objec-
tives are the minimization of the makespan, the total completion time, and the
maximum lateness. With a single machine the makespan objective is usually
only of interest when there are sequence dependent setup times; otherwise the
makespan is equal to the sum of the processing times and is independent of
the sequence. When dealing with machines in parallel the makespan becomes
an objective of considerable interest. In practice, one often has to deal with
the problem of balancing the load on machines in parallel; by minimizing the
makespan the scheduler ensures a good balance.
One may actually consider the scheduling of parallel machines as a two step
process. First, one has to determine which jobs have to be allocated to which
machines; second, one has to determine the sequence of the jobs allocated to
each machine. With the makespan objective only the allocation process is im-
111M.L. Pinedo, Scheduling, DOI: 10.1007/978-0-387-78935-4
c© Springer Science+Business Media, LLC 2008
112 5 Parallel Machine Models (Deterministic)
With parallel machines, preemptions play a more important role than with
a single machine. With a single machine preemptions usually only play a role
when jobs are released at di\ufb00erent points in time. In contrast, with machines
in parallel, preemptions are important even when all jobs are released at the
same time.
For most models considered in this chapter there are optimal schedules that
are non-delay. However, if there are unrelated machines in parallel and the total
completion time must be minimized without preemptions, then the optimal
schedule may not be non-delay.
Most models considered in this chapter fall in the category of the so-called
o\ufb04ine scheduling problems. In an o\ufb04ine scheduling problem all data (e.g., pro-
cessing times, release dates, due dates) are known in advance and can be taken
into account in the optimization process. In contrast, in an online scheduling
problem, the problem data are not known a priori. The processing time of a
job only becomes known the moment it is completed and a release date only
becomes known the moment a job is released. Clearly, the algorithms for online
scheduling problems tend to be quite di\ufb00erent from the algorithms for o\ufb04ine
scheduling problems. The last section in this chapter focuses on online schedul-
ing of parallel machines.
The processing characteristics and constraints considered in this chapter in-
clude precedence constraints as well as the set functions Mj . Throughout this
chapter it is assumed that p1 \u2265 · · · \u2265 pn.
5.1 The Makespan without Preemptions
First, the problem Pm || Cmax is considered. This problem is of interest because
minimizing the makespan has the e\ufb00ect of balancing the load over the various
machines, which is an important objective in practice.
It is easy to see that P2 || Cmax is NP-hard in the ordinary sense as it is
equivalent to PARTITION (see Appendix D). During the last couple of decades
many heuristics have been developed for Pm || Cmax. One such heuristic is
described below.
The Longest Processing Time \ufb01rst (LPT) rule assigns at t = 0 the m longest
jobs to the m machines. After that, whenever a machine is freed the longest
job among those not yet processed is put on the machine. This heuristic tries
to place the shorter jobs more towards the end of the schedule, where they can
be used for balancing the loads.
In the next theorem an upper bound is presented for
Cmax(LPT )
Cmax(OPT )
where Cmax(LPT ) denotes the makespan of the LPT schedule and Cmax(OPT )
denotes the makespan of the (possibly unknown) optimal schedule. This type
5.1 The Makespan without Preemptions 113
of worst case analysis is of interest as it gives an indication of how well the
heuristic is guaranteed to perform as well as the type of instances for which the
heuristic performs badly.
Theorem 5.1.1. For Pm || Cmax
Cmax(LPT )
Cmax(OPT )
\u2264 4
\u2212 1
Proof. By contradiction. Assume that there exists one or more counterexamples
with the ratio strictly larger than 4/3\u22121/3m. If more than one such counterex-
ample exist, there must exist an example with the smallest number of jobs.
Consider this \u201csmallest\u201d counterexample and assume it has n jobs. This
smallest counterexample has a useful property: under LPT the shortest job is
the last job to start its processing and also the last job to \ufb01nish its process-
ing. That this is true can be seen as follows: \ufb01rst, under LPT by de\ufb01nition
the shortest job is the last to start its processing. Also, if this job is not the
last to complete its processing, the deletion of this smallest job will result in a
counterexample with fewer jobs (the Cmax(LPT ) remains the same while the
Cmax(OPT ) may remain the same or may decrease). So for the smallest coun-
terexample the starting time of the shortest job under LPT is Cmax(LPT )\u2212pn.
Since at this point in time all other machines are still busy it follows that
Cmax(LPT )\u2212 pn \u2264
j=1 pj
The right hand side is an upper bound on the starting time of the shortest job.
This upper bound is achieved when scheduling the \ufb01rst n\u2212 1 jobs according to
LPT results in each machine having exactly