Pinedo_problemas_deterministicos
251 pág.

Pinedo_problemas_deterministicos


DisciplinaPlanejamento da Producao27 materiais261 seguidores
Pré-visualização50 páginas
not increase the value of Lmax. The branching rule is thus
fairly easy.
There are several ways in which bounds for nodes can be obtained. An easy
lower bound for a node at level k \u2212 1 can be established by scheduling the
remaining jobs J according to the preemptive EDD rule. The preemptive EDD
rule is known to be optimal for 1 | rj , prmp | Lmax (see Exercise 3.24) and
46 3 Single Machine Models (Deterministic)
Lower
bound = 5
Lower
bound = 6
Lower
bound = 7 Level 1
Level 0
Level 2
Level 3Value of objectivefunction is 5
1, 2, *, * 1, 3, *, *
1, *, *, * 2, *, *, * 3, *, *, *
*, *, *, *
4, *, *, *
1, 3, 4, 2
Fig. 3.5 Branch-and-bound procedure for Example 3.2.5
thus provides a lower bound for the problem at hand. If a preemptive EDD rule
results in a nonpreemptive schedule, then all nodes with a higher lower bound
may be disregarded.
Example 3.2.5 (Branch-and-Bound for Minimizing Maximum
Lateness)
Consider the following 4 jobs.
jobs 1 2 3 4
pj 4 2 6 5
rj 0 1 3 5
dj 8 12 11 10
At level 1 of the search tree there are four nodes: (1, \u2217, \u2217, \u2217), (2, \u2217, \u2217, \u2217),
(3, \u2217, \u2217, \u2217) and (4, \u2217, \u2217, \u2217). It is easy to see that nodes (3, \u2217, \u2217, \u2217) and (4, \u2217, \u2217, \u2217)
may be disregarded immediately. Job 3 is released at time 3; if job 2 would
start its processing at time 1, job 3 still can start at time 3. Job 4 is released
at time 5; if job 1 would start its processing at time 0, job 4 still can start
at time 5 (see Figure 3.5).
3.3 The Number of Tardy Jobs 47
Computing a lower bound for node (1, \u2217, \u2217, \u2217) according to the preemptive
EDD rule results in a schedule where job 3 is processed during the time
interval [4,5], job 4 during the time interval [5,10], job 3 (again) during
interval [10,15] and job 2 during interval [15,17]. The Lmax of this schedule,
which provides a lower bound for node (1, \u2217, \u2217, \u2217), is 5. In a similar way a
lower bound can be obtained for node (2, \u2217, \u2217, \u2217). The value of this lower
bound is 7.
Consider node (1, 2, \u2217, \u2217) at level 2. The lower bound for this node is 6
and is determined by the (nonpreemptive) schedule 1, 2, 4, 3. Proceed with
node (1, 3, \u2217, \u2217) at level 2. The lower bound is 5 and determined by the
(nonpreemptive) schedule 1,3,4,2. From the fact that the lower bound for
node (1, \u2217, \u2217, \u2217) is 5 and the lower bound for node (2, \u2217, \u2217, \u2217) is larger than 5
it follows that schedule 1, 3, 4, 2 has to be optimal. ||
The problem 1 | rj , prec | Lmax can be handled in a similar way. This prob-
lem, from an enumeration point of view, is easier than the problem without
precedence constraints, since the precedence constraints allow certain schedules
to be ruled out immediately.
3.3 The Number of Tardy Jobs
Another due date related objective is
\u2211
Uj. This objective may at \ufb01rst appear
somewhat arti\ufb01cial and of no practical interest. However, in the real world it is a
performance measure that is often monitored and according to which managers
are being measured. It is equivalent to the percentage of on time shipments.
An optimal schedule for 1 || \u2211Uj takes the form of one set of jobs that
will meet their due dates and that are scheduled \ufb01rst followed by the set of
remaining jobs that will not meet their due dates and that are scheduled last.
It follows from the results in the previous section that the \ufb01rst set of jobs have
to be scheduled according to EDD in order to make sure that Lmax is negative;
the order in which the second set of jobs is scheduled is immaterial.
The problem 1 || \u2211Uj can be solved easily using a forward algorithm. Re-
order the jobs in such a way that d1 \u2264 d2 \u2264 · · · \u2264 dn. The algorithm goes
through n iterations. In iteration k of the algorithm jobs 1, 2, . . . , k are taken
into consideration. Of these k jobs, the subset J refers to jobs that, in an opti-
mal schedule, may be completed before their due dates and the subset Jd refers
to jobs that already have been discarded and will not meet their due dates in
the optimal schedule. In iteration k the set Jc refers to jobs k+1, k+2, . . . , n.
Algorithm 3.3.1 (Minimizing Number of Tardy Jobs)
Step 1.
Set J = \u2205, Jc = {1, . . . , n}, and Jd = \u2205.
Set the counter k = 1.
48 3 Single Machine Models (Deterministic)
Step 2.
Add job k to J .
Delete job k from Jc.
Go to Step 3.
Step 3.
If \u2211
j\u2208J
pj \u2264 dk,
go to Step 4.
Otherwise, let , denote the job that satis\ufb01es
p\ufffd = max
j\u2208J
(pj).
Delete job , from J .
Add job , to Jd.
Step 4.
Set Jk = J .
If k = n STOP,
otherwise set k = k + 1 and go to Step 2. ||
In words the algorithm can be described as follows. Jobs are added to the
set of on-time jobs in increasing order of their due dates. If including job k to
the set of scheduled jobs implies that job k would be completed late, then the
scheduled job with the longest processing time, say job ,, is marked late and
discarded. Since the algorithm basically orders the jobs according to their due
dates, the worst case computation time is that of a simple sort, i.e., O(n log(n)).
Note that the algorithm creates in its last step n job sets J1, . . . , Jn. Set Jk
is a subset of jobs {1, . . . , k}, consisting of those jobs that are candidates for
meeting their due dates in the \ufb01nal optimal schedule. Set Jn consists of all jobs
that meet their due dates in the optimal schedule generated.
Theorem 3.3.2. Algorithm 3.3.1 yields an optimal schedule for 1 ||\u2211Uj.
Proof. The proof uses the following notation and terminology. A job set J is
called feasible if the jobs, scheduled according to EDD, all meet their due dates.
A job set J is called l\u2212optimal if it is a feasible subset of jobs 1, . . . , l and if it
has, among all feasible subsets of jobs 1, . . . , l, the maximum number of jobs.
The proof consists of three steps. The \ufb01rst step of the proof shows that the
job sets J1, . . . , Jn created in Step 4 of the algorithm are all feasible. This can
be shown by induction (see Exercise 3.27).
The second step of the proof shows that for l > k, there exists an l\u2212optimal
set that consists of a subset of jobs Jk and a subset of jobs k + 1, . . . , l. To
show this, assume it is true for k\u2212 1, i.e., there exists an l\u2212optimal set J \u2032 that
consists of a subset of jobs from set Jk\u22121 and a subset of jobs k, k + 1, . . . , l.
3.3 The Number of Tardy Jobs 49
It can be shown that an l\u2212optimal set J \u2032\u2032 can be created from Jk and jobs
k + 1, . . . , l by considering three cases:
Case 1: Set Jk consists of set Jk\u22121 plus job k. In order to create set J \u2032\u2032, just
take set J \u2032.
Case 2: Set Jk consists of set Jk\u22121 plus job k minus some job q which is not
an element of set J \u2032. Again, in order to create set J \u2032\u2032, just take set J \u2032.
Case 3: Set Jk is equal to set Jk\u22121 plus job k minus some job q which is
an element of set J \u2032. The argument is now a little bit more complicated. Since
Jk\u22121 plus k is not a feasible set, there must exist in the set that comprises Jk\u22121
and k a job r that is not an element of J \u2032. Take any such r. Now, to create set
J \u2032\u2032, take set J \u2032, include job r and delete job q. Clearly, set J \u2032\u2032 is a subset of
set Jk and jobs k + 1, . . . , n. Since the number of jobs in J \u2032\u2032 is the same as the
number of jobs in J \u2032, it only remains to be shown that J \u2032\u2032 is feasible. Since J \u2032\u2032
di\ufb00ers from J \u2032 only in its intersection with jobs {1, . . . , k}, it su\ufb03ces to verify
two properties, namely that the job set which is the intersection of set J \u2032\u2032 and
set {1, . . . , k} is feasible and that the total processing time of the jobs in the
intersection of J \u2032\u2032 and {1, . . . , k} is less than or equal to the total processing
time of the jobs in the intersection of J \u2032 and {1, . . . , k}. The feasibility of the
intersection of J \u2032\u2032 and set {1, . . . , k} follows from the fact that it is a subset
of Jk, which is feasible because of the \ufb01rst step of the proof. The second property
follows from the fact that pr \u2264 pq.
The third and \ufb01nal step of the proof shows that set Jk is k\u2212optimal for
k = 1, . . . , n. It is clearly true for k = 0 and k = 1. Suppose it is true for k\u2212 1.
From the previous step it follows that the set that comprises