DONG-HO LEE [1]

YEONG-DAE KIM [2]

The loading problem in a Flexible Manufacturing System (FMS) involves allocating operations and associated cutting tools to machines for a given set of parts. There may be different environments for the loading problem that result from three ways of grouping machines in an FMS, i.e., no grouping, partial grouping, and total grouping. Unlike most previous studies on the loading problem for the configurations of no grouping and total grouping, this paper focuses on the loading problem resulting from partial grouping, in which each machine is tooled differently but each operation can be processed by one or more machines. Two types of heuristic algorithms are suggested for the loading problem with the objective of minimizing the maximum workload of the machines. Performances of the suggested loading algorithms are tested on randomly generated test problems and the results show that the suggested algorithms perform better than existing ones. In addition, it is found from simulation experiments that loading plans f rom partial grouping give significantly better performance than those from total grouping.

1. Introduction

For the efficient operation of a Flexible Manufacturing System (FMS), a number of decisions have to be made before the FMS begins to produce parts. Such decision problems include those of selecting subsets of part types for immediate and simultaneous production, the partitioning of machines of each type into machine groups, determining relative ratios at which the selected part types are produced, allocating operations and associated cutting tools to machines or machine groups, and allocating pallets and fixtures to the selected part types. These problems are called the part type selection problem, the machine grouping problem, the production ratio problem, the loading problem, and the resource allocation problem, respectively [1]. Amongst these problems, this paper considers machine grouping and loading problems for a given set of selected part types. The loading problem depends not only on the part type selection problem but also on the grouping problem in the sense that a solution of the grouping problem o r a result of decisions on machine grouping constitutes the environment for the loading problem. Such decisions on machine grouping are related to the number of machine groups and the number of machines in each group as well as how the machines are grouped.

There are three ways to group machines, (i) no grouping; (ii) partial grouping; and (iii) total grouping. As a result of machine grouping, physically identical machines can be configured to process the same or different sets of operations according to the tooling of the machines. In the partial grouping and no grouping configurations, machines are tooled differently. While each operation is assigned to only one machine in the no grouping configuration, an operation can be processed by one or more machines in the other two configurations. In the total grouping configuration, machines are partitioned into groups and all machines in the same group are identically tooled so that they can process the same set of operations. On the other hand, in the partial grouping configuration, machines are tooled differently, as in the case of no grouping. However, multiple machines can be assigned to each operation, which means that each operation is allocated to one or more machines. In other words, a machine group is define d logically (not physically) for each operation in the partial grouping configuration.

When an operation is assigned to multiple machines, a set of tools (at least one copy of each tool) required for the operation has to be loaded on each of the machines. Since machines are tooled differently in the partial grouping configuration, each machine can be considered as a virtual cell. The system has to be reconfigured when a new set of part types is selected, that is, sets of virtual cells may differ for different sets (or groups) of selected part types. Note that the parts can be moved between the machines according to the process plans of the parts and the loading plans of operations for the parts. In other words, parts are allowed to move between cells rather than being confined to a single cell. The number of duplicate tools (or tool copies) required for an operation is equal to the number of machines to which the operation is assigned. (More copies of certain tools may be required because of the finite tool lives). In general, it can be seen that total grouping and no grouping are special forms of partial grouping.

The three grouping configurations for a four-machine case are illustrated in Fig. 1(a-c). In the total grouping configuration (Fig. 1b), the four machines are partitioned into two groups and the number of machines in each group (called the group size) is two. (In this case, the total number of tool slots available in effect for tool assignments in the FMS is equal to two times the number of tool slots on one machine, since machines in the same group should be identically tooled). On the other hand, in the partial grouping configuration (Fig. 1c), the machines are not partitioned into groups, as in the total grouping configuration, but more than one machine can process an operation. For example, in the figure, operation 1 is assigned to machines 1 and 2, and operation 2 is assigned to machines 1, 3, and 4. Note that more (routing) flexibility can be obtained with the same or a smaller number of machines through partial grouping than total grouping. Therefore, partial grouping is easier to implement or costs l ess (for obtaining more flexibility) in reality and the concept of partial grouping is preferred by system managers.

There are a number of research articles on planning problems associated with total grouping configurations. For total grouping configurations in which the machine groups are of the same size, it is optimal in terms of throughput maximization to allocate the workloads equally, this process is called balancing. As stated earlier, the group size (of a machine group) is defined as the number of machines in the machine group. In the case where the sizes of the machine groups are not the same, it is better to assign larger workloads to machines in larger groups, and this process is called unbalancing [2]. Kim [3] finds through a simulation study that balancing workloads is closely related to minimizing makespan and suggests that the former be used as a surrogate objective for the latter since the former is easier to deal with.

Stecke [1] formulates the loading problem with the objective of balancing workloads as a nonlinear mixed integer program and solves it through a linearization technique. Berrada and Stecke [4] develop a branch and bound algorithm that gives [epsilon]-optimal solutions. Lashkari et al. [5] suggest another nonlinear integer model for the loading problem with two objectives; (i) minimizing transportation load; and (ii) minimizing frequency of refixturing; and solve a linearized version of the problem with commercial integer programming software. For the same problem, Wilson [6] presents a simple integer linear programming formulation avoiding nonlinearities and solves it with a commerical integer programming software program. Kim and Yano [7] have presented another branch and bound algorithm for the objectives of (un)balancing the workloads.

Since it is not easy to find an optimal solution for a large-sized problem, various heuristic algorithms have been suggested. Shanker and Tzen [8] consider a bicriterion objective of balancing the workloads and minimizing the number of late jobs for the loading and sequencing problems and propose a heuristic algorithm in which due dates of jobs are considered. Shanker and Srinivasulu [9] develop a two-stage branch and backtrack procedure and heuristics for a bicriterion objective of balancing the workloads and maximizing the throughput. Mukhopadhyay et al. [10] propose an improved heuristic using the essentiality ratio, which is used to identify a machine-operation pair that maximizes throughput and minimizes unbalance. On the other hand, Kim and Yano [11] suggest heuristic algorithms for the objectives of workload balancing and unbalancing by regarding the loading problem as a two-dimensional bin-packing problem, and Kuhn [12] suggests a heuristic using an algorithm for the generalized assignment problem. L ee and Stecke [13] consider the grouping and loading problems in flexible flow systems with the objective of maximizing system throughput, and suggest a heuristic algorithm that decomposes the original problem into three interrelated subproblems. Interested readers are referred to the work of Rajagopalan [14], Stecke [15], O'Grady and Menon [16], Sarin and Chen [17], Brettauer and Venkataramanan [18], Co et al. [19], Kumar et al. [20], Ram et al. [21], Kirkavak and Dincer [22], Moreno and Ding [23], and Tang et al. [24] for other heuristics for the loading problems.

Most of the studies on the FMS loading problem have been performed on total grouping or no grouping configurations. There has been little work performed on the loading problem associated with partial grouping configurations. Stecke and Raman [25] consider the loading problem with the objective of (un)balancing workloads for the no grouping, total grouping, and partial grouping configurations and suggest a heuristic that is modified from the Longest Processing Time (LPT) algorithm for bin-packing problems. The heuristic can be used for no grouping, partial grouping and total grouping configurations. To the best of our knowledge, there is no paper in the published literature that explicitly considers the loading problem in partial grouping, this is despite the point that partial grouping can give more flexibility and result in better system performance than total grouping.

This paper focuses on the loading problem associated with the partial grouping configuration with the objective of minimizing the maximum workload of the machines (or palancing the workloads). Two types of heuristic algorithms are suggested. Algorithms of the first type directly allocate operations and their associated workloads to machines, while algorithms of the other type select a set of machines for each operation and then allocate requirements for the operations to the selected machines. The performance of the suggested loading algorithms is tested on randomly generated test problems. In addition, to compare the partial grouping and total grouping configurations in terms of the effect on performance of FMSs and to see whether the algorithms for the partial grouping configuration work better than those for the total grouping configuration simulation experiments are done using the loading algorithms developed in this research and those for systems with totally grouped machines.

In the next section, the loading problem considered in this paper is described in more detail with a mathematical formulation, and two types of solution approaches are briefly explained. Sections 3 and 4 present several solution algorithms using the two types of solution approaches. Results of computational tests on the performance of the suggested algorithms are given in Section 5. Finally, Section 6 concludes the paper with recommendations for future research.

2. The loading problem and solution approaches

The FMS considered here consists of several identical machines, each with an automatic tool changer and a tool magazine of a limited capacity. These machines can perform different sets of operations if tooled differently. To perform an operation, one or more tools are required, and each tool requires one or more slots in the tool magazine. In addition, several operations may share the same tools (a tool may be used for two or more operations) in the system, which is represented by the term, tool sharing or tool commonality.

In the problem considered here, it is assumed that a set of part types has been selected to be produced simultaneously during the upcoming production period, and production quantities for the parts have been determined. Operations required for the selected part types are to be assigned to the machines. In this study, operations that require different processing times are considered as different operations even though they are of the same type. For example, drilling operations for different part types are treated as different operations even though they require the same set of tools if their processing times are different. The loading problem is the problem of allocating operations and tools to the machines with the objective of minimizing the maximum workload of the machines subject to tool magazine capacity constraints. For a clear description of the problem, we formulate the loading problem as an integer linear problem. The following notation is used in the formulation.

i = index for operations, i [epsilon] I;

j = index for machines j [epsilon] J;

t = index for tools, t [epsilon] T;

[P.sub.i] = processing time of operation i;

C = capacity (number of tool slots) of a tool magazine of a machine;

[D.sub.i] = processing requirement (in units) of operation i (sum of production quantities of parts requiring operation i);

[s.sub.t] = number of tool slots needed for tool t;

[a.sub.it] = {1 if operation i requires tool t,

{0 otherwise.

[x.sub.ij] = {1 if operation i is assigned to machine j,

{0 otherwise.

[y.sub.ij] = {1 if tool t is assigned to machine j,

{0 otherwise.

[w.sub.ij] = processing requirement (in units) for operation i that is assigned to machine j.

The integer linear program is given below.

(P) Minimize Z,

subject to

[[sigma].sub.i[epsilon]I] [p.sub.i][w.sub.ij] [less than or equal to] Z for all j, (1)

1 [less than or equal to] [[sigma].sub.j[epsilon]J] [x.sub.ij] [less than or equal to] \J\ for all i, (2)

[w.sub.ij] [less than or equal to] [D.sub.i][x.sub.ij] for all i and j, (3)

[[sigma].sub.j[epsilon]J] [w.subj.ij] = [D.sub.i] for all i, (4)

[[sigma].sub.t[epsilon]T] [s.sub.t][y.sub.tj] [less than or equal to] C for all j, (5)

[a.sub.it][x.sub.ij] [less than or equal to] [y.sub.tj] for all i, j and t, (6)

[w.sub.ij] [greater than or equal to] 0 and integer for all i and j, (7)

[x.sub.ij], [y.sub.tj] [epslion] {0, 1} for all i, j and t. (8)

In the formulation, the objective function with constraint set (1) leads to workload balancing, i.e., minimization of the maximum workload, which is represented by Z. It is reported that this objective is closely related with minimization of makespan for a given set of part types [3,7]. Constraint set (2) ensures that the number of machines assigned to each operation should not be greater than the total number of machines. Constraint set (3) represents relationship between [w.sub.ij] and [x.sub.ij], that is, processing requirements of operation i can be allocated to machine j ([w.sub.ij] [greater than] 0) only if [x.sub.ij] = 1. Processing requirements of operations can be satisfied by constraint set (4), and the tool magazine capacity constraints are represented by (5). Constraint set (6) ensures all tools required for an operation be loaded on the machine to which the operation is allocated. Note that constraint (6) along with (5) limits the number of parts that can be processed on a machine.

As stated earlier, in this study, two solution approaches are suggested for the loading problem. In the first approach (called the direct approach in this paper), we let the number of machines to be assigned to each operation be the same for all operations. The number can be selected from integers, {l, 2, ..., \J\}, where \J\ is the number of machines in the system. In this approach, the number of machines that gives the best feasible loading plan is selected according to the following steps. First, processing requirement (in units) of each operation is divided into batches according to the number (of machines) obtained in the first step. Here, requirement of each batch for operation i is given as an integer closest to [D.sub.i]/[[sigma].sub.j[epsilon]J][x.sub.ij]. Such rounding of processing requirements of these divided batches should be done in such a way that their sum should be [D.sub.i] for operation i. Then, these batches are allocated to the machines using algorithms for the bin-packing problem, whic h is the problem of assigning items of various sizes into bins for a given objective. In the bin-packing model, each machine (or machine group) and each operation are represented by a bin and an item, respectively. Kim and Yano [11] regard the loading problem (resulting from the configuration of total grouping) as a two-dimensional bin-packing problem in which the dimensions are associated with tool slots and processing times. Such a bin-packing model is used for solution of the loading problem in this paper.

In the second approach (called the decomposition approach in this paper), problem (P) is decomposed into two subproblems: the Operation Assignment Problem (OAP) and the Workload Allocation Problem (WAP). The OAP is the problem of selecting machines for each operation, while the WAP is the problem of allocating processing requirement of each operation to the machine(s) selected for the operation in the OAP. Formulations for the OAP and the WAP are given below.

(OAP) Find [x.sub.ij],

subject to (2), (5), (6) and (8).

(WAP) Minimize Z,

subject to (1), (3), (4) and (7).

In (OAP), there are [([2.sup.\J\] - 1)].sup.\I\] alternatives for assignment since there are ([2.sup.\J\] - 1) assignment alternatives for each operation. Note that (OAP) is not an optimization problem but a feasibility problem. On the other hand, (WAP) is an optimization problem with the same objective as that of problem (P). In (WAP), [x.sub.ij] is given as data, and it can be obtained from a solution of (OAP). In the decomposition approach, to obtain an optimal solution for the entire problem (P), (WAP) should be solved optimally for all alternatives for operation assignment. However, the number of alternatives increases exponentially as the problem size becomes large. Since (WAP) is an integer programming problem and it has to be solved many times for problem (P), it is difficult to obtain an optimal solution for a problem of a practical size. Because of such complexity of the problem, a heuristic algorithm is developed to generate a subset of (good) feasible solutions for (OAP) in this paper.

3. Algorithms for the direct approach

This section presents three algorithms which solve the loading problem directly without solving the operation assignment problem described in Section 2. Amongst the three algorithms, the first two follow the direct approach explained in the previous section, whilst the last one does not. However, it also solves the problem directly through a linear programming relaxation of the loading problem without decomposition.

3.1. The DR-LPT algorithm

In this algorithm, the number of machines that will be assigned to each operation is set to be the same for all operations and hence the processing requirement of an operation is divided into the same number of batches for all operations. These batches are allocated to machines by an LPT (Longest Processing Time) algorithm. This is a similar approach to that of Stecke and Raman [25], however while the number of batches is arbitrarily selected in Stecke and Raman [25], the algorithm suggested here checks for all alternatives for the number, i.e., from one to \J\, the total number of machines in the system. The algorithm is summarized below.

Procedure 3.1 (DR-LPT)

Step 0. Let Z = [infinity], and m = 1. (Z is the solution value, i.e., the maximum workload and m is the number of machines to be assigned to each operation).

Step 1. If m [greater than] \J\, stop. Otherwise, go to Step 2.

Step 2. Constitute batches for each operation by dividing processing requirement (in units) of an operation by m (to a nearest integer).

Step 3. Repeat the following steps until all batches are allocated to the machines (LPT algorithm).

(a) Select a batch with the maximum workload (processing requirement of a batch x unit processing time) among the set of batches not yet allocated to machine.

(b) Assign the selected batch to a machine with the minimum workload allocated to it so far (ties are broken arbitrarily). If the selected batch cannot be assigned due to the tool magazine capacity, let m = m + 1 and go the Step 1. Otherwise, go to (a).

Step 4. If Z is improved, update Z and save the solution. Let m = m + 1 and go to Step 1.

3.2. The DR-MUL algorithm

This algorithm is the same as DR-LPT except that each batch is allocated to machines by a MULTIFIT algorithm, which is a multi-pass algorithm for bin-packing problems. To find a near optimal solution, it makes repeated trials for batch assignments with different values of the machine capacities (processing time capacities). The solution is the smallest machine capacity with which all the batches can be allocated to the machines, and it is found by a bisection search method. In this algorithm, the First Fit Decreasing (FFD) and Best Fit Decreasing (BFD) rules are used to assign operations to machines. In FFD and BFD, all operations are sorted in a nonincreasing order of workloads and they are allocated to machines in this order. While FFD allocates each operation to the lowest-indexed machine into which the operation can be allocated without violating the machine capacity, BFD allocates each operation to a machine which will have the smallest remaining capacity after the operation is allocated to it.

In general, MULTIFIT algorithms need initial lower and upper bounds on the bin size (machine capacity, in this case). Loose bounds can be obtained easily. For example, a lower bound can be computed by dividing the sum of processing times of all operations by the number of machines and an upper bound can be set to be the sum of processing times. However, a better upper bound can be obtained from a feasible solution from other heuristics. In DR-MUL, the initial upper bound is set to be equal to the maximum workload of the machines in a solution obtained from DR-LPT. A detailed procedure is given below.

Procedure 3.2 (DR-MUL)

Step 0. Let Z = [infinity] ,and m = 1.

Step 1. If m [greater than] \J\, stop. Otherwise, go to Step 2.

Step 2. Constitute batches for each operation by dividing processing requirement of an operation by m.

Step 3. Allocate the batches to the machines as follows (MULTIFIT algorithm).

(a) Initialize the upper and the lower bounds on the capacities of machines.

(b) If difference of the lower and the upper bounds is close enough, go to Step 4. Otherwise, set the machine capacities to be the midpoint of the bounds.

(c) Allocate the batches to machines by the FFD (and BFD) rule. If all the batches can be assigned by neither of the two rules, let the current machine capacity be a new lower bound. Otherwise, let the current capacity be a new upper bound and go to (b).

Step 4. If Z is improved, update Z and save the solution. Let m = m + 1 and go to Step 1.

3.3. The LP relaxation algorithm

This algorithm solves the loading problem directly using the following linear program (PR), which is a relaxed problem of (P), but tool sharing is not considered in it.

(PR) Minimize Z,

subject to

[[sigma].sub.i[epsilon]I] [A.sub.i][x.sub.ij] [less than or equal to] C' for all j, (5')

[w.sub.ij] [greater than or equal to] 0 for all i and j, (7')

0 [less than or equal to] [x.sub.ij] [less than or equal to] 1 for all i and j, (8')

and (l),(2),(3),(4).

Here, [A.sub.i] denotes the number of tool slots needed for tools required by operation i and C' is a parameter representing the capacity of a tool magazine. In the formulation, constraint sets (5) and (6) of (P) are replaced by (5'), as tool sharing is not considered in (PR).

In the algorithm, problem (PR) is solved for different values of C'. A solution of (PR) may not be feasible for (P), since the solution does not necessarily satisfy the integrality constraints, (7) and (8). To obtain an integral solution after problem (PR) is solved for a value of C', a solution of (PR) is modified as follows. Let [[x.sup.*].sub.ij] and [[w.sup.*].sub.ij] denote a solution of (PR).

Procedure 3.3 (Modification of a solution)

Step 1. Let [x.sub.ij] = {1 if [[x.sup.*].sub.ij] [greater than] 0,/0 otherwise.

Step 2. Let [w.sub.ij] = [[[w.sup.*].sub.ij]], for all i and j, where [r] denotes the largest integer less than or equal to r.

Step 3. Modify [w.sub.ij] by allocating remaining production requirements ([D.sub.i] - [[sigma].sub.j[epsilon]J] 1 [w.sub.ij], for all i) to machines with the LPT algorithm.

Note that the modified solution, which is obtained after procedure 3.3 is applied to the solution of problem (PR), is not always feasible for the original problem (P). That is, solutions resulting from the above procedure may violate the tool magazine capacity constraints of the original problem (P) even if tool sharing is considered, since all [x.sub.ij]'s with [[x.sup.*].sub.ij][greater than] 0 are fixed to be 1. If the modified solution does not satisfy the tool magazine capacity constraints, problem (PR) is solved again after increasing the value for C'. If it satisfies the constraints, problem (PR) is solved after decreasing the value for C'. By trying several values for C' (with a bisection search method), this algorithm obtains as many solutions and selects the best feasible solution that satisfies the constraints of the original problem (P). Since there may be cases in which a feasible solution is not found for any of these values for C', the final step of this algorithm is added to find a feasible so lution for the original problem (P) by modifying a solution of the relaxed problem (PR) until a feasible solution is found. The algorithm is summarized in the following.

Procedure 3.4 (LP-RILX)

Step 0. Let Z = [infinity], and let the upper and the lower bounds of C' be the total number of tool slots needed for all operations and C (the tool magazine capacity in problem (P)), respectively.

Step 1. If the lower and the upper bounds are close enough, go to Step 3. Otherwise, let the value for C' be the midpoint of the bounds.

Step 2. Solve problem (PR) and modify the solution with Procedure 3.3. If the resulting solution is feasible for problem (P), let the current value for C' be a new upper bound (and if the solution is improved, update Z and save the solution). Otherwise, let the current value for C' be a new lower bound. Go to Step 2.

Step 3. If a feasible solution has been obtained (if Z [less than] [infinity]), stop. Otherwise, solve (P) after letting C' be the tool magazine capacity (C) and repeat the following steps until a feasible solution is found.

(a) Find [x.sub.[i.sup.*][j.sup.*]] with the minimum value of [[w.sup.*].sub.ij][p.sub.i] among [x.sub.ij]'s that are fixed at 1 (find ([i.sup.*],[j.sup.*]) = arg [min.sub.(i,j)] {[[w.sup.*].sub.ij][p.sub.i]\[[x.sup.*].sub.ij] = 1}).

(b) Solve problem (PR) after letting [x.sub.[i.sup.*][j.sup.*]] = 0 and modify the solution with Procedure 3.3.

4. Algorithms for the decomposition approach

This section presents three algorithms which solve the loading problem in two steps by decomposing it into the operation assignment problem and the workload allocation problem. In these algorithms, alternatives for operation assignments are obtained from solutions of [OAP], and [WAP] defined by each of these alternatives is solved to find a solution of [P]. Since there are a large number of feasible alternatives for operation assignments, only a portion of the alternatives are considered in the algorithms.

4.1. Generating alternatives for operation assignment

The method suggested in this paper employs the Maximal Intersection and Minimal Union (MIMU) algorithm, which was originally developed for a part grouping problem in a system with a single flexible machine for the objective of minimizing the number of part groups [26]. In this paper, the MIMU algorithm is used to assign operations to machines while satisfying tool magazine capacity constraints. In order to describe the algorithm, we define the following.

(i) A class S is a set of operations that can be processed together without additional tool setups. That is, S is a class if and only if

[sigma][S.sub.t][greater than equal to] C,

t[epsilon]{[U.sub.i[epsilon]S][A.sub.i]}

where [A.sub.i] is the set of tools required for operation i and C is the tool magazine capacity.

(ii) A set S of operations is called maximal class if S satisfies

[sigma][s.sub.t][greater than equal to] C,

t[epsilon]{[U.sub.i][epsilon]S][A.sub.i]}

and

[sigma][S.sub.t][greater than]C

t[epsilon][U.sub.i[epsilon]SU]{l]}

for any operation 1 [epsilon] S.

The MIMU algorithm used in this paper finds a maximal class for each machine using the following rules.

(i) Select an operation i that maximizes the total number of common tools required by operation i and operations already included in the current class (maximal intersection).

(ii) If there is a tie in (i), select an operation that minimizes the number of tools needed by operation i but not by operations in the current class (minimal union).

By use of the MIMU algorithm, we can easily generate alternatives for operation assignment satisfying the tool magazine capacity. An alternative for operation assignment corresponds to a set of maximal classes for the machines, since operations included in a maximal class for a machine are to be assigned to the machine. Note that all the maximal classes satisfy the tool magazine capacity constraints, since the constraints are considered explicitly (by the definition of maximal classes). To start the MIMU algorithm, an operation, which is called the initial operation, should be first selected. If different operations are selected as initial operations, different maximal classes may be obtained. In other words, different sets of operations can be assigned to a machine, if the algorithm starts with different initial operations. Hence, several alternatives for operation assignment can be generated if several different sets of operations are selected as initial operations for the machines.

To generate multiple alternatives, an initial alternative is obtained by forming a maximal class for each machine, and then several other alternatives are obtained by changing the maximal classes of the machines. To form a maximal class for a machine in the initial alternative, operations are assigned to the machine in a nondecreasing order of the number of machines assigned to the operations so far (ties are broken by assigning an operation with a larger [D.sub.i][p.sub.i], value first) until the tool magazine capacity constraint is violated. From the initial alternative, another alternative can be obtained by forming another maximal class for a machine with the MIMU algorithm for an arbitrarily selected initial operation. The number of alternatives generated (from an initial operation assignment alternative) with this operation assignment method is \I\ X \J\, where \I\ and \J\, represent the numbers of operations and machines, respectively, since \Ioperations are used as an initial operation for each machi ne. Note that the number of all possible alternatives for operation assignments is [\J\.sup.\I\]. This procedure for generating multiple alternatives is summarized below.

Procedure 4.1 (Generating alternatives for operation assignment)

Step 1. (Generate an initial alternative) For j = 1 to /J/, do:

(a) Find the number ([n.sub.i]) of machines assigned to each operation so far. (Initially, they are all zero).

(b) Sort operations in a nondecreasing order of [n.sub.i]'s (in the case of ties, in a nonincreasing order of the value of [D.sub.i][p.sub.i]). In this order, assign one by one as many as operations possible to machine j without violating the tool magazine capacity constraint.

Step 2. (Generating multiple alternatives) For j = 1 to /J/, do: For i = 1 to /1/, do: Form a maximal class for machine j with the MIMU algorithm starting with operation i. Obtain a new alternative for operation assignment by replacing the set of operations assigned to machine j in the initial alternative with the set of operations included in the newly formed maximal class. If this alternative is feasible, save the alternative.

4.2. Decomposition algorithms

Each alternative for operation assignment obtained in Section 4.1 can be defined in two different ways: (i) by specifying a set of machines for each operation, i.e ., [X.sub.ij], for all i and j; or (ii) by specifying the number of machines assigned to each operation, i.e., [[[sigma].sub.j][epsilon].sub.j] [x.sub.ij] for all i. Among the three decomposition algorithms suggested in this paper, the first one (DC-LP) uses the former definition, while the other two (DC-LPT and DC-MUL) use the latter one.

4.2.1. The DC-LP algorithm

For each alternative for operation assignment obtained from procedure 4.1, the following linear program (WALP) is solved to obtain a solution for workload allocation. In (WALP), values for [X.sub.ij] are fixed at [[X.sup.*].sub.ij] that are defined by a given alternative for operation assignment. Tool magazine capacity constraints are not included since the given alternative already satisfies the constraints.

(WALP) Minimize Z,

subject to

[[sigma].sub.i[epsilon]I][P.sub.i] X [W.sub.ij] [less than or equal to] Z for all j, (1)

[w.sub.ij] [less than or equal to] [D.sub.i] X [[x.sup.*].sub.ij] for all I and j, (3')

[[sigma].sub.j][epsilon]j][w.sub.ij] = [D.sub.i] for all i, (4)

[w.sub.ij] [greater than or equal to] 0 for all i and j. (7')

In this algorithm, after a solution of (WALP) is obtained, values of [w.sub.ij] are rounded to integers. For the purpose, the algorithm uses Procedure 3.3, which was used in the LP relaxation algorithm. The algorithm is summarized below.

Procedure 4.2 (DC-LP)

Step 1. Let Z = [infinity] and obtain a set A of alternatives for operation assignment using procedure 4.1.

Step 2. If A = [Empty Set], stop. Otherwise, select an alternative a in A.

Step 3. Solve (WALP) that is defined by the selected alternative a. Find an integer solution using Procedure 3.3.

Step 4. If Z is improved, update Z and save the solution. Let A = A\{a} and go to Step 2.

4.2.2. The DC-LPT algorithm

Unlike DC-LP, this algorithm defines each alternative for operation assignment as the number of machines assigned to each operation, i.e., [[[sigma].sub.j][epsilon]J] for all i. This algorithm is the same as DR-LPT (Procedure 3.1) except that the number of machines assigned to each operation is obtained by Procedure 4.1. Therefore, the numbers of machines for different operations may differ in this algorithm. Note that they are equal in DR-LPT.

Procedure 4.3 (DC-LPT Algorithm)

Step 1. Let Z = [infinity]. Obtain a set A of alternatives for operation assignment using Procedure 4.1.

Step 2. If A = "", stop. Otherwise, select an alternative a in A. For the alternative, obtain [n.sub.i], the number of machines assigned to operation i, for all i.

Step 3. Constitute batches for each operation by dividing processing requirement of operation i by [n.sub.i], (to an integer) for all i.

Step 4. Assign the batches to the machines with the LPT algorithm described in Procedure 3.1.

Step 5. If Z is improved, update Z and save the solution. Let A = A\{a} and go to Step 2.

4.2.3. The DC-MUL algorithm

This algorithm is the same as DC-LPT except that batches are allocated to machines by a MULTIFIT algorithm. In the MULTIFIT algorithm, an initial upper bound is set to be equal to the maximum workload of the machines in a solution obtained from DC-LPT.

Procedure 4.4 (DC-MUL)

Step 1. Let Z = [infinity] and obtain a set A of alternatives for operation assignment using Procedure 4.1.

Step 2. If A = [Empty Set], stop. Otherwise, select an alternative a in A. For the alternative, obtain [n.sub.i], the number of machines assigned to operation i, for all i.

Step 3. Constitute batches for each operation by dividing processing requirement of operation i by [n.sub.i], for all i.

Step 4. Assign the batches to the machines with the MULTIFIT algorithm given in Procedure 3.2.

Step 5. If Z is improved, update Z and save the solution. Let A = A \ {a} and go to Step 2.

5. Computational experiments

Computational tests are done to compare six loading algorithms presented in this paper. For the test, 20 problems were generated randomly for several combinations of three levels for the number of operations (20, 30, and 40), three levels for the number of machines (4, 6, and 8), and two levels for the tightness of tool magazine capacity constraints (tight and loose). Capacity (the number of tool slots) of a tool magazine was set to be 80 (tight) or 100 (loose). The processing time for each operation was randomly generated from DU(20, 100), where DU(a, b) denotes a discrete uniform distribution with a range [a, b]. The number of tools needed for each operation was generated from DU(5, 15), and the number of tool slots needed for each tool was selected from 1, 2 and 3, with probabilities 0.7, 0.1 and 0.2, respectively. All the algorithms were coded in C and a subroutine of CPLEX 3.0 was used to solve linear programs in DC-LP and LP-RLX. Tests were done on a SUN/4 workstation, which is approximately six to 10 t imes slower (requires six to 10 times longer CPU times) than a Personal Computer with a Pentium processor.

Solutions from the algorithms are compared with each other using the performance ratio as an index; this is the ratio of a solution to a lower bound, i.e., [[[sigma].sub.i][epsilon]I] [P.sub.i] X [D.sub.i]//J/. The results are given in Tables 1 and 2 which shows the average and standard deviation of performance ratios of the loading algorithms. It can be seen that the newly suggested algorithms with the exceptions of LP-RLX and DC-LP outperformed DR-LPT, which is an enhanced version of the algorithm suggested by Stecke and Raman [25]. Amongst the algorithms, DC-LPT and DC-MUL gave better solutions than the others. The performance ratios of DC-MUL were very small, even though a lower bound, not the optimal solution, was used to compute the ratio. The performance of all the loading algorithms became worse (in terms of the deviation from the lower bounds) as the tool magazine capacity constraints became tighter.

From the result that DC-LPT outperforms DR-LPT, it can be argued that good alternatives for operation assignment result in better loading plans and that the MIMU algorithm in the loading algorithm generates such alternatives. As MULTIFIT algorithms generally outperform LPT algorithms, DC-MUL is slightly better than DC-LPT. Amongst the methods for workload allocation, rather simple bin-packing algorithms were better than the more sophisticated LP-based algorithm, that is, DC-LPT and DC-MUL were better than DC-LP. This may be because a good quality of an LP solution is lost when it is modified to an integer solution. Performance of LP-RLX was not consistent, since it could not find good alternatives for operation assignment in some cases.

Table 3 shows the CPU time for the loading algorithms. Decomposition algorithms require a longer time than the algorithms of the direct approach (except for LP-RLX), since the former consider more alternatives for operation assignment. Although the loading problem may have to be solved several times to obtain production and setup plan for a given set of orders, it is not likely that the problem will be solved too frequently or has to be solved very quickly for real time decisions in most real systems. Also, the computer (a SUN/4 workstation) used in this computational test is much slower than currently available Personal Computers. It was used because the version of the LP software CPLEX 3.0 used in DC-LP and LP-RLX in the experiment could only be run on SUN workstations). Therefore, loading problems in most real FMSs can be solved by DC-LPT or DC-MUL in a reasonable amount of time even on a Personal Computer. In fact, problems with 150 operations and eight machines could be solved in 10 and 20 minutes by DC -LPT and DC-MUL, respectively, on a Personal Computer with a Pentium processor.

As stated earlier, there are different environments for the loading problem that result from the three ways of grouping machines in an FMS, i.e., no grouping, partial grouping, and total grouping. Different grouping methods cause different situations for the loading problem, and the performance of loading plans under these different situations may differ. Therefore, we compared the algorithms suggested in this study with existing algorithms developed for the total grouping configuration via a series of simulation experiments. Since the no grouping situation is known to be dominated by total grouping in system throughput, the no grouping configuration is not included in the comparison [2]. A brief description of the simulation model used in the experiments and the results are given in the Appendix.

Results of the simulation experiments (given in the Appendix) showed that the algorithms suggested in this paper for partial grouping were better than the existing algorithms for total grouping. This may be because partial grouping and its corresponding loading plans help to cope with system disturbances such as machine breakdowns more easily by providing more routing flexibility. In addition, systems with a small number of machines can be benefited by partial grouping, since it is difficult to group machines totally because of tool magazine capacity constraints and hence it is difficult to get enough flexibility through total grouping in such systems. On the contrary, such systems can be configured with partial grouping and higher system performance can be obtained by assigning more machines to certain operations.

6. Concluding remarks

In this paper, we considered a loading problem for the partial grouping configuration in flexible manufacturing systems with the objective of minimizing the maximum workload of the machines. Several heuristic algorithms were suggested for the loading problem. To compare the suggested algorithms with an existing one, computational experiments were done on randomly generated test problems. In addition, simulation experiments were done to investigate the effects of grouping methods and loading algorithms on system performance. The results showed that the suggested algorithms performed better than the existing one and that loading plans from the partial grouping configuration gave significantly better results than those from the total grouping configuration. Research on the loading problem for the partial grouping configuration may be more important since the partial grouping configuration not only gives a better performance than the total grouping configuration but also is a more practical or realistic alternati ve for obtaining pooling effects with a small number of machines.

This research can be extended in several ways (certain extensions have already been performed). First, the case in which the processing time differs on different machines for the same operation should be investigated. This reflects the case in which an operation can be processed on machines of different types. In this case, loading algorithms based on the bin-packing algorithms may not be used, while those based on linear programming may be useful. Also, it would be of interest to combine the loading algorithm with those for other related problems such as the part type selection problem or the scheduling problem. Since the part type selection and loading problems are interrelated with each other [27,28], the two problems may have to be solved simultaneously. In this case, the loading algorithm suggested in this paper can be used as a subroutine for an algorithm for part type selection [29]. In addition, an effective scheduling method is needed for an FMS scheduling problem resulting from loading plans for th e partial grouping configuration [30]. As discussed in the Appendix, when scheduling and controlling part flows, it is difficult to adhere to a loading plan obtained by the suggested loading algorithm for partially grouped machines. In other words, planned workloads for the machines determined at the planning stage may not be maintained or realized at the scheduling stage. A systematic procedure for dispatching parts to available machines is needed to realize the advantage of having more flexibility through partial grouping. Finally, additional costs of tooling, such as tool purchase costs and other tool-related costs, required to get more flexibility through grouping should also be considered. For example, determination of the number of tool copies for each tool type is another important decision problem in operating FMSs. Tradeoffs between the costs and benefits of having more tools have to be analyzed to solve such tool requirements planning or tool provisioning problems.

Acknowledgments

This research was supported in part by The Institute for Advanced Engineering, Daewoo Business Group.

Biographies

Dong-Ho Lee is a research assistant at the Department of Mechanical Engineering, the Swiss Federal Institute of Technology, Lausanne (EPFL). He received a BS from Seoul National University, and an MS and a Ph.D. degree from Korea Advanced Institute of Science and Technology (KAIST) all in Industrial Engineering. His research areas include design and operation of manufacturing and remanufacturing systems, production planning and scheduling, simulation applications, and manufacturing strategy.

Yeong-Dae Kim is a Professor at the Department of Industrial Engineering, KAIST. He received a BS from Seoul National University, an MS from KAIST both in Industrial Engineering, and a Ph.D. degree from the university of Michigan in Industrial and Operations Engineering. His research areas include design and operation of manufacturing systems, operations scheduling, and production and inventory management. He is a senior member of IIE and a member of INFORMS, ORS and IEEE.

(1.) Department of Mechanical Engineering, The Swiss Federal Institute of Technology -- Lausanne (EPFL) CH -- 1015, Lausanne, Switzerland

(2.) Department of Industrial Engineering, Korea Advanced Institute of Science and Technology, Yusong-gu, Daejon 305-701, Korea E-mail: ydkim@convex.kaist.ac.kr

References

(1.) Stecke, K.E. (1983) Formulation and solution of nonlinear integer production planning problem for flexible manufacturing systems. Management Science, 26, 273-288.

(2.) Stecke, K.E. and Solberg, J.J. (1985) The optimality of unbalancing both workloads and machine group sizes in closed queueing networks of multiserver queues. Operations Research, 29, 53-75.

(3.) Kim, Y-D. (1993) A study on surrogate objectives for loading a certain type of flexible manufacturing systems. International Journal of Production Research, 31, 381-392.

(4.) Berrada, M. and Stecke, K.E. (1986) A branch and bound approach for machine load balancing in flexible manufacturing systems. Management Science, 32, 1316-1335.

(5.) Lashkari, R.S., Dutta, S.P. and Padhye, A.M. (1987) A new formulation of operation assignment problem in flexible manufacturing systems: mathematical modelling and computational experience. International Journal of Production Research, 25, 1267-1283.

(6.) Wilson, J.M. (1989) An alternative formulation of the operation assignment problem in flexible manufacturing systems. International Journal of Production Research, 27, 1405-1412.

(7.) Kim, Y-D. and Yanco, C.A. (1994) A new branch and bound algorithm for loading problems in flexible manufacturing systems. International Journal of Flexible Manufacturing Systems, 6, 361-382.

(8.) Shanker, K. and Tzen, Y.J.J. (1985) A loading and dispatching problem in a random flexible manufacturing system. International Journal of Production Research, 23, 579-595.

(9.) Shanker, K. and Srinivasula, A. (1989) Some solution methodologies for loading problems in a flexible manufacturing system. International Journal of Production Research, 27, 1019-1034.

(10.) Mukhopadhyay, S.K., Midha, S. and Murli Krishna, V. (1992) A heuristic procedure for loading problems in flexible manufacturing systems. International Journal of Production Research, 30, 2213-2228.

(11.) Kim, Y-D. and Yano, C.A. (1993) A heuristic approach for loading problems in flexible manufacturing systems. IIE Transactions, 25, 26-39.

(12.) Kuhn, H. (1995) A heuristic algorithm for the loading problem in flexible manufacturing systems. International Journal of Flexible Manufacturing Systems, 7, 229-254.

(13.) Lee, H.F. and Stecke, K.E. (1998) Production planning for flexible flow systems with limited machine flexibility. IIE Transactions, 30, 669-684.

(14.) Rajagopalan, S. (1986) Formulation and heuristic solutions for part grouping and tool loading in flexible manufacturing systems, in Proceedings of the Second ORSA/TIMS Conference of Flexible Manufacturing System: Operations Research Models and Applications, Stecke, K. E. and Suri, R. (eds.), Elsevier, Amsterdam, pp. 311-320.

(15.) Stecke, K.E. (1986) A hierarchical approach to solving machine grouping and loading problems of flexible manufacturing systems. European Journal of Operational Research, 24, 369-378.

(16.) O'Grady, P.J. and Menon, U. (1987) Loading a flexible manufacturing system. International Journal of Production Research, 25, 1053-1068.

(17.) Sarin, S. and Chen, C.S. (1987) The machine loading and tool allocation problem in a flexible manufacturing system. International Journal of Production Research, 23, 579-595.

(18.) Brettauer, K.M. and Venkataramanan, M.M. (1990) Machine loading and alternative routing in a flexible manufacturing system. Computers and Industrial Engineering, 18, 341-350.

(19.) Co, H.C., Biermann, J.S. and Chen, S.K. (1990) A methodological approach to the flexible-manufacturing-system batching, loading, and tool configuration problems. International Journal of Production Research, 28, 2171-2186.

(20.) Kumar, P., Tewari, N.K. and Singh, N. (1990) Joint consideration of grouping and loading problems in a flexible manufacturing system. International Journal of Production Research, 28, 1345-1356.

(21.) Ram, B., Sarin, S. and Chen, C.S. (1990) A model and a solution approach for the machine loading and tool allocation problem in a flexible manufacturing system. international Journal of Production Research, 28, 637-645.

(22.) Kirkavak, N. and Dincer, C. (1993) Analytical loading models in flexible manufacturing systems. European Journal of Operational Research, 71, 17-31.

(23.) Moreno, A.A. and Ding, F.-Y. (1993) Heuristics for FMS loading and part-type-selection problems. International Journal of Flexible Manufacturing Systems, 5, 287-300.

(24.) Tang, L.-L., Yih, Y. and Liu, C.-Y. (1995) A framework for part type selection and scheduling in FMS environment. International Journal of Computer Integrated Manufacturing, 8, 102-115.

(25.) Stecke, K.E. and Raman, N. (1994) Production planning decisions in flexible manufacturing systems with random material flows. IIE Transactions, 26, 2-17.

(26.) Tang, C.S. and Denardo, E.V. (1988) Models arising from a flexible manufacturing machine, part II: minimization of the number of switching instants. Operations Research, 36, 778-784.

(27.) Kim, Y-D. and Yano, C.A. (1992) An iterative approach to system setup problems in flexible manufacturing systems. International Journal of Flexible Manufacturing Systems, 4, 183-209.

(28.) Liang, M. and Dutta, S.P. (1993) An integrated approach to the part selection and machine loading problem in a class of flexible manufacturing systems. Eruopean Journal of Operational Research, 67, 387-404.

(29.) Lee, D-H. and Kim, Y-D. (1998) Iterative procedures for multi-period order selection and loading problems in flexible manufacturing systems. International Journal of Production Research, 36, 2653-2668.

(30.) Lee, D-H. and Kim, Y-D. (1998) Scheduling algorithms for flexible manufacturing systems with partially grouped machines. Journal of Manufacturing Systems, (in press).

(31.) Kim, Y-D. and Yano, C.A. (1997) Impact of throughput-based objectives and machine grouping decisions on the short-term performance of flexible manufacturing systems. International Journal of Production Research, 35, 3303-3322.

               Performance ratios of the algorithms when the
               tool magazine capacity constraints are tight
NOP [1] NMC [2]   DR-LPT [3]   DR-MUL [4]    LP-RLX [5]    DC-LP [6]
20       4      1.40 (0.98)  1.31 (1.02)  12.58 (26.28)  5.52 (9.22)
20       6      3.26 (1.80)  2.99 (1.98)   0.81 (0.72)   1.18 (1.95)
20       8      1.96 (1.43)  1.64 (1.28)   1.19 (0.68)   1.74 (3.70)
30       8      3.02 (1.29)  2.94 (1.23)   0.66 (0.30)   3.75 (6.42)
40       8      1.61 (1.04)  1.61 (1.04)  10.89 (23.06) 12.30 (15.87)
Average         2.24 (1.29)  2.10 (1.29)   5.22 (10.21)  4.90 (7.43)
NOP [1]   DC-LPT [7]   DC-MUL [8]
20      0.91 (0.46)  0.80 (0.47)
20      1.07 (0.53)  0.86 (0.51)
20      0.82 (0.37)  0.71 (0.39)
30      0.89 (0.52)  0.86 (0.53)
40      1.09 (0.47)  1.09 (0.47)
Average 0.96 (0.47)  0.86 (0.48)

This table gives averages and standard deviations (in parentheses) of the relative performance ratios

(1.)Number of operations

(2.)Number of machines

(3.)LPT algorithm by way of the direct approach

(4.)MULTIFIT algorithm by way of the direct approach

(5.)Linear programming relaxation algorithm

(6.)Linear programming algorithm by way of the decomposition approach

(7.)LPT algorithm by way of the decomposition approach

(8.)MULTIFIT algorithm by way of the decomposition approach

               Performance ratios of the algorithms when the
               tool magazine capacity constraints are loose
NOP     NMC   DR-LPT      DR-MUL       LP-RLX         DC-LP       DC-LPT
20       4  1.25 (1.10) 0.90 (0.84)  0.32 (0.18)   0.25 (0.17)  0.42 (0.27)
30       4  1.84 (0.45) 1.83 (0.45) 25.76 (40.05) 10.46 (16.02) 0.93 (0.64)
20       6  1.39 (3.04) 1.21 (3.01)  1.12 (2.75)   0.33 (0.10)  0.30 (0.23)
30       6  0.78 (0.54) 0.66 (0.49)  0.31 (0.13)   0.98 (1.88)  0.42 (0.17)
20       8  0.77 (0.70) 0.54 (0.62)  0.74 (0.29)   0.47 (0.17)  0.33 (0.19)
30       8  1.67 (0.70) 1.54 (0.68)  0.51 (0.21)   0.28 (0.09)  0.52 (0.24)
40       8  1.40 (1.02) 1.34 (0.95)  0.35 (0.20)   2.97 (4.83)  0.62 (0.38)
Average     1.30 (1.08) 1.15 (1.01)  4.16 (6.26)   2.25 (3.33)  0.51 (0.30)
NOP       DC-MUL
20      0.25 (0.19)
30      0.91 (0.65)
20      0.27 (0.24)
30      0.30 (0.17)
20      0.30 (0.18)
30      0.47 (0.27)
40      0.57 (0.35)
Average 0.44 (0.29)
See the footnotes of Table 1
                  CPU seconds for the loading algorithms
NOP NMC  DR-LPT    DR-MUL      LP-RLX       DC-LP       DC-LPT
20   4  0.5 (0.1) 1.0 (0.1)  11.4 (7.3)   11.9 (2.5)   8.2 (1.5)
30   4  0.6 (0.1) 1.4 (0.1)  27.7 (29.2)  25.8 (6.0)  22.3 (2.9)
20   6  0.9 (0.4) 2.2 (0.4)  11.5 (5.0)   28.4 (3.6)  16.5 (2.2)
30   6  1.1 (0.3) 3.0 (0.4)  14.3 (1.3)   66.4 (7.2)  44.0 (4.8)
20   8  1.8 (0.9) 4.5 (1.1)  13.9 (7.6)   52.6 (6.1)  30.1 (4.3)
30   8  1.4 (0.5) 5.3 (0.7)  36.3 (53.0) 100.4 (11.5) 62.6 (8.6)
40   8  1.3 (0.3) 6.2 (0.5) 115.9 (74.5) 139.3 (28.1) 96.5 (16.5)
NOP    DC-MUL
20   17.9 (3.6)
30   45.0 (7.2)
20   41.5 (8.3)
30   93.0 (14.5)
20   65.7 (13.1)
30  124.8 (19.7)
40  177.9 (27.1)
This table gives averages and standard
deviations (in parentheses) of CPU times

Appendix

Performance of loading algorithms for total grouping and partial grouping

Simulation experiments are done to compare the suggested algorithms for the partial grouping configuration with existing algorithms for total grouping and also to investigate the effects of the grouping methods on the performance of the system. In the experiments, loading plans are obtained from DR-LPT and DC-MUL for partial grouping, and two composite algorithms, ALLBAL and ALLUNB suggested by Kim and Yano [11] for total grouping. DC-MUL is included in the test since it is the best performing algorithm, and DR-LPT is included to compare the new loading algorithm with this enhanced version of the loading algorithm suggested by Stecke and Raman [25]. ALLBAL and ALLUNB are heuristic algorithms developed for the workload balancing and unbalancing objectives, respectively. These algorithms are composite heuristics based on the MULTIFIT algorithm in which several operation assignment rules are applied one by one for each machine capacity. See Kim and Yano [11] for details of these algorithms. For the total groupin g, configuration all possible total grouping alternatives were considered and the loading algorithms were applied to each of these alternatives and the best was selected for each algorithm. In ALLUNB, the closed queueing network model of Stecke and Solberg [2] was used to obtain an ideal (unbalanced) workload for each machine group.

Since workload (un)balancing is not considered as the ultimate or final objective in most cases, makespan (the length of time required to complete all parts) is used as the performance measure in the experiments. Workload (un)balance may not be a good system performance measure since machines may not be actually utilized well even with a perfectly balanced loading plan if a good schedule cannot be obtained for the loading plan. On the other hand, makespan is closely related to production capacity or production rate of a system. For the measure of makespan, however, scheduling must be done for each loading plan to compare grouping and/or loading methods since a specific schedule should be obtained to evaluate these methods.

The simulation experiments were done on 15 sets of problems characterized by (not necessarily all combination of) three levels for the number of machines (four, six and eight), two levels for the capacity of tool magazine (80 and 100), and three levels for the number of parts (10, 15, and 20 for the four-machine case, 15, 20 and 25 for the six-machine case, and 20, 25 and 30 for the eight-machine case). Demand quantity of each part was randomly generated from DU(10, 30). Also, the number of operations required for each part was randomly generated from DU(2, 4), DU(3, 6) and DU(4, 8) for the four, six and eight machine cases, respectively. Parts have deterministic operation processing times, and processing time for each operation was randomly generated from DU(20, 100). Other data were generated with the same method as the one used in the test of loading algorithms in Section 5.

In the experiments, machine breakdowns (including tool breakages) that often occur in real systems are included although they are not considered in the heuristic algorithms suggested in this paper. It is assumed that time between failures and time to repair are exponentially distributed. While two levels (2000 and 4000) were used in the simulation for the Mean Time Between Failures (MTBF), the Mean Time To Repair (MTTR) was set to be 200. Additionally, since buffer capacity is limited in most systems, it is assumed that there is an upper limit on the number of parts circulating in the system (20 and 30 for the four- and six-machine cases, and 30 and 40 for the eight-machine case). For each of the 15 problem sets, 40 problems were randomly generated, 10 problems each for all combinations of the two levels for MTBF and two levels for the number of parts circulating in the system. The simulation model was coded in C.

For comparison of the grouping methods and loading algorithms, it is necessary to find an optimal makespan for each loading plan as mentioned earlier. However, since it is very difficult to find an optimal schedule, heuristic methods are used in the tests. These heuristics employ rules for part selection and rules for machine selection. A part selection rule is used to select a part among those waiting in a queue for a machine, and a machine selection rule is used to select (a queue of) a machine if two or more machines are assigned to an operation (for a part).

In the experiments, 16 rule combinations (eight rules for part selection and two rules for machine selection) were applied to each of loading plans from the four algorithms to obtain schedules, and the smallest makespan among those from the 16 schedules was selected to compare the grouping/loading plans. Scheduling rules used in the simulation are given below. Before describing the scheduling rules, the following terms need to be defined. Let remaining work of an operation denote the sum of processing times of its successor operations including itself, and let remaining operations of an operation (of a part type) denote the number of successor operations including itself. (Note that a series of operations must be performed to process a part). Part processing time of a part denotes the sum of processing times of operations for the part.

Part selection rules

SJT = select an operation with the shortest part processing time;

SPT = select an operation with the shortest (operation) processing time;

MOR = select an operation with the most remaining operations;

MWR = select an operation with the most remaining work;

SDT = select an operation with the smallest ratio of processing time to part processing time;

SMT = select an operation with the smallest value obtained by multiplying processing time by part processing time;

PWR = select an operation with smallest ratio of processing time to remaining work;

POR = select an operation with the smallest ratio of processing time to remaining operations.

Machine selection rules

SQ = select a machine with the smallest number of waiting parts;

SW = select a machine with the smallest sum of (operation) processing times of waiting parts.

Note that the workload assigned to each machine after scheduling with these rules can be different from that of a given loading plan, since machines can fail and the machine selection rules cannot consider or follow exactly the loading plan, that is, the workload to be assigned to each machine cannot be exactly realized.

For evaluation of the results, we use a relative performance ratio which is defined as [([M.sub.r] - [M.sub.B])/[M.sub.B]] X 100 (%), where [M.sub.r] is the makespan from algorithm r and [M.sub.B] is the best makespan obtained for that problem. The results are given in Tables Al through A3, which show the average and standard deviation of the relative performance ratios obtained from 10 problems for each case. To show the effects of the six factors (loading algorithms, number of machines, number of parts, tool magazine capacity, MTBF, and maximum number of parts circulating in the system), an ANalysis Of VAriance (ANOVA) was done and the results are given in Table A4. The relative performance was affected by the loading algorithms and the number of machines in the system. To compare the performance of the four algorithms, Duncan's multiple range test was performed for each level of the number of machines and the results are given in Tables A5-A7.

As can be seen in these tables, partial grouping was better than total grouping. This may be because partial grouping and its corresponding loading plans help to cope with system disturbances such as machine breakdowns more easily by providing more routing flexibility. Also, the (relative) outperformance becomes more evident as the number of machines increases. This can be explained as follows. As the number of machines increases, the difference in the numbers of machines assigned to each operation in the loading plans for the two grouping configurations becomes bigger, and so is the difference in the routing flexibility (and the performance).

Among the two loading algorithms developed for the partial grouping configuration, DC-MUL gave better results than DR-LPT, that is, the loading algorithm suggested in this paper outperforms that of Stecke and Raman [25], as in the computational results given in Section 5. The makespan from the former was shorter by approximately 4%, although the difference in the performance in terms of workload balance was smaller. This is because more machines can be allocated to each operation with DC-MUL than with DR-LPT, and therefore there are more alternative routes for the parts.

For the total grouping configuration, balancing or unbalancing does not have much impact on the makespan except for the eight-machine cases, in which balancing is better. This result is consistent with that of a simulation study of Kim and Yano [31] on the relationships between various objectives for the loading problems and scheduling objectives. They report that the makespan was approximately proportional to the maximum workload among the machines since many schedules had similar ratios of interspersed idle time to total workload. This may be a reason why balancing works as good as unbalancing for the makespan measure. However, it is known that long-term or steady-state throughput rate can be maximized by unbalancing.

                        Test results for simulation
                     experiments (four-machines case)
Problem set                      Partial grouping              Total grouping
TMC [1]     NP [2] MTBF NPIS [3]     DR-LPT [4]     DC-MUL [5]    ALLBAL [6]
80          10     2000  20        8.21 (6.88)    1.10 (3.03)  13.87 (13.39)
                         30        2.58 (3.53)    1.58 (3.19)   7.06 (4.78)
                   4000  20        9.91 (8.13)    1.63 (2.67)   7.26 (7.39)
                         30        5.38 (5.65)    1.10 (1.84)   6.32 (4.55)
            15     2000  20        3.53 (4.43)    0.45 (1.42)   5.39 (6.54)
                         30        6.07 (8.19)    0.77 (1.82)  10.71 (10.29)
                   4000  20        2.36 (3.78)    0.46 (1.46)   8.50 (13.85)
                         30        0.93 (1.70)    0.11 (0.36)   2.11 (3.63)
100         10     2000  20        4.63 (6.81)    0.88 (1.45)   7.70 (6.69)
                         30        2.06 (4.11)    0.89 (1.86)   6.88 (8.44)
                   4000  20        2.52 (3.16)    0.60 (1.44)   5.59 (4.74)
                         30        1.77 (2.79)    0.16 (0.34)   2.52 (2.14)
            15     2000  20       10.86 (4.40)    1.30 (3.85)  12.31 (3.33)
                         30        6.73 (4.01)    4.22 (4.80)  11.50 (14.47)
                   4000  20       10.99 (5.41)    1.20 (3.21)  13.26 (15.92)
                         30        4.43 (4.90)    0.95 (1.98)   6.87 (6.56)
            20     2000  20        4.86 (4.99)    1.81 (3.98)   3.59 (4.38)
                         30        7.53 (6.52)    0.25 (0.53)   6.37 (8.28)
                   4000  20        5.13 (4.80)    1.43 (3.23)   9.01 (8.86)
                         30        2.56 (3.29)    0.05 (0.16)   6.07 (6.93)
Average                            5.15 (4.87)    1.05 (2.13)   7.65 (7.76)
Problem set
TMC [1]       ALL UNB [7]
80           6.33 (8.29)
             3.59 (2.30)
             3.46 (3.24)
             5.41 (4.94)
             2.95 (3.25)
            11.28 (10.20)
            10.28 (13.91)
             7.18 (10.98)
100          3.88 (4.11)
             2.28 (2.23)
            11.63 (17.37)
             2.78 (1.99)
             5.38 (3.74)
             4.49 (9.09)
             5.01 (3.57)
             3.64 (3.78)
             8.77 (10.90)
             6.87 (7.52)
            10.21 (12.76)
             6.62 (6.29)
Average      6.10 (7.02)

This table gives averages and standard deviations (in parentheses) of the relative performance ratios

(1.)Number of tool slots in a tool magazine

(2.)Number of parts

(3.)Maximum number of parts circulating in the system

(4.)LPT algorithm by way of the direct approach

(5.)MULTIFIT algorithm by way of the decomposition approach

(6.)Loading algorithm of Kim and Yano [11] for the configuration of total machine grouping (for workload balancing)

(7.)Loading algorithm of Kim and Yano [11] for the configuration of total machine grouping (for workload unbalancing)

                        Test results for simulation
                      experiments (six-machines case)
Problem set              Partial grouping             Total grouping
TMC         NP MTBF NPIS      DR-LPT        DC-MUL        ALLBAL
80          15 2000  20    8.85 (7.01)    3.37 (5.28) 10.68 (7.08)
                     30    9.73 (4.60)    1.35 (2.87)  9.44 (4.22)
               4000  20    9.04 (9.76)    1.89 (4.91) 11.93 (9.30)
                     30    6.48 (5.59)    1.67 (2.73)  5.74 (5.00)
            20 2000  20    2.00 (3.72)    0.22 (0.69)  9.84 (10.15)
                     30    1.52 (4.25)    0.00 (0.00) 12.54 (9.74)
               4000  20    1.74 (3.73)    0.00 (0.00)  8.27 (6.43)
                     30    1.59 (2.90)    0.03 (0.09) 12.78 (12.86)
100         15 2000  20    1.11 (1.63)    0.23 (0.60)  6.85 (3.76)
                     30    2.96 (5.54)    1.28 (3.75)  6.17 (2.14)
               4000  20    1.58 (2.15)    1.02 (2.23)  5.14 (2.36)
                     30    3.46 (6.34)    0.14 (0.28)  8.56 (8.73)
            20 2000  20   14.24 (11.03)   2.20 (6.69) 11.00 (5.95)
                     30    9.04 (8.76)    2.06 (3.80) 11.51 (9.19)
               4000  20    9.50 (10.18)   2.38 (5.04) 13.82 (7.12)
                     30    8.59 (6.62)    0.13 (0.40) 14.10 (12.68)
            25 2000  20    5.03 (6.29)    0.00 (0.00)  7.86 (7.24)
                     30    5.94 (6.55)    0.34 (1.07) 10.56 (12.69)
               4000  20    2.39 (3.23)    1.91 (3.19)  6.83 (6.93)
                     30    7.43 (4.57)    0.63 (1.98) 12.25 (14.24)
Average                    5.61 (5.72)    1.04 (2.28)  9.79 (7.89)
Problem set
TMC            ALLUNB
80           7.06 (8.89)
            10.29 (8.29)
            10.67 (7.65)
             8.51 (8.52)
            10.24 (5.97)
            16.23 (8.24)
            10.71 (7.73)
            13.25 (12.69)
100         11.26 (11.29)
             6.54 (8.71)
             6.53 (5.57)
             7.04 (3.36)
             6.82 (4.30)
             7.09 (7.09)
             9.94 (11.20)
            12.72 (10.30)
            10.97 (5.37)
            11.24 (6.78)
             4.25 (5.65)
            12.39 (7.00)
Average      9.69 (7.73)
See the footnotes of Table A1
                  Test results for simulation experiments
                           (eight-machines case)
Problem set              Partial grouping             Total grouping
TMC         NP MTBF NPIS      DR-LPT        DC-MUL        ALLBAL
80          20 2000  30    9.97 (9.48)    1.96 (3.49) 11.10 (11.33)
                     40   10.21 (8.41)    0.00 (0.00) 11.89 (6.73)
               4000  30    6.16 (6.58)    0.45 (1.43) 11.28 (8.75)
                     40    2.40 (4.35)    0.57 (1.82)  7.45 (10.11)
            25 2000  30    1.29 (2.48)    0.00 (0.00) 14.88 (8.57)
                     40    2.75 (4.47)    0.01 (0.03)  8.13 (6.25)
               4000  30    3.20 (7.28)    2.18 (6.89)  7.10 (5.81)
                     40    0.00 (0.00)    0.00 (0.00)  7.29 (7.68)
100         20 2000  30    3.27 (6.37)    0.68 (1.45) 10.33 (6.23)
                     40    5.73 (8.15)    1.47 (3.60) 11.15 (7.11)
               4000  30    5.10 (8.12)    1.85 (5.05)  9.58 (7.52)
                     40    9.41 (10.71)   0.00 (0.00) 10.26 (6.61)
            25 2000  30    5.91 (7.19)    1.75 (4.47)  6.84 (6.45)
                     40    7.32 (6.24)    1.93 (3.35) 12.83 (12.19)
               4000  30   11.18 (8.67)    3.16 (4.15) 14.49 (7.58)
                     40    7.06 (6.77)    0.48 (1.28)  6.73 (5.74)
            30 2000  30    6.35 (6.33)    0.46 (1.45)  9.43 (6.16)
                     40    2.84 (5.13)    0.61 (1.43)  4.28 (8.01)
               4000  30    8.11 (7.15)    1.02 (1.98)  8.12 (6.35)
                     40    1.36 (4.11)    0.06 (0.18)  7.32 (9.30)
Average                    5.48 (6.40)    0.93 (2.10)  9.52 (7.72)
Problem set
TMC            ALL UNB
80           8.99 (8.06)
            16.20 (10.26)
             9.57 (9.64)
            12.95 (7.63)
            16.13 (7.82)
            13.44 (13.10)
            12.21 (6.74)
            11.11 (7.71)
100         17.92 (12.97)
            16.32 (5.17)
            18.78 (12.09)
            13.99 (6.19)
            10.21 (10.66)
            17.14 (11.28)
            13.16 (12.71)
            18.94 (11.03)
            18.16 (11.98)
            12.18 (12.15)
            11.84 (9.31)
            12.90 (10.22)
Average     14.11 (9.84)
See the footnotes of Table A1
            Analysis of variance for the effects of six factors
Source of    Sum of   Degrees of  Mean   F values
variation   squares    freedom   squares
Algorithms  24 047.85       3    8015.95  148.06 [**]
NM [+]       1 431.83       2     715.92   13.22 [**]
TMC          1 022.50       1    1022.50   18.89 [**]
NP             235.06       1     235.06    4.34
MTBF           149.30       1     149.30    2.76
NPIS           111.26       1     111.26    2.05
Error      103 410.53    1910
Total      130 408.33    1919
(+.)Number of machines
(**.)There is difference in the effects
at a significance level of 0.01
     Results of the Duncan's multiple range test (four machines case)
Algorithms (ARPR [+]) DC-MUL DR-LPT ALLUNB
DC-MUL     (1.05)
DR-LPT     (5.15)       **
ALLUNB     (6.10)       **     =
ALLBAL     (7.65)       **     **     =
(+.)Average relative performance ratio
(**.)Statistically different at a significant level of 0.01
= Statistically indifferent at a significant level of 0.01
             Results of the Duncan's multiple range test (six
                              machines case)
Algorithms (ARPR [+]) DC-MUL DR-LPT ALLUNB
DC-MUL     (1.04)
DR-LPT     (5.61)       **
ALLUNB     (9.69)       **     **
ALLBAL     (9.79)       **     **     =
See the footnotes for Table A5
            Results of the Duncan's multiple range test (eight
                              machines case)
Algorithms  (ARPR [+]) DC-MUL DR-LPT ALLBAL
DC-MUL      (0.93)
DR-LPT      (5.48)       **
ALLBAL      (9.52)       **     **
ALLUNB     (14.11)       **     **     **
See the footnotes for Table A5