251 pág.

# Pinedo_problemas_deterministicos

Pré-visualização50 páginas

First, it considers adding job j to the schedule while assuming that it does not initiate a new batch, i.e., job j is included in the same batch as job j \u2212 1 and that batch has a processing time pk. This processing time pk already contributes to the makespan of the previous state, which may be either V (j \u2212 1, u, k) or V (j \u2212 1, u\u2212 1, k) dependent upon whether job j is on time or not. If V (j \u2212 1, u, k) \u2264 dj , then job j is on time and (j \u2212 1, u, k) is the previous state; if V (j \u2212 1, u \u2212 1, k) > dj , then job j is late and (j \u2212 1, u \u2212 1, k) is the previous state. Second, it considers adding job j to the schedule assuming that it initiates a new batch. The previous batch ends with job j \u2212 1 and the processing time of the new batch is pk. After adding the contribution from the previous state, the makespan becomes either V (j \u2212 1, u, j\u2212 1)+ pk or V (j\u2212 1, u\u2212 1, j\u2212 1)+ pk dependent upon whether job j is on time or not. If V (j\u22121, u, j\u22121)+pk \u2264 dj , then job j is assumed to be on time and (j \u2212 1, u, j \u2212 1) is the previous state; if V (j \u2212 1, u \u2212 1, j \u2212 1) + pk > dj , then job j is assumed to be tardy and (j \u2212 1, u\u2212 1, j \u2212 1) is the previous state. 4.6 Batch Processing 103 Algorithm 4.6.5 (Minimizing Number of Tardy Jobs \u2013 Batch Size In\ufb01nite) Initial Condition: V (0, 0, k) = { 0, if k = 0, \u221e, otherwise Recursive Relation: V (j, u, k) = min \uf8f1\uf8f4\uf8f4\uf8f4\uf8f4\uf8f2\uf8f4\uf8f4\uf8f4\uf8f4\uf8f3 V (j \u2212 1, u, k), if V (j \u2212 1, u, k) \u2264 dj , V (j \u2212 1, u\u2212 1, k), if V (j \u2212 1, u\u2212 1, k) > dj , V (j \u2212 1, u, j \u2212 1) + pk, if V (j \u2212 1, u, j \u2212 1) + pk \u2264 dj , V (j \u2212 1, u\u2212 1, j \u2212 1) + pk if V (j \u2212 1, u\u2212 1, j \u2212 1) + pk > dj , \u221e, otherwise for j = 1, . . . , n, u = 0, . . . , j, k = j, . . . , n. Optimal Value Function: min { u | V (n, u, n) <\u221e} || Note that the optimal value function is the smallest value of u for which V (n, u, n) <\u221e. This algorithm also operates in O(n3). Other batch scheduling problems with due date related objective functions and unlimited batch sizes tend to be harder. For example, 1 | batch(\u221e) |\u2211Tj is NP-Hard in the ordinary sense and can be solved in pseudopolynomial time. Consider now the class of batch scheduling problems with \ufb01nite and \ufb01xed batch sizes, i.e., the batch size is b and 2 \u2264 b \u2264 n \u2212 1. It is to be expected that scheduling problems with \ufb01nite and \ufb01xed batch sizes are harder than their counterparts with unlimited batch sizes. For starters, the result regarding the optimality of SPT-batch schedules when performance measures are regular (Lemma 4.6.1) does not hold here. Already, the minimization of the makespan is not as trivial as in the case of an unlimited batch size. Consider the problem 1 | batch(b) | Cmax. It is clear that in order to minimize the makespan it su\ufb03ces to determine how the n jobs are combined with one another and assembled into batches; the order in which the batches are processed does not a\ufb00ect the makespan. A schedule that minimizes the makespan consists of N = \ufffd(n/b)\ufffd batches. In the next algorithm J denotes at any point in time the set of jobs that remain to be scheduled. Algorithm 4.6.6 (Minimizing Makespan \u2013 Batch Size Finite) Step 1. (Initialization) Set J = {1, . . . , n} and k = N . 104 4 Advanced Single Machine Models (Deterministic) Step 2. (Batch Assembly) If k > 1, take from Set J the b jobs with the longest processing times and put them in batch k. If k = 1, put all jobs still remaining in set J (i.e., n\u2212 (N \u2212 1)b jobs) in one batch and STOP. Step 3. (Update Counter) Remove the jobs that have been put in batch k from set J ; reduce k by 1 and return to Step 2. || So the algorithm starts with the assembly of the b longest jobs in the \ufb01rst batch; it proceeds with selecting among the remaining jobs the b longest ones and putting them in a second batch, and so on. If n is not a multiple of b, then the last batch (containing the shortest jobs) will not be a full batch. So there exists an optimal schedule with all batches, with the exception of one, being full. This full-batch property applies only to the makespan objective. Other objective functions tend to be signi\ufb01cantly harder than the makespan objective. The problem 1 | batch(b) | \u2211Cj is already not very easy. However, some structural results can be obtained. Assume again that the jobs are ordered such that p1 \u2264 p2 \u2264 · · · \u2264 pn. Two batches are said to be not intertwined if either the longest job in the \ufb01rst batch is smaller than the shortest job in the second batch or if the shortest job in the \ufb01rst batch is longer than the longest job in the second batch. Lemma 4.6.7. There exists an optimal schedule for 1 | batch(b) | \u2211Cj with no two batches intertwined. Proof. The proof is easy and is left as an exercise (see Exercise 4.23). unionsq Note that in an SPT-batch schedule for the case b = \u221e (see Lemma 4.6.1) no two batches are intertwined either. However, it is clear that the property described in Lemma 4.6.7 is weaker than the property described in Lemma 4.6.1 for unlimited batch sizes. Lemma 4.6.1 implies also that in an optimal schedule a batch of jobs with smaller processing times must precede a batch of jobs with longer processing times. If the batch size is \ufb01nite, then this is not necessarily the case. Lemma 4.6.7 may still allow a batch of jobs with longer processing times to precede a batch of jobs with shorter processing times. The batch sequence depends now also on the numbers of jobs in the batches. Let p(Bk) denote the maximum processing time of the jobs in batch k, i.e., p(Bk) is the time required to process batch k. Let |Bk| denote the number of jobs in batch k. The following lemma describes an important property of the optimal batch sequence. Lemma 4.6.8. A batch schedule for 1 | batch(b) |\u2211Cj is optimal if and only if the batches are sequenced in decreasing order of |Bk|/p(Bk). 4.6 Batch Processing 105 Proof. The proof is easy and similar to the proof of optimality of the WSPT rule for the total weighted completion time objective when there are no batches (see Theorem 3.1.1). A batch now corresponds to a job in Theorem 3.1.1. The processing time of a batch corresponds to the processing time of a job and the number of jobs in a batch corresponds to the weight of a job. unionsq Clearly, it may be possible for a batch with a long processing time to precede a batch with a short processing time; the batch with the long processing time must then contain more jobs than the batch with the short processing time. A batch is said to be full if it contains exactly b jobs; otherwise it is non-full. Batch Bk is said to be deferred with respect to batch B\ufffd if p(Bk) < p(B\ufffd) and Bk is sequenced after B\ufffd. Lemma 4.6.9. In any optimal schedule, there is no batch that is deferred with respect to a non-full batch. Proof. The proof is easy and is left as an exercise (see Exercise 4.24). unionsq So this lemma basically says that in an optimal schedule no non-full batch can precede a batch that has a smaller processing time. In order to determine the optimal schedule it su\ufb03ces to consider schedules that satisfy the properties described above: each batch contains jobs with con- secutive indices, batches are ordered in decreasing order of |Bk|/p(Bk), and no batch is deferred with respect to a non-full batch. There exists a rather involved dynamic program for this problem that runs in O(nb(b\u22121)), i.e., polynomial as long as the batch size b is \ufb01xed. It is also possible to design fairly e\ufb00ective heuristics using the theoretical properties shown above. A heuristic must as- semble the jobs in clusters of at most b. It must try to keep the di\ufb00erences in the processing times of the jobs in a batch somewhat small and then order the batches in decreasing order of |Bk|/p(Bk). Example 4.6.10 (Minimizing Total Completion Time - Batch Size Finite) Consider a machine that allows a maximum batch size of b. Assume there are k (k < b) jobs with processing time 1 and b jobs with processing time p (p > 1). If the k jobs with processing time 1 are scheduled \ufb01rst as one batch followed by a second batch containing the b jobs with processing