251 pág.

# Pinedo_problemas_deterministicos

Pré-visualização50 páginas

h=1,...,F ( V (1, . . . , 1, h) + s0h F\u2211 g=1 ng\u2211 j=1 wjg ) || In words, this algorithm can be described as follows. The minimization selects a previous schedule to which job (qh, h) is appended at the beginning. If the \ufb01rst job of the previous schedule is also from family h, i.e., h\u2032 = h, then this previous schedule is only delayed by pqh,h. On the other hand, if the \ufb01rst job of the previous schedule is from family h\u2032, where h\u2032 \ufffd= h, then the delay is pqh,h + shh\u2032 , because the \ufb01rst job of the previous schedule starts a new batch requiring a setup between the job from family h and the job from family h\u2032. It is easy to obtain an upper bound for the makespan of any schedule by taking the sum of all the processing times plus n times the maximum setup time. Let U denote this upper bound. The number of states for which the value function has to be computed recursively is then O(nFF U). The value of each state can be computed in O(F ) (since the minimum is taken over F values). So the algorithm operates in O(F 2nF U). Example 4.5.3 (Dynamic Programming and the Total Weighted Completion Time) Consider two families, i.e., F = 2. The sequence dependent setup times between the families are s12 = s21 = 2 and s01 = s02 = 0. There is one job in family 1 and two jobs in family 2, i.e., n1 = 1 and n2 = 2. The processing times are in the table below: 4.5 Job Families with Setup Times 95 jobs (1,1) (1,2) (2,2) pjg 3 1 1 wjg 27 30 1 Applying the WSPT rule to the two jobs of family 2 indicates that job (1,2) should appear in the schedule before job (2,2). Applying the dynamic procedure results in the following computations. The initial conditions are: V (2, 3, 1) = V (2, 3, 2) = 0. These initial conditions basically represent empty schedules. The \ufb01rst recursive relation computes an optimal value function by ap- pending job (1,1) to the empty schedule and then computes an optimal value function by appending job (2,2) to the empty schedule. V (1, 3, 1) = min ( V (2, 3, 1) + (p11 + s11)w11 \u2212 s11w11, V (2, 3, 2) + (p11 + s12)w11 \u2212 s12w11 ) = min ( 0 + (3 + 0)27\u2212 0× 27, 0 + (3 + 2)27\u2212 2× 27 ) = 81 and V (2, 2, 2) = min ( V (2, 3, 2) + (p22 + s22)w22 \u2212 s22w22, V (2, 3, 1) + (p22 + s21)w22 \u2212 s21w22 ) = min ( 0 + (1 + 0)1\u2212 0× 1, 0 + (1 + 2)1\u2212 2× 1 ) = 1 The next value functions to be computed are V (1, 2, 1) and V (1, 2, 2). V (1, 2, 1) = V (2, 2, 2) + (p11 + s12)(w11 + w22)\u2212 s12w11 = 1 + (3 + 2)(27 + 1)\u2212 2× 27 = 87 (Note that it was not necessary here to consider V (2, 2, 1) on the RHS of the expression above, since state (2, 2, 1) is not a feasible state.) Similarly, V (1, 2, 2) = V (1, 3, 1) + (p22 + s21)(w11 + w22)\u2212 s21w22 = 81 + (1 + 2)(27 + 1)\u2212 2× 1 = 163 (Again, it is not necessary to consider here V (1, 3, 2) since state (1, 3, 2) is not feasible.) 96 4 Advanced Single Machine Models (Deterministic) Proceeding in a similar fashion yields V (2, 1, 2) = V (2, 2, 2) + (p12)(w12 + w22) = 1 + 1× (30 + 1) = 32. Finally, V (1, 1, 1) = V (2, 1, 2) + (p11 + s12)(w11 + w12 + w22)\u2212 s12w11 = 32 + (3 + 2)(27 + 30 + 1)\u2212 2× 27 = 268 and V (1, 1, 2) = min ( V (1, 2, 1) + (p12 + s21)(w12 + w22 + w11)\u2212 s21w12, V (1, 2, 2) + (p12)(w12 + w22 + w11) ) = min ( 87 + 3× (27 + 30 + 1)\u2212 2× 30, 163 + 1× (27 + 30 + 1) ) = min(201, 221) = 201 The optimal value function is min ( V (1, 1, 1), V (1, 1, 2) ) = min(268, 201) = 201. Backtracking yields the optimal schedule (1, 2), (1, 1), (2, 2) with a total weighted completion time of 201. || The next objective to be considered is Lmax, i.e., the problem 1 | fmls, sgh | Lmax. Let djg denote the due date of job (j, g), j = 1, . . . , ng, g = 1, . . . , F . Before describing the dynamic programming procedure for this problem it is again necessary to establish some properties pertaining to optimal schedules. Again, a schedule can be regarded as a combination of F subsequences that are intertwined with one another, each subsequence corresponding to one family. The following lemma focuses on these subsequences. Lemma 4.5.4. There exists an optimal schedule for 1 | fmls, sgh | Lmax with the jobs from any given family sequenced according to EDD. Proof. The proof can be constructed in a manner that is similar to the proof of Lemma 4.5.1 and is left as an exercise. unionsq In order to formulate a dynamic programming procedure, \ufb01rst assume that d1g \u2264 d2g \u2264 · · · \u2264 dng,g, for g = 1, . . . , F . Let V (q1, . . . , qF , h) denote the minimum value of the maxi- mum lateness for schedules containing jobs (qg, g), . . . , (ng, g) for g = 1, . . . , F where job (qh, h) is processed \ufb01rst starting at time zero, and the setup for the 4.5 Job Families with Setup Times 97 batch of jobs of family h at the start of the schedule is not included. The fol- lowing backward dynamic programming procedure can now be applied to this problem. Algorithm 4.5.5 (Minimizing the Maximum Lateness) Initial Condition: V (n1 + 1, . . . , nF + 1, g) = \u2212\u221e, for g = 1, . . . , F. Recursive Relation: V (q1, . . . , qF , h) = min h\u2032=1,...,F ( max ( V (q\u20321, . . . , q \u2032 F , h \u2032) + pqh,h + shh\u2032 , pqh,h \u2212 dqh,h )) where q\u2032h = qh + 1, q \u2032 g = qg if g \ufffd= h, and shh\u2032 = 0 if h = h\u2032; for qg = ng + 1, ng, . . . , 1, g = 1, . . . , F, h = 1, . . . , F . Optimal Value Function: min h=1,...,F ( V (1, . . . , 1, h) + s0h ) || In words, the minimization in the recursive relationship assumes that if job (qh, h) (with processing time pqh,h) is appended at the beginning of a schedule that contains jobs (q\u20321, 1), . . . , (q \u2032 F , F ), then the maximum lateness of these jobs is increased by pqh,h + shh\u2032 , while the lateness of job (qh, h) itself is pqh,h \u2212 dqh,h. In the recursive relationship the maximum of these latenesses has to be minimized. The time complexity of this algorithm can be determined in the same way as the time complexity of the algorithm for the total weighted completion time; it operates also in O(F 2nFU). Consider now the problem 1 | fmls, sgh | \u2211 Uj. Recall that the algorithm that yields an optimal solution for 1 ||\u2211Uj operates forward in time. This already may suggest that it probably would not be that easy to \ufb01nd a backward dynamic programming algorithm for 1 | fmls, sgh | \u2211 Uj ; this problem requires, indeed, a forward dynamic programming algorithm. Before describing the dynamic programming algorithm that solves this prob- lem it is again necessary to establish some properties of optimal schedules. An optimal schedule can again be regarded as a combination of F subsequences that are intertwined, with each subsequence corresponding to one family. A subse- quence from a family contains jobs that are completed early as well as jobs that are completed late. The early jobs appear in the subsequence before the late jobs. The following lemma focuses on the structure of such a subsequence. Lemma 4.5.6. There exists an optimal schedule for 1 | fmls, sgh | \u2211 Uj that has all the on-time jobs from any given family sequenced according to EDD. In such an optimal schedule the jobs from any given family that are \ufb01nished late are processed after all on-time jobs from that family have been completed. 98 4 Advanced Single Machine Models (Deterministic) Proof. The proof is easy and is left as an exercise. unionsq Assume again that the jobs within each family g are indexed so that d1g \u2264 · · · \u2264 dng,g. In order to formulate a dynamic program for 1 | fmls, sgh | \u2211 Uj let V (q1, . . . , qF , u, h) denote the minimum makespan for schedules that contain early jobs from the sets {(1, g), . . . , (qg, g)}, g = 1, . . . , F , with u being the total number of late jobs from these sets and a family h job being the last job in the schedule that is completed early. Note that qh \u2265 1. The following forward dynamic programming algorithm solves the problem. Algorithm 4.5.7 (Minimizing the Number of Tardy Jobs) Initial Condition: V (q1, . . . , qF , u, 0) = { 0, for u = \u2211F g=1 qg, \u221e, otherwise for qg = 0, 1, . . . , ng, g = 1, . . . , F, u = 0, 1, . . . , \u2211F g=1 qg. Recursive Relation: