Abstract: A facility layout design is often developed in a hierarchical way that identifies a material flow pattern in the first step and then develops a machine layout based on the material flow pattern in the next step. Popular material flow patterns in practice include spine-flow, I-flow, U-flow and circular flow. This study proposes a new unconventional material flow pattern named the Pier-type Material Flow Pattern (PMFP) and studies layout methodologies including a machine layout problem and a shortcut adding problem for the new material flow pattern. A pier in the PMFP is a unit that forms a single or double row layout in a complete layout design. Using the methodologies, layout designers could obtain not only a reasonably good machine layout but also an appropriate number of piers for a given layout problem.
INTRODUCTION
In Facility Layout Problems (FLP), the material flow pattern predetermines overall spatial and directional geometries of the layout. Several popular material flow patterns include the spine flow, U-flow, ladder flow and circular flow. In a simple layout problem, such as that of a small machine shop, the material flow pattern and machine layout are determined simultaneously. However, for designing complicated facilities such as semiconductor fabrication and steel manufacturing lines, a good design is generally obtained by a hierarchical approach. The material flow pattern is determined first and then tools or departments are located based on the flow pattern. In the literature, central issues of the FLP have been the locations of machines or departments (Meller and Gau, 1966; Singh and Sharma, 2006; Loiola et al., 2007), while a few efforts have been devoted to design issues of the material flow pattern (Ting and Tanchoco, 2001). However, the latter potentially has a higher impact on performance of the facility layout than the former.
This study proposes a new material flow pattern named the Pier-type Material Flow Pattern (PMFP) as shown in Fig. 1 to enhance performance of layout designs. Also, this work develops a mathematical model and heuristic algorithms to address the machine layout problem under the PMFP. The PMFP has a radial shape with multiple piers such as spokes in a wheel as shown in Fig. 1. Machines represented by entity nodes are placed along a pier that starts from the base node in the center of the radial and finishes at another pier node at the end. In the figure, the PMFP with two, three and four piers is illustrated and the number of piers is a decision variable depending on the layout problem. In other words, the optimal number of piers is determined by the number of machines and the material flow in it. Advantages of the PMFP compared to other conventional material flow patterns include shorter material flow distance, modular structure and better access environment from the outside, which will be discussed more in the next section.
There are mathematical models and heuristic algorithms that address the machine layout problem under several conventional material flow patterns in the literature. Langevin et al. (1994) studied a layout problem under the spine material flow using a two step approach consisting of the linear ordering step of cells in order to minimize material flows between cells and the net layout step to finalize locations of each cell in relations to other cells. For the second step, the authors developed an integer programming formulation. Yang and Peters (1997) studied the spine layout problem for semiconductor fabrication facilities operated by automated material-handling systems using the quadratic set covering problem formulation. Ting and Tanchoco (2001) proposed a method for locating single or double spines in an existing machine layout.
The Single Row Layout Problem (SRLP) studies how to place machines or departments in a one-dimensional material flow pattern. It was first studied by Simmons (1969) who developed a branch and bound algorithm. Love and Wong (1976) proposed an MIP (mixed integer programming) model for the problem.
| Fig. 1(a-c): | Pier-type material flow patterns, (a) One or two piers, (b) Three piers and (c) Four piers |
For this NP-hard problem, several researchers developed build-based algorithms that solve the problem from scratch and place one or a few machines at a time during the course of iterations (Heragu and Kusiak, 1988; Kumar et al., 1995; Braglia, 1997). Heragu and Kusiak (1988) first considered clearance between two adjacent machines. Meta-heuristic algorithms including simulated annealing, genetic algorithm and ant systems were also used to find a better solution for the given initial solution (Kouvelis and Chiang, 1992; Djellab and Gourgand, 2001; Ponnambalam and Ramkumar, 2001; Solimanpur et al., 2005). More recently, Amaral (2006) developed a stronger formulation of the TSP-based MIP model developed by Love and Wong (1976) using the well-known linear ordering polytope (Grotschel et al., 1984). Anjos et al. (2005) employed the SDP (semi-definite programming) relaxation method to solve the SRLP with a large number of machines. One issue related to the one-dimensional material flow pattern in practice is that the material flow cost increases along with the number of machines without any limitation.
The block layout problem (Meller and Gau, 1966; Singh and Sharma, 2006) places machines in the two-dimensional space based on the rectilinear distance model. This problem is analogous to the Multi-row Layout Problem (MRLP) studied by Bandara and Wirasinghe (1992). Both problems consider lengths and widths of machines. The block layout problem has been studied in three solution approaches: The QAP (quadratic assignment problem) explored by Koopmans and Beckmann (1957), the graph theoretic method by Seppanen and Moore (1975) and the MIP-based method by Montreuil (1990) and Meller and Gau (1966). It should be noted that in material flow path design, the block layout decision is determined separately (Gaskins and Tanchoco, 1987; Bozer and Srinivasan, 1991).
PIER-TYPE MATERIAL FLOW PATTERN (PMFP)
The PMFP with one or two piers in Fig. 1a is the same as the conventional I-flow or spine-flow with departments located on both sides of the center spine. The machine layout problem using the PMFP with one or two piers is identical to a single or double row machine layout problem (Simmons, 1969; Chung and Tanchoco, 2010). The PMFP with three piers or more requires the minimum center clearance as shown in Fig. 1b, which is the distance between the central node and the first machine close to the center in each pier in order to place machines along the piers without overlapping machines in different piers. As the length of the first machine is larger, a longer center clearance is required. As the number of piers increases, the lengths of each pier decrease, but the center clearance increases. Each pier can be seen as a center spine that has cells on both sides in which machines are placed.
Advantages of the PMFP: Better performance of the PMFP is expected for FLPs with a larger number of machines. The PMFP is more appropriate for FLPs with product family departments or process departments than product departments (Tompkins et al., 2003). More advantages and appropriate applications are discussed below.
SHORTER FLOW DISTANCE
With a layout problem having a larger number of machines, the PMFP is expected to provide better performance than a single or double row machine layout design since the single or double row layout structure creates a longer aisle as the number of machines increases. If material flows for source and destination machines are random (i.e., job shop), the total loaded travel distance by transporters will be decreased by increasing the number of piers because a transporter does not have to pass machines in other piers for a transfer request. If material flows in the layout are based on the pure product flow system (Tompkins et al., 2003), the total flow distance is increased because it has a center clearance while a transfer more likely occur between close machines. However, although material flows are based on the product flow system, vehicle-empty travels tend to be created based on random flows (Koo and Jang, 2002) in flexible manufacturing systems. This research will conduct several experiments to show how the number of machines, required center clearance levels and material flow systems impact the performance of the layout alternatives using the PMFP.
MODULAR STRUCTURE
Piers in the PMFP can be installed one at a time with the minimum interference with the existing Pier-type facilities. However, new machines added in a new pier can interact with existing machines in different piers. Furthermore, different departments in a cellular layout can be efficiently designed by using the PMFP since each department can be assigned in a pier. If a facility requires a storage area, one of the piers can be used as for storage.
BETTER ACCESS FROM OUTSIDE
The PMFP provides a better access environment from the outside compared with a conventional rectangular building structure as illustrated in Fig. 2. In the figure, there are two warehouse layout alternatives utilizing the PMFP: A three-pier layout in Fig. 2a and six-pier layout in Fig. 2b. Each pier in the layout alternatives has dock doors on both sides of the building with storage racks in the middle. The dock doors on one side of the piers are used for receiving incoming materials and the ones on the opposite side are used for shipping materials to facilitate direct shipping (i.e., cross docking).
| Fig. 2(a-b): | Applications of the PMFP for cross docking warehouse layout alternatives, (a) Three piers and (b) Six piers |
There are shipping and receiving doors in the center of the building, which can be used for many purposes such as handling for items with small volumes but many customers.
DISCUSSION
This part discusses potential issues of the PMFP, which impose extra expenses during construction or operation. The first issue is increased construction cost due to the pier structure that requires an unconventional building structure as illustrated in Fig. 2 and 3.
| Fig. 3(a-b): | Total flow cost upon different base center clearance and No. of piers, (a) Jop shop and (b) Flow shop |
The buildings in the figures have a longer perimeter than those with conventional rectangular shapes; hence, corresponding increases of the building construction cost are expected. However, this construction cost can be returned from reduced material handling cost during operation. If the material handling cost of units is higher in the facility, the return will be realized in a shorter period of time. It is also expected that the increase of the construction cost is a function of the number of piers; however, it differ by the characteristics of the building. For the cases in which the construction cost is very high or the material handling cost is not as high to compensate the construction cost, the PMFP is not recommended.
The second issue is expected congestion at the base node while all piers meet at the same location. Consequently, waiting time of the AMHS used in the facility such as an AGVS (automated guided vehicle system) might be increased. This problem can be overcome by two approaches. Using the center clearance, alternative paths can be installed to avoid congestion. For instance, it can be used for creating alternative routes for an AGVS. The other approach to solve the congestion problem involves setting up shortcuts between piers, which reduces not only material movements passing the base node but also moving distances between the entity nodes in different piers.
Machine layout problem under PMFP: In this section, an MIP (mixed integer programming) model is developed to address the SRLP (single row layout problem) under the PMFP. As noted, the SRLP determines locations of the machines in one-dimensional space to minimize material handling cost. The existing formulation by Heragu and Kusiak (1991) is extended for the cases of multiple piers in this research.
Preliminaries: The following preliminaries are introduced to represent problems. The input data includes widths of each machine, the matrix created by multiplying the material flow frequency and unit cost from machine i to machine j, the clearance matrix between pairs of machines and the base center clearance. The clearances between machines are assumed to be different by pairs of machines; however, a few issues related to this assumption are considered later in this section. For the center clearance, a base center clearance is given and the total clearance is a function of the number of piers and the base clearance. As it increases, so does the center clearance. The decision variables are assignments of machines in piers and relative locations of machines in each pier.
Indices:
| m | = | No. of machines |
| n | = | No. of piers, |
| i, j | = | Machine index i, j ∈ i = {1, 2, ..., m} |
| I0 | = | I∪{0}, 0 is a dummy machine |
| k | = | Pier index k∈K = {1, 2, ...., n} |
Input data:
| wi | = | Width of machine I |
| fij | = | Flow time unit cost from machine I to machine j (0 if I or j≥ No. of machines) |
| aij | = | Clearence between machine i and machine j |
| M | = | Large enough No.= |
| c | = | Base center clearence, c is increased proportion ally by n |
Variables:
| xik | = | Variable, distance of machine I in link k from the base point |
| yik | = | Binaryvariable, |
| zijk | = | Binaryvariable, |
MIP formulation: The objective function minimizes the total flow distance between machines in the layout. Note that the location variable xik becomes zero, if machine i is not assigned in pier k. If two machines are located in the same pier, their distance is directly calculated by the difference between them; otherwise, the distances from the machines to the base node are added. The constraint (a2) ensures that no machine is assigned within the center clearance. The constraints (a3) to (a5) work for assignments of machines to piers. The constraint (a3) ensures that a machine must be assigned to only one pier. Based on the constraints (a4) and (a5), the binary variable of the assignment (yik) is connected to the location variable (xik) of each machine as described in the variable definition above.
Relative locations of the machines in piers are considered by the constraints (a6) to (a10) that also prevent locations of machines from overlapping each other. The constraint (a6) assigns a value to the binary variable used for the relative locations of machines in a pier. If a machine is located on the right next to the other machine, its corresponding binary variable is assigned to one, otherwise zero, which is a typical method used for a TSP-based MIP formulation. The constraints (a7) to (a10) enforce that each machine has one predecessor and successor, which forms a tour. To convert the tour to the linear ordering in each pier, a dummy machine is introduced for each pier in the constraints (a7) to (a10), which is the first and last machine in the pier. For the dummy machines, the location variables are not created and each of them also has one predecessor and successor in the constraints (a9) and (a10). The constraint (a11) connects the assignment variable with the relative location variable, which can be described as; if the zijk is one then yik should also be one. The constraints (a12) to (a14) are individual variable definitions:
s.t.
Linearized formulation: The above formulation can be linearized by using
the well-known standard technique below. The new variables
s.t.
Problem complexity and sequence dependent clearance related issue: While the SRMLP is similar to the single machine scheduling problem with the sequence dependent set-up time (1/sjk/ΣwjCj, using Pinedo (1995) notation), this problem is similar to the multiple machine scheduling problem with the sequence dependent problem (Pm/sjk/ΣwjCj). The distances between machines are additionally considered in this problem and it is strongly NP-hard.
| Table 1: | Test cases of Pier-type material flow pattern |
Computational analysis: This section conducts computational analysis using a heuristic algorithm solving a SRLP under the PMFP. Two main purposes of this analysis are to obtain a reasonably good machine layout design and to identify an appropriate number of piers from the given number of machines in the layout problem. Also, this analysis illustrates that as the machine count increases branching a new pier is desirable to increase the performance of the layout.
Test case and algorithm: Computational experiments were conducted under several different factors explained in Table 1. The primary test factors shown in the table are the number of machines and piers, base clearance, material flow systems and different solution algorithms. Three different levels of machine numbers are tested in the table. Five different levels of the base clearance are tested and two different material systems are tested. The heuristic algorithms developed by Kusiak and Heragu (1987) and Braglia (1997) were used after slight modification for the experiments. Also, to identify the performance of these heuristic algorithms compared to the optimal solution by the MIP model, this research compares those solutions from the heuristic algorithms with the solutions by CPLEX MIP solver.
Figure 3 displays results from the experiments using the algorithm by Kusiak and Heragu (1987). In the graph, the x-axis represents the number of piers and the y-axis is the total material handling cost observed. Fig. 3a is based on flow frequencies created based on a job shop model, while Fig. 3b is obtained from the material flow frequencies based on a flow shop model. Both cases are tested with different levels of the base center clearances. From the graphs of the two cases, it is observed that as the base center clearance increases, the total flow cost also increases. As the number of piers increases, the total flow cost gradually decreases; however, after it reaches the number of piers that yields the minimum flow cost, it starts again to increase.
As seen in this figure, an appropriate number of piers in a given problem is easily obtained by using the test method above. With a larger base center clearance, the minimum flow cost is obtained with a smaller number of piers.
| Fig. 4: | Critical No. of piers based on different No. of machines and base clearance |
For example, in Fig. 3a, the minimum total cost is observed when the number of piers is 8 under a base clearance of 2 (third line in Fig. 3a); however, with a base center clearance of 3.5, it is obtained at the 6 piers (6th line in the legend of Fig. 3a).
The graph in Fig. 4 shows the number of piers producing the minimum total flow cost under the different number of machines and the base center clearance levels. The tests use the algorithm by Braglia (1997). As seen in the figure, as the number of machines increases, the minimum total flow cost is obtained after more piers are used. For instance, in the figure, when the number of machines is 12 with a base center clearance of one, the optimal number of piers is obtained at 5. With the same base center clearance, however, with 24 and 36 machines, they are obtained at 6 and 7 piers, respectively.
Optimality of existing heuristic algorithms: The experiments above show that the PMFP performs well for a machine layout problem having a large number of machines. However, one question remaining is how heuristic algorithms are computationally efficient to address practical layout problems under the PMFP. The qualities of the two heuristic algorithms used above are measured in Table 2. The MIP model explained above was tested by using the CPLEX MIP solver based on different pier numbers and base center clearance levels and the cases with 12 machines are considered, each of which is calculated for maximum 2 h. The algorithm by Kusiak and Heragu (1987) is named addition-based heuristic, while the other by Braglia (1997) is insertion-based heuristic, based on their approaches.
The results were presented in the third to last columns of the table. In the third column, the total flow cost obtained from the MIP solver for each case is presented in each row and the gap in the fourth column is calculated by {best integer node-best LP node}/{e+best integer node} where, e is a very small number to avoid a devising error.
| Table 2: | Solution quality comparison |
As seen in the table, the solution statuses of the MIP model are in the gap range of 93 to 96% after two hours of computation, which means that there is still room for improvement. The gaps between heuristic solutions and MIP solutions are presented in 6th and 8th columns. It is noted that the insertion algorithm performs better than the addition algorithm.
Based on the experiments above, using the MIP model and 2 h computation times for each case, averages of 10 and 19% of reductions in final objective values compared to the two heuristic solutions are observed. Since there are many practical problems having more than 12 machines, a better solution approach needs to be studied, which remains for future study.
CONCLUSION
This study has proposed the Pier-type material flow pattern (PMFP) and developed a machine layout problem under the PMFP based on an MIP formulation. Advantages of this material flow pattern include shorter flow distance, modular structure and better access environment from the outside. It has been noted that the PMFP is especially beneficial for a manufacturing facility with a job shop model and a warehouse facility practicing cross docking. From studies on a machine layout problem under the PMFP, this research has shown that, as the number of machines increases, branching a new pier that represents a unit of the single or double row layout improves performance of the layout. The optimal number of piers for a given number of machines could be obtained by a series of computational experiments. Developing a more computationally efficient approach than existing heuristic algorithms to address a machine layout problem under the PMFP remains for future study.
ACKNOWLEDGMENT
This study was supported by Jungseok Logistics Foundation Grant.