251 pág.


DisciplinaPlanejamento da Producao27 materiais263 seguidores
Pré-visualização50 páginas
than its processing time, causing the makespan to be strictly larger than
the lower bound. If job jh appears in the schedule after job jk, then the jobs
following job jk on machine m are not processed one after another without any
idle times in between. After job jh there is an idle time on machine m as the
next job has a processing time that is strictly larger than the processing time
of job jh. 	unionsq
There exists some similarity between this model and the proportionate \ufb02ow
shop model with unlimited intermediate storage. For the case with blocking it
also can be shown that the SPT rule minimizes
Cj .
As with \ufb02ow shops with unlimited intermediate storage, a fair amount of
research has been done in the development of heuristics for the minimization of
the makespan in \ufb02ow shops with limited intermediate storage and blocking. One
popular heuristic for Fm | block | Cmax is the Pro\ufb01le Fitting (PF) heuristic,
which works as follows: one job is selected to go \ufb01rst, possibly according to
some scheme, e.g., the job with the smallest sum of processing times. This
job, say job j1, does not encounter any blocking and proceeds smoothly from
one machine to the next, generating a pro\ufb01le. The pro\ufb01le is determined by its
departure from machine i. If job j1 corresponds to job k, then
Di,j1 =
ph,j1 =
To determine which job should go second, every remaining unscheduled job is
tried out. For each candidate job a computation is carried out to determine the
amount of time machines are idle and the amount of time the job is blocked
at a machine. The departure epochs of a candidate for the second position, say
job j2, can be computed recursively:
D1,j2 = max(D1,j1 + p1,j2 , D2,j1)
Di,j2 = max(Di\u22121,j2 + pi,j2 , Di+1,j1), i = 2, . . . ,m\u2212 1
Dm,j2 = max(Dm\u22121,j2 , Dm,j1) + pm,j2
The time wasted at machine i, that is, the time the machine is either idle or
blocked, is Di,j2 \u2212Di,j1 \u2212pi,j2 . The sum of these idle and blocked times over all
m machines is then computed. The candidate with the smallest total is selected
as the second job.
After selecting the job that \ufb01ts best as the job for second position, the new
pro\ufb01le, i.e., the departure times of this second job from the m machines, is
computed and the procedure repeats itself. From the remaining jobs in the set
of unscheduled jobs the best \ufb01t is again selected and so on.
In this description the goodness of \ufb01t of a particular job was measured by
the total time wasted on all m machines. Each machine was considered equally
170 6 Flow Shops and Flexible Flow Shops (Deterministic)
important. It is intuitive that lost time on a bottleneck machine is worse than
lost time on a machine that does not have much processing to do. When mea-
suring the total amount of lost time, it may be appropriate to multiply each of
these inactive time periods on a given machine by a factor that is proportional
to the degree of congestion at that machine. The higher the degree of congestion
at a particular machine, the larger the weight. One measure for the degree of
congestion of a machine that is easy to calculate is simply the total amount of
processing to be done on all the jobs at the machine in question. Experiments
have shown that such a weighted version of the PF heuristic works quite well.
Example 6.2.5 (Application of the PF Heuristic)
Consider again 5 jobs and 4 machines. The processing times of the \ufb01ve jobs
are in the tables in Examples 6.1.1 and 6.1.6. Assume that there is zero
storage in between the successive machines.
Take as the \ufb01rst job the job with the smallest total processing time, i.e.,
job 3. Apply the unweighted PF heuristic. Each one of the four remaining
jobs has to be tried out. If either job 1 or job 2 would go second, the total
idle time of the four machines would be 11; if job 4 would go second the total
idle time of the four machines would be 15 and if job 5 would be second, the
total idle time would be 3. It is clear that job 5 is the best \ufb01t. Continuing
in this manner the PF heuristic results in the sequence 3, 5, 1, 2, 4 with a
makespan equal to 32. From the fact that this makespan is equal to the
minimum makespan in the case of unlimited intermediate storage, it follows
that sequence 3, 5, 1, 2, 4 is also optimal in the case of zero intermediate
In order to study the e\ufb00ect of the selection of the \ufb01rst job, consider the
application of the PF heuristic after selecting the job with the largest total
processing time as the initial job. So job 2 goes \ufb01rst. Application of the
unweighted PF heuristic leads to the sequence 2, 1, 3, 5, 4 with makespan 35.
This sequence is clearly not optimal. ||
Consider now a \ufb02ow shop with zero intermediate storage that is subject to
di\ufb00erent operational procedures. A job, when it goes through the system, is
not allowed to wait at any machine. That is, whenever it has completed its
processing on one machine the next machine has to be idle, so that the job does
not have to wait. In contrast to the blocking case where jobs are pushed down the
line by machines upstream that have completed their processing, in this case the
jobs are actually pulled down the line by machines that have become idle. This
constraint is referred to as the no-wait constraint and minimizing the makespan
in such a \ufb02ow shop is referred to as the Fm | nwt | Cmax problem. It is easy
to see that F2 | block | Cmax is equivalent to F2 | nwt | Cmax. However, when
there are more than two machines in series the two problems are di\ufb00erent. The
Fm | nwt | Cmax problem, in contrast to the Fm | block | Cmax problem, can
still be formulated as a Travelling Salesman Problem. The intercity distances
6.3 Flexible Flow Shops with Unlimited Intermediate Storage 171
djk = max
( i\u2211
phj \u2212
for j, k = 0, . . . , n. When there are more than two machines in series this Trav-
elling Salesman Problem is known to be strongly NP-hard.
6.3 Flexible Flow Shops with Unlimited Intermediate
The \ufb02exible \ufb02ow shop is a machine environment with c stages in series; at
stage l, l = 1, . . . , c, there are ml identical machines in parallel. There is an
unlimited intermediate storage between any two successive stages. The machine
environment in the \ufb01rst example of Section 1.1 constitutes a \ufb02exible \ufb02ow shop.
Job j, j = 1, . . . , n, has to be processed at each stage on one machine, any one
will do. The processing times of job j at the various stages are p1j , p2j , . . . , pcj.
Minimizing the makespan and total completion time are respectively referred
to as FFc || Cmax and FFc ||
Cj . The parallel machine environment as well
as the \ufb02ow shop with unlimited intermediate storages are special cases of this
machine environment. As this environment is rather complex only the special
case with proportionate processing times, i.e., p1j = p2j = · · · = pcj = pj , is
considered here.
Consider FFc | pij = pj | Cmax. One would expect the LPT heuristic to
perform well in the nonpreemptive case and the LRPT heuristic to perform well
in the preemptive case. Of course, the LPT rule cannot guarantee an optimal
schedule; a single stage (a parallel machine environment) is already NP-hard.
The worst case behaviour of the LPT rule when applied to multiple stages in
series may be worse than when applied to a single stage.
Example 6.3.1 (Minimizing Makespan in a Flexible Flow Shop)
Consider two stages with two machines in parallel at the \ufb01rst stage and a
single machine at the second stage. There are two jobs with p1 = p2 = 100
and a hundred jobs with p3 = p4 = · · · = p102 = 1. It is clear that in order
to minimize the makespan one long job should go at time zero on machine 1
and the 100 short jobs should be processed on machine 2 between time 0 and
time 100. Under this schedule the makespan is 301. Under the LPT schedule
the makespan is 400. ||
In a preemptive setting the LRPT rule is optimal for a single stage. When
there are multiple stages this is not true any more. The LRPT schedule has the
disadvantage that at the \ufb01rst stage