A sequence-pair representation and MIP-model-based heuristic for the facility layout problem with rectangular departments

A sequence-pair representation and MIP-model-based heuristic for the facility layout problem with rectangular departments

Qi Liu

1. Introduction

As one of the most important problems in facilities planning, the Facility Layout Problem (FLP) is “concerned with determining the ‘most efficient’ arrangement of interacting departments within a designated section of a building subject to constraints imposed by the site plan, the building, the departmental area, service requirements, and the decision-maker” (Bozer et al., 1994). Thus, the facility layout design has a 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], a polyhedra outer approximation based on a suitable number of the affine supports is used in Equation (7). The value for the affine support point [bar.x] used in Equation (7) is given as follows:

[bar.x] = [lb.sub.i.sup.x] + [[lambda]/[[DELTA] – 1]]([ub.sub.i.sup.x] – [lb.sub.i.sup.x]), [for all][lambda] = 0, 1,…, [DELTA] – 1, for any selected integer [DELTA] [greater than or equal to] 2. (9)

This approximation is purely linear and does not involve any binary variables. Furthermore, it can provide as tight a representation as desired. For example, by using [DELTA] = 20, the maximum area error generated for solving a nine department problem was less than 0.3% (Sherali et al., 2003).

Although FLP2 shows an improved performance for solving the continuous-representation-based FLP, as compared with FLP0 and FLP1, it can only solve problems with up to nine departments to optimality. The main reason for this behavior is that there are a large number of binary variables in the model. For these binary variables, there are a lot of infeasible settings with respect to departments overlapping, which consumes (and wastes) a great deal of computational effort. Therefore, we employ a solution representation technique from VLSI design called the sequence-pair representation. As we show in the next section, the sequence-pair representation eliminates all infeasible binary variable settings.

2.2. The sequence-pair representation

As we discussed in Section 1, a sequence pair is a pair of department sequences used for representing the department relative location relationships in the layout. Murata et al. (1995) presented a theorem to translate a sequence pair into the relative location relationship of the modules in the chip for a VLSI design problem. We adopt this theorem (without proof) to the FLP as follows:

Definition 1. Given a sequence pair, ([[GAMMA].sub.+], [[GAMMA].sub.-]), for a department x, any other department x’ is uniquely constrained in one of four classes, which are defined in Murata et al. (1995) as follows:

[M.sup.aa](x) = (x’|x’ is after x in both [[GAMMA].sub.+] and [[GAMMA].sub.-]}, (10)

[M.sup.bb](x) = {x’|x’ is before x in both [[GAMMA].sub.+] and [[GAMMA].sub.-]}, (11)

[M.sup.ba](x) = {x’|x’ is before x in [[GAMMA].sub.+] and after x in [[GAMMA].sub.-]}, (12)

[M.sup.ab](x) = {x’|x’ is after x in [[GAMMA].sub.+] and before x in [[GAMMA].sub.-]}. (13)

Theorem 1. (After Murata et al., 1995.) Given a sequence pair, ([[GAMMA].sub.+], [[GAMMA].sub.-]), and x and x’ as two different departments in ([[GAMMA].sub.+], [[GAMMA].sub.-], then x and x’ satisfy the following horizontal/vertical relationship in a facility layout:

if x’ [member of] [M.sup.aa](x), then department x’ is to the right of department x;

if x’ [member of] [M.sup.bb](x), then department x’ is to the left of department x;

if x’ [member of] [M.sup.ba](x), then department x’ is above department x;

if x’ [member of] [M.sup.ab](x), then department x’ is below department x.

Based on Theorem 1, each layout represented by a sequence pair is guaranteed to be feasible with respect to the overlapping constraints (Murata et al., 1995); i.e., each sequence pair corresponds to a feasible setting of the binary variables in the MIP-FLP model with respect to the set of constraints represented by Equation (5). Thus, the sequence-pair representation has the property that all infeasible layout solutions due to an infeasible binary variable settings with respect to the overlapping constraints, Equation (5), are automatically excluded from sequence-pair solution space. This is a powerful property that we exploit in our methodology. In the next section we discuss the advantages, and also the limitations, of applying the sequence-pair representation to the MIP-FLP.

2.3. A methodology to combine the sequence-pair approach and the MIP-FLP

Before we consider how to combine the sequence-pair representation and the MIP-FLP model, we first provide two theorems regarding the properties of the sequence-pair representation with respect to the MIP-FLP model.

Theorem 2. (Binary variable specifying theorem) Given a sequence pair, ([[GAMMA].sub.+], [[GAMMA].sub.-]), and departments i and j as two different departments in ([[GAMMA].sub.+], [[GAMMA].sub.-]), then the corresponding binary variables in FLP1 are specified as follows:

i [member of] [M.sup.bb](j) [right arrow] [z.sub.ij.sup.x] = 1, [z.sub.ji.sup.x] = 0;

i [member of] [M.sup.aa](j) [right arrow] [z.sub.ij.sup.x] = 0, [z.sub.ji.sup.x] = 1;

i [member of] [M.sup.ab](j) [right arrow] [z.sub.ij.sup.y] = 1, [z.sub.ji.sup.y] = 0;

i [member of] [M.sup.ba](j) [right arrow] [z.sub.ij.sup.y] = 0, [z.sub.ji.sup.y] = 1.

Different from the VLSI problem, where the chip size is the objective function, the facility size in the FLP is typically fixed. Thus, there are constraints to limit a department’s placement to within the facility. Also, there are other types of constraints in the FLP, such as the departmental aspect ratio requirement. Therefore, although a sequence pair is feasible in terms of the overlapping constraints, it may be infeasible due to other constraints in the MIP-FLP. Considering the sequence-pair representation in the MIPFLP framework, we provide the following definitions with respect to sequence-pair feasibility.

Definition 2. (Position-consistent sequence pair.) Setting the binary variables of the MIP-FLP as specified in Theorem 2 results in a layout that is consistent with respect to Equation (5) of the MIP-FLP. Thus, all sequence pairs are denoted as position consistent, although any sequence pair may not satisfy all constraints of the MIP-FLP.

Definition 3. (Layout-feasible sequence pair.) A sequence pair is classified as layout feasible if setting the binary variables of the MIP-FLP as specified in Theorem 2 results in a layout that is feasible with respect to all constraints of the MIP-FLP (department overlap constraints, department aspect ratio constraints, department placement within the facility constraints, etc.). Likewise, a sequence pair is classified as layout infeasible with respect to the MIP-FLP if setting the binary variables of the MIP-FLP as specified in Theorem 2 does not result in a feasible layout.

Definition 4. (Sequence-pair optimal layout.) A layout-feasible sequence pair may yield multiple feasible layouts in the MIP-FLP. For a layout-feasible sequence pair, the layout that achieves the best objective function value for the MIP-FLP is denoted as the sequence-pair optimal layout (there is no sequence-pair optimal layout for a layout-infeasible sequence pair).

Definition 5. (Optimal sequence pair.) A sequence pair is denoted as optimal with respect to the MIP-FLP if the sequence-pair optimal layout for this sequence pair corresponds to the optimal facility layout of the MIP-FLP.

So, each sequence pair is position consistent and a subset of those sequence pairs leads to a set of layout feasible sequence pairs. According to these facts, we have the following theorem:

Theorem 3. An exhaustive search of the sequence pair solution space will result in finding the optimal layout of the MIP-FLP.

Proof. For any feasible layout solution of the MIP-FLP (including the optimal MIP-FLP layout), there must exist a corresponding layout-feasible sequence pair, ([GAMMA].sub.+), [GAMMA].sub.-). For any layout-feasible sequence pair, there must be one or multiple corresponding feasible layout solutions of the MIP-FLP by specifying the binary variables according to Theorem 2 and solving the resulting model. Furthermore, a sequence pair optimal layout is the best layout we can obtain from all the feasible layouts represented by that layout-feasible sequence pair. Therefore, the optimal layout for the MIP-FLP must correspond to the best layout from the set of all sequence-pair optimal layout solutions. By an exhaustive search of the layout-feasible sequence-pair solution space, every sequence-pair optimal solution can be obtained. Thus, we can choose the best layout solution from the set of all sequence-pair optimal layout solutions, which is also the optimal layout of the MIP-FLP. In addition, the corresponding sequence pair for that optimal layout solution is the optimal sequence pair. [black square]

Our methodology to combine the sequence pair and the MIP-FLP model is to design a heuristic to search efficiently in the sequence pair solution space. For each sequence-pair searched by the heuristic, we correspondingly set the values of the binary variables in the MIP-FLP model to simplify the MIP-FLP model into a linear programming model. We then solve the linear programming model to optimality to find the sequence-pair optimal layout (if it exists) for that sequence-pair.

For the MIP-FLP with n departments, there are 2n(n – 1) binary variables, so there are [2.sup.2n(n-1)] possible binary variable setting combinations. Among all these binary variable settings, the number of combinations satisfying [[summation].sub.s]([z.sub.ij.sup.s] + [z.sub.ji.sup.s]) = 1 is equal to [2.sup.n(n-1)]. That is, for each pair of departments, we have four different binary variables: [z.sub.ij.sup.x], [z.sub.ij.sup.y], [z.sub.ji.sup.x], and [z.sub.ji.sup.y]. The number of possible combinations of randomly picking one variable from the four binary variables to make it equal to one is equal to [C.sub.4.sup.1] = 4. By doing so, the other three binary variables are determined to be zero. So actually, for each pair of departments there are four possible binary variable settings that satisfy the constraint [[summation].sub.s]([z.sub.ij.sup.s] + [z.sub.ji.sup.s]) = 1. Given n departments, the number of possible combinations of a pair of departments is equal to [C.sub.n.sup.2] = n(n – 1)/2. So the total number of binary variable settings that satisfy [[summation].sub.s]([z.sub.ij.sup.s] + [z.sub.ji.sup.s]) = 1 is equal to [4.sup.n(n-1)]/2 = [2.sup.n(n-1)].

However, the binary variable settings satisfying [[summation].sub.s]([z.sub.ij.sup.s] + [z.sub.ji.sup.s]) = 1 for one department do not ensure that the binary variable settings will lead to a feasible layout with respect to all department pairs. For example, a binary variable setting of [z.sub.ij.sup.x] = 1, [z.sub.ij.sup.y] = [z.sub.ji.sup.x] = [z.sub.ji.sup.y] = 0, [z.sub.jk.sup.x] = 1, [z.sub.jk.sup.y] = [z.sub.kj.sup.x] = [z.sub.kj.sup.y] = 0, [z.sub.ki.sup.x] = 1, and [z.sub.ki.sup.y] = [z.sub.ik.sup.x] = [z.sub.ik.sup.y] = 0 satisfies [[summation].sub.s]([z.sub.ij.sup.s] + [z.sub.ji.sup.s]) = 1, but these binary variable values are not layout feasible since this setting cannot represent a feasible relative location relationship between the three departments (i.e., this setting implies that department i is to the left of j, j is to the left of k, and k is to the left of i). Such a “cycling” conflict is just one example of feasible binary variable settings satisfying [[summation].sub.s]([z.sub.ij.sup.s] + [z.sub.ji.sup.s]) = 1 that lead to an infeasible layout.

On the other hand, the sequence-pair representation represents the “true” feasible binary variable settings since given any sequence pair there is a series of corresponding feasible layouts. As an example, consider how the sequence-pair representation can filter such a “cycling” conflict since the sequence-pair representation does not allow i to be before j in both sequences (i is to the left of j), j to be before k in both sequences (j is to the left of k), and k to be before i in both sequences (k is to the left of i) simultaneously. Therefore, the number of possible combinations of the sequence-pair representation for a FLP with n departments is equal to [(n!).sup.2], which represents the number of feasible binary variable settings.

As noted above in defining layout-feasible sequence-pairs, not every sequence pair solution is feasible with respect to the other layout constraints of the MIP-FLP. Thus, even with a position consistent solution obtained from a sequence-pair, the MIP-FLP must still be solved to determine layout feasibility. The advantage is that the problem is not an integer program since each binary variable has been set vis a vis the sequence-pair representation.

Table 1 illustrates the percentage of MIP-FLP position consistent, but not layout feasible, settings correctly eliminated with the sequence-pair representation.

3. SEQUENCE: A heuristic based on the sequence-pair representation and MIP-FLP model

We present a GA-based heuristic named SEQUENCE to solve the sequence-pair-based MIP-FLP. Although there is no proof that a GA will perform better than other meta-heuristics, such as Simulated Annealing (SA) and tabu search, in solving the sequence-pair-based MIP-FLP, there are some potential advantages we expect from utilizing a GA scheme. One main potential advantage in using a GA-based heuristic is that, unlike most other meta-heuristics that utilize random “mutation” as the main instrument for variation and evolution, a GA also utilizes a crossover operator. The ability of a crossover operator to recombine highly fit chromosome patterns makes us believe that a GA is more powerful in keeping, recombining and further strengthening some good “combination patterns” (relative location patterns between departments in the FLP) with respect to the permutation encoding scheme. (In fact, we have tested a SA version of SEQUENCE, but found that the GA version of SEQUENCE outperformed it.)

3.1. Encoding scheme

We first present our encoding scheme for SEQUENCE. Here we consider utilizing a permutation encoding scheme because of the nature of the order-based structure in the sequence-pair representation. However, a sequence pair includes a pair of permutations (ordered departments), so simple permutation encoding schemes are not suitable for our problem. We next present our encoding scheme, which we refer to as a position-pair-based encoding scheme.

To represent a sequence pair, ([[GAMMA].sub.+], [[GAMMA].sub.-]), a chromosome in a position-pair-based encoding scheme is a string with a pair of values assigned to each gene in the string. The first value represents the position of the corresponding department in the first department sequence, [[GAMMA].sub.+]. Correspondingly, the second value represents the position of the same department in the second department sequence, [[GAMMA].sub.-]. For example, for a given sequence pair, ([[GAMMA].sub.+], [[GAMMA].sub.-]) = (e c a d f b, f c b e a d), the corresponding position-pair-based chromosome is shown in Fig. 2.

The reason that the position-pair-based encoding scheme is of potential benefit is that it establishes some “links” between the two positions of each department in a sequence pair by including them in the same gene. That is, in a sequence pair, the location of a department is determined by both of its positions in [[GAMMA].sub.+] and [[GAMMA].sub.-]. Such “links” may be useful for keeping a “good” pattern after crossover and mutation operations. For example, if department a at (3, 5) and department b at (6, 3) is a “good” pattern to some extent, then in a position-pair-based encoding scheme, such a good pattern in a chromosome will be more likely to survive than we would expect in a pair of independent single-valued-string-based chromosomes.

[FIGURE 2 OMITTED]

3.2. Fitness function and selection rule

In a GA, the combination of a fitness function and the selection rule determines how to perform selection; i.e., how to select the chromosomes in the current population that are used to create offspring for the next generation. For the MIP-FLP, the objective is to minimize the total material handling travel distances, so the smaller the objective function value, the higher the fitness score corresponding to the chromosome. In SEQUENCE, we use the following fitness function:

F(i, j) = [f.sub.i.sup.0] – [f.sub.ij], [for all]i [member of] {1,…, G}, [for all]j [member of] {1,…, M}, (14)

where F(i, j) is the fitness score function for chromosome j in generation i, [f.sub.ij] is the objective function value of the sequence-pair optimal solution corresponding to chromosome j in generation i and [f.sub.i.sup.0] = [max.sub.j] {[f.sub.ij]}. Parameter G is the total number of generations and M is the population size in each generation.

Given the above fitness score function, one of the most widely applied selection rules, the “roulette wheel”, is used in SEQUENCE. Roulette wheel selection is a fitness-proportionate selection, where each chromosome is assigned a slice of a circular “roulette wheel”, the size of the slice being proportional to the individual’s fitness score in comparison with the fitness scores of the other chromosomes in the population. The probability that a chromosome is selected on a particular spin is given as follows:

[p.sub.ij] = [F(i, j)]/[[[summation].sub.k=1.sup.M] F(i, k)], [for all]i [member of] {1,…, G}, j [member of] {1,…, M}. (15)

In addition to the roulette wheel selection, we also consider applying an additional operator termed “elitism”, which was first introduced by De Jong (1975). An elitism operator is an addition to the selection operator, where the elitism operator forces the GA to retain some number of the best individuals at each generation. Such individuals can be lost if they are not selected to reproduce or if they are destroyed by crossover or mutation. Many researchers have found that elitism significantly improves the GA’s performance (Mitchell, 1999).

In SEQUENCE, we designed a revised elitism operator, which combines an elitism operator and a best two-way exchange operator. In order to describe the best two-way exchange operator, we first give the following definition:

Definition 6. (Two-way optimal sequence pair.) A sequence pair is defined as a two-way optimal sequence pair if the exchange of the positions of any pair of departments in the sequence pair cannot generate a better sequence pair optimal solution.

In each iteration, the best two-way exchange operator tests the possible improvement by exchanging the positions of any pair of departments in the sequence pair. It then accepts the exchange that can provide the largest improvement on the sequence-pair optimal solution and proceeds to the next iteration. The best two-way exchange operator stops when there is no two-way exchange of department positions that can provide a better sequence pair optimal solution. Therefore, the resulting sequence pair from a best two-way exchange operator must be a two-way optimal sequence pair.

Our revised elitism operator first selects the best K chromosomes from the last generation and then applies the best two-way exchange operator to the best chromosome of the K selected chromosomes before copying the K chromosomes to the new generation. The reason why we combine the elitism operator with the best two-way exchange operator is because the best chromosome in each generation has a very important impact on the overall performance of the next generation (the best chromosome is always selected to be copied to the next generation by the elitism operator, and it also has the highest probability to be selected for other GA operations). This operator facilitates the convergence of SEQUENCE by emphasizing the superiority of the best chromosomes in each generation by applying the best two-way operator on the best chromosomes.

3.3. GA operator design

In SEQUENCE, besides the revised elitism operator we discussed in Section 3.2, we also apply two other GA operators: crossover and mutation. We now present our design for these operators.

As the major instrument of variation and evolution in a GA, the crossover operator exchanges sub-chromosomes between two parent chromosomes, which results in two new offspring chromosomes. An obvious attribute of permutation problems is that simple crossover operators fail to generate offspring that are valid permutations. Therefore, Davis (1985) defined some of the first crossover operators for permutation problems. After that, a variety of permutation crossover operators were designed for different purposes. One of the most commonly used crossover operators is the uniform order-based crossover proposed by Davis (1991). To implement a uniform order-based crossover operator, a binary bit string is generated to denote the selection of positions. Offspring 1 copies the genes directly from parent 1 in those positions in the bit string marked by a “1” bit. Offspring 2 copies the genes from parent 2 in those positions marked by “0” bits. Both offspring then copy remaining genes from the other parent in the relative order of the genes in the other parent’s code.

Although useful with a normal single string permutation, the uniform order-based crossover operator cannot be directly applied to a position-pair-based encoding scheme because a position-pair-based chromosome is not a pure permutation of department positions, but rather a list of position pairs corresponding to each department. Therefore, we consider a modified order-based crossover specifically designed for the position-pair-based encoding scheme.

In stage 1, as in the uniform order-based crossover, our modified crossover first generates a bit string to indicate the selection of positions. Then offspring 1 copies the position pair directly from parent 1 in those positions in the bit string marked by a “1” bit. Offspring 2 copies the elements from parent 2 in those positions marked by “0” bits. Until this step, it is similar to the uniform order-based crossover. An illustration of stage 1 of our modified order-based crossover operator is provided in Fig. 3.

Our primary modification to the uniform order-based crossover operator is implemented in stage 2. In stage 2 of the modified order-based crossover operator, both offspring calculate the new position-pairs for the elements remaining after stage 1 based on the relative order in the other parent. However, instead of simply copying the remaining elements in the relative order from another parent, both offspring replicate the remaining elements in the relative orders of the elements according to the sequence pair corresponding to the other parent (the two relative orders in [[GAMMA].sub.+] and [[GAMMA].sub.-], separately).

[FIGURE 3 OMITTED]

For example, examining the offspring after stage 1 reveals that for offspring 1, the position pairs of elements a, b and f have not been specified (this is indicated by no pair being shown under these element indices in Fig. 3). This means that the sequence pair of offspring 1 after stage 1 can be expressed as ((e, c,, d,,), (, c,, e,, d)). The ordering of elements a, b and f in parent 2 (also shown in Fig. 3) is ((, a, f, b,,), (,, b, a, f,)), or more simply, a is before f, which is before b and likewise, b is before a, which is before f, in the two pair positions, respectively. Therefore, we take the sequence pair after stage 1 for offspring 1 and fill the empty positions in the same order as those elements are positioned in parent 2, which results in a sequence-pair for offspring 1 of ((e, c, a, d, f, b), (b, c, a, e, f, d)). The final representation of offspring 1 is shown in Fig. 4. Also illustrated in Fig. 4 is stage 2 of the modified order-based crossover operation that generates offspring 2.

Another important operator, mutation, provides insurance that the population will evolve to other regions of the solution space. Any form of a mutation operator applied to a permutation-structured code must yield a valid string, which also represents a feasible permutation. In SEQUENCE, we consider utilizing the random two-way exchange mutation operator, which mutates the chosen chromosome by exchanging two randomly picked genes.

[FIGURE 4 OMITTED]

3.4. Algorithm description

The following notation is used to describe the algorithm SEQUENCE.

G = maximum number of generations;

M = population size of each generation;

m = counter of the number of the chromosomes in the new population;

i = generation index;

j, k = chromosome index;

F(i, j) = fitness function value of chromosome j in generation i;

[p.sub.ij] = selection probability of chromosome j in generation i based on the roulette selection rule;

[bar.F.sub.i] = the average fitness function value of generation i;

[g*.sub.i] = the fittest chromosome in generation i;

[f*.sub.i] = the objective function value of the sequence-pair optimal solution corresponding to [g*.sub.i];

g* = the overall best chromosome;

f* = the objective function value of the sequence-pair optimal solution corresponding to g*;

K = the number of the best chromosomes to be copied to the next generation in the elitism operator;

PC = the probability of applying the crossover operator to the selected chromosomes;

PM = the probability of applying the mutation operator to the selected chromosomes;

S = the maximum number of successive generations without producing a new g*;

[epsilon] = the tolerance value for the percentage difference between [bar.F.sub.i] and [bar.F.sub.i+1];

T = the number of the best chromosomes in the last generation that are selected to apply the best two-way exchange operator.

The genetic procedures of SEQUENCE to solve the sequence-pair-based MIP-FLP are given as follows:

Step 1. Generate the initial generation, Generation 0, of size M. Each chromosome in generation 0 corresponds to a feasible sequence pair and has an objective function value of [f.sub.ij]. Calculate F(0, j) by using Equation (14) and [p.sub.0j] by using Equation (15). Record the fittest chromosome, [g*.sub.0], and its corresponding objective function value, [f*.sub.0]. Set i = 0, g* = [g*.sub.0] and f* = [f*.sub.0].

Step 2. Apply the revised elitism operator to generation i:

2.1. Select the fittest K chromosomes from generation i, which will include the best chromosome of generation i, [g*.sub.i].

2.2. If [g*.sub.i] is not a chromosome that represents a two-way optimal sequence pair, apply the best two-way exchange operator to [g*.sub.i]. The resulting [g*.sub.i] represents a two-way optimal sequence pair.

2.3. Copy the K chromosomes to generation i + 1 and set m = K.

Step 3. To fill the remaining M – m chromosomes in the new generation, randomly select two different parent chromosomes, [j.sub.1] and [j.sub.2], from generation i based on the roulette wheel selection rule.

Step 4. With the probability of PC and PM, where PC + PM = 1, apply crossover and mutation operators as shown below to Chromosomes [j.sub.1] and [j.sub.2] to generate two offspring chromosomes, [k.sub.1] and [k.sub.2], for generation i + 1.

4.1 Generate a random number, r, from a standard uniform distribution U(0, 1).

4.2 If r [less than or equal to] PC, apply crossover operator to chromosomes [j.sub.1] and [j.sub.2] to generate chromosomes [k.sub.1] and [k.sub.2].

4.3 If r > PC, apply the random two-way exchange mutation operator to [j.sub.1] and [j.sub.2] to generate chromosomes [k.sub.1] and [k.sub.2].

Step 5. Translate chromosomes [k.sub.1] and [k.sub.2] into sequence pairs, set the corresponding binary variables in the MIP-FLP model, and then solve the simplified MIP-FLP model to optimality. If chromosome [k.sub.i] (i = 1, 2) corresponds to a feasible sequence pair, add chromosome [k.sub.i] into the new population. Update the value of m as appropriate.

Step 6. If m < M, go to Step 3. Otherwise, set the new generation as the current generation by i = i + 1 and m = 0.

Step 7. In generation i, calculate F(i, j) using Equation (14) and [p.sub.ij] using Equation (15) for each chromosome. Record the fittest chromosome, [g*.sub.i], and its corresponding objective function value, [f*.sub.i]. If [f*.sub.i] < f*, set g* = [g*.sub.i] and f* = [f*.sub.i].

Step 8. If at least one of the following two stopping criteria is satisfied: (i) i [greater than or equal to] G; (ii) ||[bar.F](i) – [bar.F](i – 1)||/[bar.F](i – 1) [less than or equal to] [epsilon] and g* has not been updated for S generations, go to Step 9. Otherwise, go to Step 2.

Step 9. Apply the best two-way exchange operator to the best T chromosomes of the last generation. If the best chromosome of the T chromosomes after applying the best two-way exchange operator is better than g*, update g* and f*. Stop SEQUENCE and output g* and f*.

3.5. Parameter setting

Parameter setting is another important aspect in GA design since it has a major impact on the performance of the GA. However, these parameters typically interact with each other and their effects cannot be isolated, so it is extremely difficult to optimize them one at a time. Although parameter settings have been discussed extensively in the GA literature, no conclusive results have been presented. So, in most cases, researchers either conduct experimental tests to find “good” parameter settings or they set the parameters according to experience or knowledge about the specific problems to which the GA is applied. Through a full factorial experimental design with three factors (M = (50, 100), PC = (0.5, 0.7, 0.9), and PM = (0.01, 0.05, 0.1)), we set the parameters of SEQUENCE as follows: G = 200, M = 50, K = 10, PC = 0.9, PM = 0.1, S = 10, [member of] = 0.1% and T = 5.

3.6. Usage of a penalty function in the MIP model

Through our initial research, we found that the main constraints that affect the feasibility of a sequence pair are the aspect ratio constraint and the facility dimension constraint, especially when the facility area is 100% utilized. That is, when a relatively small departmental aspect ratio is used along with a 100% area utilization of a facility, it is difficult to generate feasible sequence pairs in SEQUENCE (especially in generating the initial feasible sequence pairs).

This difficulty can be addressed by adding some extra area to the facility, which relaxes the facility area constraint and decreases the area utilization. Based on our research, even just a very limited relaxation (e.g., 5% of the total facility size) permits many of the sequence-pairs to be declared feasible, which greatly reduces the heuristic solution time. An additional benefit of a small relaxation is that the algorithm can provide better chromosome variety in the first several generations with some additional chromosomes that may not be exactly feasible, but are close to feasible under the small relaxation.

To relax the facility dimensions, we fix the bottom-left corner of the facility and increase the width and height of the facility with the same proportion (e.g., a 5% increase in the height and width simultaneously). To implement such a relaxation in the MIP-FLP, we modify the MIP-FLP model as follows (only the modified expressions are shown):

1. Objective function:

min [summation over i] [summation over (j>i)][f.sub.ij]([d.sub.ij.sup.x] + [d.sub.ij.sup.y]) + ([summation over i] [summation over j][f.sub.ij])([L.sup.x] + [L.sup.y]) [summation over i] [summation over s] [t.sub.i.sup.s-]. (16)

2. Facility boundary constraints:

[L.sup.s] – [l.sub.i.sup.s] – [c.sub.i.sup.s] = [t.sub.i.sup.s+] – [t.sub.i.sup.s-], [for all]i; [for all]s. (17)

[t.sub.i.sup.s-] [less than or equal to] (r – 1)[L.sup.s], [for all]i; [for all]s. (18)

3. Overlapping constraints:

[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] + r[L.sup.s](1 – [z.sub.ij.sup.s]), [for all]i, j; [for all]s, (19)

where [t.sub.i.sup.s-] ([t.sub.i.sup.s+]) measures the distance from the right (above) side of department i to the right or above side of the facility as defined in Equation (17), and [t.sub.i.sup.s-] is greater than zero if i exceeds the actual dimension of the facility in the s direction ([t.sub.i.sup.s+] is used to ensure an equality in Equation (17) when the solution is feasible). The relaxation of the facility dimensions is constrained by Equation (18), where r is a relaxation factor (r > 1) to determine how much relaxation is applied to the facility dimensions. We use an upper bound of the layout objective function value, ([[summation].sub.i] [[summation].sub.j][f.sub.ij])([L.sub.x] + [L.sub.y]), in Equation (16) as the penalty multiplier. Furthermore, we also modify the overlapping constraint as shown in Equation (19) by changing the constant parameter L to r L, which means that if [z.sub.ij] = 0 (i does not proceed j in the s-direction) the distance from the left-hand side of j to the right-hand side of i is no more than r [L.sup.s].

Table 2 illustrates the effectiveness of our relaxation method on the efficiency of the generating “feasible” sequence pairs in SEQUENCE. A 5% relaxation of the facility dimensions (r = 1.05) is applied to three test data sets. We then compared the total number of sequence pairs and CPU time required to generate 50 initial feasible sequence pairs (the population size in SEQUENCE) with and without the relaxation. Data sets O9, M15 and M25, are of nine, 15 and 25 departments, respectively.

It is obvious that the application of the relaxation of the facility dimensions to SEQUENCE greatly improves the efficiency of SEQUENCE to generate feasible sequence pairs. To guarantee the feasibility of the sequence pair in the final solution, the relaxation parameter, r (r [greater than or equal to] 1) is reduced exponentially as shown in Equation (20) as the generations evolve:

r = 1.0 + 0.05 [1/[square root of ([e.sup.g])]], (20)

where g is the generation index of the GA. So, after just a few generations, all chromosomes become feasible.

4. Numerical experiments

To illustrate the effectiveness and efficiency of SEQUENCE for solving the continuous-representation-based FLP, a series of numerical experiments based on differently sized test problems from both the literature and industrial applications are conducted. The following numerical tests are conducted in two phases: (i) an optimality comparison test; and (ii) heuristic comparison tests. We also conduct a sensitivity analysis with respect to the department aspect ratio parameter in terms of solution quality and solution time. All numerical tests are conducted on a computer with a Pentium IV 3.2M Hz CPU and 2.0 GB of physical memory.

4.1. Optimality comparison test

In the optimality comparison test, our purpose is to compare SEQUENCE solutions with optimal solutions to show the quality of SEQUENCE solutions. The data sets we use for the optimality comparison test are the 15 test problems delineated by Sherali et al. (2003), which, to our knowledge, represent all of the continuous-representation-based FLPs that have been solved to global optimality in the framework of MIP-FLP.

The properties of the test data sets for the optimality comparison test are summarized in Table 3. Here the flow density is defined as a percentage of the number of departmental pairs with positive flow interactions over the maximum possible number of pairs. The area utilization is defined as the sum of the department areas divided by the available area.

For each test problem, we run SEQUENCE until the optimal solutions reported in Sherali et al. (2003) are found. The maximum number of runs of SEQUENCE for the test problems is eight; i.e., if SEQUENCE cannot achieve the optimal solutions in eight runs, we stop SEQUENCE and report the optimality gap between the best SEQUENCE solutions and the optimal solutions. Correspondingly, the reported SEQUENCE solution time is the total runtime for SEQUENCE to find the optimal solutions or the total runtime of eight runs if SEQUENCE fails to find the optimal solutions in eight runs.

The results of the optimality comparison test are summarized in Table 4. Here the optimality gap represents the percentage of the difference between the objective function value of the best SEQUENCE solutions and the objective function value of the optimal solutions (Sherali et al., 2003) for the test problems.

From Table 4, we can see that SEQUENCE achieves the optimal solutions for 13 of the 15 test problems within eight runs and the optimality gaps for the two problems that SEQUENCE does not solve to optimality in eight runs are small. Therefore, according to the results for the optimality comparison test, the best solutions from eight runs of SEQUENCE are equal to or at least very close to the global optimal layout solutions of the test problems and the solution time for relatively larger test problems are reduced (clearly GAs have a great deal of overhead associated with them, which makes it a poor choice as a heuristic for small, relatively easy-to-solve problems). The detailed best SEQUENCE solutions for all data sets used in the optimality comparison test are available from the authors.

4.2. Heuristic comparison tests

In the heuristic comparison tests, we use SEQUENCE to solve larger data sets from the literature that are widely used in FLP heuristic research. We compare the results from SEQUENCE to the results published in the literature. These test data sets, to our knowledge, have only been solved to sub-optimality by existing heuristics and through the comparison of our results with the best reported results from these heuristics, we can show the advantages of SEQUENCE compared with other algorithms. Additionally, in order to test the effectiveness of our heuristic for even larger and more practical data sets, we also provide some new data sets based on a recent industrial project.

4.2.1. Data set description

Because different researchers often use different data sets to conduct their numerical experiments, we tried to find as many as possible applicable data sets to compare SEQUENCE solutions. Table 5 shows the properties of the data sets used in the heuristic comparison tests, where the “Reference” column provides the sources that have referred to the corresponding data sets in their research (in chronological order). Data sets Ba12 and Ba14 are two data sets with 12 and 14 departments, respectively, which were first presented by Bazaraa (1975). There is a small dummy department in data set Ba14, which has no flow in and out. It should be noted that Bazaraa (1975), Hassan et al. (1986), Van Camp et al. (1991) and Kamoun and Yano (1996) refer to Ba14 in their research without considering the dummy department, so we refer to the revised Ba14 without the dummy department as Ba13. Data sets M11*, M15* and M25* are three data sets first presented by Bozer et al. (1994). There is a fixed department in each of the original data sets of M11, M15 and M25, and we modified the original data sets by relaxing the fixed department restrictions in our heuristic test and named the revised data sets as M11*, M15* and M25*, respectively.

In the heuristic comparison tests, as appears to be the standard, we run SEQUENCE ten times and compare the best SEQUENCE solutions of ten runs with the best solutions from different heuristics.

4.2.2. Heuristic comparison test 1

In heuristic comparison test 1, we compare the best SEQUENCE solutions with other heuristic solutions based on five widely used data sets with the best solution found by continuous-representation-based heuristics. To make our solutions comparable to the results from other heuristics, we use the same aspect ratio value as used in the best solutions of other heuristics. For data set v10, we use a minimum side length equal to five. For data sets Ba12 and Ba13, we use a minimum side length equal to one. For data sets Ba14, we use a minimum side length equal to one, except for the dummy department, where we place no shape restriction on it (as also done by other researchers Tate and Smith (1995) and Banerjee et al. (1997)). For AB20, we use a common aspect ratio of four for each department.

Table 6 presents the numerical test results for heuristic comparison test 1 (the detailed best SEQUENCE solutions for all data sets used in the heuristic comparison tests are available from the authors). For each data set, the solutions from different heuristics are given. The improvement column shows the percentage of the improvements compared with the best solution found by other heuristics.

From Table 6, it is obvious that SEQUENCE performs better than all compared heuristics in all test data sets in terms of the best objective function value. The improvements over the best solutions we found in literature for the five test data sets are: v10 (10.71%), Ba12 (0.76%), Ba13 (23.46%), Ba14 (0.94%) and AB20 (1.31%), respectively.

4.2.3. Heuristic comparison test 2

In heuristic comparison test 2, we compare the SEQUENCE solutions with two discrete-representation-based heuristics, MULTIPLE (Bozer et al. (1994) and SABLE (originally by Meller and Bozer (1996), but we use the version implemented in Layout SFC 1.0 by Meller and Liu (2003)). Note that for a discrete representation it is difficult to control and measure the department shapes through an aspect ratio. We therefore utilize the department shape irregularity factor defined by Bozer et al. (1994) as follows:

[[OMEGA].sub.i] = [P.sub.i]/4[square root of ([a.sub.i])], (21)

where [P.sub.i] and [a.sub.i] are the perimeter and area of department i, respectively. The smaller the shape factor, [[OMEGA].sub.i], the more squared the department shape. The purpose for heuristic comparison test 2 is that it shows not only the relative advantage of SEQUENCE in terms of solution quality, but also the potential benefits that can be obtained from a continuous-representation-based heuristic, specifically, in terms of shape factor as measured by Equation (21). We ran MULTIPLE, SABLE and SEQUENCE ten times for the discrete-representation-based data sets and compare both the best solutions and the maximum shape factor in the best solutions to illustrate that SEQUENCE can provide the overall better solutions in terms of both the material handling distances and the resulting department shapes.

For the data sets used in heuristic comparison test 2, we use the common aspect ratio values of four, four, four, five, and five for data sets BM9, BM12, M11*, M15* and M25*, respectively, even though no shape control is used by MULTIPLE and SABLE. Table 7 shows the results of heuristic comparison test 2. From Table 7 we can see that SEQUENCE performs better than MULTIPLE and SABLE in terms of both the best objective function value and the department shape factor in all five test data sets.

Finally, in order to explore the capability of SEQUENCE in solving larger-scale industry-based FLPs, we provide two new data sets for relatively large problems based on a real industrial application. For this industrial application, we aggregate the departments with two methods, resulting in 30-and 35-department versions of the problem, SC30, SC35. These two problems, to our knowledge, are larger than any continuous-representation-based test problems in the literature. The properties of data sets SC30 and SC35, including the maximum allowed aspect ratio setting for these two data sets in the numerical test, are summarized in Table 8 (full details on these new data sets are provided in the Appendix; the best-known solutions found during testing are available from the authors). Based on requirements of the departments that resulted from the aggregation, we initially use a common aspect ratio of five for SC30 and four for SC35 to control the department shape (other ratios are explored later in our testing). For MULTIPLE and SABLE, we do not apply any department shape restrictions. We also compare the best objective value of SEQUENCE solutions in ten runs with the best objective value of MULTIPLE and SABLE solutions in ten runs in Table 9. We can see that for problems SC30 and SC35, SEQUENCE improves the best solution from MULTIPLE and SABLE by 39 and 41%, respectively, while maintaining better department shapes.

4.2.4. Heuristic comparison tests summary

Through the heuristic comparison tests, we conclude that SEQUENCE performs better than all heuristics we studied with respect to the test data sets in terms of the best objective function value. SEQUENCE also provides the better department shapes for test data sets if compared with discrete-representation-based heuristics. However, it is worth noting that many of the algorithms with which we compared SEQUENCE have comparably shorter runtimes. We present the runtime results for SEQUENCE below.

Table 10 shows the solution time of SEQUENCE for finding its best solutions within ten runs (which is how solution time results are reported in Tate and Smith (1995)) and the total run time of ten runs of SEQUENCE for all test data sets used in the heuristic comparison tests. As we can see, this improved performance in obtaining objective function values does come at a cost in terms of runtime. Since GA solutions are based on the evolution of many generations of chromosomes and SEQUENCE solves one simplified MIP-FLP model for each chromosome in each generation, the solution time for SEQUENCE is relatively long. In general, the larger the test data set, the longer the runtime. For the largest problem, SC35, it takes SEQUENCE approximately 26 hours to run SEQUENCE ten times. Given that in most FLP applications layout planning is not a real-time decision process, and that a lower number of runs may be used (i.e., four runs instead of ten runs), we believe that such a solution time can still be justified for large FLPs.

4.3. Sensitivity analysis

As noted earlier, Goetschalackx (1998) showed that, in general, the level to which department shapes are limited affects an algorithm’s performance. In particular, for an algorithm based on a sequence-pair representation, like SEQUENCE, generating feasible sequence pairs will be difficult when either the space constraint is tight or the departments are constrained to a low aspect ratio (or both of these conditions exist). Therefore, to test the sensitivity of SEQUENCE’s results to the aspect ratio chosen, we solved the two largest data sets used in our numerical experiments, SC30 and SC35, for common department aspect ratios of two, three, four and five. For each aspect ratio setting, we ran SEQUENCE ten times. The best objective function value found in ten runs and the total solution time for the ten runs are used to evaluate the impact of changing the aspect ratio constraint.

These results are summarized in Table 11 and Fig. 5, where we indicate the best objective function value and total solution time (in hours) over ten runs.

As shown in Fig. 5, the best objective function value found by SEQUENCE in ten runs decreases as the aspect ratio increases. This is expected since as the aspect ratio increases, more layout solutions become feasible, which leads to a better objective function value. It is also evident by comparing the results from SEQUENCE in Table 11 with the results from MULTIPLE and SABLE from Table 9 that even with the tightest aspect ratio constraint (i.e., an aspect ratio equal to two, which corresponds to a shape factor of 1.06) the best SEQUENCE solution is much better (i.e., 15 to 20% better) than the best SABLE and MULTIPLE solutions (which have much worse department shapes as measured by the department shape factor).

[FIGURE 5 OMITTED]

[FIGURE 6 OMITTED]

Finally, in terms of the sensitivity of solution time to the department aspect ratio constraint, we can see from Fig. 6, where the total solution time for ten runs is presented as a function of aspect ratio, that the relationship is not as straightforward as the relationship between objective function value and aspect ratio. That is, for SC30, the total solution time does not vary to a significant degree as the aspect ratio increases. However, for SC35, the total solution time first decreases and then increases as the aspect ratio increases. In an attempt to understand why such a relationship may exist, consider the following factors. When the department aspect ratio increases for all departments, as explained earlier in the context of objective function value, there are more feasible solutions. And this increase in the number of feasible solutions would tend to lead to an increase in solution time. On the other hand, SEQUENCE may generate solutions that are ultimately infeasible with respect to some problem constraints and SEQUENCE is negatively impacted in terms of solution time by a restricted number of feasible solutions since it has to filter such infeasible solutions. Thus, we can see that too many feasible or too many infeasible solutions both lead to a long solution time. Thus, we cannot use aspect ratio to predict algorithm solution time and conclude that problem size (in terms of the number of departments) is still a fairly good (but not perfect) indicator of problem difficulty for SEQUENCE.

5. Conclusions

In this paper we presented fundamental results with respect to the sequence-pair representation, which originated in the VLSI design literature, and its application to the FLP. We showed, in particular, how to integrate the sequence-pair representation with the MIP model for FLP (MIP-FLP). This integration is based on results we provide that show that searching the sequence-pair solution space eliminates many combinations of binary variable settings in the MIP-FLP that are infeasible while not eliminating any binary variable combinations that are feasible with respect to the department overlap constraint.

We propose a GA-based heuristic, SEQUENCE, which integrates the sequence-pair representation with the MIP-FLP model to solve the continuous-representation-based FLP with all-rectangular-shaped departments. In developing the GA for this problem, it was necessary to develop a new pair-based crossover operator and to modify other elements of standard GAs to this optimization problem.

To illustrate the effectiveness of SEQUENCE, we compared it with both optimal solutions and other heuristics based on widely used data sets from the literature and some new larger data sets based on our industrial experience. The current best solutions now reported in the literature were improved for seven data sets, and in two cases, the objective function values were improved by over 10%. The best solutions for the two new industrial-based data sets were provided for future researchers’ consideration.

In addition to investigating a reduction in the runtime of SEQUENCE, future research in the area of integrating the sequence pair representation with other aspects of the FLP is needed. One aspect is the consideration of fixed departments. When fixed departments are added, the sequence pairs have to be “repaired” so as to provide a feasible setting of binary variables to the MIP. Another aspect is how to consider nonrectangular department shapes, which are very common in industrial applications, within the MIP-FLP model and whether or not a sequence-pair representation would be amenable to this problem. And finally, a third aspect that is clear when studying industrial problems is that many FLP applications need to consider an existing facility aisle structure, which is prohibitively expensive to revise. Such an aisle structure partitions the facility into different zones, with the relative location and dimensions of these zones known. Since the sequence pair representation is a relative-location-relationship-based representation, we also believe that utilizing the sequence-pair representation, perhaps in a hierarchical fashion, can be used to solve the FLP with an existing aisle structure.

The sequence-pair representation can also be applied to other difficult two-dimensional optimization problems such as variations on the two-dimensional version of the linear ordering problem. Therefore, an avenue of future research that appears promising is to investigate the appropriateness of applying the sequence-pair representation to other problem domains such as scheduling and routing problems.

Acknowledgements

This study was supported in part by NSF Grant DMII-0355178 and the Center for High Performance Manufacturing at Virginia Tech.

References

Armour, G.C. and Buffa, E.S. (1963). A heuristic algorithm and simulation approach to relative allocation of facilities. Management Science, 9, 294-309.

Banerjee, P., Montreuil, B., Moodie, C.L. and Kashyap, R.L. (1992) A modeling of interactive facilities layout designer reasoning using qualitative patterns. International Journal of Production Research, 30, 433-453.

Banerjee, P., Zhou, Y., Krishnasami, K. and Montreuil, B. (1997) Genetically assisted optimization of cell layout and material flow path skeleton. IIE Transactions, 29(4), 277-291.

Bazaraa, M.S. (1975) Computerized layout design: a branch and bound approach. AIIE Transactions, 7(4), 432-437.

Bozer, Y.A. and Meller, R.D. (1997) A reexamination of the distance-based facility layout problem. IIE Transactions, 29, 549-560.

Bozer, Y.A., Meller, R.D. and Erlebacher, S.J. (1994) An improvement-type layout algorithm for single and multiple floor facilities. Management Science, 40, 918-932.

Castillo, I. and Westerlund, T. (2005) An [member of]-accurate model for optimal unequal-area block layout design. Computers & Operations Research, 429-447.

Davis, L. (1985) Applying adaptive algorithms to epistatic domains, in Proceedings of the International Joint Conference on Artificial Intelligence, Los Angeles, CA, pp. 213-238.

Davis, L. (1991) Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, NY.

De Jong, K.A. (1975) An analysis of the behavior of a class of genetic adaptive systems. Ph.D. thesis, University of Michigan, Ann Arbor, MI.

Goetschalckx, M. (1998) Models and algorithms for block layout design with departmental shape constraints. In Progress in Material Handling Research: 1998, Graves, R.J., McGinnis, L.F., Medeiros, D.J., Ward, R.E. and Wilhelm, M.R., (eds). Braun-Brumfield, Ann Arbor, MI, pp. 213-238.

Hassan, M. M.D., Hogg, G.L. and Smith, D.R. (1986) SHAPE: A construction algorithm for area placement evaluation. International Journal of Production Research, 24, 1283-1295.

Kamoun, M. and Yano, C.A. (1996) Facility layout to support just-in-time: Transportation/manufacturing interface. Transportation Science, 30(4), 315-329.

Lacksonen, T.A. (1994) Static and dynamic layout problems with varying areas. Journal of the Operations Research Society, 45, 59-69.

Lacksonen, T.A. (1997) Preprocessing for static and dynamic facility layout problems. International Journal of Production Research, 35, 1095-1106.

Langevin, A., Montreuil, B. and Riopel, D. (1994) Spine layout design. International Journal of Production Research, 32, 429-442.

Meller, R.D. and Bozer, Y.A. (1996) A new simulated annealing algorithm for the facility layout problem. International Journal of Production Research, 34(6), 1675-1692.

Meller, R.D. and Gau, K.Y. (1996) Facility layout objective functions and robust layouts. International Journal of Production Research, 34, 2727-2742.

Meller, R.D. and Liu, Q. (2003) LayoutSFC 1.0. Software, Center for High Performance Manufacturing, Virginia Tech., Blacksburg, VA.

Meller, R.D., Narayanan, V. and Vance, P.H. (1999) Optimal facility layout design. Operations Research Letters, 23, 117-127.

Mitchell, M. (1999) An Introduction to Genetic Algorithms, MIT Press, Cambridge, MA.

Montreuil, B. (1990) A modeling framework for integrating layout design and flow network design, in Proceedings of the Material Handling Research Colloquium, Hebron, KY, pp. 43-58.

Montreuil, B., Venkatadri, U. and Ratliff, H.D. (1993) Generating a layout from a design skeleton. IIE Transactions, 25, 3-15.

Murata, H., Fjuiyoshi, K., Nakatake, S. and Kajitani, Y. (1995) Rectangle-packing-based module placement, in Proceedings of the IEEE International Conference on Computer Aided Design, San Jose, CA, pp. 472-479.

Murata, H. and Kuh, E. (1998a) Sequence-pair based placement method for hard/soft/pre-placed modules, in Proceedings of the International Symposium on Physical Design, Monterey, CA, pp. 167-172.

Murata, H. and Kuh, E. (1998b) VLSI/PCB placement with obstacles based on sequence pair. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 17, 60-68.

Norman, B.A., Smith, A.E. and Arapoglu, R.A. (2001) Integrated facility design using a contour distance metric. IIE Transactions, 33, 337-344.

Sha, L. and Dutton, R.W. (1985) An analytical algorithm for placement of arbitrarily sized rectangular blocks, in Proceedings of the 22nd ACM/IEEE Design Automation Conference, San Diego, CA, pp. 602-608.

Sherali, H.D., Fraticelli, B.M.P. and Meller, R.D. (2003) Enhanced model formulations for optimal facility layout. Operations Research, 51, 629-644.

Tate, D.M. and Smith, A.E. (1995) Unequal area facility layout using genetic search. IIE Transactions, 27(4), 465-472.

Van Camp, D.J., Carter, M.W. and Vannelli, A. (1991) A nonlinear optimization approach for solving facility layout problems. European Journal of Operational Research, 57, 174-189.

Appendix

We now present the data used in our investigations of the application of SEQUENCE to large data sets.

Table A1. The dimensional data for SC30

Department 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Area 3 4 4 16 4 5 2 3 5 6 2 24 5 3 11

Department 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Area 6 2 8 4 5 4 3 1 3 1 4 6 1 14 4

Table A2. The flow data for SC30

Dept i Dept j Flow [f.sub.ij]

1 24 2.95

1 25 6.32

1 26 1.26

1 27 2.11

1 28 1.26

1 30 13.91

2 6 20.38

2 19 4.50

2 20 3.63

2 21 2.93

2 22 1.29

2 23 1.43

4 3 394.11

5 11 4.09

5 12 33.09

6 5 8.92

6 7 2.07

6 8 4.84

6 10 4.56

6 12 1.83

6 17 0.61

7 8 12.97

8 9 43.23

9 11 4.76

9 12 38.47

10 12 38.03

11 12 8.84

12 13 12.97

12 14 4.67

12 15 53.42

12 16 1.83

13 15 12.97

14 15 4.67

15 4 63.95

15 18 190.74

16 15 4.58

17 15 0.76

18 4 190.74

19 29 9.18

20 29 7.40

21 29 5.97

22 29 2.63

23 29 2.92

24 29 5.90

25 29 12.65

26 29 2.53

27 29 4.22

28 29 2.53

29 4 190.13

30 29 59.64

Table A3. The dimensional data for SC35

Department 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Area 3 5 4 14 4 5 2 3 5 6 2 6 5 3 13

Department 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

Area 6 2 10 4 5 4 3 1 3 1 4 6 1 18 4

Department 31 32 33 34 35

Area 9 14 10 4 3

Table A4. The flow data for SC35

Dept i Dept j Flow [f.sub.ij]

1 24 2.95

1 25 6.32

1 26 1.26

1 27 2.11

1 28 1.26

1 30 13.91

2 6 20.38

2 19 4.50

2 20 3.63

2 21 2.93

2 22 1.29

2 23 1.43

4 3 225.65

5 11 4.09

5 12 33.09

6 5 8.92

6 7 2.07

6 8 4.84

6 10 4.56

6 12 1.83

6 17 0.61

6 31 3.93

7 8 12.97

8 9 43.23

9 11 4.76

9 12 38.47

10 12 38.03

11 12 8.84

12 32 72.89

13 15 12.97

14 15 4.67

15 4 63.95

15 18 190.74

16 15 4.58

17 15 0.76

18 4 190.74

19 29 9.18

20 29 7.40

21 29 5.97

22 29 2.63

23 29 2.92

24 29 5.90

25 29 12.65

26 29 2.53

27 29 4.22

28 29 2.53

29 33 190.13

30 29 59.64

31 32 22.92

32 13 12.97

32 14 4.67

32 15 53.42

32 16 1.83

33 34 168.45

Biographies

Qi Liu is a Senior Analyst for Capital One in Richmond, VA. He received his Ph.D. from the Grado Department of Industrial and Systems Engineering at Virginia Tech in 2004. He received both his M.S. and B.S. in Industrial Automation from East China University of Science and Technology. In 2001 he commenced his Ph.D. studies at Virginia Tech in the Department of Industrial & Systems Engineering. While working towards the Ph.D. degree, he received the Robert R. Reisinger Honor Scholarship from the Material Handling Education Foundation. His research was sponsored by the National Science Foundation. This paper is part of his dissertation that earned an Honorable Mention in the UPS-SOLA (INFORMS) Dissertation Award Competition in 2005.

Russell D. Meller holds the title of the Hefley Professor of Logistics and Entrepreneurship at the University of Arkansas. He joined the Department of Industrial Engineering as Director of the Center for Engineering Logistics and Distribution (CELDi; a National Science Foundation Industry/University Cooperative Research Center) in 2005 after six years on the faculty at Virginia Tech, where he most recently held the title of Professor of Industrial & Systems Engineering in the Grado Department of Industrial & Systems Engineering. He joined Virginia Tech after seven years on the faculty at Auburn University. He received his B.S.E., M.S.E. and Ph.D. in Industrial and Operations Engineering from The University of Michigan. His dissertation on facility layout was awarded the 1994 Institute of Industrial Engineers Outstanding Dissertation Award and First Prize in the 1993 College on Location Analysis Dissertation Prize Competition from The Institute of Management Sciences. In 1996 he received a CAREER Development Grant from the National Science Foundation. In 2002 he received the Outstanding Young IE award from the Institute of Industrial Engineers. His professional experience includes consulting with the SysteCon Division of Coopers & Lybrand, General Electric, Cross Creek Apparel, and the Russell Corporation. His research interests include facility logistics, facilities layout and location, automated material handling systems, and operations research applications in forestry. He has published his research in IIE Transactions, Operations Research, Manufacturing & Service Operations Management, Management Science, Journal of Manufacturing Systems, IJPR, and other journals. He co-authored a paper that won the 2003-2004 Best Paper Award for IIE Transactions on Design & Manufacturing. In addition, he is a Department Editor for IIE Transactions and is on the Editorial Board of Journal of Manufacturing Systems. He is a member of IIE, INFORMS, and Alpha Pi Mu, and is currently serving as President of the College-Industry Council for Material Handling Education.

QI LIU (1) and RUSSELL D. MELLER (2,*)

(1) Barclays Bank Delaware, Wilmington, DE 19801, USA

E-mail: qi.liu@barclaycardus.com

(2) Department of Industrial Engineering, University of Arkansas, Fayetteville, AR 72701, USA

E-mail: rmeller@vt.edu

Received August 2004 and accepted April 2005

*Corresponding author

Table 1. The percentage of MIP-FLP position consistent, but not layout

feasible, settings correctly eliminated with the sequence-pair

representation

Number of Number of binary variable settings

departments (n) MIP-FLP ([2.sup.n(n-1)]) SP ([(n!).sup.2])

2 4 4

3 64 36

4 4096 576

5 1048576 14400

6 1073741824 518400

7 4.398 x [10.sup.12] 25401600

Number of

departments (n) Percentage of eliminated binary variable settings

2 0.0

3 43.8

4 85.9

5 98.6

6 99.9

7 [approximately equal to]100

Table 2. Impact of a 5% relaxation of the facility dimensions on

SEQUENCE performance

Without relaxation With relaxation

Number CPU time Number CPU time

Problem of SPs (seconds) of SPs (seconds)

O9 746 79 74 9

M15 2816 348 75 11

M25 100000 (a) 8929 3393 323

Note: SPs = sequence pairs.

(a) SEQUENCE has reached the maximum number of sequence pairs without

generating any feasible sequence pair.

Table 3. Properties of the test problems for the optimality comparison

tests

Problem Number of Aspect

name depts ratio Flow density (%) Area utilization (%)

M6 6 4 26.67 98.67

M7 6 4 23.81 99.00

FO7 7 4 28.57 99.98

FO7-1 7 4 28.57 97.48

FO7-2 7 5 28.57 99.98

FO8 8 4 25.00 99.98

FO9 9 4 22.22 100.00

NO7 7 4 42.86 99.98

NO7-1 7 4 42.86 97.48

NO7-2 7 5 42.86 99.98

O7 7 4 47.62 99.98

O7-1 7 4 47.62 97.48

O7-2 7 5 47.62 99.98

O8 8 4 53.57 99.98

O9 9 4 41.67 100.00

Table 4. Comparison between SEQUENCE solutions and the optimal solutions

Optimal solution SEQUENCE solution

Time Number Time

Problem name Objective (seconds) (a) Objective of runs (seconds)

M6 82.26 0.04 82.26 1 562

M7 106.76 0.07 106.76 1 607

FO7 20.73 29 20.73 8 3615

FO7-1 19.56 17 19.56 1 243

FO7-2 17.75 6 17.75 7 2825

FO8 22.31 29 22.31 4 1985

FO9 23.46 56 23.46 6 2403

NO7 98.49 244 98.49 1 360

NO7-1 90.73 71 90.73 2 1134

NO7-2 90.50 80 90.50 1 417

O7 131.63 790 131.63 6 1644

O7-1 120.99 691 120.99 1 358

O7-2 116.94 619 116.94 1 238

O8 242.88 3860 245.41 8 3056

O9 235.95 5384 246.26 8 3879

Problem name Optimality gap (%)

M6 0.00

M7 0.00

FO7 0.00

FO7-1 0.00

FO7-2 0.00

FO8 0.00

FO9 0.00

NO7 0.00

NO7-1 0.00

NO7-2 0.00

O7 0.00

O7-1 0.00

O7-2 0.00

O8 1.03

O9 4.37

(a) The solution time for the optimal solutions is revised from the

literature based on the same computer we used to run SEQUENCE.

Table 5. Properties of the test problems for the heuristic comparison

tests

Dept Flow Area

Problem number density (%) utilization (%) Reference

BM9 9 41.67 100.00 Bozer and Meller (1997)

v10 10 26.67 100.00 Van Camp et al. (1991),

Tate and Smith (1995),

Kamoun and Yano (1996),

Banerjee et al. (1997)

and Norman et al.

(2001)

M11* 11 32.73 100.00 Bozer et al. (1994),

Meller and Bozer (1996)

and Meller and Gau

(1996)

BM12 12 25.76 100.00 Bozer and Meller (1997)

Bal2 12 89.39 88.33 Bazaraa (1975), Hassan et

al. (1986), Van Camp et

al. (1991), Tate and

Smith (1995), Kamoun

and Yano (1996),

Banerjee et al. (1997)

and Norman et al.

(2001)

Bal3 13 73.08 95.24 Bazaraa (1975), Hassan et

al. (1986), Van Camp et

al. (1991) and Kamoun

and Yano (1996)

Bal4 14 62.64 96.83 Bazaraa (1975), Tate and

Smith (1995), Banerjce

et al. (1997) and

Norman et al. (2001)

M15* 15 20.00 100.00 Bozer et al. (1994),

Meller and Bozer (1996)

and Meller and Gau

(1996)

AB20 20 64.74 100.00 Armour and Buffa (1963),

Bozer et al. (1994),

Tate and Smith (1995),

Meller and Gau (1996)

and Banerjee et al.

(1997)

M25* 25 11.33 100.00 Bozer et al. (1994),

Meller and Bozer (1996)

and Meller and Gau

(1996)

Table 6. Results of numerical test 1

CRAFT SHAPE NLT (Van Tate and

Data (Armour and Bazaraa (Hassan et Camp et Smith

set Buffa, 1963) (1975) al., 1986) al., 1991) (1995)

v10 — — 28119 — 23671

Ba12 — 14079 11910 10578 8768

Ba13 — — 6875 6339 —

Ba14 — 8171 — — 5080

AB20 7862 — — — 5743

Data Kamoun and Banerjee

set Yano (1996) et al., (1997) SEQUENCE Imp. (%)

v10 24085 22395 19997 10.71

Ba12 11470 — 8702 0.76

Ba13 6671 — 4852 23.46

Ba14 — 5052 5004 0.94

AB20 — 5833 5668 1.31

Table 7. Results of numerical test 2

Best layout solutions

Imp. (a) Maximum shape factor

Problem MULTIPLE SABLE SEQUENCE (%) MULTIPLE SABLE SEQUENCE

BM9 252 252 246 2 1.67 1.67 1.25

M11* 1344 1373 1171 13 1.34 1.34 1.24

BM12 149 149 142 4 1.25 1.25 1.25

M15* 32359 31936 28526 11 1.42 1.55 1.31

M25* 1596 1588 1371 14 1.34 1.34 1.34

(a) The improvement is calculated between the SEQUENCE solution and the

better of the MULTIPLE and SABLE solutions.

Table 8. Properties of the two larger industrial-based data sets

Maximum Flow Area

Department allowed density utilization Facility

Problem number aspect ratio (%) (%) dimensions

SC30 30 5 11.49 90.00 15 by 12

SC35 35 4 9.08 80.00 16 by 15

Table 9. Results of the comparison on new data sets

Best layout solutions Maximum shape factor

Problem MULTIPLE SABLE SEQUENCE Imp. (%) MULTIPLE SABLE SEQUENCE

SC30 5605 6175 3707 34 1.38 1.43 1.34

SC35 6086 6733 3604 41 1.43 1.53 1.25

Table 10. Solution time for all data sets used in the heuristic

comparison tests

Problem Solution tiem (hours) Total time of ten runs (hours)

BM9 0.29 1.30

v10 1.85 2.16

M11* 0.19 2.00

BM12 0.28 2.53

Bal2 0.83 1.64

Bal3 0.46 2.69

Ba14 0.80 3.37

M15* 3.11 3.11

AB20 3.46 6.51

M25* 6.70 9.05

SC30 4.07 20.23

SC35 16.04 26.64

Table 11. Aspect ratio sensitivity analysis for SEQUENCE for ten runs on

SC30 and SC35

Data set Aspect ratio Best obj. Total solution time (hours)

SC30 2 4790.43 22

3 4332.87 25

4 4165.83 25

5 3706.83 20

SC35 2 4839.45 25

3 4332.87 20

4 3604.12 27

5 3247.48 36

COPYRIGHT 2007 Institute of Industrial Engineers, Inc. (IIE)

COPYRIGHT 2008 Gale, Cengage Learning