251 pág.

# Pinedo_problemas_deterministicos

Pré-visualização50 páginas

= \u2211 j\u2264k+\u3b4 pj . It is clear that for the entire sequence to be optimal the \ufb01rst and third sub- sets must be optimally sequenced within themselves. This suggests a dynamic programming procedure that determines an optimal sequence for a larger set of 3.4 The Total Tardiness - Dynamic Programming 53 jobs after having determined optimal sequences for proper subsets of the larger set. The subsets J used in this recursive procedure are of a very special type. A subset consists of all the jobs in a set {j, j + 1, . . . , l \u2212 1, l} with processing times smaller than the processing time pk of job k. Such a subset is denoted by J(j, l, k). Let V (J(j, l, k), t) denote the total tardiness of this subset under an optimal sequence, assuming that this subset starts at time t. The dynamic programming procedure can now be stated as follows. Algorithm 3.4.4 (Minimizing Total Tardiness) Initial Conditions V (\u2205, t) = 0, V ({j}, t) = max(0, t+ pj \u2212 dj). Recursive Relation V (J(j, l, k), t) = min \u3b4 ( V (J(j, k\u2032 + \u3b4, k\u2032), t) + max(0, Ck\u2032(\u3b4)\u2212 dk\u2032 ) + V (J(k\u2032 + \u3b4 + 1, l, k\u2032), Ck\u2032 (\u3b4)) ) where k\u2032 is such that pk\u2032 = max ( pj\u2032 | j\u2032 \u2208 J(j, l, k) ) . Optimal Value Function V ({1, . . . , n}, 0). || The optimal \u2211 Tj value is given by V ({1, . . . , n}, 0). The worst case compu- tation time required by this algorithm can be established as follows. There are at most O(n3) subsets J(j, l, k) and \u2211 pj points in time t. There are therefore at most O(n3 \u2211 pj) recursive equations to be solved in the dynamic programming algorithm. As each recursive equation takes O(n) time, the overall running time of the algorithm is bounded by O(n4 \u2211 pj), which is clearly polynomial in n. However, because of the term \u2211 pj it quali\ufb01es only as a pseudopolynomial time algorithm. Example 3.4.5 (Minimizing Total Tardiness) Consider the following 5 jobs. jobs 1 2 3 4 5 pj 121 79 147 83 130 dj 260 266 266 336 337 54 3 Single Machine Models (Deterministic) The job with the largest processing time is job 3. So 0 \u2264 \u3b4 \u2264 2. The recursive equation yields: V ({1, 2, . . . , 5}, 0) = min \uf8f1\uf8f2\uf8f3 V (J(1, 3, 3), 0) + 81 + V (J(4, 5, 3), 347) V (J(1, 4, 3), 0) + 164 + V (J(5, 5, 3), 430) V (J(1, 5, 3), 0) + 294 + V (\u2205, 560) The optimal sequences of the smaller sets can be determined easily. Clearly, V (J(1, 3, 3), 0) is zero and there are two sequences that yield zero: 1, 2 and 2, 1. The value of V (J(4, 5, 3), 347) = 94 + 223 = 317 and this is achieved with sequence 4, 5. Also V (J(1, 4, 3), 0) = 0. This value is achieved with the sequences 1, 2, 4 and 2, 1, 4. The value of V (J(5, 5, 3), 430) is equal to 560 minus 337 which is 223. Finally, V (J(1, 5, 3), 0) = 76. This value is achieved with sequences 1, 2, 4, 5 and 2, 1, 4, 5. V ({1, 2, . . . , 5}, 0) = min \uf8f1\uf8f2\uf8f3 0 + 81 + 317 0 + 164 + 223 76 + 294 + 0 \uf8fc\uf8fd\uf8fe = 370. Two optimal sequences are 1, 2, 4, 5, 3 and 2, 1, 4, 5, 3. || The 1 || \u2211Tj problem can also be solved with a branch-and-bound pro- cedure. As this branch-and-bound procedure can also be applied to the more general problem with arbitrary weights, it is presented in Section 3.6. 3.5 The Total Tardiness - An Approximation Scheme Since 1 || \u2211Tj is NP-hard, neither branch-and-bound nor dynamic program- ming can yield an optimal solution in polynomial time. It may therefore be of interest to have an algorithm that yields, in polynomial time, a solution that is close to optimal. An approximation scheme A is called fully polynomial if the value of the objective it achieves, say \u2211 Tj(A), satis\ufb01es\u2211 Tj(A) \u2264 (1 + 4) \u2211 Tj(OPT ), 3.5 The Total Tardiness - An Approximation Scheme 55 where \u2211 Tj(OPT ) is the value of the objective under an optimal schedule. Moreover, for the approximation scheme to be fully polynomial its worst case running time has to be bounded by a polynomial of a \ufb01xed degree in n and in 1/4. The remainder of this section discusses how the dynamic programming algorithm described in the previous section can be used to construct a Fully Polynomial Time Approximation Scheme (FPTAS). It can be shown that a given set of n jobs can only be scheduled with zero total tardiness if and only if the EDD schedule results in a zero total tardi- ness. Let \u2211 Tj(EDD) denote the total tardiness under the EDD sequence and Tmax(EDD) the maximum tardiness, i.e., max(T1, . . . , Tn), under the EDD se- quence. Clearly, Tmax(EDD) \u2264 \u2211 Tj(OPT ) \u2264 \u2211 Tj(EDD) \u2264 nTmax(EDD). Let V (J, t) denote the minimum total tardiness of the subset of jobs J , which starts processing at time t. For any given subset J , a time t\u2217 can be computed such that V (J, t) = 0 for t \u2264 t\u2217, and V (J, t) > 0 for t > t\u2217. Moreover, it can be shown easily that V (J, t\u2217 + \u3b4) \u2265 \u3b4, for \u3b4 \u2265 0. So in executing the pseudopolynomial dynamic programming algo- rithm described before, one only has to compute V (J, t) for t\u2217 \u2264 t \u2264 n Tmax(EDD). Substituting \u2211 pj in the overall running time of the dynamic programming algo- rithm by nTmax(EDD) yields a new running time bound of O(n5Tmax(EDD)). Now replace the given processing times pj by the rescaled processing times p\u2032j = \ufffdpj/K\ufffd, where K is a suitable chosen scaling factor. (This implies that p\u2032j is the largest integer that is smaller than or equal to pj/K.) Replace the due dates dj by new due dates d\u2032j = dj/K (but without rounding). Consider an optimal sequence with respect to the rescaled processing times and the rescaled due dates and call this sequence S. This sequence can be obtained within the time bound O(n5Tmax(EDD)/K). Let \u2211 T \u2217j (S) denote the total tardiness under sequence S with respect to the processing times Kp\u2032j and the original due dates and let \u2211 Tj(S) denote the total tardiness with respect to the original processing times pj (which may be slightly larger than Kp\u2032j) and the original due dates. From the fact that Kp\u2032j \u2264 pj < K(p\u2032j + 1), 56 3 Single Machine Models (Deterministic) it follows that\u2211 T \u2217j (S) \u2264 \u2211 Tj(OPT ) \u2264 \u2211 Tj(S) < \u2211 T \u2217j (S) +K (n(n+ 1) 2 ) . From this chain of inequalities it follows that\u2211 Tj(S)\u2212 \u2211 Tj(OPT ) < K (n(n+ 1) 2 ) . Recall that the goal is for S to satisfy\u2211 Tj(S)\u2212 \u2211 Tj(OPT ) \u2264 4 \u2211 Tj(OPT ). If K is chosen such that K = ( 24 n(n+ 1) ) Tmax(EDD), then the stronger result\u2211 Tj(S)\u2212 \u2211 Tj(OPT ) \u2264 4 Tmax(EDD) is obtained. Moreover, for this choice ofK the time bound O(n5Tmax(EDD)/K) becomes O(n7/4), making the approximation scheme fully polynomial. This Fully Polynomial Time Approximation Scheme can be summarized as follows: Algorithm 3.5.1 (FPTAS for Minimizing Total Tardiness) Step 1. Apply EDD and determine Tmax. If Tmax = 0, then \u2211 Tj = 0 and EDD is optimal; STOP. Otherwise set K = ( 24 n(n+ 1) ) Tmax(EDD). Step 2. Rescale processing times and due dates as follows: p\u2032j = \ufffd pj/K\ufffd, d\u2032j = dj/K. Step 3. Apply Algorithm 3.4.4 to the rescaled data. || The sequence generated by this algorithm, say sequence S, satis\ufb01es\u2211 Tj(S) \u2264 (1 + 4) \u2211 Tj(OPT ). 3.6 The Total Weighted Tardiness 57 The following example illustrates the approximation scheme. Example 3.5.2. (FPTAS Minimizing Total Tardiness) Consider a single machine and 5 jobs. jobs 1 2 3 4 5 pj 1210 790 1470 830 1300 dj 1996 2000 2660 3360 3370 It can be veri\ufb01ed (via dynamic programming) that the optimal sequence is 1, 2, 4, 5, 3, and that the total tardiness under this optimal sequence is 3700. Applying EDD yields Tmax(EDD) = 2230. If 4 is chosen 0.02, then K = 2.973. The rescaled data are: jobs 1 2 3 4 5 pj 406 265 494 279 437 dj 671.38 672.72 894.72 1130.17 1133.54 Solving this instance using the dynamic programming procedure described in Section 3.4 yields two optimal sequences: 1,2,4,5,3 and 2,1,4,5,3. If se- quence 2,1,4,5,3 is applied to the original data set, then the total tardiness is 3704. Clearly,\u2211 Tj(2, 1, 4, 5, 3) \u2264 (1.02) \u2211 Tj(1, 2, 4, 5, 3). || 3.6 The Total Weighted Tardiness The problem 1 ||\u2211wjTj is an important generalization of the 1 ||\u2211Tj prob- lem discussed in the previous sections. Dozens of researchers have worked on this problem and have experimented