 251 pág.

Pinedo_problemas_deterministicos

DisciplinaPlanejamento da Producao27 materiais263 seguidores
Pré-visualização50 páginas
V (q1, . . . , qF , u, h) = min
(
min
h\u2032\u2208G(q1,...,qF ,u,h)
(
V (q\u20321, . . . , q
\u2032
F , u, h
\u2032) + \u3c4
)
,
V (q\u20321, . . . , q
\u2032
F , u\u2212 1, h)
)
,
where q\u2032g = qg for g \ufffd= h, q\u2032h = qh \u2212 1, \u3c4 = sh\u2032h + pqh,h,
sh\u2032h = 0 if h = h\u2032, and where G(q1, . . . , qF , u, h) =
= {h\u2032 | h\u2032 \u2208 {0, 1, . . . , g}, V (q\u20321, . . . , q\u2032g, u, h\u2032) + \u3c4 \u2264 dqh,h};
for qg = 0, 1, . . . , ng, g = 1, . . . , F, and
u = 0, 1, . . . ,
\u2211F
g=1 qg and h = 1, . . . , F.
Optimal Value Function:
min
(
u | min
g=0,1,...,F
(
V (n1, . . . , nF , u, g)
)
<\u221e
)
||
In words, the procedure can be described as follows: the \ufb01rst term in the
minimization of the recursion selects job (qh, h) to be scheduled on time if this
is possible and chooses a batch h\u2032 for the previous on-time job; the second term
selects job qh of batch h to be late.
Note that the optimal value function is equal to the smallest value of u for
which
min
g=0,1,...,F
(
V (n1, . . . , nF , u, g)
)
<\u221e.
In order to determine the computational complexity of the procedure, note
that the number of states that have to be evaluated is again O(nFn F ). Since
4.6 Batch Processing 99
each recursive step requires O(F ) steps to solve, the time complexity of this
algorithm is O(F 2nF+1), which is polynomial for \ufb01xed F .
The more general problem 1 | fmls, sgh |
\u2211
wjUj can be solved in pseu-
dopolynomial time when F is \ufb01xed. This result follows from the fact that Al-
gorithm 4.5.7 can be generalized to minimize the weighted number of late jobs
in O(nFW ) time, where W =
\u2211n
j=1 wj .
The total tardiness objective
\u2211
Tj and the total weighted tardiness objective\u2211
wjTj turn out to be considerably harder than the
\u2211
Uj objective.
4.6 Batch Processing
Consider a machine that can process a number of jobs simultaneously, i.e., a
machine that can process a batch of jobs at the same time. The processing times
of the jobs in a batch may not be all the same and the entire batch is \ufb01nished
only when the last job of the batch has been completed, i.e., the completion
time of the entire batch is determined by the job with the longest processing
time. This type of machine is fairly common in industry. Consider, for example,
the \u201dburn-in\u201d operations in the manufacturing process of circuit boards; these
operations are performed in ovens that can handle many jobs simultaneously.
Let b denote the maximum number of jobs that can be processed in a batch.
Clearly, the case b = 1 refers to the standard scheduling environment considered
in previous sections. It is to be expected that the b = 1 case is easier than the
case b \u2265 2. Another special case that tends to be somewhat easier is the case
b = \u221e (i.e., there is no limit on the batch size). This case is not uncommon
in practice; it occurs frequently in practice when the items to be produced are
relatively small and the equipment is geared for a high volume. In this section
the case b = \u221e (or equivalently, b \u2265 n) is considered \ufb01rst; several objective
functions are discussed. Subsequently, the case 2 \u2264 b \u2264 n \u2212 1 is considered;
several objective functions are discussed.
When b = \u221e the minimization of the makespan is trivial. All jobs are pro-
cessed together and the makespan is the maximum of the n processing times.
However, other objective functions are not that easy. Assume p1 \u2264 p2 \u2264
· · · \u2264 pn. An SPT-batch schedule is de\ufb01ned as a schedule in which adja-
cent jobs in the sequence 1, . . . , n are assembled in batches. For example, a
possible batch schedule for an 8-job problem is a sequence of four batches
({1, 2}, {3, 4, 5}, {6}, {7, 8}). The following result holds for 1 | batch(\u221e) | \u3b3
when the objective function \u3b3 is a regular performance measure.
Lemma 4.6.1. If the objective function \u3b3 is regular and the batch size is
unlimited, then the optimal schedule is an SPT-batch schedule.
Proof. The proof is easy and left as an exercise (see Exercise 4.22). 	unionsq
Consider the model 1 | batch(\u221e) | \u2211wjCj . This problem can be solved
via dynamic programming. Let V (j) denote the minimum total weighted com-
100 4 Advanced Single Machine Models (Deterministic)
pletion time of an SPT-batch schedule that contains jobs j, . . . , n, assuming
that the \ufb01rst batch starts at t = 0. Let V (n + 1) denote the minimum total
weighted completion time of the empty set, which is zero. A backward dynamic
programming procedure can be described as follows.
Algorithm 4.6.2 (Minimizing Total Weighted Completion Time \u2013
Batch Size In\ufb01nite)
Initial Condition:
V (n+ 1) = 0
Recursive Relation:
V (j) = min
k=j+1,...,n+1
(
V (k) + pk\u22121
n\u2211
h=j
wh
)
j = n, . . . , 1.
Optimal Value Function:
V (1) ||
The minimization in the recursive relationship of the dynamic program se-
lects the batch of jobs {j, . . . , k \u2212 1} with processing time pk\u22121 for insertion at
the start of a previously obtained schedule that comprises jobs {k, . . . , n}. It is
clear that this algorithm is O(n2).
Consider now the model 1 | batch(\u221e) | Lmax. This problem also can be solved
via a backward dynamic programming procedure. Assume again that p1 \u2264 p2 \u2264
· · · \u2264 pn. Let V (j) denote now the minimum value of the maximum lateness for
SPT-batch schedules containing jobs j, . . . , n, assuming their processing starts
at time t = 0.
Algorithm 4.6.3 (Minimizing Maximum Lateness \u2013 Batch Size In\ufb01-
nite)
Initial Condition:
V (n+ 1) = \u2212\u221e
Recursive Relation:
V (j) = min
k=j+1,...,n+1
(
max
(
V (k) + pk\u22121, max
h=j,...,k\u22121
(pk\u22121 \u2212 dh)
))
j = n, . . . , 1.
4.6 Batch Processing 101
Optimal Value Function:
V (1) ||
The minimization in the recursive relationship assumes that if a batch of
jobs j, . . . , k \u2212 1 (with processing time pk\u22121) is inserted at the beginning of a
schedule for jobs k, . . . , n, then the maximum lateness of jobs k, . . . , n increases
by pk\u22121, while the maximum lateness among jobs j, . . . , k \u2212 1 is
max
h=j,...,k\u22121
(pk\u22121 \u2212 dh).
This algorithm also operates in O(n2).
Example 4.6.4 (Minimizing Maximum Lateness \u2013 Batch Size
In\ufb01nite)
Consider the following scheduling with \ufb01ve jobs, i.e., n = 5.
jobs 1 2 3 4 5
pj 2 3 8 10 27
dj 10 7 6 16 43
The initial condition is V (6) = \u2212\u221e. The recursive relationships result in
the following:
V (5) = max(V (6) + p5, p5 \u2212 d5) = \u221216.
V (4) = min
k=5,6
(
max(V (k) + pk\u22121, max
h=4,...,k\u22121
(pk\u22121 \u2212 dh))
)
= min
(
max(\u221216 + 10, 10\u2212 16) , max(\u2212\u221e, 11,\u221216)
)
= min(\u22126, 11) = \u22126
V (3) = min
k=4,5,6
(
max(V (k) + pk\u22121, max
h=3,...,k\u22121
(pk\u22121 \u2212 dh))
)
= min
(
max(\u22126 + 8, 8\u2212 6) , max(\u221216 + 10, 10\u2212 6, 10\u2212 16) ,
max(\u2212\u221e, 27\u2212 6, 27\u2212 16, 27\u2212 43)
)
= min(2, 4, 21) = 2
V (2) = min
k=3,...,6
(
max(V (k) + pk\u22121, max
h=2,...,k\u22121
(pk\u22121 \u2212 dh))
)
102 4 Advanced Single Machine Models (Deterministic)
= min
(
max(2 + 3, 3\u2212 7) , max(\u22126 + 8, 8\u2212 7, 8\u2212 6) ,
max(\u221216 + 10, 10\u2212 7, 10\u2212 6, 10\u2212 16),
max(\u2212\u221e, 27\u2212 7, 27\u2212 6, 27\u2212 16, 27\u2212 43)
)
= min(5, 2, 4, 21) = 2
V (1) = min
k=2,...,6
(
max(V (k) + pk\u22121, max
h=1,...,k\u22121
(pk\u22121 \u2212 dh))
)
= min
(
max(4,\u22128) , max(5,\u22127,\u22124) , max(2,\u22122, 1, 2),
max(\u22126, 0, 3, 4,\u22126) , max(\u2212\u221e, 17, 20, 21, 11,\u221216)
)
= min(4, 5, 2, 4, 21) = 2
Backtracking yields the following schedule: The fact that the minimum for
V (1) is reached for k = 4 implies that the \ufb01rst three jobs are put together
in one batch. The minimum for V (4) is reached for k = 5, implying that job
4 is put in a batch by itself. ||
The 1 | batch(\u221e) |\u2211Uj problem is slightly more complicated. In Chapter 3
it was already observed that there is not any backward algorithm for minimizing
the number of late jobs when b = 1. It turns out that no backward algorithm has
been found for the b =\u221e case either. However, the problem can be solved via
a forward dynamic programming algorithm. Let V (j, u, k) denote the minimum
makespan of an SPT-batch schedule for jobs 1, . . . , j, with u being the number
of late jobs among these j jobs and the last batch having a processing time pk
(implying that this last batch will end up containing also jobs j + 1, . . . , k, but
not job k + 1).
The dynamic program operates in a forward manner and distinguishes be-
tween two cases.