Pinedo_problemas_deterministicos
251 pág.

Pinedo_problemas_deterministicos


DisciplinaPlanejamento da Producao27 materiais264 seguidores
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.