251 pág.

# Pinedo_problemas_deterministicos

Pré-visualização50 páginas

V (q1, . . . , qF , u, h) = min ( min h\u2032\u2208G(q1,...,qF ,u,h) ( V (q\u20321, . . . , q \u2032 F , u, h \u2032) + \u3c4 ) , V (q\u20321, . . . , q \u2032 F , u\u2212 1, h) ) , where q\u2032g = qg for g \ufffd= h, q\u2032h = qh \u2212 1, \u3c4 = sh\u2032h + pqh,h, sh\u2032h = 0 if h = h\u2032, and where G(q1, . . . , qF , u, h) = = {h\u2032 | h\u2032 \u2208 {0, 1, . . . , g}, V (q\u20321, . . . , q\u2032g, u, h\u2032) + \u3c4 \u2264 dqh,h}; for qg = 0, 1, . . . , ng, g = 1, . . . , F, and u = 0, 1, . . . , \u2211F g=1 qg and h = 1, . . . , F. Optimal Value Function: min ( u | min g=0,1,...,F ( V (n1, . . . , nF , u, g) ) <\u221e ) || In words, the procedure can be described as follows: the \ufb01rst term in the minimization of the recursion selects job (qh, h) to be scheduled on time if this is possible and chooses a batch h\u2032 for the previous on-time job; the second term selects job qh of batch h to be late. Note that the optimal value function is equal to the smallest value of u for which min g=0,1,...,F ( V (n1, . . . , nF , u, g) ) <\u221e. In order to determine the computational complexity of the procedure, note that the number of states that have to be evaluated is again O(nFn F ). Since 4.6 Batch Processing 99 each recursive step requires O(F ) steps to solve, the time complexity of this algorithm is O(F 2nF+1), which is polynomial for \ufb01xed F . The more general problem 1 | fmls, sgh | \u2211 wjUj can be solved in pseu- dopolynomial time when F is \ufb01xed. This result follows from the fact that Al- gorithm 4.5.7 can be generalized to minimize the weighted number of late jobs in O(nFW ) time, where W = \u2211n j=1 wj . The total tardiness objective \u2211 Tj and the total weighted tardiness objective\u2211 wjTj turn out to be considerably harder than the \u2211 Uj objective. 4.6 Batch Processing Consider a machine that can process a number of jobs simultaneously, i.e., a machine that can process a batch of jobs at the same time. The processing times of the jobs in a batch may not be all the same and the entire batch is \ufb01nished only when the last job of the batch has been completed, i.e., the completion time of the entire batch is determined by the job with the longest processing time. This type of machine is fairly common in industry. Consider, for example, the \u201dburn-in\u201d operations in the manufacturing process of circuit boards; these operations are performed in ovens that can handle many jobs simultaneously. Let b denote the maximum number of jobs that can be processed in a batch. Clearly, the case b = 1 refers to the standard scheduling environment considered in previous sections. It is to be expected that the b = 1 case is easier than the case b \u2265 2. Another special case that tends to be somewhat easier is the case b = \u221e (i.e., there is no limit on the batch size). This case is not uncommon in practice; it occurs frequently in practice when the items to be produced are relatively small and the equipment is geared for a high volume. In this section the case b = \u221e (or equivalently, b \u2265 n) is considered \ufb01rst; several objective functions are discussed. Subsequently, the case 2 \u2264 b \u2264 n \u2212 1 is considered; several objective functions are discussed. When b = \u221e the minimization of the makespan is trivial. All jobs are pro- cessed together and the makespan is the maximum of the n processing times. However, other objective functions are not that easy. Assume p1 \u2264 p2 \u2264 · · · \u2264 pn. An SPT-batch schedule is de\ufb01ned as a schedule in which adja- cent jobs in the sequence 1, . . . , n are assembled in batches. For example, a possible batch schedule for an 8-job problem is a sequence of four batches ({1, 2}, {3, 4, 5}, {6}, {7, 8}). The following result holds for 1 | batch(\u221e) | \u3b3 when the objective function \u3b3 is a regular performance measure. Lemma 4.6.1. If the objective function \u3b3 is regular and the batch size is unlimited, then the optimal schedule is an SPT-batch schedule. Proof. The proof is easy and left as an exercise (see Exercise 4.22). unionsq Consider the model 1 | batch(\u221e) | \u2211wjCj . This problem can be solved via dynamic programming. Let V (j) denote the minimum total weighted com- 100 4 Advanced Single Machine Models (Deterministic) pletion time of an SPT-batch schedule that contains jobs j, . . . , n, assuming that the \ufb01rst batch starts at t = 0. Let V (n + 1) denote the minimum total weighted completion time of the empty set, which is zero. A backward dynamic programming procedure can be described as follows. Algorithm 4.6.2 (Minimizing Total Weighted Completion Time \u2013 Batch Size In\ufb01nite) Initial Condition: V (n+ 1) = 0 Recursive Relation: V (j) = min k=j+1,...,n+1 ( V (k) + pk\u22121 n\u2211 h=j wh ) j = n, . . . , 1. Optimal Value Function: V (1) || The minimization in the recursive relationship of the dynamic program se- lects the batch of jobs {j, . . . , k \u2212 1} with processing time pk\u22121 for insertion at the start of a previously obtained schedule that comprises jobs {k, . . . , n}. It is clear that this algorithm is O(n2). Consider now the model 1 | batch(\u221e) | Lmax. This problem also can be solved via a backward dynamic programming procedure. Assume again that p1 \u2264 p2 \u2264 · · · \u2264 pn. Let V (j) denote now the minimum value of the maximum lateness for SPT-batch schedules containing jobs j, . . . , n, assuming their processing starts at time t = 0. Algorithm 4.6.3 (Minimizing Maximum Lateness \u2013 Batch Size In\ufb01- nite) Initial Condition: V (n+ 1) = \u2212\u221e Recursive Relation: V (j) = min k=j+1,...,n+1 ( max ( V (k) + pk\u22121, max h=j,...,k\u22121 (pk\u22121 \u2212 dh) )) j = n, . . . , 1. 4.6 Batch Processing 101 Optimal Value Function: V (1) || The minimization in the recursive relationship assumes that if a batch of jobs j, . . . , k \u2212 1 (with processing time pk\u22121) is inserted at the beginning of a schedule for jobs k, . . . , n, then the maximum lateness of jobs k, . . . , n increases by pk\u22121, while the maximum lateness among jobs j, . . . , k \u2212 1 is max h=j,...,k\u22121 (pk\u22121 \u2212 dh). This algorithm also operates in O(n2). Example 4.6.4 (Minimizing Maximum Lateness \u2013 Batch Size In\ufb01nite) Consider the following scheduling with \ufb01ve jobs, i.e., n = 5. jobs 1 2 3 4 5 pj 2 3 8 10 27 dj 10 7 6 16 43 The initial condition is V (6) = \u2212\u221e. The recursive relationships result in the following: V (5) = max(V (6) + p5, p5 \u2212 d5) = \u221216. V (4) = min k=5,6 ( max(V (k) + pk\u22121, max h=4,...,k\u22121 (pk\u22121 \u2212 dh)) ) = min ( max(\u221216 + 10, 10\u2212 16) , max(\u2212\u221e, 11,\u221216) ) = min(\u22126, 11) = \u22126 V (3) = min k=4,5,6 ( max(V (k) + pk\u22121, max h=3,...,k\u22121 (pk\u22121 \u2212 dh)) ) = min ( max(\u22126 + 8, 8\u2212 6) , max(\u221216 + 10, 10\u2212 6, 10\u2212 16) , max(\u2212\u221e, 27\u2212 6, 27\u2212 16, 27\u2212 43) ) = min(2, 4, 21) = 2 V (2) = min k=3,...,6 ( max(V (k) + pk\u22121, max h=2,...,k\u22121 (pk\u22121 \u2212 dh)) ) 102 4 Advanced Single Machine Models (Deterministic) = min ( max(2 + 3, 3\u2212 7) , max(\u22126 + 8, 8\u2212 7, 8\u2212 6) , max(\u221216 + 10, 10\u2212 7, 10\u2212 6, 10\u2212 16), max(\u2212\u221e, 27\u2212 7, 27\u2212 6, 27\u2212 16, 27\u2212 43) ) = min(5, 2, 4, 21) = 2 V (1) = min k=2,...,6 ( max(V (k) + pk\u22121, max h=1,...,k\u22121 (pk\u22121 \u2212 dh)) ) = min ( max(4,\u22128) , max(5,\u22127,\u22124) , max(2,\u22122, 1, 2), max(\u22126, 0, 3, 4,\u22126) , max(\u2212\u221e, 17, 20, 21, 11,\u221216) ) = min(4, 5, 2, 4, 21) = 2 Backtracking yields the following schedule: The fact that the minimum for V (1) is reached for k = 4 implies that the \ufb01rst three jobs are put together in one batch. The minimum for V (4) is reached for k = 5, implying that job 4 is put in a batch by itself. || The 1 | batch(\u221e) |\u2211Uj problem is slightly more complicated. In Chapter 3 it was already observed that there is not any backward algorithm for minimizing the number of late jobs when b = 1. It turns out that no backward algorithm has been found for the b =\u221e case either. However, the problem can be solved via a forward dynamic programming algorithm. Let V (j, u, k) denote the minimum makespan of an SPT-batch schedule for jobs 1, . . . , j, with u being the number of late jobs among these j jobs and the last batch having a processing time pk (implying that this last batch will end up containing also jobs j + 1, . . . , k, but not job k + 1). The dynamic program operates in a forward manner and distinguishes be- tween two cases.