251 pág.

# Pinedo_problemas_deterministicos

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(k) pi + 1(k) Wik > 0 and Ii + 1, k = 0 pi + 1(k \u2014 1) pi + 1(k + 1) pi(k + 1) \ufffdik Wik 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 m\u22121\u2211 i=1 pi(1) + n\u22121\u2211 j=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) = n\u2211 j=1 xjkpij , the MIP can now be formulated as follows. min (m\u22121\u2211 i=1 n\u2211 j=1 xj1pij + n\u22121\u2211 j=1 Imj ) , subject to n\u2211 j=1 xjk = 1 k = 1, . . . , n, n\u2211 k=1 xjk = 1 j = 1, . . . , n, Iik + n\u2211 j=1 xj,k+1pij +Wi,k+1 6.1 Flow Shops with Unlimited Intermediate Storage 159 \u2212Wik \u2212 n\u2211 j=1 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 important. 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 and 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 = n\u2211 j=1 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