Pinedo_problemas_deterministicos
251 pág.

Pinedo_problemas_deterministicos


DisciplinaPlanejamento da Producao27 materiais261 seguidores
Pré-visualização50 páginas
sequence changes between the
\ufb01rst two machines and between the last two machines (see Exercise 6.11). This
implies that there are optimal schedules for F2 || Cmax and F3 || Cmax that
do not require sequence changes between machines. One can \ufb01nd examples of
\ufb02ow shops with four machines in which the optimal schedule does require a job
sequence change in between the second and the third machine.
Finding an optimal schedule when sequence changes are allowed is signi\ufb01-
cantly harder than \ufb01nding an optimal schedule when sequence changes are not
allowed. Flow shops that do not allow sequence changes between machines are
called permutation \ufb02ow shops. In these \ufb02ow shops the same sequence, or permu-
tation, of jobs is maintained throughout. The results in this chapter are mostly
limited to permutation \ufb02ow shops.
Given a permutation schedule j1, . . . , jn for an m machine \ufb02ow shop, the
completion time of job jk at machine i can be computed easily through a set
of recursive equations:
Ci,j1 =
i\u2211
l=1
pl,j1 i = 1, . . . ,m
C1,jk =
k\u2211
l=1
p1,jl k = 1, . . . , n
Ci,jk = max(Ci\u22121,jk , Ci,jk\u22121) + pi,jk i = 2, . . . ,m; k = 2, . . . , n
The value of the makespan under a given permutation schedule can also be
computed by determining the critical path in a directed graph that corresponds
to the schedule. For a given sequence j1, . . . , jn this directed graph is constructed
as follows: for each operation, say the processing of job jk on machine i, there
is a node (i, jk) with a weight that is equal to the processing time of job jk
on machine i. Node (i, jk), i = 1, . . . ,m \u2212 1, and k = 1, . . . , n \u2212 1, has arcs
6.1 Flow Shops with Unlimited Intermediate Storage 153
pi+1, jk+1pi+1, jk
pi, jk pi, jk+1
p2, j1
p1, j1 p1, j2
pm, j1 pm, jn
p1, jn
Fig. 6.1 Directed Graph for the Computation of the Makespan in
Fm | prmu | Cmax under sequence j1, . . . , jn
going out to nodes (i+ 1, jk) and (i, jk+1). Nodes corresponding to machine m
have only one outgoing arc, as do nodes corresponding to job jn. Node (m, jn)
has no outgoing arcs (see Figure 6.1). The total weight of the maximum weight
path from node (1, j1) to node (m, jn) corresponds to the makespan under the
permutation schedule j1, . . . , jn.
Example 6.1.1 (Graph Representation of Flow Shop)
Consider 5 jobs on 4 machines with the processing times presented in the
table below.
jobs j1 j2 j3 j4 j5
p1,jk 5 5 3 6 3
p2,jk 4 4 2 4 4
p3,jk 4 4 3 4 1
p4,jk 3 6 3 2 5
The corresponding graph and Gantt chart are depicted in Figure 6.2. From
the directed graph it follows that the makespan is 34. This makespan is
determined by two critical paths. ||
An interesting result can be obtained by comparing two m machine permu-
tation \ufb02ow shops with n jobs. Let p(1)ij and p
(2)
ij denote the processing time of
job j on machine i in the \ufb01rst and second \ufb02ow shop, respectively. Assume
p
(1)
ij = p
(2)
m+1\u2212i,j .
154 6 Flow Shops and Flexible Flow Shops (Deterministic)
5 5 3 6 3
4 4 2 4 4
4 4 3 4 1
3 6 3 2 5
0 2010 30
3 6 3 2 5
4 4 4 13
4 4 2 4 4
5 5 3 6 3
Fig. 6.2 Directed graph, critical paths and Gantt chart (the numerical
entries represent the processing times of the jobs and not the job
indexes)
This basically implies that the \ufb01rst machine in the second \ufb02ow shop is identical
to the last machine in the \ufb01rst \ufb02ow shop; the second machine in the second \ufb02ow
shop is identical to the machine immediately before the last in the \ufb01rst \ufb02ow
shop, and so on. The following lemma applies to these two \ufb02ow shops.
Lemma 6.1.2. Sequencing the jobs according to permutation j1, . . . , jn in
the \ufb01rst \ufb02ow shop results in the same makespan as sequencing the jobs according
to permutation jn, . . . , j1 in the second \ufb02ow shop.
Proof. If the \ufb01rst \ufb02ow shop under sequence j1, . . . , jn corresponds to the dia-
gram in Figure 6.1, then the second \ufb02ow shop under sequence jn, . . . , j1 corre-
sponds to the same diagram with all arcs reversed. The weight of the maximum
weight path from one corner node to the other corner node does not change if
all arcs are reversed. 	unionsq
Lemma 6.1.2 states the following reversibility result: the makespan does not
change if the jobs traverse the \ufb02ow shop in the opposite direction in reverse
order.
6.1 Flow Shops with Unlimited Intermediate Storage 155
5 2 3 6 3
1 4 3 4 4
4 4 2 4 4
3 6 3 5 3
0 2010 30
3 6 3 5 5
4 4 42 4
1 4 3 4 4
5 2 3 6 3
Fig. 6.3 Directed graph, critical paths and Gantt chart (the numerical
entries represent the processing times of the jobs and not the job
indexes)
Example 6.1.3 (Graph Representations and Reversibility)
Consider the instance of Example 6.1.1. The dual of this instance is given in
the table below.
jobs j1 j2 j3 j4 j5
p1,jk 5 2 3 6 3
p2,jk 1 4 3 4 4
p3,jk 4 4 2 4 4
p4,jk 3 6 3 5 5
The corresponding directed graph, its critical paths and the Gantt charts are
depicted in Figure 6.3. It is clear that the critical paths are determined by
the same set of processing times and that the makespan, therefore, is 34 as
well. ||
156 6 Flow Shops and Flexible Flow Shops (Deterministic)
Consider now the F2 || Cmax problem: a \ufb02ow shop with two machines in
series with unlimited storage in between the two machines. There are n jobs
and the processing time of job j on machine 1 is p1j and its processing time on
machine 2 is p2j . This was one of the \ufb01rst problems to be analyzed in the early
days of Operations Research and led to a classical paper in scheduling theory
by S.M. Johnson. The rule that minimizes the makespan is commonly referred
to as Johnson\u2019s rule.
An optimal sequence can be described as follows. Partition the jobs into
two sets with Set I containing all jobs with p1j < p2j and Set II all jobs with
p1j > p2j . The jobs with p1j = p2j may be put in either set. The jobs in
Set I go \ufb01rst and they go in increasing order of p1j (SPT); the jobs in Set II
follow in decreasing order of p2j (LPT). Ties may be broken arbitrarily. In what
follows such a schedule is referred to as an SPT(1)-LPT(2) schedule. Of course,
multiple schedules may be generated this way.
Theorem 6.1.4. Any SPT(1)-LPT(2) schedule is optimal for F2 || Cmax.
Proof. The proof is by contradiction. Suppose another type of schedule is op-
timal. In this optimal schedule there must be a pair of adjacent jobs, say job j
followed by job k, that satis\ufb01es one of the following three conditions:
(i) job j belongs to Set II and job k to Set I;
(ii) jobs j and k belong to Set I and p1j > p1k;
(iii) jobs j and k belong to Set II and p2j < p2k.
It su\ufb03ces to show that under any of these three conditions the makespan is
reduced after a pairwise interchange of jobs j and k. Assume that in the orig-
inal schedule job l precedes job j and job m follows job k. Let Cij denote the
completion of job j on machine i under the original schedule and let C\u2032ij de-
note the completion time of job j on machine i after the pairwise interchange.
Interchanging jobs j and k clearly does not a\ufb00ect the starting time of job m on
machine 1, as its starting time on machine 1 equals C1l + p1j + p1k. However,
it is of interest to know at what time machine 2 becomes available for job m.
Under the original schedule this is the completion time of job k on machine 2,
i.e., C2k, and after the interchange this is the completion time of job j on ma-
chine 2, i.e., C\u20322j . It su\ufb03ces to show that C
\u2032
2j \u2264 C2k under any one of the three
conditions described above.
The completion time of job k on machine 2 under the original schedule is
C2k = max
(
max (C2l, C1l + p1j) + p2j , C1l + p1j + p1k
)
+ p2k
= max
(
C2l + p2k + p2j , C1l + p1j + p2j + p2k, C1l + p1j + p1k + p2k
)
,
whereas the completion time of job j on machine 2 after the pairwise interchange
is
C\u20322j = max
(
C2l + p2k + p2j , C1l + p1k + p2k + p2j , C1l + p1k + p1j + p2j
)
.
6.1 Flow Shops with Unlimited Intermediate Storage 157
Under condition (i) p1j > p2j and p1k < p2k. It is clear that the \ufb01rst terms
within the max expressions of C2k and C\u20322j are identical. The second term in
the last expression