251 pág.

# Pinedo_problemas_deterministicos

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