|
...plan, the building, the departmental area, service requirements, and the decision-maker" (Bozer et al., 1994). Thus, the facility layout design has major impact on the productivity and efficiency of production within the facility.
The efficiency of the facility layout is typically measured in terms of the material handling costs. The two most common surrogate objectives used to approximate the material handling costs in the literature are: (i) the closeness rating objective that is based on department adjacency relationships; and (ii) the material flow cost objective that is based on inter-departmental distances.
The representation of an FLP solution forms the basis for a mathematical model and significantly impacts the structure and efficiency of the applied optimization algorithms. There are a variety of FLP representation methods, but most of them fall into two main categories: discrete representation and continuous representation. With a discrete representation, the facility is represented by an underlying grid structure with fixed dimensions and all departments are composed of an integer number of grids. By representing the FLP in a discrete fashion, the FLP is simplified, but at the penalty of eliminating many solutions from consideration. In a continuous representation, department dimensions are not restricted to an underlying grid structure, but rather, represented continuously. Continuous representation is more accurate and realistic than discrete representation, and thus, is capable of finding the "real optimal" final layout solution. However, the continuous representation also increases the complexity of the FLP.
Most research that has been conducted in the area of exact algorithms for the continuous-representation-based FLP is focused on formulating the FLP as a Mixed-Integer Programming (MIP) model, where a large number of binary variables are used to prevent departments from overlapping. One of the first MIP-FLP models for the continuous-representation-based FLP was presented by Montreuil (1990) who uses a distance-based objective. This model is commonly referred to as FLP0. One of the problems in FLPO is that instead of the exact nonlinear area constraint, a bounded perimeter constraint is used to linearize the model. However, using a bounded perimeter constraint instead of an exact area constraint can lead to errors in the final area of each department. Goetschalackx (1998) explores the impact of shape constraints on formulation runtime.
A modified MIP-FLP model based on FLP0 was presented in Meller et al. (1999) which was able to improve the model accuracy and approach efficiency. This model is commonly referred to as FLP1. The bounded perimeter constraint in FLP1 is modified, which results in a more accurate approximation of the final department areas. More importantly, this modified MIP-FLP model also adds some valid inequalities in order to eliminate some infeasible solutions from the solution space and to improve the algorithm's efficiency.
In order to further improve the performance of the MIPFLP model and algorithm, a series of enhancements were presented in Sherali et al. (2003). Those new enhancements are based on FLP1, including a novel polyhedral outer approximation scheme for the nonlinear area constraints, some symmetry-avoiding valid inequalities, several surrogate constraints to prevent department overlapping, and a well-designed branching variable selection priority scheme. The computational results presented in Sherali et al. (2003) show that the accuracy of the final solutions is increased, but more telling, some difficult test cases with eight and nine departments are solved for the first time. Castillo and Westerlund (2005) provide an [member of]-accurate scheme for controlling the department area.
Even with all these improvements to the MIP-FLP, the problem size that can be solved to optimality is very limited (e.g., the largest continuous-representation-based FLP solved to optimality contains only nine departments (Sherali et al., 2003; Castillo and Westerlund, 2005) and is thus not applicable for most industrial applications, where there are typically more than 30 departments. The major difficulties that arise in solving the MIP-FLP are due to the disjunctive constraints and also the large number of binary integer variables that prevent departmental overlap. Associated with these binary variables, there are numerous infeasible settings, which waste a great deal of computational effort. Hence, Banerjee et al. (1992), Montreuil et al. (1993), Lacksonen (1994, 1997) and Langevin et al. (1994) attempted to solve MIP-FLP models by heuristically fixing a subset of those binary integer variables and then solving the resulting simplified model.
Banerjee et al. (1992) and Montreuil et al. (1993) applied qualitative layout anomalies and design skeletons to the Montreuil-Venkatadri-Ratliff MIP-FLP model (Montreuil et al., 1993). Lacksonen (1994) proposed an approach that combines the Quadratic Assignment Problem (QAP) model with the Montreuil Model (1990) model. Langevin et al. (1994) proposed a heuristic approach based on the Montreuil Model (1990) model to solve the spine layout problem, with a main aisle being used for material handling and all departments being located along both sides of an aisle. This approach uses a heuristically fixed ordered list as the initial input and is unable to consider all possible solutions. It is also specifically designed for application to the spine layout problem. Lacksonen (1997) proposed a pre-processing heuristic to fix a subset of the total binary variables according to a regression formula based on the area of each department and the material flows associated with each department.
All these heuristics are either designed for a specific FLP topology or cannot consider all possible all-rectangular-department solutions due to certain pre-processing or restrictions. Few efforts have been made to design a heuristic for the generic continuous-representation-based FLP that is capable of considering all possible all-rectangular-department solutions.
On the other hand, a great deal of research has been conducted in the VLSI layout design domain, which is similar to the FLP (see Fig. 1 (a and b)). In VLSI design, different modules are placed onto a chip without overlapping, whereas in the FLP different departments are to be placed into a facility without overlapping. The objective of VLSI design is to minimize the area of the chip while including all modules. In the FLP, the objective is to minimize the material handling costs for a given facility. The sequence-pair representation was first presented to solve the VLSI design problem (Sha and Dutton, 1985; Murata et al. 1995; Murata and Kuh, 1998a; 1998b). A sequence pair is a pair of module (department) sequences that is used to represent the relative location relationship of the modules (departments) in the VLSI design problem (FLP).
As we show, each sequence pair is feasible in terms of representing the departments' relative locations to one another and preventing departments from overlapping (although a sequence pair may not be feasible due to other constraints as we describe more fully later). We utilize this result to develop an MIP-FLP-based approach that is not limited to a specific FLP topology. However, our approach in its presented form is limited to rectangular department shapes, positive inter-departmental relationships, and we do not consider relationships with the perimeter of the facility or columns in the facility.
Our heuristic employs a Genetic Algorithm (GA) to search the solution space. Our heuristic is based on the optimization routines of the MIP-FLP model, but what makes the heuristic unique is that it adds the sequence-pair representation to ensure binary feasibility. By doing so, the heuristic considers only feasible binary variable settings when searching amongst the all-rectangular-department solution space, and thus, can efficiently solve larger continuous-representation-based FLPs.
[FIGURE 1 OMITTED]
The remainder of the paper is organized as follows. In the next section we first describe the MIP-FLP model and the sequence-pair representation. We then provide a methodology to combine the MIP-FLP model and sequence-pair representation. In Section 3, we present our sequence-pair representation and MIP-FLP-model-based heuristic for solving the continuous-representation-based FLP, where the important characteristics of the heuristic design are discussed in detail. Numerical tests based on some widely used test problems from the literature and some new large-sized test problems from industry are presented in Section 4, where we provide comparisons between: (i) the solutions from our heuristic and the optimal solutions; and (ii) the solutions from our heuristic and the solutions from other heuristics. We also conduct a sensitivity analysis with respect to the department aspect ratio constraint in terms of objective function value and total solution time. Finally, we provide our conclusions and discuss our future research in Section 5.
2. The MIP-FLP model and sequence-pair representation
2.1. The MIP-FLP model
The MIP-FLP model we refer to in this paper is based on FLP2 (Sherali et al., 2003), with the notation and formulation of the model being given below.
Parameters:
s = direction index (s = x, y);
[L.sup.x], [L.sup.y] = side length of the facility in the x- and y-directions;
N = the total number of departments;
i, j = department indices (i, j = 1,..., N);
[a.sub.i] = are requirements for department i;
[[alpha].sub.i] = maximum aspect ratio requirement for department i, which denotes the maximum permissible ratio between its longest and shortest sides ([[alpha].sub.i] [greater than or equal to] 1);
[ub.sub.i], [lb.sub.i] = upper and lower limits on the side length of department i;
[f.sub.ij] = material flow between department i and department j ([f.sub.ij] > 0, [for all]i < j);
[bar.x] = the value of the affine support point for the polyhedral outer approximation to the area constraints.
Decision variables:
[d.sub.ij] = rectilinear distance between department i and j, which is expressed as the sum of the distances in the x-direction, [d.sub.ij.sup.x], and the y-direction, [d.sub.ij.sup.y] ([d.sub.ij] = [d.sub.ij.sup.x] + [d.sub.ij.sup.y]);
[c.sub.i.sup.x], [c.sub.i.sup.y] = location of centroid of department with respect to x- and y-coordinates;
[l.sub.i.sup.x], [l.sub.i.sup.y] = half of side length of department i in x- and y-directions;
[z.sub.ij.sup.x], [z.sub.ij.sup.y] = binary decision variables, which denote relative locations of departments with respect to x- and y-coordinates and are used to prevent the overlapping of departments. The definition of [z.sub.ij.sup.s] (s = x, y) is as follows:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
MIP-FLP Formulation:
min [summation over i] [summation over (j>i)][f.sub.ij]([d.sub.ij.sup.x] + [d.sub.ij.sup.y]), (1)
subject to
[d.sub.ij.sup.s] = |[c.sub.i.sup.s] - [c.sub.j.sup.s]|, [for all]i < j; [for all]s (2)
[l.sub.i.sup.s] [less than or equal to] [c.sub.i.sup.s] [less than or equal to] [L.sup.s] - [l.sub.i.sup.s], [for all]i; [for all]s (3)
[lb.sub.i] [less than or equal to] 2[l.sub.i.sup.s] [less than or equal to] [ub.sub.i], [for all]i (4)
[z.sub.ij.sup.x] + [z.sub.ji.sup.x] + [z.sub.ij.sup.y] + [z.sub.ji.sup.y] = 1, [for all]i, j; i < j (5)
[c.sub.i.sup.s] + [l.sub.i.sup.s] [less than or equal to] [c.sub.j.sup.s] - [l.sub.j.sup.s] + [L.sup.s] (1 - [z.sub.ij.sup.s]), [for all]i, j; [for all]s (6)
[a.sub.i][l.sub.i.sup.x] + 4[bar.x.sup.2][l.sub.i.sup.y] [greater than or equal to] 2[a.sub.i][bar.x], [for all][lb.sub.i.sup.x] [less than or equal to] [bar.x] [less than or equal to] [ub.sub.i.sup.x] (7)
[z.sub.ij.sup.s] [member of] [0, 1] [for all]i, j; [for all]s (8)
The objective, Equation (1), is a distance-based objective function, which is equal to the product of the flow and rectilinear distances between department centroids. The absolute values in the distance function (2) can be linearized as [d.sub.ij.sup.s] [greater than or equal to] [c.sub.i.sup.s] - [c.sub.j.sup.s] and [d.sub.ij.sup.s] [greater than or equal to] [c.sub.j.sup.s] - [c.sub.i.sup.s] since [f.sub.ij] > 0. In Equation (3), each department is constrained to be within the facility. The side length is constrained in Equation (4) by using upper and lower limits [ub.sub.i] = min {[square root of ([a.sub.i][[alpha].sub.i])], [max.sub.s] {[L.sup.s]}}/2 and [lb.sub.i] = [a.sub.i]/4[ub.sub.i], where the aspect ratio for department i is defined as max{[l.sub.i.sup.x], [l.sub.i.sup.y]}/min{[l.sub.i.sup.x], [l.sub.i.sup.y]}. In Equations (5) and (6), the relative location decision variables are utilized to prevent departments from overlapping. In lieu of the exact nonlinear area constraint, [a.sub.i] = 4[l.sub.i.sup.x][l.sub.i.sup.y],...
NOTE: All illustrations and photos
have been removed from this article.
Looking for additional articles?
Search our database of over 3 million articles.
Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication
name or publication date.
About Goliath
Whether you're looking for sales prospects, competitive information, company
analysis or best practices in managing your organization,
Goliath can help you meet your business needs.
Our extensive business information databases empower business
professionals with both the breadth and depth of credible,
authoritative information they need to support their business
goals. Whether it be strategic planning, sales prospecting,
company research or defining management best practices -
Goliath is your leading source for accurate information.
|
%20%20&position=1)