251 pág.


DisciplinaPlanejamento da Producao27 materiais261 seguidores
Pré-visualização50 páginas
for each pair of adjacent jobs j
and j + 1 the inequality
dj+1 \u2212 dj \u2264 pj+1
holds and if for j = u \u2212 1 and j = v the inequality does not hold. A cluster of
jobs must therefore be processed without interruptions.
Lemma 4.1.7. In each cluster in a schedule the early jobs precede the
tardy jobs. Moreover, if jobs j and j+1 belong to the same cluster and are both
early, then Ej \u2265 Ej+1. If jobs j and j + 1 are both late then Tj \u2264 Tj+1.
Proof. Assume jobs j and j + 1 belong to the same cluster. Let t denote the
optimal start time of job j. Subtracting t+ pj from both sides of
dj+1 \u2212 dj \u2264 pj+1
4.1 The Total Earliness and Tardiness 75
and rearranging yields
dj+1 \u2212 t\u2212 pj \u2212 pj+1 \u2264 dj \u2212 t\u2212 pj .
This last inequality can be rewritten as
dj \u2212 Cj \u2265 dj+1 \u2212 Cj+1,
which implies the lemma. 	unionsq
The given job sequence 1, . . . , n can be decomposed into a set of m clusters
\u3c31, \u3c32, . . . , \u3c3m with each cluster representing a subsequence. The algorithm that
inserts the idle times starts out with the given sequence 1, . . . , n without idle
times. That is, the completion time of the kth job in the sequence is
Ck =
pj .
Since the completion times in the original schedule are the earliest possible
completion times, the algorithm has to determine how much to increase (or
shift) the completion time of each job. In fact, it is su\ufb03cient to compute the
optimal shift for each cluster since all its jobs are shifted by the same amount.
Consider a cluster \u3c3r that consists of jobs k, k + 1, . . . , ,. Let
\u2206j =
w\u2032l \u2212
w\u2032\u2032l , j = k, . . . , ,.
These numbers can be computed recursively by setting
\u2206k\u22121 = \u2212
w\u2032\u2032l ,
\u2206j = \u2206j\u22121 + w\u2032j + w
j , j = k, . . . , ,.
De\ufb01ne a block as a sequence of clusters that are processed without inter-
ruption. Consider block \u3c3s, \u3c3s+1, . . . , \u3c3m. Such a block may have one or more
clusters preceding it, but no clusters following it. Let jr be the last job in cluster
\u3c3r that is early, i.e., the job with the smallest earliness. Let
E(r) = Ejr = djr \u2212 Cjr .
E(r) = min
(dj \u2212 Cj).
76 4 Advanced Single Machine Models (Deterministic)
\u2206(r) = \u2206jr = max
\u2206j .
If none of the jobs in cluster \u3c3r is early, then E(r) =\u221e and \u2206(r) = \u2212
l=k w
l .
If djr \u2212 Cjr \u2265 1 for the last early job in every cluster \u3c3r, r = s, s + 1, . . . ,m,
then a shift of the entire block by one time unit to the right decreases the total
cost by
The idea behind the algorithm is to \ufb01nd the \ufb01rst block of clusters that
cannot be shifted. If such a block is found, then this block stays in place and
the procedure is repeated for the set of remaining clusters. If no such block is
found, then all remaining clusters are shifted by an amount that is equal to
the smallest E(r); in one of the shifted clusters the last early job becomes an
on-time job. All the completion times are updated and all the non-early jobs
are removed from the list of each cluster. The procedure is then repeated. The
algorithm terminates once a block involving the last cluster cannot be shifted.
The algorithm can be summarized as follows.
Algorithm 4.1.8 (Optimizing the Timings Given a Sequence)
Step 1.
Identify the clusters and compute \u2206(r) for each cluster.
Step 2.
Find the smallest s such that
r=1\u2206(r) \u2264 0.
Fix the current Ck for each job in the \ufb01rst s clusters.
If s = m then STOP, otherwise go to Step 3.
If no such s exists, then go to Step 4.
Step 3.
Remove the \ufb01rst s clusters from the list.
Reindex all remaining clusters and jobs.
Go to Step 2 to consider the set of remaining clusters.
Step 4.
Find min(E(1), . . . , E(m)).
Increase all Ck by min(E(1), . . . , E(m)).
Eliminate all early jobs that are no longer early.
Update E(r) and \u2206(r).
Go to Step 2. ||
Example 4.1.9 (Optimizing the Timings Given a Sequence)
Consider seven jobs. The given sequence is 1, . . . , 7.
4.1 The Total Earliness and Tardiness 77
jobs 1 2 3 4 5 6 7
pj 3 2 7 3 6 2 8
dj 12 4 26 18 16 25 30
w\u2032j 10 20 18 9 10 16 11
w\u2032\u2032j 12 25 38 12 12 18 15
The set of jobs can be decomposed into the three clusters \u3c31, \u3c32, \u3c33, where
\u3c31 = 1, 2, \u3c32 = 3, 4, 5, and \u3c33 = 6, 7. The initial schedule has job completion
3, 5, 12, 15, 21, 23, 31.
The sets of early jobs in clusters \u3c31, \u3c32, and \u3c33 are, respectively, jobs (1),
(3,4), and (6). For each one of these jobs the values of dj \u2212 Cj can be com-
puted. Applying Step 1 of the algorithm results in the table presented be-
clusters 1 2 3
E(r) 9 3 2
\u2206(r) \u221215 15 1
Step 2 of the Algorithm yields s = 1 and \u2206(1) < 0. So cluster \u3c31 is not
shifted and C1 = 3 and C2 = 5. Step 3 eliminates \u3c31. Going back to Step 2
yields \u2206(2) > 0, \u2206(2) + \u2206(3) > 0 and no s exists. Going to Step 4 results
min(E(2), E(3)) = min(3, 2) = 2.
Increase all completion times in the second and third cluster by 2 time units
and eliminate job 6 from the list of early jobs. Update dk \u2212 Ck. The new
values of E(r) and \u2206(r) are presented in the table below.
clusters 2 3
E(r) 1 \u221e
\u2206(r) 15 \u221233
Returning to Step 2 yields \u2206(2) > 0 and \u2206(2) +\u2206(3) < 0. It follows that
s = 3 = m. So the second and third cluster should not be shifted and the
algorithm stops. The optimal completion times are
3, 5, 14, 17, 23, 25, 33. ||
78 4 Advanced Single Machine Models (Deterministic)
As stated earlier, \ufb01nding at the same time an optimal job sequence as well as
the optimal starting times and completion times of the jobs is strongly NP-hard.
A branch-and-bound procedure for this problem is more complicated than
the one for the total weighted tardiness problem described in Section 3.6. The
branching tree can be constructed in a manner that is similar to the one for the
1 || \u2211wjTj problem. However, \ufb01nding good lower bounds for 1 || \u2211w\u2032jEj +\u2211
w\u2032\u2032j Tj is considerably harder. One type of lower bound can be established
by \ufb01rst setting w\u2032j = 0 for all j and then applying the lower bound described
in Section 3.6 to the given instance by taking only the tardiness penalties into
account. This lower bound may not be that good, since it is based on two
It is possible to establish certain dominance conditions. For example, if the
due dates of two adjacent jobs both occur before the starting time of the \ufb01rst
one of the two jobs, then the job with the higher w\u2032\u2032j /pj ratio has to go \ufb01rst.
Similarly, if the due dates of two adjacent jobs both occur after the completion
time of the last one of the two jobs, then the job with the lower w\u2032j/pj ratio has
to go \ufb01rst.
Many heuristic procedures have been developed for this problem. These pro-
cedures are often based on a combination of decomposition and local search.
The problem lends itself well to time-based decomposition procedures, since
it may be possible to tailor the decomposition process to the clusters and the
4.2 Primary and Secondary Objectives
In practice a scheduler is often concerned with more than one objective. For
example, he may want to minimize inventory costs and meet due dates. It would
then be of interest to \ufb01nd, for example, a schedule that minimizes a combination
Cj and Lmax.
Often, more than one schedule minimizes a given objective. A decision-maker
may then wish to consider the set of all schedules that are optimal with respect
to such an objective (say, the primary objective), and then search within this set
of schedules for the schedule that is best with regard to a secondary objective.
If the primary objective is denoted by \u3b31 and the secondary by \u3b32, then such a
problem can be referred to as \u3b1 | \u3b2 | \u3b3(1)1 , \u3b3(2)2 .
Consider the following simple example. The primary objective is the total
completion time
Cj and the secondary objective is the maximum lateness
Lmax, that is, 1 ||
j , L
max. If there are no jobs with identical processing
times, then there is exactly one schedule that minimizes the total completion
time; so there is no freedom remaining to minimize Lmax. If there are jobs with
identical processing times, then there are multiple schedules that minimize the
total completion