Pinedo_problemas_deterministicos
251 pág.

Pinedo_problemas_deterministicos


DisciplinaPlanejamento da Producao27 materiais261 seguidores
Pré-visualização50 páginas
h=1,...,F
(
V (1, . . . , 1, h) + s0h
F\u2211
g=1
ng\u2211
j=1
wjg
)
||
In words, this algorithm can be described as follows. The minimization selects
a previous schedule to which job (qh, h) is appended at the beginning. If the
\ufb01rst job of the previous schedule is also from family h, i.e., h\u2032 = h, then this
previous schedule is only delayed by pqh,h. On the other hand, if the \ufb01rst job
of the previous schedule is from family h\u2032, where h\u2032 \ufffd= h, then the delay is
pqh,h + shh\u2032 , because the \ufb01rst job of the previous schedule starts a new batch
requiring a setup between the job from family h and the job from family h\u2032.
It is easy to obtain an upper bound for the makespan of any schedule by
taking the sum of all the processing times plus n times the maximum setup
time. Let U denote this upper bound. The number of states for which the value
function has to be computed recursively is then O(nFF U). The value of each
state can be computed in O(F ) (since the minimum is taken over F values). So
the algorithm operates in O(F 2nF U).
Example 4.5.3 (Dynamic Programming and the Total Weighted
Completion Time)
Consider two families, i.e., F = 2. The sequence dependent setup times
between the families are s12 = s21 = 2 and s01 = s02 = 0. There is one job
in family 1 and two jobs in family 2, i.e., n1 = 1 and n2 = 2. The processing
times are in the table below:
4.5 Job Families with Setup Times 95
jobs (1,1) (1,2) (2,2)
pjg 3 1 1
wjg 27 30 1
Applying the WSPT rule to the two jobs of family 2 indicates that job
(1,2) should appear in the schedule before job (2,2).
Applying the dynamic procedure results in the following computations.
The initial conditions are: V (2, 3, 1) = V (2, 3, 2) = 0. These initial conditions
basically represent empty schedules.
The \ufb01rst recursive relation computes an optimal value function by ap-
pending job (1,1) to the empty schedule and then computes an optimal value
function by appending job (2,2) to the empty schedule.
V (1, 3, 1) = min
(
V (2, 3, 1) + (p11 + s11)w11 \u2212 s11w11,
V (2, 3, 2) + (p11 + s12)w11 \u2212 s12w11
)
= min
(
0 + (3 + 0)27\u2212 0× 27, 0 + (3 + 2)27\u2212 2× 27
)
= 81
and
V (2, 2, 2) = min
(
V (2, 3, 2) + (p22 + s22)w22 \u2212 s22w22,
V (2, 3, 1) + (p22 + s21)w22 \u2212 s21w22
)
= min
(
0 + (1 + 0)1\u2212 0× 1, 0 + (1 + 2)1\u2212 2× 1
)
= 1
The next value functions to be computed are V (1, 2, 1) and V (1, 2, 2).
V (1, 2, 1) = V (2, 2, 2) + (p11 + s12)(w11 + w22)\u2212 s12w11
= 1 + (3 + 2)(27 + 1)\u2212 2× 27 = 87
(Note that it was not necessary here to consider V (2, 2, 1) on the RHS of the
expression above, since state (2, 2, 1) is not a feasible state.) Similarly,
V (1, 2, 2) = V (1, 3, 1) + (p22 + s21)(w11 + w22)\u2212 s21w22
= 81 + (1 + 2)(27 + 1)\u2212 2× 1 = 163
(Again, it is not necessary to consider here V (1, 3, 2) since state (1, 3, 2) is
not feasible.)
96 4 Advanced Single Machine Models (Deterministic)
Proceeding in a similar fashion yields
V (2, 1, 2) = V (2, 2, 2) + (p12)(w12 + w22) = 1 + 1× (30 + 1) = 32.
Finally,
V (1, 1, 1) = V (2, 1, 2) + (p11 + s12)(w11 + w12 + w22)\u2212 s12w11
= 32 + (3 + 2)(27 + 30 + 1)\u2212 2× 27 = 268
and
V (1, 1, 2) = min
(
V (1, 2, 1) + (p12 + s21)(w12 + w22 + w11)\u2212 s21w12,
V (1, 2, 2) + (p12)(w12 + w22 + w11)
)
= min
(
87 + 3× (27 + 30 + 1)\u2212 2× 30, 163 + 1× (27 + 30 + 1)
)
= min(201, 221) = 201
The optimal value function is
min
(
V (1, 1, 1), V (1, 1, 2)
)
= min(268, 201) = 201.
Backtracking yields the optimal schedule (1, 2), (1, 1), (2, 2) with a total
weighted completion time of 201. ||
The next objective to be considered is Lmax, i.e., the problem 1 | fmls, sgh |
Lmax. Let djg denote the due date of job (j, g), j = 1, . . . , ng, g = 1, . . . , F .
Before describing the dynamic programming procedure for this problem it is
again necessary to establish some properties pertaining to optimal schedules.
Again, a schedule can be regarded as a combination of F subsequences that are
intertwined with one another, each subsequence corresponding to one family.
The following lemma focuses on these subsequences.
Lemma 4.5.4. There exists an optimal schedule for 1 | fmls, sgh | Lmax
with the jobs from any given family sequenced according to EDD.
Proof. The proof can be constructed in a manner that is similar to the proof of
Lemma 4.5.1 and is left as an exercise. 	unionsq
In order to formulate a dynamic programming procedure, \ufb01rst assume that
d1g \u2264 d2g \u2264 · · · \u2264 dng,g,
for g = 1, . . . , F . Let V (q1, . . . , qF , h) denote the minimum value of the maxi-
mum lateness for schedules containing jobs (qg, g), . . . , (ng, g) for g = 1, . . . , F
where job (qh, h) is processed \ufb01rst starting at time zero, and the setup for the
4.5 Job Families with Setup Times 97
batch of jobs of family h at the start of the schedule is not included. The fol-
lowing backward dynamic programming procedure can now be applied to this
problem.
Algorithm 4.5.5 (Minimizing the Maximum Lateness)
Initial Condition:
V (n1 + 1, . . . , nF + 1, g) = \u2212\u221e, for g = 1, . . . , F.
Recursive Relation:
V (q1, . . . , qF , h) =
min
h\u2032=1,...,F
(
max
(
V (q\u20321, . . . , q
\u2032
F , h
\u2032) + pqh,h + shh\u2032 , pqh,h \u2212 dqh,h
))
where q\u2032h = qh + 1, q
\u2032
g = qg if g \ufffd= h, and shh\u2032 = 0 if h = h\u2032;
for qg = ng + 1, ng, . . . , 1, g = 1, . . . , F, h = 1, . . . , F .
Optimal Value Function:
min
h=1,...,F
(
V (1, . . . , 1, h) + s0h
)
||
In words, the minimization in the recursive relationship assumes that if job
(qh, h) (with processing time pqh,h) is appended at the beginning of a schedule
that contains jobs (q\u20321, 1), . . . , (q
\u2032
F , F ), then the maximum lateness of these jobs
is increased by pqh,h + shh\u2032 , while the lateness of job (qh, h) itself is pqh,h \u2212
dqh,h. In the recursive relationship the maximum of these latenesses has to be
minimized. The time complexity of this algorithm can be determined in the same
way as the time complexity of the algorithm for the total weighted completion
time; it operates also in O(F 2nFU).
Consider now the problem 1 | fmls, sgh |
\u2211
Uj. Recall that the algorithm that
yields an optimal solution for 1 ||\u2211Uj operates forward in time. This already
may suggest that it probably would not be that easy to \ufb01nd a backward dynamic
programming algorithm for 1 | fmls, sgh |
\u2211
Uj ; this problem requires, indeed,
a forward dynamic programming algorithm.
Before describing the dynamic programming algorithm that solves this prob-
lem it is again necessary to establish some properties of optimal schedules. An
optimal schedule can again be regarded as a combination of F subsequences that
are intertwined, with each subsequence corresponding to one family. A subse-
quence from a family contains jobs that are completed early as well as jobs that
are completed late. The early jobs appear in the subsequence before the late
jobs. The following lemma focuses on the structure of such a subsequence.
Lemma 4.5.6. There exists an optimal schedule for 1 | fmls, sgh |
\u2211
Uj
that has all the on-time jobs from any given family sequenced according to EDD.
In such an optimal schedule the jobs from any given family that are \ufb01nished late
are processed after all on-time jobs from that family have been completed.
98 4 Advanced Single Machine Models (Deterministic)
Proof. The proof is easy and is left as an exercise. 	unionsq
Assume again that the jobs within each family g are indexed so that d1g \u2264
· · · \u2264 dng,g. In order to formulate a dynamic program for 1 | fmls, sgh |
\u2211
Uj
let V (q1, . . . , qF , u, h) denote the minimum makespan for schedules that contain
early jobs from the sets {(1, g), . . . , (qg, g)}, g = 1, . . . , F , with u being the total
number of late jobs from these sets and a family h job being the last job in
the schedule that is completed early. Note that qh \u2265 1. The following forward
dynamic programming algorithm solves the problem.
Algorithm 4.5.7 (Minimizing the Number of Tardy Jobs)
Initial Condition:
V (q1, . . . , qF , u, 0) =
{
0, for u =
\u2211F
g=1 qg,
\u221e, otherwise
for qg = 0, 1, . . . , ng, g = 1, . . . , F, u = 0, 1, . . . ,
\u2211F
g=1 qg.
Recursive Relation: