251 pág.

# Pinedo_problemas_deterministicos

Pré-visualização50 páginas

for each pair of adjacent jobs j and j + 1 the inequality dj+1 \u2212 dj \u2264 pj+1 holds and if for j = u \u2212 1 and j = v the inequality does not hold. A cluster of jobs must therefore be processed without interruptions. Lemma 4.1.7. In each cluster in a schedule the early jobs precede the tardy jobs. Moreover, if jobs j and j+1 belong to the same cluster and are both early, then Ej \u2265 Ej+1. If jobs j and j + 1 are both late then Tj \u2264 Tj+1. Proof. Assume jobs j and j + 1 belong to the same cluster. Let t denote the optimal start time of job j. Subtracting t+ pj from both sides of dj+1 \u2212 dj \u2264 pj+1 4.1 The Total Earliness and Tardiness 75 and rearranging yields dj+1 \u2212 t\u2212 pj \u2212 pj+1 \u2264 dj \u2212 t\u2212 pj . This last inequality can be rewritten as dj \u2212 Cj \u2265 dj+1 \u2212 Cj+1, which implies the lemma. unionsq The given job sequence 1, . . . , n can be decomposed into a set of m clusters \u3c31, \u3c32, . . . , \u3c3m with each cluster representing a subsequence. The algorithm that inserts the idle times starts out with the given sequence 1, . . . , n without idle times. That is, the completion time of the kth job in the sequence is Ck = k\u2211 j=1 pj . Since the completion times in the original schedule are the earliest possible completion times, the algorithm has to determine how much to increase (or shift) the completion time of each job. In fact, it is su\ufb03cient to compute the optimal shift for each cluster since all its jobs are shifted by the same amount. Consider a cluster \u3c3r that consists of jobs k, k + 1, . . . , ,. Let \u2206j = j\u2211 l=k w\u2032l \u2212 \ufffd\u2211 l=j+1 w\u2032\u2032l , j = k, . . . , ,. These numbers can be computed recursively by setting \u2206k\u22121 = \u2212 \ufffd\u2211 l=k w\u2032\u2032l , and \u2206j = \u2206j\u22121 + w\u2032j + w \u2032\u2032 j , j = k, . . . , ,. De\ufb01ne a block as a sequence of clusters that are processed without inter- ruption. Consider block \u3c3s, \u3c3s+1, . . . , \u3c3m. Such a block may have one or more clusters preceding it, but no clusters following it. Let jr be the last job in cluster \u3c3r that is early, i.e., the job with the smallest earliness. Let E(r) = Ejr = djr \u2212 Cjr . Clearly E(r) = min k\u2264j\u2264jr (dj \u2212 Cj). 76 4 Advanced Single Machine Models (Deterministic) Let \u2206(r) = \u2206jr = max k\u2264j\u2264jr \u2206j . If none of the jobs in cluster \u3c3r is early, then E(r) =\u221e and \u2206(r) = \u2212 \u2211\ufffd l=k w \u2032\u2032 l . If djr \u2212 Cjr \u2265 1 for the last early job in every cluster \u3c3r, r = s, s + 1, . . . ,m, then a shift of the entire block by one time unit to the right decreases the total cost by m\u2211 r=s \u2206(r). The idea behind the algorithm is to \ufb01nd the \ufb01rst block of clusters that cannot be shifted. If such a block is found, then this block stays in place and the procedure is repeated for the set of remaining clusters. If no such block is found, then all remaining clusters are shifted by an amount that is equal to the smallest E(r); in one of the shifted clusters the last early job becomes an on-time job. All the completion times are updated and all the non-early jobs are removed from the list of each cluster. The procedure is then repeated. The algorithm terminates once a block involving the last cluster cannot be shifted. The algorithm can be summarized as follows. Algorithm 4.1.8 (Optimizing the Timings Given a Sequence) Step 1. Identify the clusters and compute \u2206(r) for each cluster. Step 2. Find the smallest s such that \u2211s r=1\u2206(r) \u2264 0. Fix the current Ck for each job in the \ufb01rst s clusters. If s = m then STOP, otherwise go to Step 3. If no such s exists, then go to Step 4. Step 3. Remove the \ufb01rst s clusters from the list. Reindex all remaining clusters and jobs. Go to Step 2 to consider the set of remaining clusters. Step 4. Find min(E(1), . . . , E(m)). Increase all Ck by min(E(1), . . . , E(m)). Eliminate all early jobs that are no longer early. Update E(r) and \u2206(r). Go to Step 2. || Example 4.1.9 (Optimizing the Timings Given a Sequence) Consider seven jobs. The given sequence is 1, . . . , 7. 4.1 The Total Earliness and Tardiness 77 jobs 1 2 3 4 5 6 7 pj 3 2 7 3 6 2 8 dj 12 4 26 18 16 25 30 w\u2032j 10 20 18 9 10 16 11 w\u2032\u2032j 12 25 38 12 12 18 15 The set of jobs can be decomposed into the three clusters \u3c31, \u3c32, \u3c33, where \u3c31 = 1, 2, \u3c32 = 3, 4, 5, and \u3c33 = 6, 7. The initial schedule has job completion times 3, 5, 12, 15, 21, 23, 31. The sets of early jobs in clusters \u3c31, \u3c32, and \u3c33 are, respectively, jobs (1), (3,4), and (6). For each one of these jobs the values of dj \u2212 Cj can be com- puted. Applying Step 1 of the algorithm results in the table presented be- low. clusters 1 2 3 E(r) 9 3 2 \u2206(r) \u221215 15 1 Step 2 of the Algorithm yields s = 1 and \u2206(1) < 0. So cluster \u3c31 is not shifted and C1 = 3 and C2 = 5. Step 3 eliminates \u3c31. Going back to Step 2 yields \u2206(2) > 0, \u2206(2) + \u2206(3) > 0 and no s exists. Going to Step 4 results in min(E(2), E(3)) = min(3, 2) = 2. Increase all completion times in the second and third cluster by 2 time units and eliminate job 6 from the list of early jobs. Update dk \u2212 Ck. The new values of E(r) and \u2206(r) are presented in the table below. clusters 2 3 E(r) 1 \u221e \u2206(r) 15 \u221233 Returning to Step 2 yields \u2206(2) > 0 and \u2206(2) +\u2206(3) < 0. It follows that s = 3 = m. So the second and third cluster should not be shifted and the algorithm stops. The optimal completion times are 3, 5, 14, 17, 23, 25, 33. || 78 4 Advanced Single Machine Models (Deterministic) As stated earlier, \ufb01nding at the same time an optimal job sequence as well as the optimal starting times and completion times of the jobs is strongly NP-hard. A branch-and-bound procedure for this problem is more complicated than the one for the total weighted tardiness problem described in Section 3.6. The branching tree can be constructed in a manner that is similar to the one for the 1 || \u2211wjTj problem. However, \ufb01nding good lower bounds for 1 || \u2211w\u2032jEj +\u2211 w\u2032\u2032j Tj is considerably harder. One type of lower bound can be established by \ufb01rst setting w\u2032j = 0 for all j and then applying the lower bound described in Section 3.6 to the given instance by taking only the tardiness penalties into account. This lower bound may not be that good, since it is based on two simpli\ufb01cations. It is possible to establish certain dominance conditions. For example, if the due dates of two adjacent jobs both occur before the starting time of the \ufb01rst one of the two jobs, then the job with the higher w\u2032\u2032j /pj ratio has to go \ufb01rst. Similarly, if the due dates of two adjacent jobs both occur after the completion time of the last one of the two jobs, then the job with the lower w\u2032j/pj ratio has to go \ufb01rst. Many heuristic procedures have been developed for this problem. These pro- cedures are often based on a combination of decomposition and local search. The problem lends itself well to time-based decomposition procedures, since it may be possible to tailor the decomposition process to the clusters and the blocks. 4.2 Primary and Secondary Objectives In practice a scheduler is often concerned with more than one objective. For example, he may want to minimize inventory costs and meet due dates. It would then be of interest to \ufb01nd, for example, a schedule that minimizes a combination of \u2211 Cj and Lmax. Often, more than one schedule minimizes a given objective. A decision-maker may then wish to consider the set of all schedules that are optimal with respect to such an objective (say, the primary objective), and then search within this set of schedules for the schedule that is best with regard to a secondary objective. If the primary objective is denoted by \u3b31 and the secondary by \u3b32, then such a problem can be referred to as \u3b1 | \u3b2 | \u3b3(1)1 , \u3b3(2)2 . Consider the following simple example. The primary objective is the total completion time \u2211 Cj and the secondary objective is the maximum lateness Lmax, that is, 1 || \u2211 C (1) j , L (2) max. If there are no jobs with identical processing times, then there is exactly one schedule that minimizes the total completion time; so there is no freedom remaining to minimize Lmax. If there are jobs with identical processing times, then there are multiple schedules that minimize the total completion