A design methodology for fractal layout organization.

1. Context

The evolution of the job shop has been very interesting from its early beginnings as a function layout. Historically. it was first organized as a function layout with workstations of the same type arranged together. Due to the well known disadvantages inherent in function layouts.

cellular manufacturing systems were advocated through much of the 70s and the 80s. They are group layouts with cells devoted to products, though it must be noted that the enthusiasm towards them has recently waned and the literature is increasingly moving towards hybrid cellular systems and virtual manufacturing systems [1]. To quote the authors, "a combination of overlapping GT cells, functional layout and handling reduces the need for machine duplication among cells."

The authors introduce a method for cell formation integrating machine grouping and layout design, resulting in hybrid layouts that consist of machine groups, flow line layouts corresponding to each group, and an ordering of these line layouts to maximize the advantage of mutual proximity. Their article strongly emphasizes the inadequacy of the part formation formulation proposed by many researchers in the GT literature where duplication is generally favored over cell dependence, and where the binary input data does not capture travel distances, flow volumes, and machine rates. Another reason for the declining enthusiasm towards GT is its perception among researchers and practitioners as being inflexible and rigid. One observes a trend towards job shop layout where workstations of different types are strategically dispersed, as discussed in Heragu and Chen [2].

A new generation of layouts was deemed necessary for new and dynamic manufacturing environments that need to adapt to changing products and technologies, pressures to reduce lead times and inventories, compulsions to customize products, through quicker product changeovers and just-in-time deliveries. Such systems are referred to in the literature as agile manufacturing systems. These systems are the consequence of developments such as virtual manufacturing and virtual enterprise planning which paved the way for virtual organizations [3] in the manufacturing sector. For a discussion on the virtual manufacturing cell, and the more general virtual manufacturing system, the reader is referred to Drolet et al. [4], McLean et al. [5], Montreuil et al. [6], and Simpson et al. [7].

The holographic layout introduced by Montreuil et al. [8] is an example of a new generation layout for agile manufacturing. Here, a workstation that has only one replicate available would be placed right in the center of action of the layout while workstations with greater representation would be strategically distributed throughout the factory floor. Holographic layouts have been developed for robustness in the face of agile environments with very little information available about products and their specific routings. It is assumed on the other hand that inter-process flow rates are known and hypotheses can be made as to how inter-processor flow occurs.

It was in this context that the fractal layout was originally conceived, intended to be an agile manufacturing alternative achieved through the creation of multifunction mini factories within the confines of a factory. It was felt that the holographic layout methodology described by Montreuil et al. [8] did not take into account product routing information. While the products themselves change rapidly and acquire newer design characteristics and options, the agile manufacturing sector often consists of instances where the underlying routing structure retains relative stability.

Also, while the holographic organization (termed hoIonic organization by Askin et al. [9]) advocates systematic dispersion through the floor, we preferred dispersion within zones with the zones themselves fixed and zonal compositions specified at start based on various factors. The zones are populated with machines in order to take into account dominant product routings from the nature of the industry. This results in the formation of core centers of multifunctional competence in the manufacturing system. Expansion is achieved simply by replicating them, and flexibility by the fact that any center can process any product (even if that is not its most ideal assignment). An example from real life includes service lines in the fast food industry, where a worker at each counter can service any request.

2. The fractal layout

2.1. Definition

The layout of a job shop (group, function, etc.) has an influence on the visual characteristic of its layout. The fractal organization [ILLUSTRATION FOR FIGURE 1 OMITTED] for job shops was first proposed by the current authors [10]. Under this system, the basic unit of organization is the fractal cell, a set of contiguous workstations on the shop floor that are capable of processing most, if not all products that enter the system. Each fractal cell has a composition of workstation types in proportion to that in the overall shop.

The fractal layout, starts with an a priori assignment of workstations to cells; regions in 2D space such that the processing capability available within each region is roughly similar to that available in any other. If we can think of the density of a workstation type in a cell to be the number of processors of that type available to the total number of processors available, each cell in the fractal cell layout is of roughly the same density. Thus the basic entity in the fractal organization, the fractal cell, is in fact a multifunctional mini shop. It is natural to design the fractal layout by determining the cell layout and patching them together either as the design evolves or after they themselves are already designed.

2.2. The fractal layout as an agile alternative

Askin et al. [9] compare process, fractal, and holographic layouts over a set of varying conditions with random part routings and exponential operation and inter-arrival times, based on queuing theory and a wide variety of test conditions. They conclude that the process layout is dominated by the holonic (or holographic) and fractal layouts, and though the holonic layout provides the best performance under a number of conditions, it is not robust. In their paper, they conclude that fractal layout with a nearly square arrangement of machines is the safest choice for agile manufacturing.

Some disadvantages may also arise. Each cell encapsulates multi-process functionality thus making it more diverse and thereby more difficult to manage. One way around the problem is to define cells of core competencies (say a drilling machine, a turning center, a finishing center with grinding and heat treatment capability), call that a fractal cell, and replicate it throughout. Cell competency may then be enhanced through a constant improvement of this core group, which is at the same time flexible enough to accommodate a wide variety of products.

3. Aggregate design issues

The fractal organization poses a number of design challenges. One has to decide how the products get processed through particular machines in the job shop. We call this the flow assignment problem. While this problem is a casual detail in familiar process and product organizations, it is not trivial in fractal cell design. In addition, the processor layout problem within fractal cells and the cell layout problem with relation to each other are both hard; the former due to the variety of processes present in the cell and the latter due largely to the fact that cells are not independent. Therefore, the development of inter- and intra-cell layouts calls for a coordinated design effort that looks at core issues in fractal cell design - capacity planning, cell creation, product assignment, cell layout and global layout.

[TABULAR DATA FOR TABLE 1 OMITTED]

The context for this discussion is the example presented by Co and Arrar [11] who have developed a methodology for configuring cellular manufacturing systems. Details on part routings, and processing times are provided in their paper. Processing is limited by machine hours available during a week. Likewise, all ideas in the paper were also tested on six other cases whose sources are listed in Table 1. The number of workstation replicates in the table is shown as a range because it is a function of whether the layout is organized as a process shop, group shop, fractal shop, or holographic shop. Case 6 was a real industrial case adapted to maintain confidentiality. The rest were taken from the literature. They were selected on the basis of completeness, representation, and convenience. Cases 1, 2, 3, 5, and 6 are more or less classic job shop cases wherein products have a fair amount of diversity in routings. Case 4 is more of a flow shop. In Case 7, all products visit all workstation types, making group organization more difficult.

3.1. Capacity planning

We need to know the number and type of workstations that ought to be made available. For manufacturing systems this can be quite a delicate issue, but we restrict ourselves to a strategy that is simple; we employ capacities close to what is demanded by function layout implementations. The function layout is the job shop organization that is considered to possess highest equipment utilization, and thus it usually dictates minimum capacity. This is true because of the aggregation that takes place at the process departments, allowing for better planning and resource utilization.

The basic model often quoted in the literature [2,18] is based on available hours and required hours as shown below:

[Mathematical Expression Omitted],

Where:

[Mathematical Expression Omitted] = smallest integer greater than or equal to *;

[N.sub.t] = number of workstations required of type t;

[D.sub.j] = demand for product j;

[A.sub.jt] = hours of machine type t used by one unit of product type j;

[M.sub.t] = working hours available on a machine of type t during period of demand.

The ratio presented above is the ratio of machining hours required to machining hours available. With reference to the example in Co and Arrar [11], the model translates into 4 replicates of workstation 7, 2 replicates of workstation 9, and 3 replicates of everything else, implying a total of 30 workstations. Calculations are presented in Table 2. This very balanced result from the viewpoint of machines required of each type and thereby ease of fractal cell creation, may not always occur.

While the above model is quite simple, it denotes a start to the capacity planning process and we used it as such for computational work related to this research. The real capacity issues, however, arise also from operational parameters such as the costs of purchasing and installing machines, failure rates, machine flexibility, and setups incurred. Strategic decisions are often made in GT implementations, such as those considered in Seifoddini and Wolfe [19], where additional machines are purchased to minimize exceptional elements in the part machine incidence matrix and reduce thereby intercell transfers. The strategy applies to fractal layout. In fractal layouts, we encounter the relationship presented in Fig. 2. We are in [TABULAR DATA FOR TABLE 2 OMITTED] the process of developing a capacity model based on process information, machine capabilities, product mixes, and product response time for cells in cellular systems such as the group layout and the fractal layout. Integrating such a model into a comprehensive factory design strategy is a challenging task to which no easy answers are known.

3.2. Cell creation

The basic question here is one of allocating workstation replicates to cells in a manner appropriate to the fractal philosophy being propounded. Under the fractal organization, process capacities are distributed evenly across cells. Hence it is necessary to emphasize that the perspective here is different from group design in which cell grouping is product oriented, its basis being a thorough examination of product routings.

A natural design for a fractal cell system in the Co and Arrar [11] example would be one with 3 cells. There are two reasons for this. First, the average number of workstations of each type is roughly 3. Second, this choice leads to a cell population of 10 workstations, which is within tractable standards of 5 to 15 machines in a cell. We are not necessarily limited to the planned 30 workstations. As already mentioned, adding a few more workstations may help alleviate congestion and improve flow efficiency. In a case like this, two out of many alternatives are:

1. Assign 1 workstation of each type (other than 7 and 9) to the 3 cells. One of the cells can be assigned the extra workstation of type 7, and on the contrary, contain no workstation of type 9;

2. Make the provision for 2 additional workstations of type 7 and 1 additional workstation of type 9. Then distribute the workstations evenly across cells.

In some of the other cases encountered, the cell creation process was more difficult, specially with the absence of detailed cost data. The cells were created based on the information in Table 3.

In that table, a value of {3,2,2,2,4} in the column pertaining to the requirements string implies that we need 3 replicates of machine type 1, 2 of machine type 2, 2 of machine type 3, and so on. Recognizing that a thorough investigation of the cell creation process was outside our scope of current research, we tried more than one way to create fractal cells wherever it was possible, and kept those that yielded the best flow scores. The term flow score here refers to a measure of material handling cost estimated as a function of frequency and distance traveled.

We discuss two cases from Table 3 to highlight how one can proceed with this kind of information:

1. In case 5, machine types 5 and 6 had only one replicate in a three-fractal design. These replicates were then both assigned arbitrarily to fractal cell 3. When fractal processor layouts were developed, it turned out that machine type 5 was not critical, and its sole replicate gravitated to the periphery in the layout developed, while machine 6 was more critical and was attracted to the layout center;

2. In case 6, by choosing 6 additional machines, we were able to obtain {3,6,3,3,4,3,3,4} as the number of machines of each type. This was easily divisible in 3 cells, as the numbers 3 and 6 are divisible by 3. As for machine types 5 and 8, which had 4 replicates, the third cell was assigned the extra replicate in the cell allocation process.

Another issue is the trade-off between having too many cells and having too few. At one extreme, the entire job shop may be viewed as a cell although this is hardly what we want. Large cells also lose meaning because in practice job shops could have up to 60 or 70 machines. By the same token, it is not desirable to have too many fractal cells. If the cells are too small in size, they may not adequately represent the job shop.

Finally, excess capacity used due to rounding up the needed number of replicates in each cell should be minimized, whenever dealing with expensive machines. One of [TABULAR DATA FOR TABLE 3 OMITTED] the advantages of the fractal layout is that machines may be shared between cells, making the duplication effort optional. If for example, 1.98 replicates are needed in total in a 3-cell fractal layout, the average number required per cell is 0.66, and having 1 replicate in each cell does not result in as much duplication as the same solution applied to the situation where 1.5 total replicates are needed.

To partially conclude, fractal cells are not intended to be self contained entities. In fact, the rationale is to achieve spatial dispersion of machines with recognition given to part routings. As a result, it is not expected that small variations in the machine to cell assignment will significantly alter the performance or the appearance of the job shop, and rules of thumb may be developed for the cell creation process. In all our case studies, we tried to maintain a healthy balance between duplication and good fractal definition. Though level of capacity used was usually a little higher than in process layout implementations, it was usually much lower than in pure group layouts.

3.3. Flow assignment

Consider the layout in Fig. 3, where the notation MT - N refers to the replicate N of machine type T. From such a layout we must ask what assignment of products to workstations will minimize flow travel, if there are several products with specified machine type to machine type routings to be processed. We assume that flows between workstations will take place between their centroid locations.

For any given layout, there is an assignment of products to flow paths that minimizes travel distance. The only constraint is that workstation capacity should not be exceeded. Even though product demands are integers, it is quite practical to formulate the problem as a linear program, the solution of which normally yields fractional results. Flow assignment may be represented by the following model:

Minimize [Mathematical Expression Omitted].

Subject to:

[summation over k] [x.sub.jk] [greater than or equal to] [D.sub.j] [for every] j, (1)

[Mathematical Expression Omitted], (2)

[x.sub.jk] [greater than or equal to] 0 [for every]j. [for every]k, (3)

Where:

[C.sub.jk] = distance implied by path k for product j;

[x.sub.jk] = quantity of products of type j that use path k;

[D.sub.j] = demand for product j, i.e. product fraction times total demand;

[M.sub.t] = workstation capacity of replicate t;

[A.sub.jt] = usage of replicate t by one unit of product type j (processing time;

[A.sub.jkt] = [Mathematical Expression Omitted].

The above may be recognized as the arc-path formulation of the multicommodity network flow model (MCNF), a special form of linear programs [20]. Note that in this model, we reorder all replicates from 1,..., T, where T represents the total number of replicates in the fractal shop. The model allows product splitting because there are no constraints stating that all products of a kind should follow a unique arc-path. Since [x.sub.jk] represents the flow in path k for product j, one can immediately say that there are j times k such variables. Furthermore, if each product has [N.sub.j] stages in processing, and if there are [f.sub.n] workstations at each of these stages. n = 1,2,..., [N.sub.j], the number of paths k for each product is [[Pi].sub.n=1,[N.sub.j]] [f.sub.n], which can be quite large. As a practical matter, paths are not enumerated. Instead a column generation scheme (discussed in the following section) arising from the special structure of the multicommodity network flow linear program is employed.

We can state in simple terms what the [x.sub.jk] variables stand for. Recall that these are start-to-finish paths in the MCNF model. In Fig. 3. two such paths are shown for Product 1 in our example problem. The first of these paths, [P.sub.1], represents a part of the production of Product 1, namely 20 units, assigned to the path:

M1 - 1, M4 - 1, M7 - 2, M3 - 1, M10 - 1, M8 - 3.

A flow of 20 units will be created between each pair of consecutive workstations in this sequence. It is obvious that the path [P.sub.2] with the sequence:

M1 - 2, M4 - 2, M7 - 3, M3 - 2, M10 - 2, M8 - 2,

has lower travel, and is therefore preferable.

3.3.1 Column-generation method

Because paths are exponentially many, the model is solved using the modified Ford-Fulkerson technique developed by Tomlin [21]. The modification arises from the special form of the objective function. We may observe that the linear program has a large number of columns, and J + W constraints, where J is the number of products, and W, the number of workstations.

We can now define the arc-chain incidence matrix by:

[Mathematical Expression Omitted] (4)

As [x.sub.jk] is an arc-path, i.e, a source to sink path for product j, one could break up the objective function into the form [Mathematical Expression Omitted]. In this summation, [c.sub.jkt] is the distance implied in the transfer of the job to replicate t from its predecessor replicate in path k of product j, in accordance with the job routing requirement.

Now, let us suppose that we have a basic feasible solution and the simplex multipliers [u.sub.1], [u.sub.2], ..., [u.sub.J] for constraint set 1, and multipliers [v.sub.1], [v.sub.2], ..., [v.sub.W] for constraint set 2.

Then the path variable [x.sub.jk] will be introduced into the basis if:

[C.sub.jk] - [summation over t][v.sub.t][A.sub.jkt] - [u.sub.j] [less than or equal to] 0. (5)

i.e., if:

[summation over t] ([c.sub.jkt] - [v.sub.t][A.sub.jt])[I.sub.jkt] - [u.sub.j] [less than or equal to] 0. (6)

A shortest path algorithm attaching costs ([c.sub.jkt] - [v.sub.t][A.sub.jt]) to nodes t may be used to search for paths k satisfying the above condition for product j, once an initial basic feasible solution is obtained (see Fig. 4). Finding an initial basic solution is easy: we can simply pick the shortest path for each product, and assign as many units of flow to each, as permitted by the capacity constraints. A simple calculator was written to implement this procedure.

Fig. 4. Procedure 1: column-generation.

Procedure 1. Column-Generation

Step 0:   Start.

Step 1:   Solve shortest-path networks to decide entering columns
          for MultiCommodity Network Flow Model (MCNF).

Step 2:   Solve MCNF model with columns generated so far.

Step 3:   If enough columns have already been generated, stop.

Step 4:   Modify shortest-path network by subtracting duals of
          capacity constraints obtained in Step 2. Solve these
          to obtain new columns for MCNF model. Return to Step 2.

When the source to sink shortest path for a product j is obtained during any iteration, it identifies the [x.sub.jk] variable to enter into the model. The convention in our implementation has been to solve the shortest path network for each product in any given iteration, and then enter them all in a batch. If during any iteration, the column [x.sub.jk] slated to enter by finding the modified shortest path to the product j network is one that was already entered, no column is entered. Hence, when the shortest path network for all products indicates no new entering columns, we cannot proceed and therefore stop. Fortunately, when this point is reached, the solution to the flow assignment problem. is optimal, even if all columns combinatorially possible have not yet been generated. A proof is furnished in Tomlin [21]. The process also stops if all columns have been enumerated and entered. In this case too, the solution found is optimal. Hence in Step 3 of procedure 1, we say that enough columns have been generated either if all columns have been enumerated, or if all columns chosen for entry correspond to existing columns in the formulation.

In the next three sub-sections, we will outline how flow assignment can be regulated throughout the design process so as to control (minimize) inter-cell transfers and/or control the process of dividing work among cells.

3.3.2. Similar fractal cells

Loosely speaking, when cells are autonomous and products are well distributed among cells, we say that the cells are similar. Fractal layouts of similar cells possess several advantages; ease of control, ease of expansion, and flexibility in operation. For example, when cell breakdown occurs, products may be re-routed to other look-alike cells without compromising efficiency. When the facility needs expansion, the basic cell layout may simply be replicated. We will now describe how we direct the flow assignment model by the use of two coefficients to design layouts of similar fractal cells: when the model is used without intervention, there is the possibility that the MCNF linear program assigns a great many flows to routes that span several cells.

Cell autonomy is the property whereby a cell has little or no flow interactions with other cells. This is often desirable because autonomy is a major determinant of controllability. We define the coefficient of cell autonomy, COCA to be the fraction of flows that occur entirely within cells. Such flows will be described, for lack of a better term as intracell flows. Note that it is possible to define a distinct COCA value for each product type visiting the fractal job shop. The coefficient of autonomy may be employed in the design process to obtain fractal designs exhibiting a high degree of autonomy.

Given a fixed value for the coefficient of cell autonomy, an issue that arises is how to distribute intracell flows among cells. We define the coefficient of cell variation, COCV (a number between 0 and 1) to be a measure of the distribution of intracell flows across the cells. Again, the COCV value may be defined by product. When the coefficient value is small, say [Beta], each cell must be assigned intracell between (1 - [Beta]) and (1 + [Beta]) times the value of some targeted flow value, which will soon be calculated.

The coefficients can be effectively used to direct the flow assignment algorithm by forcing the cells to be more independent, or more like each other by adding the following additional constraints to the basic MCNF model:

[Alpha](1 - [Beta])[D.sub.j]/N [less than or equal to] [summation over k[element of]f] [x.sub.jk] [for every]j, [for every] fractal F. (7)

[Alpha](1 - [Beta])[D.sub.j]/N [greater than or equal to] [summation over k[element of]f] [x.sub.jk] [for every]j, [for every] fractal F. (8)

Here, [Alpha] is the coefficient of cell autonomy (COCA) and [Beta] the coefficient of cell variation (COCV). N denotes the number of fractal cells, and the [D.sub.j]'s as before represent job demands. In the case of unfeasibility, we need to redo the capacity planning and cell creation steps so that the linear program is feasible.

Now if for example both [Alpha] and [Beta] are equal to 1.0, all cells may be assigned anywhere from 0 to 200% of the average intracell flow. When the coefficient of autonomy approaches 1.0 and the coefficient of variation is close to 0.0, flows are all intracell and the cells must be similar in terms of what they process. Some numerical results on the use of these coefficients will be presented in a later section using four possible fractal designs, A, B, C, and D as described in Table 4. The cells are forced to be more and more like one another as we read down the table. Design A is the unrestricted case (no requirements are imposed). In Design B, the fraction of purely within-cell flows is 0.25 and the coefficient of cell variation is 0.75. This means that 25% of all flow assignments have to be purely within cells, and each cell can be assigned between 25 and 175% of its targeted share of this. In Design D, however, 75% of the flows have to be purely contained in one or other cells, and each cell must get no less than 75% and also no more than 125% of this. Thus, Design D is much more restrictive than B.

The column generation scheme already described will still work with these extra constraints, 7 and 8. As before, we look now for shortest paths in the graph for each [TABULAR DATA FOR TABLE 4 OMITTED] product. Previously, the shortest path algorithm attached costs ([c.sub.jkt] - [v.sub.t][A.sub.jt]) to the nodes t in the search for entering paths k to satisfy condition (5) for product j. We now additionally subtract the dual variable values obtained from the first of these additional constraints (set 7) for each intracell path (path residing entirely within a fractal cell) pertaining to the fractal-product when checking condition (5). Thus, when a cell has not been assigned its target in intracell flows, the path distance of an intracell path will be lower making it more attractive to enter the linear program. The objective function value of a feasible flow assignment is clearly higher when these controlling constraints are introduced in the model.

3.4. Layout design given flow assignment

Given any flow assignment at the processor level, one is interested in building a layout that minimizes flow travel. This, along with the constraint that a replicate be located inside its parent fractal cell, forms the basic problem parameter.

The processor layout problem, is a question of spatial arrangement of processors in 2 dimensions such that no two processors overlap. The problem approach ignores the design of aisle spaces, storage space, walkways, office space, workbenches, and so on, but is nevertheless ambitious. The number of processors in job shops can be as many as 100, though in test cases we did not encounter problems with more than 44 machines. A processor is considered to be an indivisible entity to be laid out. It could represent a single workstation replicate, or a work-center that contains two or three workstation replicates tied together through a common handling device. In both cases, flows occur from processor to processor, as opposed to process type to process type flows. We have chosen rectilinear distance as the measure used in our examples for expositional purposes although other distance measures could also be introduced without any loss of generality.

The layout question is a particularly hard one. Ignoring the issue of external versus internal flows, workstation replicates themselves could come in different sizes and shapes. The problem for general sizes and shapes has no satisfactorily easy solution. Internal flows occur when a product moves to a replicate of the type it needs next. External flows include the flows from receiving areas and to shipping docks. Under the more restrictive condition that each processor is a square of unit size, the layout problem can be modeled like the quadratic assignment problem (QAP) [22] with one minor change. We need to reflect upon the fact that replicates belonging to a fractal cell can only be located in locations constituting the cell. This is achieved by replacing the distance [d.sub.kh] in the objective function, between locations k and h by [d.sub.ijkh] when considering two replicates, i and j. The value of [d.sub.ijkh] is determined as follows:

[Mathematical Expression Omitted].

Despite the change, the problem can be shown to reduce to the QAP which is NP-Hard [23], and an optimal solution for cases with more than 12-15 workstations is generally impractical. The formulation is not a bad representation if processors are single workstation replicates. When they represent work-centers consisting of two or three replicates, processors are unlikely to be modeled adequately as unit squares. Using optimal solution algorithms (like Hillier's procedure [22]) is viable only when problems are small in size, and high speed computing resources are available. Several heuristics exist, however, including those such as pair-wise interchange [22], simulated annealing [24], tabu search [25], and genetic search [26]. Procedures that produce optimal or sub-optimal solutions to the QAP can serve as a basis for the more general and more difficult problem of fractal job shop layout, which is the next topic for our discussion.

3.4.1. Multiphase heuristic for fractal layout

In theory, we could simply use the QAP formulation to solve the fractal processor layout problem, for given flow assignments. In practice, realistic fractal layouts will have far too many processors, and there is also the issue of determining flow assignments.

We consider the fractal layout problem in two steps cell layout, and global layout. Cell layout refers to how replicates are placed inside cells. Global layout refers to the layout of cells in the plant. We actually begin in reverse sequence by first patching together empty cells to obtain a global layout. The basic procedures followed in global layout are:

1. Cells are rectangular in shape and are placed relative to each other according to the format (depending on the number of cells) shown in Fig. 5. This is meant to be descriptive, not prescriptive;

2. Cells are large enough to fit replicates occupying the cell;

3. For floor layout to be strictly rectangular, allocated cell space is almost equal to required cell space;

4. For floor layout to be free-formed, allocated cell space is much greater than required cell space.

Having obtained a global layout outline, we applied a heuristic based on the method of steepest descent pairwise interchange [22] to improve a layout of processors within cells. Only pair-wise interchange between replicates within the same cell were considered to improve a current solution, cutting down on computational time. Processors within other cells are assumed fixed temporarily while considering a pair-wise interchange. The procedure of pair-wise interchange is sensitive to the initial layout, which often results in implementations getting stuck in local optima. We believe that procedures that consider several starting points and those that allow transition to non-improving solutions, are very relevant.

4. Integrated design methodology

We now present an integrated scheme for the design of a fractal cell job shop based on the ideas developed above.

4.1. Overall scheme

A decomposition approach has been used to perform assignment and layout tasks. Such a strategy is necessary because of the complexity of the optimization task. Fig. 6 outlines our overall design approach. The process is initiated by capacity analysis and workstation allocation (to cells), and after performing these tasks, we get to the core of the design process.

Within Fig. 6, there is a block devoted to the assignment issue already discussed in the previous section. It refers to the assignment of products to workstations, with distances taken from the layout in a previous iteration. The basic constraints are those that reflect machine capacities. The output from the module also provides the flow volume between the workstation replicates.

The flows may be modified to reflect and capture the day-to-day realities of job shops. For example, Drolet [27] reports in virtual manufacturing systems (VMS) simulation that products almost always follow one of the 5 best routes available in the job shop (distance wise) reflected in their processing sequence. The probability that a product follows a certain route may be estimated by simulation analysis. Having done so, the flow matrix may be corrected to take this into account.

The last block in the scheme is the layout module based on the QAP formulation. Once flows between machines are known at the replicate level, layouts can be generated with the attempt to minimize overall flow distance, the transportation cost. Based on an updated layout, the whole process can be restarted. wherein a fresh assignment of products to workstations takes place. There is feedback involved at all levels in the integrated methodology. The designer may at any time look at the current layout generated, revise cell capacities and machine composition, and start afresh.

We do not believe that this process is guaranteed to converge, much as we had earlier hoped it would be. In computations, we encountered rare situations where a solution from a previous iteration was better than the current one. This could be due to the rather difficult combinatorial nature of the problem. Our position is pragmatic; we let this methodology run its course while storing the top few best solutions found to date. If the final solution found is not the best, an older solution that has a lower objective function value can always be recovered.

4.2. Computational results

We followed the design methodology very closely to obtain a fractal layout for the example problem, and all other cases in Table 1. Only the first example is discussed in detail to keep the discussion within space limits. We include later a summary of other results.

After the steps of capacity analysis and cell creation in the Co and Arrar [11] example, whose results have already been seen, the initial layout of Fig. 7 was provided as the start to the iterative process. We obtained the final layout shown in Fig. 8. The solution of Fig. 8 uses 33 machine replicates and has a flow score of 2876 rectilinear flow distance units. Recall that the modified group layout of Co and Arrar [11] used 64 replicates and had a flow score of 3996.

In our computer code, we allow the possibility of either using a random initial layout, or any user developed initial layout, recognizing its effect on the final solution obtained. This first research on fractal layouts focussed not so much on the quality of results obtained, but rather on whether the methodology could yield reasonable results, and on whether the fractal layout shows promise.

Table 5 records how four iterations were used to move from the initial layout to the final one. When the flow-assignment phase was completed on the initial layout, the resulting flow score was 3955 units. At each iteration, we let the column generation procedure run its course and find an optimal solution to the flow assignment problem. A total of 252 columns had to be generated in the course of 4 iteration steps before obtaining the final layout, which had a rectilinear flow distance of 2876 units. In the final iteration for flow assignment, no pair-wise interchanges were found that could enhance the solution.

In the final layout, product 1 has routing assignments as shown in Table 6. The flows implied are usually very complex and criss-cross through the network. The flow network built is complex with products assigned to many paths, a useful feature in that it reflects the flexibility of the production system. In the assignment sequence for product 1, it is interesting to note that intracell fractal paths were first chosen before moving on to inter-fractal paths.

Our implementation was written in the C-language and used the [CPLEX.sup.1] version 3.0 software for solving the multi-commodity network flow linear program. Runs for our example case, as well as other fractal layout cases mentioned by Venkatadri et al. [28] were made on a SUN 4c platform running SunOS 5.3. We have recorded for each case, the CPU time used in the two main phases of our design - flow assignment and layout in Table 7. The column heading which says "Iterations to convergence" refers to the number of iterations of assignment and layout it took to reach the first local optima. As one can observe, the solution to a 44 replicate layout problem takes less than 3 minutes of CPU time, enough to dispel doubts about computational feasibility.

Table 5. Iteration history

Iteration      Number of      Flow score      Flow score
                columns         after
               generated      assignment      re-layout

1                 62             3955           3404
2                 63             3111           3107
3                 64             3090           3032
4                 63             2876           2876
Table 6. Flow assignments for product 1

Route             Replicate sequence          Fractal
number                                         used

1        1-1   4-1   7-2   3-1   10-1   8-1      1
2        1-2   4-2   7-4   3-2   10-2   8-2      2
3        1-3   4-3   7-6   3-3   10-3   8-3      3
4        1-3   4-2   7-4   3-2   10-2   8-3     2,3
5        1-3   4-2   7-3   3-2   10-2   8-3     2,3
6        1-3   4-2   7-3   3-2   10-2   8-2     2,3
7        1-3   4-2   7-4   3-2   10-2   8-2     2,3
8        1-3   4-2   7-4   3-3   10-3   8-3     2,3

5. Empirical investigation

An experiment was conducted to find out whether the fractal layout really provides flow efficiencies comparable to the group layout and capacity requirements close to the function layout. If this is true, with its inherent flexibility, the fractal layout becomes an organization of promise. Seven cases were analyzed by the following four basic job shop designs: functional layout, pure group layout, holographic layout, and fractal layout. The case sources have already been listed in Table 1. In each case studied, the following data were extracted or if absent in the original presentation of the case, generated.

* Product demands and sequences.

* Processing times for each step in the sequence.

* Machine hours available per replicate.

Table 7. Computational performance

     Problem size            Time spent in        Iterations to
Number of    Number of      flow       layout      convergence
replicates   products    assignment   (seconds)
                         (seconds)

44              10          34.7       136.68            5
33              15          17.93       42.68            4
32              40          28.13        5.36            3
31              32          16.33       12.32            4
27              21          10.58       20.61            2
16              22          10.96        4.51            3
16              20           8.49        0.95            2

The original papers of cases 1 and 4 provided complete data. In the original references that introduced cases 3 and 6, processing times were omitted. To make up for this deficiency, we back-calculated processing times such that the number of workstations said to be available would be the exact number for a function or holographic implementation using the capacity planning model already presented in this paper. The hours available were omitted in the original presentations of cases 2, 5, and 7, so we again back-calculated this figure similarly such that the number of workstations available would be just sufficient for a function or holographic layout. A complete listing of all problem data, can be obtained by writing to the authors.

Layouts were generated for all cases. Additionally, fractal layouts were generated for the four fractal designs already indicated in Table 4. Lack of space does not permit us to go into the details of how these were done but the procedure used is documented in a research report [28]. Since a different number of workstations were involved in the different designs, we forced the shop to be constrained to a rectangular grid with similar aspect ratios. All workstations were assumed to be unit squares within this grid.

Table 8 summarizes our findings. It tabulates (for all cases) the number of processors used by each design, and the implied flow score (best results are indicated in bold).

In all cases, the function and holographic layouts use the least number of workstations. And as expected, the function layout is the one that has worst flow performance [TABULAR DATA FOR TABLE 8 OMITTED] in all cases. The group layout performs the best in flow distance in two out of seven cases. In terms of capacity, it is the most expensive in all cases.

The unregulated fractal layout (design A) performed very well with respect to flow distance, outperforming all other designs in five out of seven cases. On the whole, it used marginally more workstations than the function layout with significant reduction in flow distance. It performed better than the group layout in terms of flow distance in cases 1, 3, 6, and 7. The group layout performed better on flow distance in cases 2 and 4, while the two designs had comparable flow distance performance in case 5. This is impressive given substantial capacity savings over the group layout.

Holographic layouts perform very well despite the fact that they are not really designed for shops with fixed routings as is the case in the entire study. The holographic layout represents significant improvements in flow performance over the function layout, being only marginally worse than fractal design D in most cases.

Some remarks on the layouts generated for cases 2 and 3 are in order:

1. In case 2 results, it is clear that the group layout performs extremely well in flow terms at the huge cost of extra capacity since it uses 44 workstations compared to 32 in the fractal design and 30 in the function layout design;

2. In the fractal design of case 3, 27 workstations were used. This excessive duplication was deliberate, to see how well the fractal layout would perform on flow when provided almost as many workstations as group applications demand. The flow savings are obvious, 116 as opposed to 175 in the group layout. It was seen that when only 20 workstations (the least demanded) are used, flow performance worsened, with flow score up to 158 units. This was still better than the group layout flow distance.

Between the four fractal designs themselves, the least constrained design (A) performed the best. In all cases but 4, as the constraints on cell autonomy and cell variation get tighter moving from design A to D, flow performance declined though not always as much as expected. It appears that there is an appreciable difference in flow score between designs A and B, and more modest differences going from design B to design D. If this trend is true design D becomes the preferred mode of choice for fractal designs where cell autonomy and similarity are desired. After all, since one is paying the price (increased flow distance) for regulating fractal designs, one may as well make the cells highly autonomous and very similar.

Recall that the fractal design methodology is heuristic in nature with two optimization based procedures calling each other; flow assignment is updated on existing layout and layout updated on new assignments, making it possible to be stuck in local optima. Layouts are updated based on the quadratic assignment formulation, which is known to be sensitive to the initial layout provided. This may be the phenomena at work in case 4, where design B has bigger flow than design D.

We also conducted a series of runs on case 1 to assess the effect of varying the coefficient of cell variation (COCV) for a fixed coefficient of cell autonomy (COCA), and vice versa. The results are graphed in Figs. 9 and 10. In the first graph, COCA was fixed at 1.0, meaning thereby that all flows had to be within cells (as far as possible). We then varied COCV from 0 to 1.0, in steps of 0.2. Layout designs saw continuous improvement with increasing COCV. Since the cells are allowed more freedom in how much like one another they ought to be, flow assignment and cell layout proceed in a manner where cells are geared to exploit this freedom through specialization in the product mix they process.

In Fig. 9, the coefficient of cell variation is fixed at 0.0. Thus, all cells have to be very much like each other (for the flows that are processed purely within cells). When the coefficient of cell autonomy was varied from 0.0 to 1.0, flow performance of the layout generated worsened first rapidly, then more steadily. This is consistent with expectations, since flows are increasingly forced to be assigned purely within cells.

6. Conclusions

The methodology to generate fractal layouts just presented is part of the ongoing attempt in the literature to solve job shop layout problems at the processor or machine replicate level. This problem which was considered too ambitious to solve computationally, is now receiving much wider attention. Our solution approach to the fractal layout problem confronts the issue of flow assignment when more than one replicate of a particular type was present in a cell, or on the floor. By linking flow assignment to layout, and presenting a methodology rooted in optimization, we have found an approach to first-cut fractal layout generation.

Although there remain a variety of unresolved issues in fractal cell design, our computational experience has shown that the fractal processor layout problem can be tackled in relatively minor computational time. This is encouraging because it makes room for some sophisticated aspects of layout design such as dynamic layout generation, flow network design, aisle planning, and detailed layout generation.

We can foresee some refinements to our implemented methodology. One could look at how input and output to a fractal job shop would take place and adapt the design procedure such that it makes provisions for external flows and input/output stations. The allocation of workstations to cells can be fully integrated with the rest of the design. Also, the design process can be enhanced by looking at broader objectives other than material transfer. Only the economics of production can pronounce verdicts of a general or specific nature. So one must find creative ways to resolve issues like the capacity/flow trade-off. It would be nice to incorporate measures of flexibility to this study as well as expand the study to measure robustness under variations in design parameters.

We hope that the design process will be a useful reference point from which the fractal and other prevalent organizational forms could be compared and contrasted with. At this point in our research, we feel that the fractal organization combines (very favorably) the best in function and product organizations. It offers advantages like lowered machine requirements, flow efficiency, and flexibility.

Acknowledgments

The authors thank the Purdue Research Foundation (grant 690-1287-1318), the Office of Naval Research (grant N00014-86-K-0689), and the Natural Sciences and Engineering Research Council of Canada (grant 0G0044138) for financial support of this project. The authors would also like to express thanks to two anonymous referees for their valuable comments and suggestions.

1 A registered trademark of CPLEX Optimization, Inc.

References

[1] Irani. S.A., Cavalier, T.M. and Cohen, P.H. (1993) Virtual manufacturing cells: exploiting layout design and intercell flows for the machine sharing problem. International Journal of Production Research, 31(4), 791-810.

[2] Heragu, S.S. and Chen, J.-S. (1996) Incorporating planning issues in facilities design, in R.J. Graves, L.F. McGinnis, D.J. Medeiros, R.E. Ward and M.R. Wilhelm (Eds.), Progress in Material Handling Research: Braun-Brumfield, Inc., Ann Arbor. MI 1997, pp. 207-225.

[3] Goldman, S.L., Nagel, R.N. and Preiss, K. (1995) Agile Competitors and Virtual Organizations: Strategies .for Enriching the Customer. Van Nostrand Reinhold, New York.

[4] Drolet, J.R., Montreuil, B. and Moodie, C.L. (1990) Virtual cellular manufacturing layout planning, in lie Conference Proceedings, San Francisco CA May 1990 Institute of Industrial Engineers, Norcross, Georgia.

[5] McLean, C.R., Bloom, H.M. and Hopp, T.H. (1982) The virtual manufacturing system, in Proceedings of the 4th IFAC/IFIP Conference on Information Control Problems in Manufacturing Technology, Gaithersburg, MD, October 1982. Published for the International Federation of Automatic Control by McGregor and Werner, Inc., Washington.

[6] Montreuil, B., Drolet, J.R. and LeFrancois, P. (1992) Design and management of virtual cellular manufacturing systems, in Proceedings of the APICS 35th International Conference, Montreal, Quebec, Canada pp. 410-414. American Society of Production and Inventory Control (APICS), Fails Church. Virginia.

[7] Simpson, J.A., Hocken, R.J. and Albus, J.S. (1982) The automated manufacturing research facility of the National Bureau of Standards. Journal of Manufacturing Systems, 1(1), 17-32.

[8] Montreuil, B., LeFrancois, P., Marcotte, S. and Venkatadri, U. (1993) Holographic layout of manufacturing systems operating in chaotic environments. Technical Report 93-53, Document de Recherche GRGL, Faculte des Sciences de l'Administration, Universite Laval, Quebec.

[9] Askin, R.G, Lundgren, N.H. and Ciarallo, F. (1996) A material flow based evaluation of layout alternatives for agile manufacturing, in R.J. Graves, L.F. McGinnis, D.J. Medeiros, R.E. Ward and M.R. Wilhelm (Eds.). Progress in Material Handling Research: Braun-Brumfield, Inc., Ann Arbor, MI 1997 pp. 71-90.

[10] Montreuik B., Venkatadri, U. and Rardin, R.L. (1996) The fractal layout organization for job shop environments. Technical report, Document de travail SORCIIER 96-25, Universite Laval, Quebec, Canada G1K 7P4.

[11] Co, H.C. and Araar, A. (1988) Configuring cellular manufacturing systems. International Journal of Production Research, 26(9), 1511-1522.

[12] Morris, J.S. and Tersine, R.J. (1990) A simulation analysis of factors influencing the attractiveness of group technology cellular layouts. Management Science, 36(12), 1567-1578.

[13] Vakharia, A.J. and Wemmerlov, U. (1990) Designing a cellular manufacturing system: a materials flow approach based on operation sequences. IIE Transactions, 22(1) 84-97.

[14] Ham, I. (1982) Group Technology, in Handbook of Industrial Engineering, edited by Gavriel Salvendy, John Wiley, New York, NY.

[15] Song, S. and Hitomi, K. (1992) GT cell formation for minimizing the intercell parts flow. International Journal of Production Research, 30, 2737-2753.

[16] Moodie, C.L. (1993) Material flow improvement: a report prepared for a sports boat corporation. IE 590M Class Notes, Purdue University, West Lafayette, IN47907, USA.

[17] Fisher, H. and Thompson, G.L. (1963) Probabilistic learning combinations of local job shop scheduling rules, in Industrial Scheduling, Muth, J.F. and Thompson, G.L. (eds.), Prentice Hall, Englewood Cliffs, New Jersay.

[18] Askin, R.G. and Standridge, C. (1993) Modeling and Analysis of Manufacturing Systems, John Wiley and Sons, New York, NY.

[19] Seifoddini, H. and Wolfe, P.M. (1986) Application of the similarity coefficient method in group technology. IIE Transactions, 18, 271-277.

[20] Hu, T.C. (1963) Multi-commodity network flows. Operations Research, 11, 344-360.

[21] Tomlin, J.A. (1966) Minimum cost multi-commodity network flows. Journal of the Operations Research Society of America, 14(1), 45-51.

[22] Francis, R.L. and White, J. (1974) Facility Layout and Location: An Analytical Approach, Prentice-Hall, Englewood Cliffs, NJ.

[23] Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. San Francisco, CA.

[24] Wilhelm, M.R. and Ward, T.L. (1987) Solving quadratic assignment problems by simulated annealing. IIE Transactions 19(1), 107-119.

[25] Glover, F. (1988) Tabu search. Technical Report CAAI-Report 88-3, Center for Applied AI, Graduate School of Business, University of Colorado, Boulder. CO.

[26] Goldberg, D.E. (1989) Genetic Algorithms in Search Optimization. and Machine Learning, Addison Wesley, Reading, MA.

[27] Drolet, J.R. (1989) Scheduling virtual manufacturing systems. PhD thesis, Purdue University, West Lafayette, IN 47907, USA.

[28] Venkatadri, U., Rardin, R.L. and Montreuik B. (1996) Facility organization and layout design: an experimental comparison for job shops. Technical report, Document de travail 96-27 SORCIIER Universite Laval, Quebec, Canada G1K 7P4.

Biographies

Uday Venkatadri is a research professional working at the SORCIIER Research Center on International Competitiveness and the Engineering of Network Enterprises at Universite Laval, Quebec. He is currently working on NetMan, a project looking into the development of an operating system for networked manufacturing. He received his B.Tech. (1984) in Mechanical Engineering from the Institute of Technology, Banaras Hindu University (IT-BHU), India, his M.S. (1987) in Industrial Engineering from Clemson University, and his Ph.D. (1995) from Purdue University. He is interested in facility planning, design, and layout, manufacturing planning and control, and logistics systems analysis. He has published previously in IIE Transactions and Management Science.

Ronald L. (Ron) Rardin is a Professor of Industrial Engineering at Purdue University. He joined Purdue in 1982 after nine years on the faculty of the School of Industrial and Systems Engineering at the Georgia Institute of Technology and five years of professional experience. Professor Rardin received his B.A. (1965) and M.P.A. (1967) from the University of Kansas, and his Ph.D. from Georgia Tech (1974). His teaching and research interests center on large-scale and heuristic discrete optimization. He is co-author of numerous research papers in that field and (with R. Gary Parker) a graduate text Discrete Optimization. Dr. Rardin's comprehensive new undergraduate textbook on mathematical programming, Optimization in Operations Research, was published in August, 1997. His many honors include the Pritsker award for outstanding undergraduate teaching in Industrial Engineering (1991 and 1997).

Benoit Montreuil is Professor of Operations & Decision Systems at Universite Laval. He is Associate Research Director of the SORCIIER Research Center on International Competitiveness and the Engineering of Network Enterprises. He is President of Systemes Espace Temps Inc., a technology firm producing planning and design software, and providing strategic services in industrial engineering and operations management. He holds a B.Ing (1978, Industrial Engineering) from Universite du Quebec a Trois-Rivieres, an M.S.I.E. (1980) and a Ph.D. (1982, Industrial Engineering) from the Georgia Institute of Technology. His current research interests encompass factory design and layout, intelligent manufacturing and logistic, virtual organization and networked manufacturing. He is currently the principal investigator of the NetMan and NetFac research projects, respectively, aiming to develop an operating system for networked manufacturing, and a computer-aided methodology for agile network factory design. He has published numerous papers in refereed scientific journals, book chapters. and refereed international conference proceedings. He is editor, facilities layout and material handling, for lie Transactions. He is a member of lie and INFORMS. He is a registered Professional Engineer in Quebec. In 1997, Laval University awarded him the Hermes prize for research excellence.