251 pág.

# Pinedo_problemas_deterministicos

Pré-visualização50 páginas

= (4,8,2,4) and q¯(t) = (3,0,6,6). Rearranging the elements within each vector and putting these in decreasing order results in vectors (8,4,4,2) and (6,6,3,0). It can be veri\ufb01ed easily that p¯(t) \u2265m q¯(t). || Lemma 5.2.6. If p¯(t) >m q¯(t) then LRPT applied to p¯(t) results in a makespan that is larger than or equal to the makespan obtained by applying LRPT to q¯(t). Proof. The proof is by induction on the total amount of remaining processing. In order to show that the lemma holds for p¯(t) and q¯(t), with total remaining processing time \u2211n j=1 pj(t) and \u2211n j=1 qj(t) respectively, assume as induction hypothesis that the lemma holds for all pairs of vectors with total remaining processing less than or equal to \u2211n j=1 pj(t) \u2212 1 and \u2211n j=1 qj(t) \u2212 1 respec- tively. The induction base can be checked easily by considering the two vectors 1, 0, . . . , 0 and 1, 0, . . . , 0. If LRPT is applied for one time unit on p¯(t) and q¯(t), respectively, then the vectors of remaining processing times at time t + 1 are p¯(t + 1) and q¯(t + 1), respectively. Clearly, n\u2211 j=1 p(j)(t+ 1) \u2264 n\u2211 j=1 p(j)(t)\u2212 1 126 5 Parallel Machine Models (Deterministic) and n\u2211 j=1 q(j)(t+ 1) \u2264 n\u2211 j=1 q(j)(t)\u2212 1. It can be shown that if p¯(t) \u2265m q¯(t), then p¯(t + 1) \u2265m q¯(t + 1). So if LRPT results in a larger makespan at time t+ 1 because of the induction hypothesis, it also results in a larger makespan at time t. It is clear that if there are less than m jobs remaining to be processed, the lemma holds. unionsq Theorem 5.2.7. LRPT yields an optimal schedule for Pm | prmp | Cmax in discrete time. Proof. The proof is based on induction as well as on contradiction arguments. The \ufb01rst step of the induction is shown as follows. Suppose not more than m jobs have processing times remaining and that these jobs all have only one unit of processing time left. Then clearly LRPT is optimal. Assume LRPT is optimal for any vector p¯(t) for which n\u2211 j=1 p(j)(t) \u2264 N \u2212 1. Consider now a vector p¯(t) for which n\u2211 j=1 p(j)(t) = N. The induction is based on the total amount of remaining processing, N\u22121, and not on the time t. In order to show that LRPT is optimal for a vector of remaining processing times p¯(t) with a total amount of remaining processing \u2211n j=1 pj(t) = N , assume that LRPT is optimal for all vectors with a smaller total amount of remaining processing. The proof of the induction step, showing that LRPT is optimal for p¯(t), is by contradiction. If LRPT is not optimal, another rule has to be optimal. This other rule does not act according to LRPT at time t, but from time t+ 1 onwards it must act according to LRPT because of the induction hypothesis (LRPT is optimal from t + 1 on as the total amount of processing remaining at time t + 1 is strictly less than N). Call this supposedly optimal rule, which between t and t + 1 does not act according to LRPT, LRPT\u2032. Now applying LRPT at time t on p¯(t) must be compared to applying LRPT\u2032 at time t on the same vector p¯(t). Let p¯(t+1) and p¯\u2032(t+1) denote the vectors of remaining processing times at time t+1 after applying LRPT and LRPT\u2032. It is clear that p¯\u2032(t + 1) \u2265m p¯(t + 1). From Lemma 5.2.6 it follows that the makespan under LRPT\u2032 is larger than the makespan under LRPT. This completes the proof of the induction step and the proof of the theorem. unionsq 5.2 The Makespan with Preemptions 127 0 5 10 2 3 1 2 1 3 3 2 1 t Fig. 5.6 LRPT with three jobs on two machines with preemptions allowed at integer points in time (Example 5.2.8) 0 5 10 2 2, 3 1 1, 2, 3 1, 2, 3 t Fig. 5.7 LRPT with three jobs on two machines with preemptions allowed at any time (Example 5.2.9) Example 5.2.8 (Application of LRPT in Discrete Time) Consider two machines and three jobs, say jobs 1, 2 and 3, with processing times 8, 7 and 6. The schedule under LRPT is depicted in Figure 5.6 and the makespan is 11. || That LRPT is also optimal in continuous time (resulting in an in\ufb01nite num- ber of preemptions) can be argued easily. Multiply all processing times by K, K being a very large integer. The problem intrinsically does not change, as the relative lengths of the processing times remain the same. The optimal policy is, of course, again LRPT. But now there may be many more preemptions (recall preemptions must occur at integral time units). Basically, multiplying all pro- cessing times by K has the e\ufb00ect that the time slots become smaller relative to the processing times and the decision-maker is allowed to preempt after shorter intervals. Letting K go to \u221e shows that LRPT is optimal in continuous time as well. Example 5.2.9 (Application of LRPT in Continuous Time) Consider the same jobs as in the previous example. As preemptions may be done at any point in time, processor sharing takes place, see Figure 5.7. The makespan is now 10.5. || Consider the generalization to uniform machines, that is, m machines in parallel with machine i having speed vi. Without loss of generality it may be assumed that v1 \u2265 v2 \u2265 · · · \u2265 vm. Similar to Lemma 5.2.2 a lower bound can be established for the makespan here as well. 128 5 Parallel Machine Models (Deterministic) Lemma 5.2.10. Under the optimal schedule for Qm | prmp | Cmax Cmax \u2265 max ( p1 v1 , p1 + p2 v1 + v2 , . . . , \u2211m\u22121 j=1 pj\u2211m\u22121 i=1 vi , \u2211n j=1 pj\u2211m i=1 vi ) Proof. The makespan has to be at least as large as the time it takes for the fastest machine to do the longest job. This time represents the \ufb01rst term within the \u201cmax\u201d on the R.H.S. The makespan also has to be at least as large as the time needed for the fastest and second fastest machine to process the longest and second longest job while keeping the two machines occupied exactly the same amount of time. This amount of time represents the second term within the \u201cmax\u201d expression. The remainder of the \ufb01rst m\u22121 terms are determined in the same way. The last term is a bit di\ufb00erent as it is the minimum time needed to process all n jobs on the m machines while keeping all the m machines occupied exactly the same amount of time. unionsq If the largest term in the lower bound is determined by the sum of the processing times of the k longest jobs divided by the sum of the speeds of the k fastest machines, then the n\u2212 k smallest jobs under the optimal schedule do not receive any processing on the k fastest machines; these jobs only receive processing on the m\u2212 k slowest machines. Example 5.2.11 (Minimizing Makespan on Uniform Machines) Consider three machines, 1, 2 and 3, with respective speeds 3, 2 and 1. There are three jobs, 1, 2 and 3, with respective processing times 36, 34 and 12. The optimal schedule assigns the two longest jobs to the two fastest machines. Job 1 is processed for 8 units of time on machine 1 and for 6 units of time on machine 2, while job 2 is processed for 8 units of time on machine 2 and for 6 units of time on machine 1. These two jobs are completed after 14 time units. Job 3 is processed only on machine 3 and is completed at time 12. || A generalization of the LRPT schedule described before is the so-called Longest Remaining Processing Time on the Fastest Machine \ufb01rst (LRPT-FM) rule. This rule assigns, at any point in time, the job with the longest remain- ing processing time to the fastest machine; the job with the second longest remaining processing time to the second fastest machine, and so on. This rule typically requires an in\ufb01nite number of preemptions. If at time t two jobs have the same remaining processing time and this processing time is the longest among the jobs not yet completed by time t, then one of the two jobs has to go on the fastest machine while the other has to go on the second fastest. At time t+ 4, 4 being very small, the remaining processing time of the job on the second fastest machine is longer than the remaining processing time of the job on the fastest machine. So the job on the second fastest machine has to move to the fastest and vice versa. Thus the LRPT-FM rule often results in so-called processor sharing.