Division of Research School of Business Administration The University of Michigan December 1992 SCHEDULING PARTS THROUGH A TWO-STAGE TANDEM FLEXIBLE FLOW SHOP J. Blazewicz Technical University of Poznan Moshe Dror The University of Arizona G. Pawlak Technical University of Poznan K.E. Stecke The University of Michigan Working Paper No. 699

I II I~~~~~~~~~~~ I~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ABSTRACT With the increasing installation of flexible manufacturing systems, a need exists to investigate methods for their analysis and modeling. The type of FMS considered here is a tandem flexible flow system (FFS), in which at each stage there may be more than one machine executing operations. Here, we investigate input sequencing heuristics into a tandem two-stage FFS for the performance measure of minimizing makespan. As this scheduling problem with the schedule length criterion is NP-hard, one should investigate heuristic algorithms. For these, we estimate their worst-case, as well as mean, behavior. In this paper, an open NP case of the flexible flow shop problem is studied for which four heuristic algorithms are proposed and analyzed.

1 r~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~' *i I II~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ I~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

1. INTRODUCTION An important problem that needs to be addressed in the operation of a flexible manufacturing system (FMS) is the scheduling of parts on machines (Stecke [1985]). As the machines become more complicated, the FMSs are versatile, so that most of the operations on a part can be accomplished by just one or two machine types (Jaikumar [1986]). One type of an FMS used in practice is a flexible flow system (FFS), where the routing of operations is unidirectional. As opposed to the classical flow shop, an FFS may have more than one machine at each stage, processing operations of different parts in parallel. Recently, Hoogeveen and Lenstra [1992] prove that the problem of scheduling parts in such a system in order to minimize schedule length is NP-hard in the strong sense. This means that in general, not even a pseudo-polynomialtime optimization algorithm is likely to be able to solve the problem. This indicates the usefulness of the development of some polynomial-time heuristic algorithms along with the evaluation of their accuracy. The first work in this direction has been done by Sriskandarajah and Sethi [1989], who analyze flow shop problems with two stages. The first stage contains either one machine or the same number of machines as the second stage. They analyze the worst case behavior of several heuristic algorithms. Different input sequencing problems of FFSs are addressed by Kubiak and Sethi [1992] and Smith and Stecke [1991]. The former finds JIT sequences to balance workloads. The latter determines cyclic input sequences that balance workloads. In this paper, we investigate heuristic algorithms for the special open case of the flow shop scheduling problem with parallel machines at the first stage. Here, the flexible flow shop consists of 2 machine stages [S1, S2], with stage S1 having ml > 2 parallel machines and S2 having m2 = 1 machine. One real-life FMS like this is described in Biazewici et al. [1991]. We begin in Section 2 by analyzing a scheduling algorithm based on Johnson's procedure [1954], which minimizes schedule length for a two-machine problem. The heuristic's worst case behavior is proven to be equal to two. Then three additional simple heuristics are presented. These algorithms are evaluated experimentally. Next we define the problem formally.

-2 - There are n parts, Tj, j=l,...,n, to be processed in up to two operations in the FFS. For each part, there is specified a processing time vector j = [PjlPj2], where pjl and Pj2 denote the operation processing times of part Tj at S1 and S2, respectively. The parts are independent and the operations are nonpreemptable. The optimality criterion here is minimizing the schedule length, Cmax = max{cj}, where c. is a completion time of part T.. According to notation proposed by Graham et al. [1979], with extensions given by Sriskandarajah and Sethi [1989], this problem is denoted as follows: F2 ml=m, m2=1 Cmax In this note, buffers at the machine stages have sufficient capacity to hold all parts waiting for processing. The outline of this paper is as follows. In Section 2, an algorithm based on Johnson's algorithm is presented, and its worst case performance is analyzed. In Section 3, three other algorithms are presented and the average performances of all of the algorithms are tested. A summary is provided in Section 4. 2. ALGORITHM 1 The following heuristic Algorithm 1, which is based on Johnson's algorithm [1954], finds a schedule of possibly minimal length. Algorithm 1 STEP 1. Choose those parts for which the operation times pjl < Pj2. Schedule these parts on the m1 machine at stage S1 in non-decreasing order of their processing times, Pjl. STEP 2. The remaining parts are scheduled on the machines at stage S1 in nonincreasing order of their processing times, pj2. STEP 3. Schedule all of these parts on the single machine at stage S2 in order of their completion at stage S1. — I-" —~I"1 _1--1*11~-1_ -r

-3 - We see that the algorithm uses Johnson's strategy to sort parts at the first stage. However, since there are more than one machine at this stage, it may fail to find an optimal schedule. The worst case behavior of Algorithm 1 is analyzed in the following Theorem 1. Theorem 1. For the problem, F2 m1 =m>2, m2 =1 Cmax, let Pjl and Pj2'j = l...n, be the part processing times on machines at stages S1 and S2, respectively. Let C be the schedule length after applying Algorithm 1 and C* be the optimal schedule max max length. Then C max < 2. C max this bound is the best possible. Proof: A lower bound on the optimal schedule length cannot be less than the following: *1 n *l Cma =maxtmin{Pil}+ XPj2, Clmax +min{pj2 }}, (1) J j=l J where Cmax is a lower bound on an optimal schedule lengthfor stage S1: +* I n Clmax = max{- Pjl, max{pjl}}. m j=l J Condition (1) describes the only two possible cases for the worst schedule at either the first or the second stage. Of course, we can define other terms to describe the optimal schedule length (for example, max{pjl + Pj2). Then, for some instances we could get better results than using J condition (1) only. However, all other cases reduce to condition (1) for Algorithm 1 within the bound of value 2. If we can find any parts that satisfy the inequality from STEP 1 of Algorithm 1, then the schedule produced by Algorithm 1 would not generate the worst case. The worst case occurs when we cannot find parts which satisfy the inequality from STEP 1. Because parts are assigned in non-increasing order of pj2, in the worst case we can first schedule the longest operation time

-4 - parts (Pj) at stage S1, which would give the maximum idle time at the beginning of the second stage. This situation is described by equation (3) and is illustrated by Example 1. On the other hand, if the longest operation time part can be scheduled at the end of stage S1 and if the processing times, Pj2, of the parts are small, then this provides the second case of the worst schedule. This situation is described by equation (9) and is illustrated by Example 2. All other cases can be reduced to these two cases. Now we consider the two possible cases that can follow from equation (1). Case 1: Assume first that the lower bound is *I n Cmax = min {Pj1) + EIPj2 (2) j J=l1 We see that it is the best lower bound of the schedule length. From Algorithm 1, the worst case occurs when the schedule length Cmax fulfills the following equation: n Cmax = max {Pjl +. Pj2 (3) j j=p j This is the upper bound of the schedule length for Case 1. This is because if the max {Pjl} is J scheduled at the beginning of the schedule, then this gives the maximum idle time at the beginning at stage S2. Hence Cax Cm +max( Pji} - min {Pjl}. Thus max {pjl}-min{pjl} Cmax < 1+ J (4) max min {P j}+ P 2 J j=1 Let us denote: max {Pjl} =B and min {Pjl} =. i ij

-5 - We can assume without loss of generality for n>m that n P j2 B. (5) j=l If condition (5) were not true, then Case 1 would reduce to Case 2. We now have max =1+ <2. C B+~ Cmax B Thus Cmax < 2, and this is the worst bound in this case. C Cmax C Now we show an example for which max approaches 2. Cmax Example 1: We define two types of parts with processing times, respectively, of: j=[- m-l, 1 pj [ 1 j-=... m;[" m1 '2 p, = -,- -~M j=l...m2; J m m and e < 3. m3' A schedule constructed from this data by Algorithm 1 is shown in Figure 1.

-6 - (m - ) (m-l) + m/m= m 11 11 Pil = 1 S1 i i I I I I I I III Pjl =m-l -i i I&A m S2 1 I ////////////////// I I I * * I I T 1T idle time ( )m - )m -i ( ) ~~~~~~~~(m ) Figure 1. Schedule Constructed by Algorithm 1, for Example 1. We see that for this schedule, C = m - l+m-I- +-( - ( m 2 max Mm-l1 m = 2m+ m 1 —m2. m - On the other hand, an optimal schedule for this data is shown in Figure 2. (6) m m m IL 1 S1 s! w 0 0 0 (M-I). 0 0 0 i. Ji m pi=m- 1 m S2 1 I I L idle time ( )..... I I I I ( - )m2 m I (M- 1) m Figure 2. The Optimal Schedule for Example 1. _ --- - --- —---- --------- -- -----— ~ --- —-`-*'" ~'r-*1^11"

-7 - Thus, the optimal schedule length is cj+~)n 1 2 1 C = -+. - -m +,m Cmax m m m- 1 1 2 m = +m-m ~+m m-1 Dividing equation (6) by equation (7), we have: (7) C 2m+- m-l-m2e max_ m -1 C* - 1 m 2 max m +-+ -m ~ m m-1 As -> 0, then C max C* max 2m m 1 m-1 1 m +-+ --- m m-1 2m + m-1 — )2, asm->oo. m 1 m+ — + m-1 m Case 2: Case 2 occurs when the second part of equation (1) is greater than the first part. We then have: max Cmax + m Pj (8) In the worst case, a schedule length, Clmax, at stage S1 (a list schedule) is related to an optimal schedule as follows (see Graham [1966]): C1 = 2 — 1 C* Imax. Imax ' In this worst case, from Algorithm 1, we have: C 2ax - C x + min {Pj2} (9)

-8 - This is the worst case of Algorithm 1 for Case 2, where the largest part (max {Pj1 }) is scheduled at the end of Stage 1. On the other hand, we have: *1 <* * C1max max ' Dividing equation (9) by equation (8), we have: C (2 - C1 tmax+min {Pj2 Cmax m j Cax m *a * From equation (1), we know that Cmax Cmax, and thus C 1 max <2 — C* - m max Example 2: We define two types of parts whose processing times are: pj = [1,, 2], j= 1... m(m - 1); 1 pj=[m, ~, whj=lere 2. and ~ < m where b > 2. bm' In Figure 3, the worst case behavior of Algorithm 1 is shown. c-I --- - --- —---------------- -----— ~""-~~"~'~"" '-r ~1-^1"~-~ —~1 —~~"`~""~"`r

-9 - m-1 I 1 IIII I I 0 T 1 * ~ ~ == * === =~~~~ Pj'1 P=m pjl = I Pj= m S1 * * * m ~I, 0 9 I I —I I. mI S2 1 L' / ill 1 0 0 ~ 1 2E * m(m-l) E Figure 3. Schedule for Example 2 Developed from Algorithm 1. 1 If ~ - bm' then 2 e * m(m - 1) < m, and from Figure 3, we have C =m- 1+m+ =2m- 1+ ~. n optimal schedule is shown in Figure 4. An optimal schedule is shown in Figure 4. (10) Si 1 * * * * * * * * * * m _ ^ __ _____ n__________ m S2 1 I I I/ II/11/!1/111 (m-l)*2 e Figure 4. Optimal Schedule for Example 2. The optimal schedule length is: Cax = m + 2 (m- 1) +.

-10 - Dividing equation (10) by equation (11), we obtain I C 2m-a1+ 2m-l+ max 2 - bm Cax m+2e(m-l)+e 2 2 1 b bm bm As b -> oo, then ~ -> 0. Then for m -> oo, C max <2 C* max Hence from Case 1 and Case 2, we conclude that the worst case performance for the considered Algorithm 1 is: C max < 2, and this bound is the best possible. I max 3. COMPUTATIONAL EXPERIMENTS, In addition to Algorithm 1, three other algorithms are tested. They have a similar framework, but a different ordering of the operations. These algorithms are now described: Algorithms 2. 3. and 4 STEP 1. Schedule the operations on the machines at stage S1 in SPT (LPT, random, respectively) order of their processing times, pj1. STEP 2. Schedule all of these operations on the single machine at stage S2 in order of their completion at stage S 1 These four algorithms have been tested experimentally. These computational experiments are now described as follows. All of the parameters are randomly generated using a uniform distribution with the following ranges: 1. The number of operations, n, is from 1 to 1000. 2. The number of machines at the first stage, m, is from 1 to 50. 3. Two cases of processing times are distinguished: _~CI —~ 11 — — —111 —.1 ---~~1*-~~ —1111l —rt-~C~tr -

-11 - a) Processing times are generated randomly according to pjl from 1 to 1000 and 2 from 1 to 1000; or pj2 b) The processing times at stage S2 depend on the number of machines at stage S1 as follows: Pjl from 1 to 1000 and j2 from 1 to 1000/m. Other data of the computational experiments are as follows: - The total number of problems generated is 50,000. - The computer installation used is a SUN station IPC. A *' *' - The ratio, Cax/Cma,,, is evaluated, where Cmax is a lower bound on the optimal * A schedule length, Cmax and Cma is the performance of Algorithm A, where A is 1, 2, 3, or 4. The results are provided in Tables 1 and 2. In these tables, the numbers of cases are A *' shown in which the ratio, Cmax/Cmax, has been reached for each of the four algorithms. The best results are highlighted in boldface. Table 1. A *' The Ratio CmaxCmx for the Four Algorithms and Arbitrary Processing Times of Parts at Both Stages. Ratio: Heuristic/Best Lower Bound Algorithm 1 Alg. 2 (SPT) Alg. 3 (LPT) Alg. 4 (RND) Mean 1.008 1.006 1.0979 1.0880 Std. Dev. 0.0104 0.0096 0.0153 0.0330 Best1 49,647 49,726 1,139 6,051 1. This is the number of times that each Algorithm obtained the best lower bound out of all 50,000 problems tested.

-12 - Table 2. A *t The Ratio Cmax/Cmax for the Four Algorithms and Processing Times of Parts at Stage S2 Depending on the Number of Machines at Stage S1. Ratio: Heuristic/Best Lower Bound Algorithm I Alg. 2 (SPT) Alg. 3 (LPT) Alg. 4 (RND) Mean 1.1112 1.1129 1.337 1.1330 Std. Dev. 0.0950 0.0950 0.0797 0.0833 Best1 9,392 9,168 111 115 1. This is the number of times that each Algorithm obtained the best lower bound out of all 50,000 problems tested. We see from Table 1 that for an arbitrary generation of processing times of operations of parts, the machine at the second stage becomes a bottleneck. All of the algorithms become nearly optimal and the ratio nearly never exceeds 1.3. Algorithm 1 and the modified SPT heuristic are both by far the best. However, when the processing times at the second stage depend on the number of machines at the first stage, then the algorithms behave quite differently. The best percentage of solutions close to optimum are still Algorithm 1 and a close second, Algorithm 2 (modified SPT). The standard deviation for none of the algorithms is high. The worst algorithm in both situations is Algorithm 3 (LPT). LPT is even a bit worse than a random assignment of operations to the machines at stage S1. This could be expected, because an LPT assignment at the first stage can increase the idle time at the second stage. 4. SUMMARY In this paper, a special case of the flow shop scheduling problem has been analyzed in which the first stage contains parallel identical machines, while the second stage contains only i ~___IIIIIC —~llllllII _ P ---I-

-13 - one machine. An algorithm based on Johnson's strategy has been proposed and its worst case behavior is shown to be 2. Then, three other simple heuristics have been proposed and all four of the algorithms have been tested experimentally. The mean behaviors of Algorithm 1 (based on Johnson's approach) and of Algorithm 2 (based on the SPT rule) were the best and close to optimal. Further investigation along these lines would be useful. Such research should include different criteria (for example, mean weighted completion time or tardiness). Other details that could be included are the usual finite buffers between stages or automated guided vehicle routing. ACKNOWLEDGMENTS The authors gratefully acknowledge helpful comments made by Ervin Pesch on an earlier draft of this paper. Kathy Stecke would like to acknowledge a summer research grant from the Business School of The University of Michigan.

-14 - REFERENCES BIazewici, J., H. A. Eiselt, G. Finke, G. Laporte, and J. Weglarz, "Scheduling Tasks and Vehicles in a Flexible Manufacturing System," International Journal of Flexible Manufacturing Systems, Vol. 4, No. 1, pp. 5-16 (August 1991). Hoogeveen, J. A., J. K. Lenstra, and B. Veltman, "Minimizing Makespan in a Multiprocessor Flowshop is Strongly NP-hard," Working Paper, Eindhoven University of Technology, The Netherlands (1992). Jaikumar, R., "Postindustrial Manufacturing," Harvard Business Review, Vol. 64, No. 6 (November-December 1986). Johnson, S. M., "Optimal Two- and Three-stage Production Schedules with Set-up Times Included," Naval Research Logistics Ouarterly, Vol. 1, pp. 61-68 (1954). Kubiak, W. and S. P. Sethi, "Optimal Just-In-Time Schedules for Flexible Transfer Lines," Working Paper, Memorial University of Newfoundland, Faculty of Business Administration, St. John's, Canada, A1B 3X5 (July 1992). Graham, R. J., "Bounds for Certain Multiprocessing Anomalies," Bell Systems Technical Journal, Vol. 45, No. 9 (November 1966). Graham, R. J., E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnoy Kan, "Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey," Annals of Discrete Mathematics, Vol. 5, pp. 287-294 (1979). Smith, T. M. and K. E. Stecke, "On the Robustness of Using Balanced Part Mix Ratios to Determine Cyclic Part Input Sequences Into Flexible Flow Systems," Working Paper, No. 658, Division of Research, The University of Michigan, School of Business, Ann Arbor, MI (May 1991). Sriskandarajah, C. and S. P. Sethi, "Scheduling Algorithms for Flexible Flowshops: Worst and Average Case Performance," European Journal of Operational Research, Vol. 43, pp. 143-160 (1989). Stecke, K. E., "Design, Planning, Scheduling, and Control Problems of Flexible Manufacturing Systems," Annals of Operations Research, Vol. 3, pp. 3-12 (1985).