A Technical Note A BRANCH AND BOUND APPROACH FOR THE LOADING PROBLEM IN FLEXIBLE MANUFACTURING SYSTEMS: AN UNBALANCING CASE Yeong-Dae Kim Candace A. Yano Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 Technical Report 87-18 July 1987

A BRANCH AND BOUND APPROACH FOR THE LOADING PROBLEM IN FLEXIBLE MANUFACTURING SYSTEMS: AN UNBALANCING CASE Abstract Loading problems in flexible manufacturing systems involve assigning operations and tools to machines or machine groups for part types that have been selected to be processed simultaneously. There are several objectives for the loading problems, one of which is to maximize expected production of the system. In this paper, we test several objective functions and discuss correlations between these functions and the expected production. Using a selected objective function from the test, we give a branch and bound approach for the loading problem with the objective of unbalancing workloads. This objective is known to aid in maximizing system throughput when the number of machines in each group varies. Computational results are reported.

1. Introduction A flexible manufacturing system (FMS) is an automated batch manufacturing system consisting of numerically controlled machines capable of performing multiple functions, and linked together with a material handling system, all controlled by a computer system. The aim of an FMS is to achieve the efficiency of automated highvolume mass production while retaining the flexibility of low-volume job shop production. The system setup problem (see Kiran and Tansel 1986), a part of which is addressed in this paper, is one of several problems that must be solved before production begins, to best utilize FMSs. The subproblems to be solved in this problem are: selecting a subset of part types for immediate and simultaneous production; partitioning machines into groups; allocating operations and tools to machine groups; and determining the numbers of pallets and fixtures and allocating them to part types. This paper focuses on the third subproblem, called the FMS loading problem. The FMS loading problem is to assign the operations of the selected part types and the tools needed for these operations to machines or machine groups subject to tool magazine capacity constraints according to some loading objective. Some research has been done on the FMS loading problem. Stecke (1983) formulates it as a nonlinear mixed integer program and solves it through linearization techniques. A branch and bound algorithm is developed by Berrada and Stecke (1986) for this formulation with the objective of balancing the workloads. Ammons et al. (1985) and Shanker and Tzen (19851 give different formulations and present heuristic procedures. Also the loading problem is studied together with other FMS-related problems in other research [ Greene and Sadowski (1986), Rajagopalan (1986), and Stecke (1986) ]. A commonly used objective of the loading problem is balancing workloads of machines. This objective can help to maximize system throughput or expected production [Stecke and Morin (1985) and Stecke and Solberg (1985)] as well as to minimize in-process inventories [Shanthikumar and Stecke (1986)]. Moreover, Raman et al. (1986) report that 1

balanced workloads are desirable from the perspective of due-date based scheduling measures as indicated by simulation experiments. However, balancing cannot always guarantee the maximum throughput. When machines are pooled into groups - machines in a group are identically tooled and therefore can process the same operations - and the group sizes (numbers of machines) are different, expected production can be maximized by a particular unbalanced assignment of workload per machine. Stecke and Solberg (1985) prove that pooling increases system throughput and that it can be further improved by having unbalanced rather than balanced partitions of machines into groups. Also, using simulation studies, Stecke and Kim (1987) show that unbalancing gives higher system utilization and shorter makespan. This makes the loading problem with the objective of unbalancing important. Here the term unbalancing means achieving ideal workloads for a grouping which maximizes the expected production. Our objective for the loading problem is to maximize system throughput, which can be achieved by balancing or unbalancing workloads. There may be several measures of workload balance or unbalance which can be used as an objective function for the problem. In this paper, we test these measures of workload (un)balance and discuss their correlations with system throughput. Also we give a branch and bound procedure for workload unbalancing. This procedure is a simple modification of the branch and bound algorithm for workload balancing given in Berrada and Stecke (1986). 2. Measures of Workload Balance or Unbalance There is no known unified measure of workload (un)balance for the loading problems. Instead, several different functions of workloads can be used to measure balance or deviation of assigned workloads from ideal (objective) workloads. This may be a reason that Ammons et al. (1985), Shanker and Tzen (1985), and Berrada and Stecke 2

(1986) use different objective functions for the same objective, balancing workloads. Since balancing or unbalancing itself can hardly be a direct measure of performance of an FMS, it may not be a final objective of the loading problem. As noted earlier, our objective is to maximize expected production of the system. Since this objective is hard to deal with directly, workload balancing or unbalancing is used as an objective. Herein comes the need for the study of the relationship between the expected production and measures of (un)balance. In this paper, we test twelve objective functions as measures of (un)balance which can be handled relatively easily in the loading problems. The following are the measures of (un)balance tested. These are all to be minimized for our objective. Xl and IXi denote actual load and ideal load for machine group I (not per machine), respectively. C1 = maxI (X - IX1) C2 = max, (IX - X1) C3 = C1 + C2 C4 = max I| X1 - IXI C5 = |Xi-IX1I C6 = E ( X- IX )2 C7 = max, ( X - IX)/ IX/ C8 = max, (IXI- X )/IXI C9 = C6 + C7 C10 = max | X - IXI /IX/ Cl1 = E |X - IXII/IX/ C12 = E (Xl- IX )2/IX/ I 3

By C1, the maximum workload among the groups is to be minimized, while the minimum workload is to be maximized by C2. C4 is the maximum deviation of actual workload from the ideal workload and is equal to the maximum of C1 and C2. C5 is the sum of the deviations and C6 is the sum of squared deviations. C7 through C12 are the counterparts of C1 through C6 with the reciprocal of the ideal workload as a weighting factor for each group. Note that the measures C7 through C12 are equivalent to the measures C1 through C6 for the objective of balancing workloads in our test. To compare these measures, fifty sets of system configurations were tested for both balancing and unbalancing objectives. A configuration defines the number of machine groups (ranging from 3 to 7) and the number of machines in each group (ranging from 1 to 6). Each set consists of fifty problems with randomly generated actual loads for machine groups. To calculate the expected production for a given configuration and workload assignment, the closed queueing network (CQN) model of Stecke and Solberg (1985) was used. For each set, the ideal loads and their expected production were calculated with the CQN model, and the values of the measures of (un)balance and the expected production were also calculated from the randomly generated workloads of the fifty problems. We calculated the coefficient of correlation between the values of the measures and the expected production for each set and tested differences among these coefficients. The results are shown in Tables 1 and 2. Table 1 shows means and standard deviations of the correlation coefficients of the fifty sets. Table 2 shows the results of paired t test for the difference of the correlations for different measures. For the balancing, case, C1 significantly dominates others. This justifies the objective function of the formulation of Berrada and Stecke (1986), minimizing the maximum workload. For the unbalancing case, however, C1 does not work very well. Instead, C7 (the maximum ratio of overload to the ideal load among the machine groups) works well in this case. C9, whose value is the sum of C7 and C8, also works well, but this can be considered to be from the effect of C7. In the next section, C7 will be used in 4

Table 1. Correlation coefficients (r) of the measures with the expected production Unbalancing Balancing Measure Standard Standard Mean Deviation Mean Deviation C1 -.813.104 -.979.009 C2 -.750.092 -.546.152 C3 -.840.081 -.946.020 C4 -.811.083 -.919.041 C5 -.853.060 -.892.054 C6 -.793.070 -.925.030 C7 -.945.028 C8 -.288.173 C9 -.938.024 C10 -.916.033 C11 -.917.031 C12 -.897.038 Table 2. Test results for difference of the correlation coefficients ( Paired t test ) Objective Results Balancing C1 >> C3 >> C6 = C4 >> C5 >> C2 Unbalancing C7 > C9 >> C11 = C10 >> C12 >> C5 > C3 >> C1 = C4 >> C6 >> C2 >> C8 > >: statistically different at significance level of.01 >: statistically different at significance level of.05 =: not statistically different at significance level of.05 the objective function of the loading problem in which group sizes are different. 3. Branch and bound approach for the unbalancing case Since only the objective jeti of this branch and bound approach is different from that of Berrada and Stecke (1986), we use a similar formulation for the problem. We follow the 5

notation of Stecke (1983) for the formulation, which is: I set of operations, I = {i i=1,-,b} L set of machine groups, L = f I |= 1,-..,M} p.i processing time of operation i on one of the machines in machine group I d. number of slots required in a tool magazine by operation i tl capacity of the tool magazine of the machines in machine group l WB number of slots saved when the operations in subset B C I are assigned to the same machine group a. relative production ratio at which operation i will be produced IXl (relative) ideal workload per group of machine group I x.l decision variable ( 1 if operation i is assigned to machine group 1, 0 otherwise). As specified in the previous section, our objective of the loading problem with different sizes of machine groups is to minimize the measure C7. Let 6 be an upper bound on C7. Then the problem is to find {xil I i=1,,b, l=1,.,M } to: Problem (UB) Minimize 6 b subject to ( E aip xil -IX) I l=Il,'.,M ~ i=l'1' b b di.xi+ S (-1) S w, n Xl t, =I,..,M i=1 p=2 /B/=p iEB M x = 1, i=1,,b i=l (3, x = 0 or 1, for all i and., 4 Xil 0 or 1 6

Note that problem (UB) is identical to the problem (P) of Berrada and Stecke (1986) except constraint (1). The tool magazine capacity constraints (with provision for tools shared by operations) are reflected in (2). The operation assignment constraints appear in (3). Constraint (1) can be rewritten as b Pil E a. - x -1 6, 1=1,,M. i 1 IX If we let = P.l IXI and = 6 + 1, then the constraint is identical to b S ai qil xil -, l=1,,M. i=l (5) By this substitution the problem (UB) is equivalent to: Problem (B) Minimize 7 subject to (5), (2), (3), and (4). Since problem (B) is identical to the problem (P) of Berrada and Stecke (1986), their branch and bound algorithm can be used for the problems with the unbalancing objective through simple transformation of data. As the numbers of constraints and variables do not change, complexities of the two problems (balancing and unbalancing) can be considered equal. 4. Computational results For the test of applicability of the branch and bound algorithm of Berrada and 7

Stecke to the unbalancing case, forty two problems were run on an IBM3090-400 with an optimizing compiler for FORTRAN using the code provided by them. The problems with the objective of balancing were from Berrada and Stecke. (The other thirteen problems which appeared in their paper were not available.) The unbalancing problems are identical to those of balancing except that the group sizes are different. In the computer code, a subroutine was added for calculating the ideal workloads of groups for the given group sizes. Computational results are shown in Table 3. CPU times are compared for the two cases, balancing and unbalancing. To compare the expected production of the two cases, the expected production was calculated from the solution of the algorithm with the CQN model. The CPU times for the unbalancing case are slightly longer than those for the balancing case. However, it cannot be concluded that these resulted from the objective, unbalancing, since the two objectives give the exactly same formulation and the only difference is that of data. (For different data, the results may be different.) Advantage of unbalancing can be seen from the expected production of the two cases. The expected production for the unbalancing case is higher than that for the balancing case for all the problems except three (problems 10, 32, and 37). These exceptions may have resulted from lumpiness of the processing times of operations, which prohibits actual workloads from being close enough to the ideal workloads for the groups with unbalanced sizes. The computational results are encouraging. The objective of workload unbalancing is not only solvable in reasonable time by the already-existing algorithm for workload balancing, but also more favorable from the aspect of increasing production capability of the system when the number of groups is small (less than ten). With a larger number of machine groups, it appears that balancing workloads provides excellent performance. 8

Table 3. Computational results of the two branch and bound approaches Balancing Unbalancing Problem Number Number Number of of Expected CPU time Expected CPU time Groups Operations Production (seconds) Production (seconds) I I 1 4 12.823.039.833.020 2 4 12.772.159.845.018 3 4 12.796.015.821.029 4 4 12.768.039.817.075 5 5 10.758.035.772.024 6 5 10.790.037.803.062 7 5 12.747.163.755.213 8 5 12.716.200.785.128 9 5 14.793.222.809.909 10 5 14.788.287.783 1.910 11 6 12.707.035.760.046 12 6 12.762.029.776.081 13 6 14.709.030.788.059 14 6 14.730.068.745.299 15 7 10.714.090.717.651 16 7 12.702.028.702.030 17 7 12.725.074.726.192 18 8 12.665.026.675.011 19 8 14.627.086.688.208 20 8 14.643.111.696.448 21 8 15.687.195.687.407 22 9 15.621.020.657.058 23 9 15.621.022.643.078 24 9 20.656.060.683.432 25 9 20.706.067.718.331 26 10 20.666.403.668.848 27 10 20.666.445.680 1.119 28 10 25.688 2.167.690 2.359 29 11 20.651.485.667.696 30 11 20.651.298.651 1.279 31 11 24.651 1.467.662 2.157 32 11 30.665 2.581.664 4.302 33 11 30.657 1.987.664 4.172 34 12 20.607 1.065.635.669 35 12 20.607 1.071.610.607 36 12 35.639.481.643 4.607 37 12 35.639 4.601.637 7.604 38 13 36.614 5.208.616 5.815 39 13 36.614 5.266.616 6.249 40 14 35.585 3.973.589 3.545 41 15 30.569 1.993.574 1.537 42 15 40.623 7.814.629 8.152 All the problems were run on an IBM3090-400. 9

5. Concluding remarks The FMS loading problem was considered in this paper. Workload balancing or unbalancing is used as an intermediate objective to maximize the expected production. Several measures of balance or unbalance were tested for problem formulation and solution. The test revealed that among the tested measures, minimizing the maximum workload (Cl) is the best for balancing and minimizing the maximum ratio of actual load to the ideal load for a group (C7) is the best for unbalancing. For the objective function of minimizing C7, a branch and bound approach was presented. With a simple data transformation, an existing branch and bound algorithm for workload balancing can be used directly for our unbalancing objective. The computational results showed that CPU time was reasonable for the objective of unbalancing workloads as well. Moreover, the solutions for unbalancing gave higher system throughputs than those for balancing, which is consistent with other research. The differences are most pronounced when the number of machine groups is less than ten. For larger numbers of machine groups, balancing workloads provides excellent results as well. Our approach provides more flexibility in optimally solving the FMS loading problems, especially for the cases in which balanced group sizes cannot be obtained and the maximum possible system throughput is sought through unbalanced group sizes. Acknowledgement The authors would like to thank Drs. Mohammed Berrada and Kathryn E. Stecke for providing the computer code of their branch and bound algorithm and the data for the problems of workload balancing. 10

References Ammons, J.C., C.B. Lofgren and L.F. McGinnis, 1985. A Large Scale Machine Loading Problem in Flexible Assembly. Annals of Operations Research, Vol.3, pp.319-322. Berrada, M. and K.E. Stecke, 1986. A Branch and Bound Approach for Machine Load Balancing in Flexible Manufacturing Systems. Management Science, Vol.32, No.10, pp.1316-1335. Greene, T.J. and R.P. Sadowski, 1986. A Mixed Integer Program for Loading and Scheduling Multiple Flexible Manufacturing Cells. European J. of Operational Research. Vol.24, pp.379-386. Kiran, A.S. and B.C. Tansel, 1986. The System Setup in FMS: Concepts and Formulation. Proc. of the 2nd ORSA/TIMS Conf. on Flexible Manufacturing Systems. Ann Arbor, MI, pp.321-332. Raman, N., F.B. Talbot and R.V. Rachamadugu, 1986. Simultaneous Scheduling of Machines and Material Handling Devices in Automated Manufacturing. Proc. of the 2nd ORSAITIMS Conf. on Flexible Manufacturing Systems, Ann Arbor, MI, pp.455-465. Rajagopalan, S., 1986. Formulation and Heuristic Solutions for Parts Grouping and Tool Loading in Flexible Manufacturing Systems. Proc. of the 2nd ORSAITIMS Conf. on Flexible Manufacturing Systems, Ann Arbor, MI, pp.312-314. Shanker, K. and Y-J. J. Tzen, 1985. A Loading and Dispatching Problem in a Random Flexible Manufacturing System. Int. J. Prod. Res., Vol.23, pp.579-595. Shanthikumar, J.G. and K.E. Stecke, 1986. Reducing Work-in-Process Inventory in Certain Classes of Flexible Manufacturing Systems. European Journal of Operational Research, Vol.26, pp.266-271. Stecke, K.E., 1983. Formulation and Solution of Nonlinear Integer Production Planning Problems for Flexible Manufacturing Systems. Management Science, Vol.29, No.3. pp.273-288. Stecke, K.E., 1985. Design, Planning, Scheduling, and Control Problems of Flexible Manufacturing Systems. Annals of Operations Research, Vol.3, pp.3-12. Stecke, K.E., 1986. A Hierarchical Approach to Solving Machine Grouping and Loading Problems of Flexible Manufacturing Systems. European J. of Operational Research. Vol.24, pp.369-378. Stecke,K.E. and I. Kim, 1987. A Study of Unbalancing and Balancing for Systems of Pooled Machines of Unequal Sizes. Proceedings of the IEEE Robotics and Automation Conference, Raleigh, NC. 11

Stecke, K.E. and T.L. Morin, 1985. The Optimality of Balancing Workloads in Certain Types of Flexible Manufacturing Systems. European J. of Operational Research, Vol.20, pp.68-82. Stecke, K.E. and J.J. Solberg, 1985. The Optimality of Unbalancing Both Workloads and Machine Group Sizes in Closed Queueing Networks of Multi-Server Queues. Operations Research, Vol.33, No.4, pp.882-910. 12