Division of Research Graduate School of Business Administration The University of Michigan October 1983 Heuristic Loading Algorithms for Flexible Manufacturing Systems Working Paper No. 348 Kathryn E. Stecke and F. Brian Talbot The University of Michigan FOR DISCUSSION PURPOSES ONLY None of this material is to be quoted or reproduced without the expressed permission of the Division of Research.

I

in Proceedings of the Seventh International Conference on Production Research, Windsor, Ontario, Canada, August 22-24, 1983 HEURISTIC LOADING ALGORITHMS FOR FLEXIBLE MANUFACTURING SYSTEMS Kathryn E. Stecke and F. Brian Talbot Graduate School of Business Administration The University of Michigan Ann Arbor, Michigan USA ABSTRACT The flexible manufacturing system (FMS) is an alternative to conventional discrete manufacturing processes that permits highly automated, efficient, and simultaneous machining of a variety of part types. In managing these systems, technological requirements indicate that several decisions must be made prior to system start-up. To this end, previous research has defined a set of production planning problems. The final production planning problem is called the loading problem, which is described as follows. Given a set of part types chosen for immediate simultaneous production, allocate the operations and associated tooling of these part types among the machines subject to the capacity and technological constraints, and according to some loading objective. This problem has previously been formulated as a nonlinear mixed integer program for several loading objectives. Although it has been shown that the nonlinear MIPs are solvable on large computer systems, real-time FMS control requirements and the typical availability of -minicomputers in shop environments make it- impractical and cost inefficient to optimally solve the loading problem in many plants today. As a result, the authors develop several heuristic algorithms that provide good solutions to various versions of the FMS loading problem. We expect that these rules can be executed on minicomputers available today in essentially real-time. 1. INTRODUCTION The development of highly automated flexible manufacturing systems (FMSs) has created new opportunities for the efficient manufacture of component parts in the metal-cutting industry. The effective use of these systems, however, requires the solution of new and complicated production planning and control problems. In an effort to make these problems tractable, Stecke [1983] has devised a hierarchical scheme comprising five production planning problems which must be solved prior to system operation. A brief description of these appears in Table 1. The primary purpose of this paper is to present heuristic solution procedures for one of these problems, the loading problem. The loading problem is one of deciding how individual machines are to be tooled to collectively accomplish all manufacturing operations for each part type that will be machined concurrently. A solution to this problem specifies the tools which must be loaded in each machine tool magazine before production begins, and hence, the machine or machines to which a part can be routed for each of its operations. Since a variety of products (parts) can be manufactured simultaneously on an FMS, where each part has its own, potentially unique, set of required operations, loading becomes a combinatorial problem. Some of the characteristics which make this a difficult combinatorial problem to solve include the possibility that: i) some particular part operations may be performed on any of several different types of machines; ii) different part operations may be able to use some of the same cutting tools; and iii) tools, measured individually and collectively, require various amounts of space (slots) in fixed-size tool magazines.

Table 1 Production Planning Problems 1. Part Type Selection Problem: From a set of part types that have production requirements, determine a subset for immediate and simultaneous processing. 2. Machine Grouping Problem: Partition the machines into machine groups in such a way that each machine in a particular group is able to perform the same set of operations. 3. Production Ratio Problem: Determine the relative ratios at which the part types selected in problem (1) will be produced. 4. Resource Allocation Problem: Allocate the limited number of pallets and fixtures of each fixture type among the selected part types. 5. Loading Problem: Allocate the operations and required tools of the selected part types among the machine groups subject to technological and capacity constraints of the FMS. Although it is possible to model these characteristics as nonlinear mixed integer programs (Stecke [1983]), it is time and cost prohibitive to optimally solve the resultant loading problems that are large, despite the existence of an efficient branch and bound procedure (Berrada and Stecke [1983]). Bence, there is a need for fast heuristic procedures that give good, if not optimal, solutions. The loading problem addressed in this paper assumes that the grouping problem has been solved. Stecke [1981] introduced the notion of the grouping problem as one way of simplifying overall production planning and control of FMSs while also automatically providing machine redundancy, which is useful during machine breakdown situations. A machine group is composed of'machines that are tooled so that they can individually perform the same operations. Typically, machines in a group are of the same type and are identically tooled. Through the use of closed queueing networks to model FMSs, Stecke and Solberg [1982] found optimal grouping patterns and associated optimal allocation ratios, which indicate the amount of work (operation processing time) which should ideally be assigned to each machine group, to provide maximum expected production. Knowing how machines should be grouped affects other aspects of production planning, but specifically, simplifies the loading problem both by reducing the tooling options and by reducing the size of the problem to be solved. Several loading objectives are considered in this paper as indicated in Table 2. Each might be applicable in different manufacturing situations. In some systems, several objectives may apply. 2. HEURISTIC LOADING ALGORITHMS In this section, several loading algorithms are described for the situations where the grouping problem has already been solved. That is, we know how many groups there are, the sizes of each machine group, and which machines are in each group. The solution to the loading problem will define precisely which operations, and hence tooling, will be assigned to each machine. There are several machines of each type. (If there is only one machine of each type, then the loading problem that is solved in this section becomes trivial). We assume that each operation can be accomplished by only one machine type. This assumption can easily be relaxed. 2.1 Loading Algorithms for Minimizing Part Movement The first two algorithms are designed to minimize part movement in an FMS. This objective is especially important in a system having relatively high travel or pallet positioning times (see Stecke and Solberg [1981]). The first - 2 -

Table 2 Alternative Loading Objectives (1) minimize part movement between machines, or equivalently, maximize the number of consecutive operations for a part to be processed by the same machine; (2) balance the workload (total procesing time) per machine on all machines; (3) balance the workload per machine for a system configured of groups of machines of equal sizes; (4) unbalance the workload per machine for a system of groups composed of unequal numbers of machines; (5) duplicate certain operation assignments. algorithm approaches the problem by examining consecutive operations sequentially, whereas the second, pre-groups consecutive operations before loading. The algorithms are presented in increasing order of complexity. ALGORITHM 1 i. Taking each part in numerical order, assign each operation consecutively to the lowest numbered machine of the correct type which has magazine capacity available for the tools required for the operation. 2. Continue assigning operations until all have been allocated. This is a simple application of the first-fit bin packing heuristic [1973] and involves very little computational effort beyond feasibility testing. At each magazine capacity test, common tool and slot overlap checks, and corresponding adjustments, should be made to determine feasibility. A potential drawback of this approach is that the resulting solution will likely not conform to given commonly-tooled machine grouping goals, related to total assigned processing times. ALGORITHM 2 1. For each part type, group maximally into "operation sets", consecutive operations which require the same machine type. Calculate the number of magazine slots required for each operation set. 2. Calculate a priority index for each operation set, and assign operation sets to machines of the correct type according to this index. Several possible prioritizing schemes are: (a) assign operation sets to the lowest numbered machine possible according to the index: "largest number of tool slots required" first. This is a variation of the first-fitdecreasing bin packing heuristic. (b) assign operation sets according to the index "largest number of tool slots required" first, but to the machine having the cutting tools already in its magazine which will most reduce the number of slots actually needed by the operation set being assigned. (c) assign operation sets to the lowest numbered machine possible according to the index: "largest number of operations in a set" first. (d) assign operation sets according to the largest value of the ratio: (number of operations in a set)/(number of additional tool slots required). This rule is designed to assign as many operations as possible at the lowest cost in terms of additional tool magazine slots needed. These heuristics of Algorithm 2 will, like Algorithm 1, probably give solutions which do not conform to ideal groupings of machines as provided by closed queueing network analysis. In addition, if the use of maximally grouped sets of operations does not lead to a feasible solution, then alternative - 3 -

methods must be devised to define operation sets. This could be a difficult problem, although as Stecke [1981] has suggested, a starting point for defining sets can be provided by the L.P. relaxed solution to the nonlinear I.P. statement of the loading problem. The L.P. solution could be adjusted heuristically, to conform to the integrality requirement while remaining feasible. 2.2 Loading Procedures for Balancing and Unbalancing Objectives Closed queueing network analysis provides idealized groupings of identically tooled machines as well as corresponding optimal group workload allocation ratios (Stecke and Solberg [1982]). In general, the analysis proves that for balanced configurations of grouped machines, expected production is maximized by balancing the assigned workload per machine. Alternatively, better machine configurations are unbalanced, and in these situations, expected production is maximized by a specific unbalanced allocation of work. The following heuristics are designed to assign operations to machines in an effort to meet these allocation ratios. These ratios were developed to provide guidelines on how to allocate work to machines to maximize expected system productivity as measured by the amount of processing time which can be completed in a given period of time. Before the following loading algorithms are implemented, it is useful to obtain an estimate of the maximum workload. This is accomplished with the following calculations: (i) Sum the operation processing times, weighted by the part production ratios, of all operations for all part types (that will be simultaneously produced by the FMS over the next time period) that require a particular type of machine. Do this for each type of machine. (Part production ratios can be either provided by a production plan, or can be analytically derived ratios designed to maximize system productivity.) (ii) Divide each of these sums by the corresponding number of machines of each type to obtain an estimate of the workload per machine, if the workload were balanced. ALGORITHM 3 1. Order the machine types by nonincreasing average workload per machine. 2. Order machine groups within each machine type by nonincreasing number of machines in each group (as previously solved by the grouping problem). 3. Order operations, for all part types that shall be simultaneously machined, which require the same machine type, by nonincreasing processing time. 4. Assign the first operation from each of the lists developed in step 3, to the first machine group of the correct type. 5. The assignments of the remaining operations depend on whether the machines of a given type are organized into groups of equal or unequal size: (a) Equal Size Machine Groups (requires the Balancing Loading Objective). It is necessary to assign operations from their ordered lists to their corresponding required machine types. Thus, the following allocation procedure is repeated for each list. Suppose there are L machine groups for some list. Consecutively assign the first L operations from this list to the L machine groups. Consecutively assign the next L operations, but in reverse machine group order. For example, machine group one will contain operations 1, 2L, 2L + 1, 4L, 4L + 1, etcetera. Machine group two will contain operations 2, 2L - 1, 2L + 1, etcetera. (b) Unequal Size Machine Groups (requires the Unbalancing Loading Objective) - 4 - _- i, - - - T 'tl- -

The following procedure is repeated for each operation list as they were defined in step 3: Corresponding to each list is a set of machine groups which were ordered in step 2. Suppose these groups are labeled:,=l,...,L, with the number of machines in the i-th group denoted by Min. The allocation rule is to assign the next ML operations to the ~-th group, for %=1,...,L. When E M1 operations have been assigned, continue the process with =l1,2,..L., Repeat until all operations have been assigned. Figure 1 further illustrates Algorithm 3(a). Here, nine machines of the same type have been placed into three equal sized groups. Operations one to nine have been allocated thus far, as indicated by the numbers in the rectangles. The height of each rectangle is proportional to the operation processing time. The rationale for reversing the allocation across groups, in an effort to balance workload, is evident from Figure 1. If the processing times are highly variable, then it may be worthwhile to deviate from the rigid allocation procedure by skipping a group that appears to have an excess workload, or allocating an extra operation to an underloaded group, or by making adjustments (i.e, pairwise exchanges) after an initial solution has been found. 2 8 MGI MG2 MG3 X;=3 Figure 1. Three Equal-Sized Groups Containing Nine Machines. Figure 2 illustrates Algorithm 3(b). There are seven machines of the same type placed into groups of four, two, and one machines. Operations one to 14 have been assigned thus far, as indicated by the numbered rectangles. The height of each rectangle is a measure of the operation processing time. The X* values are hypothetical optimal allocation ratios which would usually be obtained from using the closed queueing network model. These ratios are guidelines which could be used to measure the "goodness" of a particular heuristic (as well as an optimal) solution. Consistent with the relative magnitude of these ratios, the heuristic procedure described attempts to assign slightly more than an average amount of processing time to the larger groups and slightly less than average to the smaller groups. X2 XI — 4 3 2 X3 5 7 MGI MG2 MG3 X = 4.25 X2.= a. X3 0.85 Figure 2. Seven Machines Partitioned Into Unequal Sized Groups. - 5 -

A more comprehensive example demonstrating Algorithm 3 will now be given. Figure 3 illustrates a 13-machine manufacturing system containing three types of machines which have been arranged into six groups. Optimal allocation ratios X are specified for each group. According to Step 1, machine types have been ordered such that: the workloads per machine of type 1 > machine 2 > machine type 3. For each type of machine, the groups have been ordered such that the largest groups are first (Step 2). Table 3 contains the ordered operations for all parts and the type of machine required. As specified by Step 3, operations have been ordered by largest processing time first. mll mt2 mt3 MB X450. 85 X,=1.95 X4-1.95 X6~4.25 Figure 3. Thirteen Machines of Three Machine Types Partitioned Into Six Groups. Table 3 Operations Ordered According to LPT First Since the groups for machine type 1 are of unequal size, Algorithm 3 is followed. The number of operations assigned to each group is equal to the number of machines in each group. Then the process is repeated until all operations have been assigned. See Figure 4. 4 13 Alcto of prtosf th Thre MahnIS 3 8 a MGI MG2 3 4 5 6 Figure 4. Allocation of Operations for the Thirteen Machine FMS. - 6 -

There are three groups of type 2 machines. Since groups three and four have equal numbers of machines and group five has a different number, a combination of Algorithm (3a) and (3b) is applied. Groups three and four will be assigned operations on the forward and reverse pass. Group five will be assigned an operation at the end of the reverse pass. Machine type three has only one group of four machines, so all operations are simply assigned to it in order. 3. SUMMARY AND FUTURE RESEARCH This paper presents several heuristics for determining how machine tool magazines in a flexible manufacturing system can be loaded to meet simultaneous production requirements of a number of different part types. This loading problem is multicriteria in nature, and hence, no one of the heuristics introduced would likely meet the needs of all FMSs. Future research is needed to better define the variety and character of loading objectives, how the loading problem links with the other four FMS production planning problems presented, and how loading and real time scheduling of parts on a system interact. It seems that detailed simulation of real systems could be used to help decide these issues. BIBLIOGRAPHY BERRADA, MOHAMMED and STECKE, KATHRYN E., "A Branch and Bound Approach for Machine Loading in Flexible Manufacturing Systems," Working Paper No. 329, Division of Research, Graduate School of Business Administration, The University of Michigan, Ann Arbor MI (April 1983). JOHNSON, D. S., "Near Optimal Bin Packing Algorithm," Ph.D. dissertation, Mathematics Department, M.I.T., Cambridge MA (1973). STECKE, KATHRYN E., "Experimental Investigation of a Computerized Manufacturing System," Master's Thesis, School of Industrial Engineering, Purdue University, W. Lafayette IN (December 1977). STECKE, KATHRYN E., "Production Planning Problems for Flexible Manufacturing Systems," Ph.D. dissertation, Department of Industrial Engineering, Purdue University, W. Lafayette IN (August 1981). STECKE, KATHRYN E., "A Hierarchical Approach to Production Planning in Flexible Manufacturing Systems," in Proceedings, Twentieth Annual Allerton Conference on Communication, Control and Computing, Monticello IL (October 6-8, 1982). STECKE, KATHRYN E., "Formulation and Solution of Nonlinear Integer Production Planning Problems for Flexible Manufacturing Systems," Management Science, Vol. 29, No. 3, pp. 273-288 (March 1983). STECKE, KATHRYN E. and MORIN, THOMAS L., "Optimality of Balanced Workloads in Flexible Manufacturing Systems," Working Paper No. 289, Division of Research, Graduate School of Business Administration, The University of Michigan, Ann Arbor MI (January 1982). STECKE, KATHRYN E. and SOLBERG, JAMES J., "Loading and Control Policies for a Flexible Manufacturing System," International Journal of Production Research, Vol. 19, No. 5, pp. 481-490 (September-October 1981). STECKE, KATHRYN E. and SOLBERG, JAMES J., "The Optimality of Unbalanced Workloads and Machine Group Sizes for Flexible Manufacturing Systems," Working Paper No. 290, Division of Research, Graduate School of Business Administration, The University of Michigan, Ann Arbor MI (January 1982). - 7 -