Pinedo_problemas_deterministicos
251 pág.

Pinedo_problemas_deterministicos


DisciplinaPlanejamento da Producao27 materiais264 seguidores
Pré-visualização50 páginas
=
\u2211
j\u2264k+\u3b4
pj .
It is clear that for the entire sequence to be optimal the \ufb01rst and third sub-
sets must be optimally sequenced within themselves. This suggests a dynamic
programming procedure that determines an optimal sequence for a larger set of
3.4 The Total Tardiness - Dynamic Programming 53
jobs after having determined optimal sequences for proper subsets of the larger
set. The subsets J used in this recursive procedure are of a very special type.
A subset consists of all the jobs in a set {j, j + 1, . . . , l \u2212 1, l} with processing
times smaller than the processing time pk of job k. Such a subset is denoted
by J(j, l, k). Let V (J(j, l, k), t) denote the total tardiness of this subset under
an optimal sequence, assuming that this subset starts at time t. The dynamic
programming procedure can now be stated as follows.
Algorithm 3.4.4 (Minimizing Total Tardiness)
Initial Conditions
V (\u2205, t) = 0,
V ({j}, t) = max(0, t+ pj \u2212 dj).
Recursive Relation
V (J(j, l, k), t) = min
\u3b4
(
V (J(j, k\u2032 + \u3b4, k\u2032), t) + max(0, Ck\u2032(\u3b4)\u2212 dk\u2032 )
+ V (J(k\u2032 + \u3b4 + 1, l, k\u2032), Ck\u2032 (\u3b4))
)
where k\u2032 is such that
pk\u2032 = max
(
pj\u2032 | j\u2032 \u2208 J(j, l, k)
)
.
Optimal Value Function
V ({1, . . . , n}, 0). ||
The optimal
\u2211
Tj value is given by V ({1, . . . , n}, 0). The worst case compu-
tation time required by this algorithm can be established as follows. There are
at most O(n3) subsets J(j, l, k) and
\u2211
pj points in time t. There are therefore at
most O(n3
\u2211
pj) recursive equations to be solved in the dynamic programming
algorithm. As each recursive equation takes O(n) time, the overall running time
of the algorithm is bounded by O(n4
\u2211
pj), which is clearly polynomial in n.
However, because of the term
\u2211
pj it quali\ufb01es only as a pseudopolynomial time
algorithm.
Example 3.4.5 (Minimizing Total Tardiness)
Consider the following 5 jobs.
jobs 1 2 3 4 5
pj 121 79 147 83 130
dj 260 266 266 336 337
54 3 Single Machine Models (Deterministic)
The job with the largest processing time is job 3. So 0 \u2264 \u3b4 \u2264 2. The recursive
equation yields:
V ({1, 2, . . . , 5}, 0) = min
\uf8f1\uf8f2\uf8f3
V (J(1, 3, 3), 0) + 81 + V (J(4, 5, 3), 347)
V (J(1, 4, 3), 0) + 164 + V (J(5, 5, 3), 430)
V (J(1, 5, 3), 0) + 294 + V (\u2205, 560)
The optimal sequences of the smaller sets can be determined easily. Clearly,
V (J(1, 3, 3), 0) is zero and there are two sequences that yield zero: 1, 2 and
2, 1. The value of
V (J(4, 5, 3), 347) = 94 + 223 = 317
and this is achieved with sequence 4, 5. Also
V (J(1, 4, 3), 0) = 0.
This value is achieved with the sequences 1, 2, 4 and 2, 1, 4. The value of
V (J(5, 5, 3), 430) is equal to 560 minus 337 which is 223. Finally,
V (J(1, 5, 3), 0) = 76.
This value is achieved with sequences 1, 2, 4, 5 and 2, 1, 4, 5.
V ({1, 2, . . . , 5}, 0) = min
\uf8f1\uf8f2\uf8f3
0 + 81 + 317
0 + 164 + 223
76 + 294 + 0
\uf8fc\uf8fd\uf8fe = 370.
Two optimal sequences are 1, 2, 4, 5, 3 and 2, 1, 4, 5, 3. ||
The 1 || \u2211Tj problem can also be solved with a branch-and-bound pro-
cedure. As this branch-and-bound procedure can also be applied to the more
general problem with arbitrary weights, it is presented in Section 3.6.
3.5 The Total Tardiness - An Approximation Scheme
Since 1 || \u2211Tj is NP-hard, neither branch-and-bound nor dynamic program-
ming can yield an optimal solution in polynomial time. It may therefore be of
interest to have an algorithm that yields, in polynomial time, a solution that is
close to optimal.
An approximation scheme A is called fully polynomial if the value of the
objective it achieves, say
\u2211
Tj(A), satis\ufb01es\u2211
Tj(A) \u2264 (1 + 4)
\u2211
Tj(OPT ),
3.5 The Total Tardiness - An Approximation Scheme 55
where
\u2211
Tj(OPT ) is the value of the objective under an optimal schedule.
Moreover, for the approximation scheme to be fully polynomial its worst case
running time has to be bounded by a polynomial of a \ufb01xed degree in n and
in 1/4. The remainder of this section discusses how the dynamic programming
algorithm described in the previous section can be used to construct a Fully
Polynomial Time Approximation Scheme (FPTAS).
It can be shown that a given set of n jobs can only be scheduled with zero
total tardiness if and only if the EDD schedule results in a zero total tardi-
ness. Let
\u2211
Tj(EDD) denote the total tardiness under the EDD sequence and
Tmax(EDD) the maximum tardiness, i.e., max(T1, . . . , Tn), under the EDD se-
quence. Clearly,
Tmax(EDD) \u2264
\u2211
Tj(OPT ) \u2264
\u2211
Tj(EDD) \u2264 nTmax(EDD).
Let V (J, t) denote the minimum total tardiness of the subset of jobs J , which
starts processing at time t. For any given subset J , a time t\u2217 can be computed
such that V (J, t) = 0 for t \u2264 t\u2217, and V (J, t) > 0 for t > t\u2217. Moreover, it can be
shown easily that
V (J, t\u2217 + \u3b4) \u2265 \u3b4,
for \u3b4 \u2265 0. So in executing the pseudopolynomial dynamic programming algo-
rithm described before, one only has to compute V (J, t) for
t\u2217 \u2264 t \u2264 n Tmax(EDD).
Substituting
\u2211
pj in the overall running time of the dynamic programming algo-
rithm by nTmax(EDD) yields a new running time bound of O(n5Tmax(EDD)).
Now replace the given processing times pj by the rescaled processing times
p\u2032j = \ufffdpj/K\ufffd,
where K is a suitable chosen scaling factor. (This implies that p\u2032j is the largest
integer that is smaller than or equal to pj/K.) Replace the due dates dj by new
due dates
d\u2032j = dj/K
(but without rounding). Consider an optimal sequence with respect to the
rescaled processing times and the rescaled due dates and call this sequence S.
This sequence can be obtained within the time bound O(n5Tmax(EDD)/K).
Let
\u2211
T \u2217j (S) denote the total tardiness under sequence S with respect to
the processing times Kp\u2032j and the original due dates and let
\u2211
Tj(S) denote
the total tardiness with respect to the original processing times pj (which may
be slightly larger than Kp\u2032j) and the original due dates. From the fact that
Kp\u2032j \u2264 pj < K(p\u2032j + 1),
56 3 Single Machine Models (Deterministic)
it follows that\u2211
T \u2217j (S) \u2264
\u2211
Tj(OPT ) \u2264
\u2211
Tj(S) <
\u2211
T \u2217j (S) +K
(n(n+ 1)
2
)
.
From this chain of inequalities it follows that\u2211
Tj(S)\u2212
\u2211
Tj(OPT ) < K
(n(n+ 1)
2
)
.
Recall that the goal is for S to satisfy\u2211
Tj(S)\u2212
\u2211
Tj(OPT ) \u2264 4
\u2211
Tj(OPT ).
If K is chosen such that
K =
( 24
n(n+ 1)
)
Tmax(EDD),
then the stronger result\u2211
Tj(S)\u2212
\u2211
Tj(OPT ) \u2264 4 Tmax(EDD)
is obtained. Moreover, for this choice ofK the time bound O(n5Tmax(EDD)/K)
becomes O(n7/4), making the approximation scheme fully polynomial.
This Fully Polynomial Time Approximation Scheme can be summarized as
follows:
Algorithm 3.5.1 (FPTAS for Minimizing Total Tardiness)
Step 1.
Apply EDD and determine Tmax.
If Tmax = 0, then
\u2211
Tj = 0 and EDD is optimal; STOP.
Otherwise set
K =
( 24
n(n+ 1)
)
Tmax(EDD).
Step 2.
Rescale processing times and due dates as follows:
p\u2032j = \ufffd pj/K\ufffd,
d\u2032j = dj/K.
Step 3.
Apply Algorithm 3.4.4 to the rescaled data. ||
The sequence generated by this algorithm, say sequence S, satis\ufb01es\u2211
Tj(S) \u2264 (1 + 4)
\u2211
Tj(OPT ).
3.6 The Total Weighted Tardiness 57
The following example illustrates the approximation scheme.
Example 3.5.2. (FPTAS Minimizing Total Tardiness)
Consider a single machine and 5 jobs.
jobs 1 2 3 4 5
pj 1210 790 1470 830 1300
dj 1996 2000 2660 3360 3370
It can be veri\ufb01ed (via dynamic programming) that the optimal sequence is
1, 2, 4, 5, 3, and that the total tardiness under this optimal sequence is 3700.
Applying EDD yields Tmax(EDD) = 2230. If 4 is chosen 0.02, then K =
2.973. The rescaled data are:
jobs 1 2 3 4 5
pj 406 265 494 279 437
dj 671.38 672.72 894.72 1130.17 1133.54
Solving this instance using the dynamic programming procedure described
in Section 3.4 yields two optimal sequences: 1,2,4,5,3 and 2,1,4,5,3. If se-
quence 2,1,4,5,3 is applied to the original data set, then the total tardiness
is 3704. Clearly,\u2211
Tj(2, 1, 4, 5, 3) \u2264 (1.02)
\u2211
Tj(1, 2, 4, 5, 3). ||
3.6 The Total Weighted Tardiness
The problem 1 ||\u2211wjTj is an important generalization of the 1 ||\u2211Tj prob-
lem discussed in the previous sections. Dozens of researchers have worked on
this problem and have experimented