251 pág.


DisciplinaPlanejamento da Producao27 materiais261 seguidores
Pré-visualização50 páginas
Jk\u22121 and k must
contain a k\u2212optimal set. If set Jk contains the entire set Jk\u22121 plus job k then it
must clearly be k\u2212optimal since Jk\u22121 is (k \u2212 1)-optimal. If set Jk\u22121 combined
with job k is not feasible, then the k\u2212optimal set must be a smaller set within
the set that contains Jk\u22121 and k; however, it must contain at least as many
jobs as set Jk\u22121. Set Jk clearly satis\ufb01es this condition. 	unionsq
Example 3.3.3 (Minimizing Number of Tardy Jobs)
Consider the following 5 jobs.
jobs 1 2 3 4 5
pj 7 8 4 6 6
dj 9 17 18 19 21
Jobs 1 and 2 can be positioned \ufb01rst and second in the sequence with both
jobs being completed on time. Putting job 3 into the third position causes
problems. Its completion time would be 19 while its due date is 18. Algo-
rithm 3.3.1 prescribes the deletion of the job with the longest processing time
among the \ufb01rst three jobs. Job 2 is therefore deleted and jobs 1 and 3 remain
in the \ufb01rst two positions. If now job 4 follows job 3, it is completed on time at
50 3 Single Machine Models (Deterministic)
17; however, if job 5 follows job 4, it is completed late. The algorithm then
prescribes to delete the job with the longest processing time among those
already scheduled, which is job 1. So the optimal schedule is 3, 4, 5, 1, 2 with\u2211
Uj = 2. ||
Note that Algorithm 3.3.1 is an algorithm that goes forward in time. For this
problem there is not any algorithm that goes backward in time. Note also that
there may be many optimal schedules; characterizing the class of all optimal
schedules seems to be a very di\ufb03cult problem.
The generalization of this problem with weights, i.e., 1 ||\u2211wjUj is known to
be NP-hard (see Appendix D). The special case with all due dates being equal
is equivalent to the so-called knapsack problem. The due date is equivalent to
the size of the knapsack, the processing times of the jobs are equivalent to the
sizes of the items and the weights are equivalent to the bene\ufb01ts obtained by
putting the items into the knapsack. A popular heuristic for this problem is the
WSPT rule which sequences the jobs in decreasing order of wj/pj . A worst case
analysis shows that this heuristic may perform arbitrarily badly, i.e., that the
ratio \u2211
wjUj(WSPT )\u2211
wjUj(OPT )
may be arbitrarily large.
Example 3.3.4 (The WSPT Rule and a Knapsack)
Consider the following three jobs.
jobs 1 2 3
pj 11 9 90
wj 12 9 89
dj 100 100 100
Scheduling the jobs according to WSPT results in the schedule 1, 2, 3. The
third job is completed late and
wjUj(WSPT ) is 89. Scheduling the jobs
according to 2, 3, 1 results in
wjUj(OPT ) being equal to 12. ||
3.4 The Total Tardiness - Dynamic Programming
The objective
Tj is one that is important in practice as well. Minimizing the
number of tardy jobs,
Uj , in practice cannot be the only objective to measure
how due dates are being met. Some jobs may have to wait for an unacceptably
long time if the number of late jobs is minimized. If instead the sum of the
tardinesses is minimized it is less likely that the wait of any given job will be
unacceptably long.
3.4 The Total Tardiness - Dynamic Programming 51
The model 1 || \u2211Tj has received an enormous amount of attention in the
literature. For many years its computational complexity remained open, until
its NP-hardness was established in 1990. As 1 || \u2211Tj is NP-hard in the ordi-
nary sense it allows for a pseudo-polynomial time algorithm based on dynamic
programming (see Appendix D). The algorithm is based on two preliminary
Lemma 3.4.1. If pj \u2264 pk and dj \u2264 dk, then there exists an optimal
sequence in which job j is scheduled before job k.
Proof. The proof of this result is left as an exercise. 	unionsq
This type of result is useful when an algorithm has to be developed for
a problem that is NP-hard. Such a result, often referred to as a Dominance
Result or Elimination Criterion, often allows one to disregard a fairly large
number of sequences. Such a dominance result may also be thought of as a set
of precedence constraints on the jobs. The more precedence constraints created
through such dominance results, the easier the problem becomes.
In the following lemma the sensitivity of an optimal sequence to the due
dates is considered. Two problem instances are considered, both of which
have n jobs with processing times p1, . . . , pn. The \ufb01rst instance has due dates
d1, . . . , dn. Let C\u2032k be the latest possible completion time of job k in any op-
timal sequence, say S\u2032, for this instance. The second instance has due dates
d1, . . . , dk\u22121,max(dk, C\u2032k), dk+1, . . . , dn. Let S\u2032\u2032 denote the optimal sequence
with respect to this second set of due dates and C\u2032\u2032j the completion of job j
under this second sequence.
Lemma 3.4.2. Any sequence that is optimal for the second instance is also
optimal for the \ufb01rst instance.
Proof. Let V \u2032(S) denote the total tardiness under an arbitrary sequence S with
respect to the \ufb01rst set of due dates and let V \u2032\u2032(S) denote the total tardiness
under sequence S with respect to the second set of due dates. Now
V \u2032(S\u2032) = V \u2032\u2032(S\u2032) +Ak
V \u2032(S\u2032\u2032) = V \u2032\u2032(S\u2032\u2032) +Bk,
where, if C\u2032k \u2264 dk the two sets of due dates are the same and the sequence
that is optimal for the second set is therefore also optimal for the \ufb01rst set. If
C\u2032k \u2265 dk, then
Ak = C\u2032k \u2212 dk
Bk = max(0,min(C\u2032\u2032k , C
k)\u2212 dk)
It is clear that Ak \u2265 Bk. As S\u2032\u2032 is optimal for the second instance V \u2032\u2032(S\u2032) \u2265
V \u2032\u2032(S\u2032\u2032). Therefore V \u2032(S\u2032) \u2265 V \u2032(S\u2032\u2032) which completes the proof. 	unionsq
52 3 Single Machine Models (Deterministic)
In the remainder of this section it is assumed for purposes of exposition
that (without loss of generality) all processing times are di\ufb00erent, if neces-
sary after an in\ufb01nitesimal perturbation. Assume that d1 \u2264 · · · \u2264 dn and
pk = max(p1, . . . , pn). That is, the job with the kth smallest due date has
the longest processing time. From Lemma 3.4.1 it follows that there exists an
optimal sequence in which jobs {1, . . . , k \u2212 1} all appear, in some order, before
job k. Of the remaining n\u2212 k jobs, i.e., jobs {k + 1, . . . , n}, some may appear
before job k and some may appear after job k. The subsequent lemma focuses
on these n\u2212 k jobs.
Lemma 3.4.3. There exists an integer \u3b4, 0 \u2264 \u3b4 \u2264 n\u2212 k, such that there
is an optimal sequence S in which job k is preceded by all jobs j with j \u2264 k+ \u3b4
and followed by all jobs j with j > k + \u3b4.
Proof. Let C\u2032k denote the latest possible completion time of job k in any se-
quence that is optimal with respect to the given due dates d1, . . . , dn. Let S\u2032\u2032 be a
sequence that is optimal with respect to the due dates d1, . . . , dk\u22121,max(C\u2032k, dk),
dk+1, . . . , dn and that satis\ufb01es the condition stated in Lemma 3.4.1. Let C\u2032\u2032k
denote the completion time of job k under this sequence. By Lemma 3.4.2 se-
quence S\u2032\u2032 is also optimal with respect to the original due dates. This implies
that C\u2032\u2032k \u2264 max(C\u2032k, dk). One can assume that job k is not preceded in S\u2032\u2032 by
a job with a due date later than max(C\u2032k, dk) (if this would have been the case
this job would be on time and repositioning this job by inserting it immedi-
ately after job k would not increase the objective function). Also, job k has to
be preceded by all jobs with a due date earlier than max(C\u2032k, dk) (otherwise
Lemma 3.4.1 would be violated). So \u3b4 can be chosen to be the largest integer
such that dk+\u3b4 \u2264 max(C\u2032k, dk). This completes the proof. 	unionsq
In the dynamic programming algorithm a subroutine is required that gener-
ates an optimal schedule for the set of jobs 1, . . . , l starting with the processing
of this set at time t. Let k be the job with the longest processing time among
these l jobs. From Lemma 3.4.3 it follows that for some \u3b4 (0 \u2264 \u3b4 \u2264 l\u2212 k) there
exists an optimal sequence starting at t which may be regarded as a concate-
nation of three subsets of jobs, namely
(i) jobs 1, 2, . . . , k \u2212 1, k + 1, . . . , k + \u3b4 in some order, followed by
(ii) job k, followed by
(iii) jobs k + \u3b4 + 1, k + \u3b4 + 2, . . . , l in some order.
The completion time of job k, Ck(\u3b4), is given by