Optimal design for flexible manufacturing systems: generalized analytical methods.

Advanced manufacturing systems such as Flexible Manufacturing Systems (FMSs) are capital-intensive. Designing functional yet cost-effective FMSs is a challenging task because it involves the solution of a complex series of interrelated problems. In this paper, we study a design problem for FMSs

that consist of multiple types of machines. Using closed queueing network models for FMSs, this problem seeks the minimum cost design subject to meeting throughput requirements. The design decisions include the number of machine groups, the number of machines for each group, the workload allocation among machine groups, the number of pallets, the number of transporters, and the batch size. Since these design decisions are highly interdependent, we present the optimum and heuristic methods that simultaneously determine them. To our knowledge, these methods are the most general analytical methods for FMS design. Development of the heuristic methods is crucial because of the time-consuming nature of the optimum method as the number of machine types increases. Computational results show that the heuristic methods are both effective and efficient.

1. Introduction

A typical Flexible Manufacturing System (FMS) consists of groups of versatile Numerically Controlled (NC) machines that are linked by a Material Handling System (MHS). Machines within each group are tooled identically and are capable of performing a certain set of operations. Operations and material movements are all under a central computer control. Since FMSs were introduced in the early 1960s, broader applications of FMSs have been developed in the areas of injection molding, metal forming and fabricating, and assembly. FMSs, however, are highly capital-intensive and FMS designers are interested in seeking the minimal cost design that satisfies performance and technical requirements such as throughput capacity and flexibility capacity.

Given selection of part types to be produced, we study a design problem of FMSs that consist of multiple types of NC machines. This problem seeks the minimal cost design subject to meeting throughput requirements. The decisions to be made include: (1) the number of machine groups; (2) the number of machines at each group; (3) the workload allocation among the machine groups; (4) the number of pallets; (5) the number of transporters; and (6) batch transfer size. When parts are small, a batch of parts can be mounted on a pallet and transferred together between machine groups in order to reduce material handling operations. We also investigate the effect of this batch size on the design cost and decisions.

In order to address design problems for FMSs, researchers commonly use Closed Queueing Networks (CQN) to model FMSs. Machines at each machine group are modeled as a multiserver station and pallets carrying work-in-process inventories modeled as the fixed job population circulating in CQN. In this paper we also use a CQN model for FMSs and review the related literature that use CQN models to address FMS design problems.

Vinod and Solberg [1] were the first to formulate the optimal system configuration problem of an FMS. They optimized two parameters in the CQN model which were the number of servers at each multiserver station and the job population in the system. The objective was to minimize the sum of operating costs of the servers and the job population. They proposed an implicit enumeration algorithm and presented computation results. Dallery and Frien [2] have presented an improved algorithm using a modified marginal allocation procedure to find a good initial solution. Kouvelis and Lee [3] have presented a more efficient algorithm by combining a branch and bound procedure with fathoming rules that exploit the properties of the throughput function of the CQN model. Tetzlaff [4] has extended the above works by determining not only the numbers of machines and pallets but also the types of machines when several types are available. Askin and Krisht [5] have also used the CQN model to jointly determine the optimum number o f pallets and workcenter processing rates.

The above works assume other design parameters are already determined and available as input to their problem. For example, they assume that the workload at each machine group and the batch size are given. Millar and Yang [6] have studied the batch sizing issue for FMSs separately. They presented a method that determines an optimal batch size that minimizes the sum of work-in-process and final inventory costs. They found that batch sizing can be a cheap and effective variable for controlling system throughput for FMSs.

At the early design stage of complex manufacturing systems such as FMSs, different design issues are highly related and should not be treated independently [7]. Highly significant interactions between the design factors may invalidate simple one-factor-at-a-time procedures for finding a minimum-cost system design [8]. In FMSs, machines are flexible and versatile and there is a large latitude in allocating workload among machine groups. Clearly there are strong interactions between the workload allocation and the optimal system configuration and between the batch size and the MHS capacity.

Lee et al. [9] have studied a more general design problem than the optimal system configuration problem defined by Vinod and Solberg. They simultaneously optimized not only the above two parameters but also the workload allocation among machine groups and the batch size. They present an implicit enumeration algorithm over the integer solution space combined with a nonlinear programming method. However, their method has two limitations: (1) FMSs consist of only one type of flexible machine; and (2) the material handling devices that move pallets between machines are conveyors. FMSs usually consist of different types of NC machines such as CNC mills, VTL, and Coordinate Measuring Machines (CMM). More common material handling devices for FMSs are transporters or Automated Guided Vehicles (AGVs). In this paper, we present generalized methods that obviate these limitations and thereby are more suitable for applications.

We first present the optimum method that is based on an implicit enumeration scheme. This is more complex than one used by Lee et al. [9] for FMSs with one machine type. Because of the time-consuming nature of the optimum method as the number of machine type increases, we also present heuristic methods. These heuristic methods are far more efficient than the optimum method, yet they are equally effective. To our knowledge, the proposed methods are the most general analytical design methods that use the CQN model for FMSs. These methods are particularly useful at the early design stage where many design alternatives need to be investigated before the selection of a cost-effective design that meets design requirements. The proposed methods retain an overview of complex interdependencies among the various elements of the FMSs, and quickly provide a small number of good design candidates to which detailed analysis using a technique such as simulation can be applied. The importance of early design activities is e mphasized for highly automated manufacturing systems. About 80% of the total budget is committed at the design stage [10] and 55% of the engineering cost is spent by the project authorization point [11]. For a more complete discussion on design models for FMSs, refer to Kouvelis [12] and Solot and van Vliet [13].

The remainder of the paper is organized as follows. In Section 2, we describe a CQN model for FMSs and state a mathematical formulation of the problem under consideration, assuming a unit batch size. In Section 3, we present both optimum and heuristic methods, and the extension of the methods under batch sizing. In Section 4, we present computational results for these methods. In Section 5, we conclude with a brief summary and future research issues.

2. Model and mathematical formulation

We use a Jackson CQN [14] model a represent the FMSs. The basic assumptions of a Jackson CQN are: (1) whenever a job has completed processing by the system, it is possible to release an external job immediately into the system; (2) at all stations a FCFS queue discipline is used, in which the service time distributions are exponential and all job classes have the same service parameter at a station; (3) each station has sufficient buffer capacity to accommodate all parts that are queued there; (4) parts follow a Markovian routing through the system. We also assume that FMSs use universal pallets which can carry any type of parts.

In practice, processing times for individual part types may be nearly constant but not exponentially distributed. However, processing times at a particular machine vary due to part changes and random disturbances such as tool breakage, thus giving some justification for the exponential processing time assumption. The assumption of sufficient buffer capacity can be reasonable for FMSs with central buffer storage. Even for FMS design with limited local buffer spaces, Lee and Stecke [15] show that the CQN model can be useful. They first use the CQN model and determine the number of machine groups and the capacities of key resources of flexible machines and MHS, assuming sufficient local buffer spaces. Then with the input from the CQN model, they use simulation and a search method to find the size of local buffer spaces. The justification of this approach is that machines and MHS are far more expensive than buffer spaces. Templemeier and Kuhn [16] give an extensive literature survey on the CQN models for FMSs an d the model justifications. They also provide several illustrations in which the CQN model accurately represents various types of FMSs.

A particular performance measure of our interest is the throughput, which is the rate of pallets leaving the system with completed parts. We first define necessary notation:

d = throughput requirements;

C = number of machine types;

[M.sub.c] = number of machine groups with machines of type c for c = 1,.. C;

M = total number of machine groups = [[sigma].sub.c][M.sub.c];

N = number of pallets circulating in the system;

[K.sub.c] = total number of machines of type c for c = 1,... C;

[TW.sub.c] = total workload (i.e., total average processing time) of type c machine required to produce a part;

[P.sub.0] = total available material handling time by a transporter or conveyor per period;

[S.sub.0] = number of transporters if required;

[W.sub.0] = average material handling time taken to produce parts carried on a pallet;

[P.sub.c] = total available processing time by a machine of type c per period;

S = ([S.sub.ci]) vector indicating the number of machines at the ith machine group with type c for c = 1,... C and i =1,...[M.sub.c];

W = ([W.sub.ci]) vector indicating the workload at the ith machine group with type c for c = 1,..., C and

TH = throughput of the CQN for given N, ([M.sub.c]), [P.sub.0], [S.sub.0], [W.sub.0], ([P.sub.c]), S, W

With use of the CQN model for FMSs, we can compute the throughput, denoted as TH, as follows:

TH(N) = G(N - 1)/G(N), (1)

Where N is the number of pallets in the system and G(N) denotes the normalizing constant and is defined as

G(N) = [[sigma].sub.[n.sub.0]+[n.sub.11]+...+[n.sub.c][M.sub.c]=N] [[[pi].sup.[n.sub.0]].sub.j=0] [g.sub.0](j) [[[pi].sup.C].sub.c=1] [[[pi].sup.[M.sub.c]].sub.i=1] [[[pi].sup.[n.sub.ci]].sub.k=0] [f.sub.ci](k), (2)

When node 0 is a central server representing the material handling node, and C is a number of machine types, [M.sub.c] is a number of machine groups of type c, and [n.sub.0] and [n.sub.ci] are numbers of pallets at nodes 0 and [c.sub.i] for c = 1,...,C and i = 1,...,[M.sub.c] and [g.sub.0](j) and [f.sub.ci](k) are given as

[g.sub.0](j) = 1 for j = 0,

= [W.sub.0]/[P.sub.0] min(j, [S.sub.0]) for j [greater than] 0, (3)

[f.sub.ci](k) = 1 for k = 0

= [W.sub.ci]/[P.sub.c]min(k, [S.sub.ci]) for k [greater than] 0. (4)

[S.sub.ci] and [W.sub.ci] indicate the number of machines and the workload at group i of type c, respectively. [P.sub.c]([P.sub.0]) is total available processing time of type c (material handling time) per period. [S.sub.0] and [W.sub.0] indicate the number of transporters and total material handling time required to finish partson a pallet, respectively. If conveyors are used instead, we can set [S.sub.0] to N and model the MHS as a delay node in the CQN. This makes no queueing delay in accessing conveyors. TH(N) can be computed using efficient algorithms such as the mean value analysis algorithm [17]. Using this throughput function for the CQN model, we mathematically state the problem under consideration as follows:

(P1):

Minimize z([K.sub.1],..., [K.sub.C],[S.sub.0],N)

Subject to:

TH(S, W, N) [greater than or equal to] d, (5)

[[[sigma].sup.[M.sub.c]].sub.i=1] [S.sub.ci] = [K.sub.c] c = 1,..., C, (6)

[[[sigma].sup.[M.sub.c]].sub.i=1] [W.sub.ci] = [TW.sub.c], c = 1,..., C, (7)

[L.sub.ci] [less than or equal to] [W.sub.ci] [less than or equal to] [U.sub.ci], i = 1,..., [M.sub.c], c = 1,..., C. (8)

The cost function z([K.sub.1],..., [K.sub.C], [S.sub.0], N) is monotone increasing in each of the variables andincudes operating and amortized acquisition cost of various resources such as machines, transporters, pallets and fixtures, and inventory holding costs for work in process. The decision variables of Problem (P1) are N, [S.sub.0], S, and W. Thus, (P1) is nonlinear mixed-integer programming.

Workload bounds of Constraints (8) can arise from technical constraints such as machine flexibility and precedence requirements among operations. Lee and Stecke [18] provide a method that determines workload bounds for flexible flow systems using these constraints. Machine flexibility is often characterized by the size of a tool magazine that can hold a number of tools and interchange them with little changeover times. The tool magazine size is typically 30, 60, or 120 slots in commercial flexible machines [19].

3. Solution methods

We now present solution methods for (P1). We first introduce an optimum method and then two heuristic methods that are embedded into the optimum method to improve speed. These solution methods assume that [M.sub.c] is given. When [M.sub.c] is unknown, however, the solution methods can be applied multiple times, once for every possible value of [M.sub.c]. The optimum solution is one that gives the minimum cost among these solutions obtained over different [M.sub.c]. A general recommendation for [M.sub.c], however, is to use the smallest possible [M.sub.c] in order to maximize resource pooling, routing flexibility, and system reliability.

3.1. An optimum method

The optimum method consists of three parts: (1) deriving the lower bounds on integer decision variables; (2) finding an effective initial solution; and (3) implicitly enumerating over integer solution space. The implicit enumerations solves a subproblem several times that is another mixed-integer nonlinear programming.

We first derive the lower bounds on the optimal number of pallets, transporters, and machines,[N.sup.B], [[S.sup.B].sub.0], ([[S.sup.B].sub.ci]), and ([[K.sup.B].sub.c]) as follows.

[N.sup.B] = [d x ([W.sub.0]/[P.sub.0] + [[sigma].sub.c] [TW.sub.c]/[P.sub.c])],

[[S.sup.B].sub.0] = [d x [W.sub.0]/[P.sub.0]],

[[S.sup.B].sub.ci] [d x [L.sub.ci]/[P.sub.c]] for all c, i,

[[K.sup.B].sub.c] = max ([d x [TW.sub.c]/[P.sub.c]], [[[sigma].sup.[M.sub.c]].sub.i=1] [[S.sup.B].sub.ci]) for c = 1,...,C, (9)

where [x] is the smallest integer greater than or equal to x and [y] is the smallest integer greater than y. These bounds are obtained by considering the extremes of system behavior: either no queueing delay occurs or machines are constantly busy.

We find an initial solution to (P1) by first obtaining an initial workload [W.sup.0] that meets workload constraints (7) and (8) and then obtaining an initial configuration ([[S.sup.0].sub.0],[S.sup.0], [N.sup.0]) for this given [W.sup.0] that meets constraints (6) and (7). We determined [W.sup.0] by assigning near equal workloads among machine groups of the same machine type and concatenating the results over all types. The procedure is outlined as follows:

Procedure 1. Find ([W.sup.0], [[S.sup.0].sub.0], [S.sup.0], [N.sup.0]), an initial feasible solution to (P1).

Step 0 Set c to 1 and go to Step 1.

Step 1. Assign [W.sub.ci] = [TW.sub.c]/[M.sub.c] for all i. If [L.sub.ci] [less than or equal to] [W.sub.ci] [less than or equal to] [U.sub.ci] for all i, go to Step 2. Otherwise set [omega] = {1,2,... ,[M.sub.c]} and go to Step 3.

Step 2. Assign c [left arrow] c + 1. If c [greater than] C, then go to Step 6 else go to Step 1.

Step 3. Let X = {i\[W.sub.ci] [greater than or equal to] [U.sub.ci] for all i in [omega]}, Y = {i\[W.sub.ci][less than or equal to] [L.sub.ci] for all i in [omega]}, [S.sub.X] = [[sigma].sub.i[epsilon]X] ([W.sub.ci] - [U.sub.ci]), and = [S.sub.Y] = [[sigma].sub.i[epsilon]Y]([L.sub.ci] - [W.sub.ci]), where [S.sub.X] ([S.sub.Y]) is the sum of workloads exceeding the upper (lower) bounds. If [S.sub.X] - [S.sub.Y] [greater than] 0, go to Step 4. If [S.sub.X] - [S.sub.Y], [less than] 0, go to Step 5. Otherwise, go to Step 2.

Step 4. Make the following assignments to reallocate the workload of [S.sub.X]: [W.sub.ci] [left arrow] [U.sub.ci] for every i [epsilon] X; [delta] [left arrow] [S.sub.X]/cardinality of [omega] - X; [W.sub.ci] [left arrow] [W.sub.ci] + [delta] for every i [epsilon] [omega] - X. Reset [omega] = [omega] - X and go to Step 3.

Step 5. Make the following assignments to reallocate the workload of [S.sub.Y]: [W.sub.ci] [left arrow] [L.sub.ci] for every i [epsilon] Y; [delta] [left arrow] [S.sub.Y]/cardinality of [omega] - Y; [W.sub.ci] [left arrow] [W.sub.ci] - [delta] for every i [epsilon] [omega] - Y. Reset [omega] = [omega] - Y and go to Step 3.

Step 6. Given [W.sup.0], find an initial feasible configuration ([[S.sup.0].sub.0], [S.sup.0], [N.sup.0]) by applying the method of Dallery and Frien [2].

The above procedure generalizes one by Lee et al. [9] for FMSs with one type of machine. Step 1 of the above procedure assigns equal workloads to machine groups of type c. If this violates the workload bound constraint, Steps 3 to 5 adjust the workloads while maintaining equality among the remaining workloads. The method by Dallery and Frien [2] used in Step 6 is basically a marginal allocation scheme which adds one server at a time that gives the most TH improvement per capital unit invested until the throughput requirements is met. Since [[W.sup.0].sub.ci] is nearly equal for all i, the initial server vector [[S.sup.0].sub.c] usually has the same number of machines. The rationale behind this initial solution approach is that the balanced system (i.e., balanced workload and balanced configuration) performs reasonably well, particularly, for large N. As N increases, the optimal solution becomes more balanced and for a totally saturated system (N = [infinity]), the balanced system gives the maximum throughput [20].

We define another problem related to (P1). This problem seeks S and W that maximize TH, given [K.sub.1],...,[K.sub.C], [S.sub.0], N. We denote this problem as (P2) and mathematically state as follows:

(P2):

f([K.sub.1],...,[K.sub.C],[S.sub.0],N) = Max Th(S,W\[K.sub.1],...,[K.sub.C], [S.sub.0],N),

subject to constraints (6), (7), and (8)

(P2) is also mixed-integer nonlinear programming. Lee [21] presents an optimum solution method for (P2). This method generates server vectors S's for a given K, eliminates several S's with several fathoming rules, and applies the reduced gradient algorithm to each remaining S in order to find W maximizing TH. Since the solution method to (P1) we propose here requires solving (P2) several times, we use this method as a subroutine. After redefining K = ([K.sub.1],...,[K.sub.C+2]) = ([K.sub.1],...,[K.sub.C],[S.sub.0],N), we rewrite (P1) with use of the lower bounds of (9) as follows:

(P3):

Minimize z(K)

subject to:

f(K) [greater than or equal to] d, (10)

K [greater than or equal to] [K.sup.B] and integers, (11)

where K [greater than or equal to] [K.sup.B] implies that [K.sub.c] [greater than or equal to] [[K.sup.B].sub.c] for every c = l,...,C + 2.

Lemma 1. f(K + [e.sub.c]) [greater than or equal to] f(K) for every c = 1,...,C + 1, where [e.sub.c] is a unit vector with all elements set to 0 except the cth element which is set to 1.

Proof. Suppose that [S.sup.K] and [W.sup.K] is the optimum solution of (P2) for K. Then we have TH([S.sup.K] + [e.sub.ci], [W.sup.K]\[K + [e.sub.c]) [greater than or equal to] TH([S.sup.K], [W.sup.K]\K) = f(K) for all i and c = 1,. .. , C + 1 because of the nondecreasing concavity of TH in [S.sub.ci] for a multiserver CQN [22]. By definition, f(K + [e.sub.c]) [greater than or equal to] TH([S.sup.K] + [e.sub.ic], [W.sup.K]\K + [e.sub.c]) and the result follows.

Lemma 2. f(K + [e.sub.c+2]) [greater than or equal to] f(K).

Proof. The proof is similar to that of Lemma 1 except the nondecreasing concavity of TH in N for the CQN [23].

Since both the objective and constraint functions of (P3) are monotone nondecreasing in each of variables K, we can apply the Lawler and Bell algorithm [24] to implicitly search over K. However, it requires to convert the decision variables to 0-1 variables and may not be efficient. We take a different implicit enumeration scheme that is similar to one used by Dallery and Frien (DF) [2] to solve the optimum configuration system problem. There are three differences between one proposed here and DF. First, the proposed method finds an initial solution ([W.sup.0],[[S.sup.0].sub.0],[S.sup.0],[N.sup.0]) from Procedure 1 using the balancing notion, while DF finds an initial configuration ([[S.sup.0].sub.0],[S.sup.0],[N.sup.0]) for a given W using the marginal allocation scheme. Second, the proposed method implicitly enumerates over machine types K while DF does over machine groups S. Third, the proposed method solves the subproblem (P2) for a given K while DF just computes the throughput function TH for a given S. Figure 1 depicts the proposed implicit enumeration scheme.

3.2. Heuristic methods

In this section, we discuss two heuristic methods that can be used to speed up the implicit enumeration scheme adopted in the optimum method. Computing f(K), i.e., solving (P2), is the most time-consuming part in the optimum method. The first heuristic uses the concavity claim of f(K) in order to reduce the number of times to compute f(K). That is, marginal increase in f(K) is non-increasing in each of variables. This is stated as the following conjecture:

Conjecture. [delta][f.sub.c](K-[e.sub.c]) [greater than or equal to] [delta][f.sub.c](K) for all c = l,...,C + 2,

where [delta][f.sub.c](K) = f(K + [e.sub.c])-f(K).

Lemmas 1 and 2 show that f(K) has the monotonic property in [k.sub.c]. Shanthikumar and Yao [22] show that TH(S) has the concavity property in [S.sub.ci]. Although this law of diminishing returns is intuitively evident for f(K), it is difficult to prove. This concavity conjecture of f(K) leads to the following heuristic rule.

Heuristic 1.

Let [[delta].sup.c](K) = [(d-f(K)/[delta][f.sub.c](K)]. If f(K + [e.sub.c]) [less than] d, then fathom K + k x [e.sub.c] for every k [less than] [[delta].sub.c](K). This is because when f(K + [e.sub.c]) [less than] d, [[delta].sub.c](K) represents from the above conjecture the theoretical minimum number of additional units of type c required to meet the production requirements d. To make this more general, let [delta][f.sub.c] [(K).sup.n] = [(f(K + n x [e.sub.c])-f(K))/n]. [delta][f.sub.c](K) is viewed as a discrete gradient of the cth element based on a unit step while [delta][f.sub.c][(K).sup.n] is viewed as the counterpart based on step size n. Similarly define [[delta].sub.c][(K).sup.n] = [(d-f(K))/ [delta][f.sub.c][(K).sup.n]] for step size n [greater than or equal to] 1. If f(K + n x [e.sub.c]) [less than]d, then fathom K + k x [e.sub.c] for every k [less than] [[delta].sup.c][(K).sup.n].

This heuristic is implemented by maintaining two lists, [theta] and [psi]. The first list [theta] contains pairs of K and f(K), while the second list [psi] contains vectors of [K.sup.F] = K + [[delta].sub.c][(K).sup.n] x [e.sub.c] such that [K.sup.F1] [less than or not equal to] [K.sup.F2] for any two vectors in [psi]. Notation [K.sup.F1] [less than or not equal to] [K.sup.F2] means that there exists at least one element c such that [[K.sup.F1].sub.c] [less than] [[K.sup.F2].sup.c]. Each time a new K is considered such that z(K) is less than the incumbent cost [z.sup.*], we check if K [less than or equal to] [K.sup.F] for any [K.sup.F] in [psi]. If so, K is fathomed because f(K) [less than]d according to this heuristic. Otherwise, f(K) is computed and the two lists are updated.

The first heuristic above reduces the number of times to compute f(K) over different K's. The second heuristic speeds up computing f(K) for a given K. This heuristic method was introduced by Lee [21]. Here we give its brief description so that readers can understand its impact on the proposed design methods in terms of speed and the solution quality. We first define the two closely related subproblems of (P2) which seek W that maximizes TH for a given S.

(P4):

Max TH(W\S) subject to constraint (7) and W [greater than or equal to] 0.

(P4)':

Max TH(W\S) subject to constraint (7) and (8).

Solving (P2) requires solving (P4)' several times over different S's constructed from a given K. The second heuristic intends to reduce the number of times to solve (P4)'. Consider two server vectors of type p, [[S.sup.1].sub.p] and [[S.sup.2].sub.p]. Assume that [S.sub.p1] [greater than or equal to] ... [greater than or equal to] [S.sub.pMp] and let i be the first index such that [[S.sup.1].sub.pi] [less than] [[S.sup.2].sub.pi] for i [greater than] 1. If [[S.sup.1].sub.pj] [greater than or equal to] [[S.sup.2].sub.pj] for all j [less than] i and [[S.sup.1].sub.pj] [greater than] [[S.sup.2].sub.pj] for at least one j [less than] i, then we say that [[S.sup.1].sub.p] is more unbalanced than [[S.sup.2].sub.p] and denote [[S.sup.1].sub.p] [greater than] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [[S.sup.2].sub.p]. For example, (5,1,1) [greater than] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII](4,2,l) [greater than] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII](3,3,1). Also consider two server vectors, [S.sup.1] = ([[S.sup.1].sub.c]) and [S.sup.2] = ([[S.sup.2].sub.c]). If [[S.sup.1].sub.c] = [[S.sup.2].sub.c] for all c [not equal to] p and [[S.sup.1].sub.p] [greater than] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII][[S.sup.2].sub.p], then [S.sup.1] [greater than] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII][S.sup.2].

Suppose we solve the following special case of (P4): [W.sub.c] is fixed for all c except c = p and there is no workload bound constraint for type p. Then, from the conjecture by Stecke and Solberg [20] that the more unbalanced server vector provides the larger maximum TH for (P4), we have the following relation for this special (P4):

Max TH([W.sub.p]\[[S.sup.1].sub.p]) [greater than or equal to] Max TH([W.sub.p]\[[S.sup.2].sub.p]), if [[S.sup.1].sub.p] [greater than] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII][[S.sup.2].sub.p] (13)

If this optimum workload [[W.sup.*].sub.p] for [[S.sup.1].sub.p] is an interior point to (P4)', (i.e., [L.sub.pi] [less than] [[W.sup.*].sub.pi] [less than] [U.sub.pi] for all i), we can eliminate every [S.sub.p] such that [[S.sup.1].sub.p] [greater than] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII][S.sub.p] when the rest of the server vector S remains unchanged. This notion is generalized for multiple machine types as follows:

Heuristic 2:

Let [W.sup.*] be the optimum workload vector for (P4)' for [S.sup.1] = ([[S.sup.1].sub.c]) and J be {c\[L.sub.ci] [less than] [[W.sup.*].sub.ci] [less than] [U.sub.ci] for all i and for c = 1,...,C}. Then TH([W.sup.*]\[S.sup.1]) [greater than] Max TH(W\S) of (P4)' for each S = ([S.sub.c]) satisfying the following two conditions: (1) [S.sub.c] = [[S.sup.1].sub.c] for every c [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] J and (2) either [S.sub.c] = [[S.sup.1].sub.c] or [[S.sup.1].sub.c] [greater than] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII][S.sub.c] for every c [epsilon] J. For such S', therefore, this heuristic rule eliminates solving (P4)'.

Figure 2 shows the modified implicit enumeration scheme when these two heuristics are embedded. The following example illustrates both the optimum and heuristic methods.

Example 1. This example is based on an industrial FMS discussed in Stecke [25]. An FMS designer considers designing an FMS which simultaneously produces five different parts. Specific equipment types for processing, inspection, and material handling are selected and named as follows: MILL, VTL, DRILL, CMM (a coordinate measuring machine for inspection), L/UL (a loading and unloading station for pallet entry into or removal from the system), and AGVs. Table 1 summarizes the input data for these part types and equipment. The input data include: (1) average time required on each equipment to produce one part, [TW.sub.c]; (2) total number of tools required on each machine type to process all the part types; (3) tool magazine capacity in terms of the maximum number of tools that can be loaded on each machine type; (4) workload bounds, ([L.sub.ci], [U.sub.ci]); and (5) annually amoritzed equipment cost for investment and operation. We set the number of machine groups, [M.sub.c], to the smallest possible number tha t is determined by (2) and (3). Annual costs for WIP inventories and pallets are $100/part/year and $500/pallet/year, respectively. Thus, the objective function z(.) is written as:

Z([K.sub.c],...,[K.sub.c],[S.sub.0],N) = 60000 X [K.sub.1] + 30000 x [K.sub.2]

+ 50000 x [K.sub.3] + 40000 x [K.sub.4]

+ 10000 x [K.sub.5] + 6000 x [S.sub.0]

+ (500+ 100) x N.

The FMS will operate in two 8-hour shifts per day and the expected production requirements, d, is 200 parts/day.

We applied the proposed optimum method to this input data. The initial solution obtained by Procedure 1 is given as

Machine Groups and Workload Allocations, [S.sub.c] and [W.sub.c], for all c:

Mill = (1, 1, 1) & (4.3, 4.3, 4.3),

Drill = (2, 2) & (8.5, 8.5),

VTL = (2, 2)& (7, 7),

CMM = (2) & (7),

MHSs:

number of L/UL stations = 3,

number of AVGs, [S.sub.0] = 2,

number of Pallets, N = 50

System Through TH = 200.1 per day, and

Total Amortized Annual Cost = $652000 per year.

After execution of the implicit enumeration algorithm of Fig. 1 with the above initial solution, the following solution for the minimum-cost FMS design is found:

Machine Groups and Workload Allocations, [S.sub.c] and [W.sub.c] for all c:

Mill = (1, 1, 1) & (4.3, 4.3, 4.3),

Drill = (3, 1) & (13.1, 3.9),

VTL = (3, 1) & (11, 3),

CMM = (2) & (7),

MHSs:

number of L/UL stations = 3,

number of AVGs, [S.sub.0] = 2,

number of Pallets, N = 49

System Throughput TH = 200.2 per day, and

Total Amortized Annual Cost=$651400 per year.

In order to find the above solution, the proposed optimum method solved (P2) 114 times, solved (P4)' 456 times, and computed the throughput function, TH, 2749 times. We also applied to the same input data the two heuristic methods, Heuristic 1 and Heuristic-Com. Heuristic-Com uses both Heuristic 1 and Heuristic 2. Heuristic 1 and Heuristic-Com found the exact same solution as the optimum method, but required significantly less computation. Heuristic 1 solved (P2) only 19 times and (P4)' 76 times, and computed TH 528 times. Heuristic-Com further reduced computation. It solved (P2) the same number of times as Heuristic 1, but solved (P4)' only 32 times and computed TH 349 times. Consequently, the CPU times on an PC-586 recorded 35.1, 4.8, and 3.8 seconds for the three methods. We will provide more experimental results and interpretations on these methods in Section 4.

3.3. Batch sizing

So far we have considered a pallet loaded with only one part. When parts are small, however, a batch of parts can be mounted on a pallet using a special fixture such as a tombstone fixture [26]. A batch of parts, say, Q parts are processed consecutively at a machine and then moved together to the next machine by a transporter. Batch sizing can be effective in reducing costs for material handling resources without decreasing system throughput [6].

We can view a batch of Q parts as one part of a new product whose total workload for type c is Q x [TW.sub.c] and TH(S, [W.sup.Q]) as a rate at which pallets with completed parts leave the system at the L/UL. We can find minimum cost FMS designs over different Q values and the resulting mathematical formulation can be stated as follows:

[(P1).sup.Q]:

Minimize z([K.sub.1],...,[K.sub.C], [S.sub.0], N, Q),

Subject to:

Q x TH (N, S, [W.sup.Q]) [greater than or equal to] d, (14)

[[[sigma].sup.[M.sub.c]].sub.i=1] [S.sub.ci] = [K.sub.c], c = 1,...,C, (15)

[[[sigma].sup.[M.sub.c]].sub.i=1] [[W.sup.Q].sub.ci] = Q x [TW.sub.c], c = 1,...,C, (16)

Q x [L.sub.ci] [less than or equal to] [[W.sup.Q].sub.ci] [less than or equal to] Q x [U.sub.ci], i = 1,...,[M.sub.c], c = 1,...,C, (17)

1 [less than or equal to] Q [less than or equal to] [Q.sub.U] and integer, (18)

where the objective function z(.) increases in Q since WIP inventory cost increases in Q, [W.sup.Q] is the workload allocation of one part of the new product, and [Q.sub.U] is the upper bound on the batch size. [Q.sub.U] can be derived from the transfer capacity of a transporter or a pallet or from a maximal allowable limit on WIP parts. The decision variables of [(PI).sup.Q] are Q, S, [S.sub.0],N and [W.sup.Q] From [W.sup.Q], we can obtain the workload allocation of the original part, W, by dividing [W.sup.Q] by Q.

Lemma 3. If the material handling time is negligible (i.e., [W.sub.0] = 0), then the unit batch size is the optimum 9 to [(P1).sup.Q].

Proof. Suppose that the optimum solution to [(P1).sup.Q] is [A.sup.Q] = ([Q.sup.*], [S.sup.*], [[S.sup.*].sub.0], [N.sup.*], [W.sup.[Q.sup.*]] where [Q.sup.*] [greater than] 1. Consider another solution [A.sup.1] = (Q = 1, [S.sup.*], [[S.sup.*].sub.0], [N.sup.*], W = [W.sup.[Q.sup.*]] / [Q.sup.*]). When [W.sub.0] = 0, we have G(N, [W.sup.Q]) = [Q.sup.N] G(N, W) from Equation (2). and [W.sup.[Q.sup.*]] = [Q.sup.*] x W, which leads to TH ([N.sup.*], [W.sup.[Q.sup.*]]) = TH([N.sup.*], W)/[Q.sup.*]. Thus. [A.sup.1] is a feasible solution. Since z(.) increases in Q and other resource levels remain unchanged, Z([A.sup.Q]) [greater than] z([A.sup.1]) and we have a contradicition.

For some FMSs, [W.sub.0] is not negligible and can be represented as a function of Q. For example, as Q increases, a transporter becomes slower or loading/unloading times become longer. The solution method to [(P1).sup.Q] is simply to apply the proposed methods developed in the previous section for each Q, and to find one that gives the minimum cost.

Example 2. We use the same input data as Example 1 except the following changes. The FMS designer considers replacing MILL with a different machine [MILL.sup.B] which is faster and more flexible (i.e., a larger tool magazine capacity) but more expensive. He also considers using different transporter [AGV.sup.B] and pallets which are more expensive but capable of transferring up to a batch of 4 parts. Table 2 summarizes the changes in the input data. Note that the transfer time varies over batch size Q. Thus, the new objective function z(.) is

z([K.sub.1],...,[K.sub.C], [S.sub.0], N, Q) = 70000 x [K.sub.1] + 30000 x [K.sub.2]

+ 50000 x [K.sub.3] + 40000 x [K.sub.4]

+ 10000 x [K.sub.5] + 7000 x [S.sub.0]

+ (600 + 100 x Q) x N.

We applied the proposed optimum and Heuristic-Corn methods to this problem at each different Q value and summarized the solutions in Table 3. Again HeuristicCoin found the same solution as the optimum method at each Q with significantly less computation time. Table 3 shows that batch size Q = 2 gives the least cost, and the associated FMS design specification is given as follows:

Machine Groups and Workload Allocations, [S.sub.c] and [W.sub.c], for all c:

[Mill.sup.B] = (1, 1) & (4, 4),

Drill = (3, 1) & (13.2, 3.8),

VTL = (3, 1) & (11, 3)

CMM = (2) & (7),

MHSs:

number of L/UL stations = 3,

number of [AGV.sup.B]s, [S.sub.0] = 1,

number of Pallets, N = 34,

batch size, Q = 2

System Throughput TH = 200.7 per day, and

Total Amortized Annual Cost = $ 604200 per year.

This FMS design is superior to the previous one obtained in Example. 1. This design costs less by $47200/year but gives slightly higher throughput than the previous one. These benefits were possible with a combination of more flexible and faster milling machines and batch size, Q = 2. This helped to reduce [M.sub.1], [K.sub.1], [S.sub.0], and N from 3, 3, 2, 49 to 2, 2, 1 and 34, respectively, although the WIP level increased from 49 to 68. The larger batch size (Q [greater than] 2), however, did not bring any more benefits but increasing the WIP inventory cost.

This example illustrates that the proposed methods can be valuable in quickly investigating different FMS design scenarios such as various equipment and part type selections, cost factors, flexibility capacity, and batch sizing. The methods provides cost-effective design alternatives with key design specifications, and can be particularly useful at the early phase of FMS design.

4. Experiments

We conducted more extensive experiments to investigate the performance of the proposed optimum and heuristic methods. We considered five different FMSs that are numbered A to E. Table 4 summarizes their problem data sets including C, [W.sub.0], ([M.sub.c]), and ([TW.sub.c]). These data sets cover the wide range of parameter values: C up to six machine types, two different material handling workloads [W.sub.0] = 1 or 10, total number of machine groups [[sigma].sub.c] [M.sub.c] up to 13, and grand total workload [[sigma].sub.c] [TW.sub.c] up to 105 minutes. For each of these five problems, we used: (1) two different cost data sets (see Table 5); (2) two different throughput requirements (d = 100 or 200 per day); and (3) two sets of workload bonds, looser and tighter, such that the feasible region of the tighter bounds is a subset of that of the looser bounds (see Table 6). For simplicity, we assumed that [L.sub.ci] = [L.sub.c] and [U.sub.ci] = [U.sub.c] for all i Each FMS is operating two 8-hour shifts per day, i.e., [P.sub.0] = [P.sub.c] = 960 minutes for all c.

First we fixed batch size Q to 1 and applied to each of the 40 problems the three proposed methods, OPTIMUM (OPT), Heuristic 1 (H1), and Heuristic-COM (HC). Tables 7 and 8 summarize the following statistics collected for each of the three methods: (1) the minimum cost-found; (2) CPU time in seconds taken on an PC-586; (3) the number of times (P2) was solved; and (4) the number of times (P4)' was solved. Table 7 shows the summary statistics for 20 problems with the looser workload bounds. We numbered each of these 20 problems as a triple of FMS type, cost data set number, and throughput requirements. For example, B2/200 refers to FMS type B (3 machine types) with the 2nd cost data set and 200 daily throughout requirements. Table 8 shows the statistics for the other 20 problems with the tighter workload bounds.

The heuristic methods are very effective and efficient. Both heuristics, H1 and HC always found the same optimum solution as OPT for every problem tested. The heuristics required significantly less computation than OPT. For some problems, OPT took more than seven times longer than H1 and more than 27 times longer than HC. Problem El/200 with tighter bounds, for example, required 1.72 hours of CPU time by OPT, while it required about 14 minutes by H1 and only less than 4 minutes by HC (see Table 8). When (P1) is solved numerous times for different batch sizes of other design scenarios, OPT can be impractical for this problem. In this case the heuristic method, particularly, HC, is a useful alternative, yet as effective as OPT. On average, OPT took 3.6 times longer than H1 while took 6.2 times longer than HC. This reduction in CPU time is directly translated from reduction in the number of times (P2) is solved by H1 (ranging from 14 to 71% with an average of 34% of the number solved by OPT) and further reducti on in the number of times (P4)' is solved by HC (ranging from 4 to 66% with an average of 26% of the number solved by OPT). All the three methods generally required more computation for larger throughput requirements and a larger number of machine types, which led to a larger number of FMS configurations to search.

The minimum cost of the problems with looser bounds is slightly less (not exceeding 2%) than that of the counterpart problems with tighter bounds. The tighter workload bounds caused a smaller feasible region for workload allocation, which led to less unbalanced configuration, consequently, less chance to take advantage of resource pooling.

Heuristic HC is more efficient under the looser bounds, solving (P4)' less times by 21% on average than under the tighter bounds. With the looser bounds, the optimal workload allocation of (P4)' becomes an interior point more often, which consequently makes the second heuristic rule more effective. Heuristic H1 is more efficient under larger throughput requirements. The CPU time ratio of OPT/H1 (see Table 7) is larger most times when d = 200 than when d = 100 (there is one exception, Problem El). This is because a larger number of (P2) needs to be searched larger d and H1 prunes more (P2) from consideration.

We also studied the effect of batch size Q. We used the same problem data sets as above. Assuming that [W.sub.0] remained unchanged by Q, we solved [(P1).sup.Q] at eight different values of Q, i.e., Q= 1, 2, 3, 5, 7, 10, 15, and 20. Figure 3 depicts the minimum cost z over these Q values for the four representative problems. These problems are B1/200, C1/200, D1/100, and E1/100 with the tighter bounds. Similar results were obtained for the other problems.

Figure 3 shows that a unit batch size is the optimum for El/100 and C1/200. These two problems have a small material handling time ([W.sub.0] = 1), which leads to compliance of Lemma 3. Under a larger material handling time ([W.sub.0] = 10), the optimum batch size increases to 2 and 3 for D1/100 and Bl/200, respectively. Figure 3 indicates that the minimum cost curve is unimodal with respect to Q. In fact, this was true for every problem we tested. This gives empirical evidence that [(P1).sup.Q] can be solved with a more efficient search on optimum Q such as a bisection search method rather than enumeration without sacrificing the solution quality. Again, both heuristics, H1 and HC, always found the same optimum solution as OPT at every Q for all the problems with significantly less computation time.

5. Conclusions

FMSs require large capital investment and a large portion of this investment is committed at the early design stage. Manufacturing systems design involves the solution of a complex series of interrelated problems. This design complexity further increases in integrated manufacturing systems such as FMSs, and designing cost-effective yet functional FMSs is a challenging process. In this paper, we have presented analytical methods that can assist this design process by simultaneously determining several key design parameters for FMSs. To our knowledge, these are the most general analytical design methods that use the CQN model for FMSs. We first presented the optimum method using an implicit enumeration algorithm. In order to speed up the optimum method, we also presented a heuristic method. Experimental results show that the heuristic method always finds the optimal solution with significantly less computation, solving a moderate size of FMS design problems (up to six machine types and 13 machine groups) in les s than 4 minutes on a PC.

One future research direction is to combine the proposed methods with simulation. The proposed methods are analytical queueing model-based and suitable for the early design stage where many design alternatives need to be narrowed into a small number of potential candidates. Simulation can use the results form the proposed methods as input in order to perform detail analysis for fine-tuning of design parameters. Such a combined framework is introduced for designing flexible assembly systems [15].

A hybrid simulation and expert system can also be used for detail analysis in order to reduce trial and errors required by simulation alone [27,28].

Acknowledgements

This research is supported in part by grants from National Science Foundation (Grant No. DDM-9201954) and from Southern Illinois University at Edwardsville. The author thanks Ming Zhou for his help with coding and experimenting the proposed methods.

Biography

Heungsoon Felix Lee is an Associate Professor of Industrial Engineering at Southern Illinois University at Edwardsville. He holds a B.S. in Industrial Engineering from Hanyang University in Korea, an M.S. in Industrial Engineering and Management from Oklahoma State University, and a Ph.D. in Industrial and Operations Engineering from the University of Michigan. His current research interests are in the design and management of advanced manufacturing and material handling systems. He is a recipient of a NSF research grant on developing an integrated design-aid tool for flexible manufacturing systems. Dr. Lee is a member of IIE, INFORMS, Tau Beta Pi, and Phi Kappa Phi. His papers appear in various journals including International Journal of Flexible Manufacturing Systems, Journal of Manufacturing Systems, Performance Evaluation, Expert Systems with Applications, lIE Transactions, Naval Research Logistics, International Journal of Production Research, Telecommunication Systems, and Computers and Industrial Engin eering.

Contributed by the Manufacturing Systems Modeling Department.

References

(1.) Vinod, B. and Solberg, J.J. (1985) The optimal design of flexible manufacturing systems. International Journal of Production Research, 23, 1141-1151.

(2.) Dallery, Y. and Frein, Y. (1988) An efficient method to determine the optimal configuration of a flexible manufacturing system. Annals of Operations Research, 15, 207-225.

(3.) Kouvelis, P. and Lee, H.L. (1995) An improved algorithm for optimizing a closed queueing network model of a flexible manufacturing system. IIE Transactions, 27, 1--8.

(4.) Tetzlaff, U. (1995) A model for the minimum cost configuration problem in flexible manufacturing systems. International Journal of Flexible Manufacturing Systems, 7, 127-146.

(5.) Askin, R.G. and Krisht, A.H. (1994) Optimal operation of manufacturing systems with controlled work-in-process levels. International Journal of Production Research, 32, 1637-1653.

(6.) Millar, H.H. and Yang, T. (1996) Batch sizes and lead time performance in flexible manufacturing systems. International Journal of Flexible Manufacturing Systems, 8, 5-21.

(7.) Heavey, C. and Browne, J. (1996) A model management systems approach to manufacturing systems design. International Journal of Flexible Manufacturing Systems, 8, 103-130.

(8.) Dessouky, M.M. and Wilson, J.R. (1991) Minimizing production costs for a robotic assembly system. Engineering Costs and Production Economics, 21, 81-92.

(9.) Lee, H.F., Srinivasan M.M. and Yano, C.A. (1991) The optimal configuration and workload allocation problem in flexible manufacturing systems. International Journal of Flexible Manufacturing Systems, 3, 213--230.

(10.) Vollbracht, G.R. (1986) The time for CAEDM is now, in Proceedings of the Fourth National Conference on University Programs in Computer-Aided Engineering, Design and Manufacturing, Purdue University, West Lafayette, IN. pp. 86-92.

(11.) Hatter, J.A. and Mueller, C.J. (1988) FMS at Remington, Manufacturing Engineering, 100, 91-95.

(12.) Kouvelis, P. (1991) Design and planning problems in flexible manufacturing systems: a critical review. Journal of Intelligent Manufacturing, 3, 75-99.

(13.) Solot, P. and van Vliet, M. (1994) Analytical models for FMS design optimization: a survey. International Journal of Flexible Manufacturing Systems, 6, 209-233.

(14.) Jackson, J.R. (1963) Jobshop-like queueing systems. Management Science, 10, 131-142.

(15.) Lee, H.F. and Stecke, K.E. (1996) An integrated design support system for flexible assembly systems. Journal of Manufacturing Systems, 15, 13-32.

(16.) Tempelmeier, H. and Kuhn, H. (1993) Flexible Manufacturing Systems: Design Support for Design and Operation. John Wiley and Sons, New York, NY.

(17.) Reiser, M. and Lavenberg, S. (1980) Mean-value analysis of closed multichain queueing networks. Journal of the Association for computing Machinery, 27, 313-322.

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

(19.) Siogh, N. (1996) Systems Approach to Computer-Integrated Design and Manufacturing, John Wiley & Sons, New York, NY.

(20.) Stecke K.E. and Solberg, J.J. (1985) The optimality of unbalancing both workloads and machine group sizes in closed queueing networks of multi-server queues. Operations Research, 33, 882-910.

(21.) Lee, H.F. (1998) Production planning for flexible manufacturing systems with multiple machine types: a practical method. International Journal of Production Research, 36, 2911-2927.

(22.) Shanthikumar, J.G. and Yao, D.D. (1987) Optimal server allocation is a system of multi-server stations. Management Science, 33, 1173-1180.

(23.) Shanthikumar, J.G. and Yao, D.D. (1988) On server allocation in multiple center manufacturing systems. Operations Research, 36,333-342.

(24.) Lawler, E.L. and Bell, M.D. (1966) A method for solving discrete optimization problems. Operations Research, 14, 1098-1112.

(25.) Stecke, K.E. (1991) flexible manufacturing systems: design and operating problems and solutions. Industrial Engineering Handbook, Hodson, W.K. (ed), McGraw-Hill, New York, NY, pp.7.6.1-7.6.39.

(26.) Luggen, W.W. (1991) Flexible Manufacturing Cells and Systems, Prentice Hall, Englewood Cliffs, NJ.

(27.) Floss, P. and Talavage, J. (1990) A knowledge-based design assistant for intelligent manufacturing systems. Journal of Manufacturing Systems, 9 87-102.

(28.) Lee, H.F., Cho, H.J. and Klepper, R. (1996) A hybrid expert and simulation system (HESS) for resource planning in service and manufacturing industries. Expert Systems with Applications, 10, 147-156.

                         Input data for Example 1
                                             Machines
                                               MILL    DRILL    VTL    CMM
[TW.sub.c] (in mimutes) [1]                     13      17      14      7
Number of tools needed                         110      60      50
Tool magazine size                              50      50      40
Number of m/c groups [M.sub.c]                  3        2       2      1
Workload bounds ([L.sub.ci], [U.sub.ci]) [2] (1, 11)  (2, 15) (3, 13)
Amortized annual cost ($)                     60000    30000   50000  40000
                                             MHSs
                                             L/UL  AGV
[TW.sub.c] (in mimutes) [1]                   10    5
Number of tools needed
Tool magazine size
Number of m/c groups [M.sub.c]                 1
Workload bounds ([L.sub.ci], [U.sub.ci]) [2]
Amortized annual cost ($)                    10000 6000
(1.)[TW.sub.c] for AGV is the same as [W.sub.0]
(2.)For simplicity, [L.sub.ci] = [L.sub.c] and
[U.sub.ci] = [U.sub.c] for all i
                   Changes in input data for Example [2]
                                             Alternative equipment
                                                 [MILL.sup.B]
[TW.sub.c] (in minutes)                                8
Number of tools needed                                110
Tool magazine size                                    75
Number of m/c groups [M.sub.c]                         2
Workload bounds ([L.sub.ci], [U.sub.ci]) [1]        (1, 7)
Amortized annual cost ($)                            70000
                                              [AGV.sup.B]
[TW.sub.c] (in minutes)                      4 + [Q.sup.2]
Number of tools needed
Tool magazine size
Number of m/c groups [M.sub.c]
Workload bounds ([L.sub.ci], [U.sub.ci]) [1]
Amortized annual cost ($)                        7000
(1.)For simplicity [L.sub.ci] = [L.sub.c] and
[U.sub.ci] = [U.sub.c] for all i
(2.)[TW.sub.c] for AGV is a function of Q, i.e.,
[W.sub.0](Q) = 4 + Q for 1 [less than or equal to]
Q [less than or equal to] [Q.sup.U] = 4
(3.)The new pallent costs $600/pallent/year
              Example 2: optimum FMS design with batch sizing
                   CPU times (seconds) by the
                     two proposed methods
Q Minimum cost ($)          Optimum           Heuristic-Com
1      607800                 9.8                  1.2
2      604200                10.5                  1.7
3      606700                10.9                  1.5
4      610000                13.9                  1.5
                             Problem data sets
Problem C [W.sub.0]    ([M.sub.c])           ([TW.sub.c])
A       2     1           (3, 2)               (20, 15)
B       3    10         (3, 2, 5)            (20, 15, 25)
C       4     1        (3, 2, 2, 1)        (20, 15, 25, 10)
D       5    10      (3, 2, 2, 1, 2)     (20, 15, 25, 10, 15)
E       6     1     (3, 2, 2, 1, 2, 3) (20, 15, 25, 10, 15, 20)
An FMS is operating two 8-hour shifts per day for every problem
                   Equipment costs for problem data sets
Problem Cost data set 1 (unit: $1000) fpr [K.sub.1]...,
                  [K.sub.C], [S.sub.0] N [1]
A                       12, 13, 5, 1.01
B                     23, 63, 54, 9, 1.31
C                   52, 43, 34, 12, 5, 1.01
D                 92, 73, 64, 31, 15, 9, 1.31
E              82, 43, 64, 51, 95, 12.5, 4, 1.4
Problem Cost data set 2 (unit: $1000) for [K.sub.1]....,
                  [K.sub.C], [S.sub.0], N [1]
A                       23, 54, 9, 1.31
B                     43, 13, 74, 5, 1.01
C                   22, 83, 14, 10, 9, 1.31
D                 15, 31, 64, 11, 92, 9, 1.31
E               42, 13, 94, 61, 35, 72.5, 8, 1.3
(1.)WIP cost = $100/part/year for every problem
                   Workload bounds for problem data sets
Problem       Losser bounds ([L.sub.c] [U.sub.c]) [1]
A                        (1, 18), (3, 14)
B                    (1, 19), (1, 14), (1, 24)
C               (1, 18), (3, 14), (1, 23), (1, 10)
D           (1, 18), (3, 14), (1, 23), (1, 10) (1, 14)
E       (1, 18), (3, 14), (1, 23), (1, 10) (1, 14), (1, 18)
Problem     Tighter bounds ([L.sub.c], [U.sub.c]) [1]
A                       (4, 10), (4, 10)
B                   (3, 13), (3, 10), (4, 8)
C               (4, 9), (5, 9), (10, 15) (1, 10)
D          (6, 10), (6, 10), (7, 15), (1, 10), (4, 11)
E       (5, 9), (4, 11), (8, 15), (1, 10), (6, 9), (4, 8)
(1.)[L.sub.ci] = [L.sub.c] and [U.sub.ci] = [U.sub.c] for all i

               Experimental results with the three proposed
                      methods: looser workload bounds
                Optimum (OPT)             Heuristic 1 (H1)
        Mimimum      CPU      (P2)  (P4)'       CPU        (P2) (P4)'
Problem  cost       (sec)                      (sec)
A1/100    80320       1        12     12         1           4     4
A1/200   142320       1         7     42         1           5    30
A2/100   202920       1        10     10         1           4     4
A2/200   379920       1         5     30         1           3    18
B1/100   508380       2        14     14         1           4     4
B1/200   989430      19        10    420         8           5   210
B2/100   554980       2        17     17         1           4     4
B2/200  1090530      23        12    504         8           5   210
C1/100   426980       2        17     34         1           6    12
C1/200   760080      18        37    666         5          12   216
C2/100   342380       2        18     36         1           9    18
C2/200   625070      19        35    630         5          12   216
D1/100   824660       4        36     72         1          10    20
D1/200  1461580      81        54   1944        14          13   468
D2/100   623660       5        48     96         1          14    28
D2/200  1079580      70        72   2700        14          18   684
E1/100   968000      21       119    244         3          22    44
E1/200  1724500    4403       147  17100       717          26  3096
E2/100   988900       8        62    126         2          15    30
E2/200  1694200    2583        76   8262       459          16  1728
        Heuristic-Com (HC)             CPU time
                                      comparison
               CPU         (P2) (P4)'   Opt/H1   Opt/Hc
Problem       (sec)
A1/100          1            4    4      1.0      1.00
A1/200          1            5   13      1.0      1.00
A2/100          1            4    4      1.0      1.00
A2/200          1            3    7      1.0      1.00
B1/100          1            4    4      2.0      2.0
B1/200          3            5   30      2.38     6.33
B2/100          1            4    4      2.0      2.0
B2/200          3            5   30      2.88     7.67
C1/100          1            6   12      2.00     2.0
C1/200          5           12  199      3.60     3.60
C2/100          1            9   18      2.00     2.0
C2/200          5           12  199      3.80     3.80
D1/100          1           10   20      4.00     4.00
D1/200          6           13  217      5.79    13.50
D2/100          1           14   28      5.00     5.00
D2/200          8           18  325      5.00     8.75
E1/100          3           22   43      7.00     7.00
E1/200        202           26  901      6.14    21.80
E2/100          2           15   29      4.00     4.00
E2/200        136           16  541      5.63    19.00
               Experimental results with the three proposed
                     methods: tighter workload bounds
                Optimum (OPT)             Heuristic 1 (H1)
        Minimum      CPU      (P2)  (P4)'       CPU        (P2) (P4)'
Problem  cost       (sec)                      (sec)
A1/100    80320       1        12     12         1           6     6
A1/200   144540       1         8     48         1           5    30
A2/100   202920       1        10     10         1           6     6
A2/200   382740       1         6     36         1           3    18
B1/100   508380       2        14     14         1           5     5
B1/200   989430      19        10    420         6           4   168
B2/100   554980       2        17     17         1           5     5
B2/200  1090530      23        12    504         6           4   168
C1/100   426980       2        17     34         1           6    12
C1/200   763410      22        45    810         5          13   234
C2/100   342380       2        18     36         1           9    18
C2/200   630710      28        52    942         7          16   294
D1/100   824660       4        36     72         1          10    20
D1/200  1465810      93        62   2232        13          12   432
D2/100   623660       5        48     96         1          14    28
D2/200  1083810      93        93   3564        17          21   828
E1/100   969500      23       126    262         3          23    46
E1/200  1730500    6192       194  24048       809          28  3492
E2/100   990300       9        65    134         2          14    28
E2/200  1699800    3444        99  11016       574          19  2160
        Heuristic-Com (HC)             CPU time
                                      comparison
               CPU         (P2) (P4)'   Opt/H1   Opt/HC
Problem       (sec)
A1/100          1            6     6     1.0       1.0
A1/200          1            5    30     1.0       1.0
A2/100          1            6     6     1.0       1.0
A2/200          1            3    18     1.0       1.0
B1/100          1            5     5     2.0       2.0
B1/200          2            4    24     3.3       9.5
B2/100          1            5     5     2.0       2.0
B2/200          2            4    24     3.8      11.5
C1/100          1            6    12     2.0       2.0
C1/200          6           13   234     4.4       3.7
C2/100          1            9    18     2.0       2.0
C2/200          8           16   294     4.0       3.5
D1/100          1           10    20     4.0       4.0
D1/200          6           12   216     7.8      15.5
D2/100          1           14    28     5.0       5.0
D2/200         10           21   414     5.5       9.3
E1/100          3           23    46     7.7       7.7
E1/200        226           28  1008     7.7      27.3
E2/100          2           14    28     4.5       4.5
E2/200        183           19   726     6.0      18.8