 251 pág.

Pinedo_problemas_deterministicos

DisciplinaPlanejamento da Producao27 materiais264 seguidores
Pré-visualização50 páginas
First, it considers adding job j to the schedule while assuming
that it does not initiate a new batch, i.e., job j is included in the same batch
as job j \u2212 1 and that batch has a processing time pk. This processing time pk
already contributes to the makespan of the previous state, which may be either
V (j \u2212 1, u, k) or V (j \u2212 1, u\u2212 1, k) dependent upon whether job j is on time or
not. If V (j \u2212 1, u, k) \u2264 dj , then job j is on time and (j \u2212 1, u, k) is the previous
state; if V (j \u2212 1, u \u2212 1, k) > dj , then job j is late and (j \u2212 1, u \u2212 1, k) is the
previous state.
Second, it considers adding job j to the schedule assuming that it initiates a
new batch. The previous batch ends with job j \u2212 1 and the processing time of
the new batch is pk. After adding the contribution from the previous state, the
makespan becomes either V (j \u2212 1, u, j\u2212 1)+ pk or V (j\u2212 1, u\u2212 1, j\u2212 1)+ pk
dependent upon whether job j is on time or not. If V (j\u22121, u, j\u22121)+pk \u2264 dj ,
then job j is assumed to be on time and (j \u2212 1, u, j \u2212 1) is the previous state;
if V (j \u2212 1, u \u2212 1, j \u2212 1) + pk > dj , then job j is assumed to be tardy and
(j \u2212 1, u\u2212 1, j \u2212 1) is the previous state.
4.6 Batch Processing 103
Algorithm 4.6.5 (Minimizing Number of Tardy Jobs \u2013 Batch Size
In\ufb01nite)
Initial Condition:
V (0, 0, k) =
{
0, if k = 0,
\u221e, otherwise
Recursive Relation:
V (j, u, k) = min
\uf8f1\uf8f4\uf8f4\uf8f4\uf8f4\uf8f2\uf8f4\uf8f4\uf8f4\uf8f4\uf8f3
V (j \u2212 1, u, k), if V (j \u2212 1, u, k) \u2264 dj ,
V (j \u2212 1, u\u2212 1, k), if V (j \u2212 1, u\u2212 1, k) > dj ,
V (j \u2212 1, u, j \u2212 1) + pk, if V (j \u2212 1, u, j \u2212 1) + pk \u2264 dj ,
V (j \u2212 1, u\u2212 1, j \u2212 1) + pk if V (j \u2212 1, u\u2212 1, j \u2212 1) + pk > dj ,
\u221e, otherwise
for j = 1, . . . , n, u = 0, . . . , j, k = j, . . . , n.
Optimal Value Function:
min { u | V (n, u, n) <\u221e} ||
Note that the optimal value function is the smallest value of u for which
V (n, u, n) <\u221e. This algorithm also operates in O(n3).
Other batch scheduling problems with due date related objective functions
and unlimited batch sizes tend to be harder. For example, 1 | batch(\u221e) |\u2211Tj
is NP-Hard in the ordinary sense and can be solved in pseudopolynomial time.
Consider now the class of batch scheduling problems with \ufb01nite and \ufb01xed
batch sizes, i.e., the batch size is b and 2 \u2264 b \u2264 n \u2212 1. It is to be expected
that scheduling problems with \ufb01nite and \ufb01xed batch sizes are harder than
their counterparts with unlimited batch sizes. For starters, the result regarding
the optimality of SPT-batch schedules when performance measures are regular
(Lemma 4.6.1) does not hold here.
Already, the minimization of the makespan is not as trivial as in the case
of an unlimited batch size. Consider the problem 1 | batch(b) | Cmax. It is
clear that in order to minimize the makespan it su\ufb03ces to determine how the
n jobs are combined with one another and assembled into batches; the order in
which the batches are processed does not a\ufb00ect the makespan. A schedule that
minimizes the makespan consists of N = \ufffd(n/b)\ufffd batches. In the next algorithm
J denotes at any point in time the set of jobs that remain to be scheduled.
Algorithm 4.6.6 (Minimizing Makespan \u2013 Batch Size Finite)
Step 1. (Initialization)
Set J = {1, . . . , n} and k = N .
104 4 Advanced Single Machine Models (Deterministic)
Step 2. (Batch Assembly)
If k > 1, take from Set J the b jobs with the longest
processing times and put them in batch k.
If k = 1, put all jobs still remaining in set J
(i.e., n\u2212 (N \u2212 1)b jobs) in one batch and STOP.
Step 3. (Update Counter)
Remove the jobs that have been put in batch k from set J ;
reduce k by 1 and return to Step 2. ||
So the algorithm starts with the assembly of the b longest jobs in the \ufb01rst
batch; it proceeds with selecting among the remaining jobs the b longest ones
and putting them in a second batch, and so on. If n is not a multiple of b, then
the last batch (containing the shortest jobs) will not be a full batch. So there
exists an optimal schedule with all batches, with the exception of one, being
full. This full-batch property applies only to the makespan objective.
Other objective functions tend to be signi\ufb01cantly harder than the makespan
objective. The problem 1 | batch(b) | \u2211Cj is already not very easy. However,
some structural results can be obtained. Assume again that the jobs are ordered
such that p1 \u2264 p2 \u2264 · · · \u2264 pn. Two batches are said to be not intertwined if
either the longest job in the \ufb01rst batch is smaller than the shortest job in the
second batch or if the shortest job in the \ufb01rst batch is longer than the longest
job in the second batch.
Lemma 4.6.7. There exists an optimal schedule for 1 | batch(b) | \u2211Cj
with no two batches intertwined.
Proof. The proof is easy and is left as an exercise (see Exercise 4.23). 	unionsq
Note that in an SPT-batch schedule for the case b = \u221e (see Lemma 4.6.1)
no two batches are intertwined either. However, it is clear that the property
described in Lemma 4.6.7 is weaker than the property described in Lemma 4.6.1
for unlimited batch sizes. Lemma 4.6.1 implies also that in an optimal schedule
a batch of jobs with smaller processing times must precede a batch of jobs with
longer processing times. If the batch size is \ufb01nite, then this is not necessarily the
case. Lemma 4.6.7 may still allow a batch of jobs with longer processing times
to precede a batch of jobs with shorter processing times. The batch sequence
depends now also on the numbers of jobs in the batches.
Let p(Bk) denote the maximum processing time of the jobs in batch k, i.e.,
p(Bk) is the time required to process batch k. Let |Bk| denote the number of
jobs in batch k. The following lemma describes an important property of the
optimal batch sequence.
Lemma 4.6.8. A batch schedule for 1 | batch(b) |\u2211Cj is optimal if and
only if the batches are sequenced in decreasing order of |Bk|/p(Bk).
4.6 Batch Processing 105
Proof. The proof is easy and similar to the proof of optimality of the WSPT
rule for the total weighted completion time objective when there are no batches
(see Theorem 3.1.1). A batch now corresponds to a job in Theorem 3.1.1. The
processing time of a batch corresponds to the processing time of a job and the
number of jobs in a batch corresponds to the weight of a job. 	unionsq
Clearly, it may be possible for a batch with a long processing time to precede
a batch with a short processing time; the batch with the long processing time
must then contain more jobs than the batch with the short processing time.
A batch is said to be full if it contains exactly b jobs; otherwise it is non-full.
Batch Bk is said to be deferred with respect to batch B\ufffd if p(Bk) < p(B\ufffd) and
Bk is sequenced after B\ufffd.
Lemma 4.6.9. In any optimal schedule, there is no batch that is deferred
with respect to a non-full batch.
Proof. The proof is easy and is left as an exercise (see Exercise 4.24). 	unionsq
So this lemma basically says that in an optimal schedule no non-full batch
can precede a batch that has a smaller processing time.
In order to determine the optimal schedule it su\ufb03ces to consider schedules
that satisfy the properties described above: each batch contains jobs with con-
secutive indices, batches are ordered in decreasing order of |Bk|/p(Bk), and no
batch is deferred with respect to a non-full batch. There exists a rather involved
dynamic program for this problem that runs in O(nb(b\u22121)), i.e., polynomial as
long as the batch size b is \ufb01xed. It is also possible to design fairly e\ufb00ective
heuristics using the theoretical properties shown above. A heuristic must as-
semble the jobs in clusters of at most b. It must try to keep the di\ufb00erences in
the processing times of the jobs in a batch somewhat small and then order the
batches in decreasing order of |Bk|/p(Bk).
Example 4.6.10 (Minimizing Total Completion Time - Batch Size
Finite)
Consider a machine that allows a maximum batch size of b. Assume there
are k (k < b) jobs with processing time 1 and b jobs with processing time p
(p > 1). If the k jobs with processing time 1 are scheduled \ufb01rst as one batch
followed by a second batch containing the b jobs with processing