251 pág.


DisciplinaPlanejamento da Producao27 materiais261 seguidores
Pré-visualização50 páginas
is smaller than the third in the \ufb01rst expression and the third
term in the last expression is smaller than the second in the \ufb01rst expression.
So, under condition (i) C\u20322j \u2264 C2k.
Under condition (ii) p1j < p2j, p1k < p2k and p1j > p1k. Now the second as
well as the third term in the last expression are smaller than the second term
in the \ufb01rst expression. So, under condition (ii) C\u20322j \u2264 C2k as well.
Condition (iii) can be shown in a similar way as the second condition. Actu-
ally, condition (iii) follows immediately from the reversibility property of \ufb02ow
shops. 	unionsq
These SPT(1)-LPT(2) schedules are by no means the only schedules that are
optimal for F2 || Cmax. The class of optimal schedules appears to be hard to
characterize and data dependent.
Example 6.1.5 (Multiple Optimal Schedules)
Consider a set of jobs with one job that has a very small processing time
on machine 1 and a very large processing time on machine 2, say K, with
K \u2265 \u2211nj=1 p1j . It is clear that under the optimal sequence this job should
go \ufb01rst in the schedule. However, the order of the remaining jobs does not
a\ufb00ect the makespan. ||
Unfortunately, the SPT(1)-LPT(2) schedule structure cannot be generalized
to characterize optimal schedules for \ufb02ow shops with more than two machines.
However, minimizing the makespan in a permutation \ufb02ow shop with an arbi-
trary number of machines, i.e., Fm | prmu | Cmax, can be formulated as a
Mixed Integer Program (MIP).
In order to formulate the problem as a MIP a number of variables have to
be de\ufb01ned: The decision variable xjk equals 1 if job j is the kth job in the
sequence and 0 otherwise. The auxiliary variable Iik denotes the idle time on
machine i between the processing of the jobs in the kth position and (k + 1)th
position and the auxiliary variable Wik denotes the waiting time of the job in
the kth position in between machines i and i+1. Of course, there exists a strong
relationship between the variables Wik and the variables Iik. For example, if
Iik > 0, then Wi\u22121,k+1 has to be zero. Formally, this relationship can be estab-
lished by considering the di\ufb00erence between the time the job in the (k + 1)th
position starts on machine i+ 1 and the time the job in the kth position com-
pletes its processing on machine i. If \u2206ik denotes this di\ufb00erence and if pi(k)
denotes the processing time on machine i of the job in the kth position in the
sequence, then (see Figure 6.4)
\u2206ik = Iik + pi(k+1) +Wi,k+1 =Wik + pi+1(k) + Ii+1,k.
158 6 Flow Shops and Flexible Flow Shops (Deterministic)
pi + 1(k)
Wik > 0 and Ii + 1, k = 0
pi + 1(k \u2014 1) pi + 1(k + 1)
pi(k + 1)
Machine i
Machine i + 1
Iik Wi, k + 1
Fig. 6.4 Constraints in the integer programming formulation
Note that minimizing the makespan is equivalent to minimizing the total idle
time on the last machine, machine m. This idle time is equal to
pi(1) +
Imj ,
which is the idle time that must occur before the job in the \ufb01rst position reaches
the last machine and the sum of the idle times between the jobs on the last
machine. Using the identity
pi(k) =
xjkpij ,
the MIP can now be formulated as follows.
xj1pij +
subject to
xjk = 1 k = 1, . . . , n,
xjk = 1 j = 1, . . . , n,
Iik +
xj,k+1pij +Wi,k+1
6.1 Flow Shops with Unlimited Intermediate Storage 159
\u2212Wik \u2212
xjkpi+1,j \u2212 Ii+1,k = 0 k = 1, . . . , n\u2212 1; i = 1, . . . ,m\u2212 1,
Wi1 = 0 i = 1, . . . ,m\u2212 1,
I1k = 0 k = 1, . . . , n\u2212 1.
The \ufb01rst set of constraints speci\ufb01es that exactly one job has to be assigned to
position k for any k. The second set of constraints speci\ufb01es that job j has to be
assigned to exactly one position. The third set of constraints relate the decision
variables xjk to the physical constraints. These physical constraints enforce the
necessary relationships between the idle time variables and the waiting time
variables. Thus, the problem of minimizing the makespan in an m machine
permutation \ufb02ow shop is formulated as a MIP. The only integer variables are
the binary (0\u22121) decision variables xjk. The idle time and waiting time variables
are nonnegative continuous variables.
Example 6.1.6 (Mixed Integer Programming Formulation)
Consider again the instance in Example 6.1.1. Because the sequence is now
not given, the subscript jk in the table of Example 6.1.1 is replaced by the
subscript j and the headings j1, j2, j3, j4 and j5 are replaced by 1, 2, 3, 4,
and 5, respectively.
jobs 1 2 3 4 5
p1,j 5 5 3 6 3
p2,j 4 4 2 4 4
p3,j 4 4 3 4 1
p4,j 3 6 3 2 5
With these data the objective of the MIP is
5x11 + 5x21 + 3x31 + 6x41 + 3x51 + 4x11 + 4x21 + 2x31 + 4x41 + 4x51+
+4x11 + 4x21 + 3x31 + 4x41 + x51 + I41 + I42 + I43 + I44 =
13x11 + 13x21 + 8x31 + 14x41 + 8x51 + I41 + I42 + I43 + I44
The \ufb01rst and second set of constraints of the program contain 5 constraints
each. The third set contains (5 \u2212 1)(4 \u2212 1) = 12 constraints. For example,
the constraint corresponding to k = 2 and i = 3 is
I32 + 4x13 + 4x23 + 3x33 + 4x43 + x53 +W33
\u2212W32 \u2212 3x12 \u2212 6x22 \u2212 3x32 \u2212 2x42 \u2212 5x52 \u2212 I42 = 0. ||
160 6 Flow Shops and Flexible Flow Shops (Deterministic)
. . .
. . .
. . .
Fig. 6.5 3-PARTITION reduces to F3 || Cmax
The fact that the problem can be formulated as a MIP does not immediately
imply that the problem is NP-hard. It could be that the MIP has a special
structure that allows for a polynomial time algorithm (see, for example, the
integer programming formulation for Rm || \u2211Cj). In this case, however, it
turns out that the problem is hard.
Theorem 6.1.7. F3 || Cmax is strongly NP-hard.
Proof. By reduction from 3-PARTITION. Given integers a1, . . . , a3t, b, under the
usual assumptions, let the number of jobs n equal 4t+ 1 and let
p10 = 0, p20 = b, p30 = 2b,
p1j = 2b, p2j = b, p3j = 2b, j = 1, . . . , t\u2212 1,
p1t = 2b, p2t = b, p3t = 0,
p1,t+j = 0, p2,t+j = aj , p3,t+j = 0, j = 1, . . . , 3t.
Let z = (2t + 1)b. A makespan of value z can be obtained if the \ufb01rst t + 1
jobs are scheduled according to sequence 0, 1, . . . , t. These t+ 1 jobs then form
a framework, leaving t gaps on machine 2. Jobs t + 1, . . . , t + 3t have to be
partitioned into t sets of three jobs each and these t sets have to be scheduled
in between the \ufb01rst t + 1 jobs. A makespan of value z can be obtained if and
only if 3-PARTITION has a solution (see Figure 6.5). 	unionsq
This complexity proof applies to permutation \ufb02ow shops as well as to \ufb02ow
shops that allow sequence changes midstream (as said before, for three machine
\ufb02ow shops it is known that a permutation schedule is optimal in the larger class
of schedules).
Even though Fm | prmu | Cmax is strongly NP-hard it is of interest to study
special cases that have nice structural properties. A number of special cases are
6.1 Flow Shops with Unlimited Intermediate Storage 161
One important special case of Fm | prmu | Cmax is the so-called propor-
tionate permutation \ufb02ow shop. In this \ufb02ow shop the processing times of job j
on each of the m machines are equal to pj , i.e., p1j = p2j = · · · = pmj = pj .
Minimizing the makespan in a proportionate permutation \ufb02ow shop is denoted
by Fm | prmu, pij = pj | Cmax. For a proportionate \ufb02ow shop an SPT-LPT
sequence can be de\ufb01ned as follows. The jobs are partitioned into two sets; the
jobs in one subset go \ufb01rst according to SPT and the remaining jobs follow ac-
cording to LPT. So a sequence j1, . . . , jn is SPT-LPT if and only if there is a
job jk such that
pj1 \u2264 pj2 \u2264 · · · \u2264 pjk
pjk \u2265 pjk+1 \u2265 · · · \u2265 pjn .
From Theorem 6.1.4 it follows that when m = 2 any SPT-LPT sequence must
be optimal. As might be expected, these are not the only sequences that are
optimal. This \ufb02ow shop has a very special structure.
Theorem 6.1.8. For Fm | prmu, pij = pj | Cmax the makespan equals
Cmax =
pj + (m\u2212 1)max(p1, . . . , pn)
and is independent of the schedule.
Proof. The proof is left as an exercise. 	unionsq
It can be shown that permutation schedules are also optimal in