251 pág.


DisciplinaPlanejamento da Producao27 materiais261 seguidores
Pré-visualização50 páginas
necessarily yield an optimal schedule.
5.26. Consider Pm | intree, prmp | Cmax with the processing time of each job
at level k equal to pk. Show that a preemptive version of the generalized CP
rule minimizes the makespan.
5.27. Consider Q\u221e | prec, prmp | Cmax. There are an unlimited number of
machines that operate at the same speed. There is one machine that is faster.
Give an algorithm that minimizes the makespan and prove its optimality.
5.28. Consider an online version of Pm | rj , prec | Cmax. An online algorithm
for this problem can be described as follows. The jobs are again presented
in a list; whenever a machine is freed, the job that ranks highest among the
remaining jobs which are ready for processing is assigned to that machine (i.e.,
it must be a job that already has been released and of which all predecessors
already have been completed). Show that the bound presented in Theorem 5.6.1
applies to this more general problem as well.
Comments and References
The worst case analysis of the LPT rule for Pm || Cmax is from the classic
paper by Graham (1969). This paper gives one of the \ufb01rst examples of worst
case analyses of heuristics (see also Graham (1966)). It also provides a worst
case analysis of an arbitrary list schedule for Pm || Cmax. A more sophisticated
heuristic for Pm || Cmax, with a tighter worst case bound, is the so-called MUL-
TIFIT heuristic, see Co\ufb00man, Garey and Johnson (1978) and Friesen (1984a).
Lee and Massey (1988) analyze a heuristic that is based on LPT as well as on
MULTIFIT. Hwang, Lee and Chang (2005) perform a worst case analysis of the
LPT rule for Pm | brkdwn | Cmax. For results on heuristics for the more gen-
eral Qm || Cmax, see Friesen and Langston (1983), Friesen (1984b), and Dobson
Comments and References 149
(1984). Davis and Ja\ufb00e (1981) present an algorithm for Rm || Cmax. The CPM
and PERT procedures have been covered in many papers and textbooks, see for
example, French (1982). The CP result in Theorem 5.1.5 is due to Hu (1961).
See Lenstra and Rinnooy Kan (1978) with regard to Pm | pj = 1, prec | Cmax,
Du and Leung (1989) with regard to P2 | tree | Cmax and Du, Leung and Young
(1991) with regard to P2 | chains | Cmax. Chen and Liu (1975) and Kunde (1976)
analyze the worst case behavior of the CP rule for Pm | pj = 1, prec | Cmax. Lin
and Li (2004) and Li (2006) do a complexity analysis of Pm | pj = 1,Mj | Cmax
and Qm | pj = p,Mj | Cmax. Apparently, no worst case analysis has been done
for the LFJ rule.
For Pm | prmp | Cmax, see McNaughton (1959). For Qm | prmp | Cmax, see
Horvath, Lam and Sethi (1977), Gonzalez and Sahni (1978a) and McCormick
and Pinedo (1995).
Conway, Maxwell and Miller (1967) discuss the SPT rule for Pm ||\u2211Cj; they
also give a characterization of the class of optimal schedules. For a discussion
of Qm || \u2211Cj, see Horowitz and Sahni (1976). The worst case bound for the
WSPT rule for Pm ||\u2211wjCj is from Kawaguchi and Kyan (1986). Elmaghraby
and Park (1974) and Sarin, Ahn and Bishop (1988) present branch-and-bound
algorithms for this problem. Eck and Pinedo (1993) present a heuristic for
minimizing the makespan and the total completion time simultaneously. The
optimality of the CP rule for Pm | pj = 1, outtree | \u2211Cj is due to Hu (1961).
For complexity results with regard to Pm | prec | \u2211Cj, see Sethi (1977) and
Du, Leung and Young (1990).
For an analysis of the Qm | prmp |\u2211Cj problem, see Lawler and Labetoulle
(1978), Gonzalez and Sahni (1978a), McCormick and Pinedo (1995), Leung and
Pinedo (2003) and Gonzalez, Leung and Pinedo (2006).
A signi\ufb01cant amount of work has been done on Qm | rj , pj = p, prmp | \u3b3; see
Garey, Johnson, Simons and Tarjan (1981), Federgruen and Groenevelt (1986),
Lawler and Martel (1989), Martel (1982) and Simons (1983).
For results with regard to Qm | prmp | Lmax, see Bruno and Gonzalez (1976)
and Labetoulle, Lawler, Lenstra and Rinnooy Kan (1984). For other due date
related results, see Sahni and Cho (1979b).
Chen and Powell (1999) and Van den Akker, Hoogeveen and Van de Velde
(1999) applied branch-and-bound methods (including column generation) to
Rm ||\u2211wjCj and Rm ||\u2211wjUj.
The worst case analysis of an arbitrary list schedule for Pm || Cmax is re-
garded as one of the basic results in online scheduling. Theorem 5.6.1 is due to
Graham (1966). The analysis of the Round Robin rule and the total completion
time objective is due to Motwani, Phillips and Torng (1994). Research in online
scheduling has focused on other parallel machine scheduling problems as well;
see, for example, Shmoys, Wein and Williamson (1995). For an overview of on-
line scheduling on parallel machines with the makespan objective, see Fleischer
and Wahl (2000). For comprehensive overviews of online scheduling, see Sgall
(1998) and Pruhs, Sgall and Torng (2004).
Chapter 6
Flow Shops and Flexible Flow
Shops (Deterministic)
6.1 Flow Shops with Unlimited Intermediate Storage . . . . 152
6.2 Flow Shops with Limited Intermediate Storage . . . . . . 163
6.3 Flexible Flow Shops with Unlimited Intermediate
Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
6.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
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 \ufb02ow
The storage or bu\ufb00er capacities in between successive machines may some-
times be, for all practical purposes, virtually unlimited. This is often the case
when the products that are being processed are physically small (e.g., printed
circuit boards, integrated circuits), making it relatively easy to store large quan-
tities between machines. When the products are physically large (e.g., television
sets, copiers), then the bu\ufb00er space in between two successive machines may
have a limited capacity, causing blocking. Blocking occurs when the bu\ufb00er is
full and the upstream machine is not allowed to release a job into the bu\ufb00er
after completing its processing. If this is the case, then the job has to remain
at the upstream machine, preventing a job in the queue at that machine from
beginning its processing.
A somewhat more general machine environment consists of a number of
stages in series with a number of machines in parallel at each stage. A job
has to be processed at each stage only on one of the machines. This machine
environment is often referred to as a \ufb02exible \ufb02ow shop, compound \ufb02ow shop,
multi-processor \ufb02ow shop, or hybrid \ufb02ow shop.
Most of the material in this chapter concerns the makespan objective. The
makespan objective is of considerable practical interest as its minimization is
151M.L. Pinedo, Scheduling, DOI: 10.1007/978-0-387-78935-4
c© Springer Science+Business Media, LLC 2008
152 6 Flow Shops and Flexible Flow Shops (Deterministic)
to a certain extent equivalent to the maximization of the utilization of the
machines. The models, however, tend to be of such complexity that makespan
results are already relatively hard to obtain. Total completion time and due
date related objectives tend to be even harder.
6.1 Flow Shops with Unlimited Intermediate Storage
When searching for an optimal schedule for Fm || Cmax the question arises
whether it su\ufb03ces merely to determine a permutation in which the jobs traverse
the entire system. Physically it may be possible for one job to \u201cpass\u201d another
while waiting in queue for a machine that is busy. The machines may not operate
according to the First Come First Served principle and the sequence in which
the jobs go through the machines may change from one machine to another.
Changing the sequence of the jobs waiting in a queue between two machines
may at times result in a smaller makespan. However, it can be shown that there
always exists an optimal schedule without job