Monte-Carlo-Based Robust Procedure for Dynamic Line Layout Problems

1. Introduction

Most material flow based layout techniques assume that the designer has access to data describing the rate of movement of unit loads in a facility. This data is typically in the form of process routings and forecasted production volumes that can be reformulated as material flow rates between workcenters. Using product and facility data in this form, alternative layouts are evaluated using measures of material handling volume distance, i.e., the total unit load travel distance needed to execute a production schedule. Most line layout methods are aimed at finding the volume distance minimizing assignment of workcenters to locations in a facility for specific production and process data. In many practical situations, product and process information is not known with certainty or may be subject to future changes resulting from model changeovers, seasonal variations, etc. Uncertainty and/or dynamic variation in production data motivates the proactive management of risk in applying line layout algorithms. A designer seeking to avert inflexibility with dynamically changing production data and/or under-performance with stochastic production data is more apt to favor solutions exhibiting robustness as opposed to those which minimize a single measure of expected performance. In this study, volume distance robustness corresponds to meeting minimum acceptable performance standards for most or all operating scenarios. This objective is contrary to the logic of line layout algorithms that focus on the computationally difficult problem of finding the best performing solution for a fixed operating scenario. Achieving robustness requires techniques that can identify reliable measures of solution performance for each operating scenario to efficiently terminate the search for layout alternatives.

This study investigates line layout strategies focused on volume distance robustness. Uncertainty in layout information is represented through discrete probability distributions of material flow rates and workcenter space requirements. Recent research suggesting that Monte Carlo simulation techniques can be applied to map the distribution of volume distance values in the solution space corresponding to deterministic line layout problems is exploited to define stopping criteria for robust procedures. A line layout algorithm is proposed which uses these sampling procedures to first construct a mapping of the volume distance solution space for each parameter set, and then identify layouts meeting minimum performance standards for all potential operating scenarios.

The next section describes uncertainty in the information base associated with line layout problems and describes previous work associated with solving stochastic problems and the empirical mapping of volume distance distributions. The third section describes a robust algorithm for solving the stochastic and/or dynamic line layout problem. In the fourth section, two test problems are introduced and computational experience with the procedure is described. The fifth section extends the study by allowing nonlinear material handling costs. The final section offers a summary and conclusions.

2. Background information

Most layout techniques assume a deterministic, static production environment with many of these methods based on a variation of the quadratic assignment problem (Koopmans and Beckman 1957) which usually, although not always, assumes equal workcenter areas. Numerous linear-integer models for layout problems based on the quadratic assignment problem (QAP) have been proposed including Kaufman and Broeckx (1978), Ritzman et al. (1979), Bazaraa and Sherali (1980), Burkard and Bonninger (1983), and Frieze and Yadegar (1983), Heragu and Kusiak (1991), and others. Given the NP completeness of the QAP (Sahni and Gonzalez 1976), many heuristic methods have also been proposed which have increasingly focused on optimization tools such as simulated annealing, genetic algorithms and tabu search to improve the performance of local search procedures, (see Burkard and Rendl 1984, Wilhelm and Ward 1987, Goldberg 1988). Heragu and Alfa (1992) present a detailed performance comparison of several of these heuristics. Skorin-Kapov (1990, 1994) adapted tabu search to the QAP using the two phase "tabu-navigation procedure". Kelly et al. (1994) developed diversification strategies and applied them to the QAP independently of search procedures such as tabu search, simulated annealing, and genetic algorithms.

The assumption of static production data contrasts with many applications where there is known to be time variation in the parameters driving layout design. Increasingly, researchers are addressing such dynamic variations of the problem. Rosenblatt (1986) presented a dynamic programming strategy for the stochastic layout problem that could be applied in either an optimal or heuristic mode. Lacksonen and Enscore (1993) modified the QAP to prototype the dynamic layout problem to minimize flow costs and rearrangement costs over discrete time periods and compared five alternative solution methods. Conway and Venkataraman (1994) used a genetic search algorithm to solve the constrained dynamic layout problem (CDLP) and found it to be effective in solving the sample problems presented in Rosenblatt (1986). Lacksonen (1994) extended the analysis of dynamic layout problems by developing heuristic procedures for the QAP applicable to problems where workcenters have varying areas.

Other studies have modeled parameter uncertainty that is associated with stochastic variation in product mix, production volume and process routings. Previous studies addressing stochasticity in layout problems include Rosenblatt and Lee (1986) which assumes that demands for individual products are characterized by three alternative levels; low, medium and high. Their method for resolving uncertainty involved the enumeration of all possible demand scenarios and evaluation of layout alternatives for each scenario with respect to expected volume distance and maximum regret criteria. The method then identified robust solutions as those within a given percentage of the optimal for each scenario and both criteria. The study assumed equal workcenter space requirements and feasibility to enumerate all potential layout alternatives for each scenario. Other studies have attempted to address stochasticity by proposing measures of flexibility as a basis for solving the layout problem. Gupta (1986) proposed a simulation strategy for generating material flow rates and then used a CRAFT-like procedure to solve for a layout associated with each scenario. A flexibility measure based on a penalty measure associated with workcenter travel distances, not material flow rates, was used to find a solution. Webster and Tyberghein (1980) proposed a performance measure for individual layouts based on volume distance performance across the set of potential material flow scenarios.

Rosenblatt and Kropp (1992) have presented a formulation of the single period stochastic layout problem. A variation of the formulation presented in that study can be based on the following parameters:

• n : the number of workcenters and workcenter locations, (and load transfer points), in a facility,

• S : the number of potential material flow scenarios that could occur in the application problem,

• m_ijs : the expected volume of material flow between workcenters i and j within material flow scenario s, in unit handling loads per unit time, for i, j = 1,...,n and s = 1,...,S,

• p_s : the probability that material flow scenario s is realized for s = 1,...,S, 0 ≤ p_s≤ 1, p_s > 0.

• d_yz : the travel distance between workcenter locations y and z,

• d(i,j)^k : the travel distance between workcenters i and j associated with layout alternative k for k = 1,...,n!, where d(i,j)^k = d_yz when workcenters i and j are assigned to locations y and z, respectively.

The expected volume distance can then be formulated as:

$$$$

$$\underset{k}{min} v_k = p_s\Sigma \Sigma {\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^n{m}_{ij}d{\left(i,j\right)}^k fork=1,\mathrm{...},n!}}.$$E1

$$$$

In contrast to their use in Rosenblatt and Kropp (1992), the p_s probability terms could also represent the proportion of time that a system operates under scenario s. If layout rearrangement were not feasible, this interpretation of p_s could be applied in the same formulation of v_k for dynamic layout problems. Assuming workcenters of equal area, Rosenblatt and Kropp (1992) computed a weighted average flow matrix and solved the problem as a quadratic assignment problem (QAP). They related the results from this procedure to a flexible facilities design measure proposed by Shore and Tompkins (1980) known as the total expected facility penalty. This measure is based on the regret value of using a layout designed for one scenario under the changing conditions of the other states.

The motivation to focus on a single set of expected parameter values in most of the studies described above is related to the computational difficulty of solving the QAP. Simultaneous consideration of multiple production scenarios requires interpretation of the performance of candidate layout alternatives relative to the set of all possible layout alternatives. In effect, this requires knowledge about the optimal solution, (possibly by solving the QAP), for the parameter sets associated with each production scenario. To address this problem, one study was focused on analyzing the form of the distribution of volume distance values associated with the solution space for 6,400 line layout problems representing a diverse range of material flow parameters (Malmborg and Bukhari 1997). For each of the 6,400 randomly generated line layout problems, the corresponding volume distance distributions were enumerated and analyzed. Fit parameters for volume distance distributions were formulated to represent several well-known distributions including the uniform, gamma, normal and exponential. For every case examined, the fit of the volume distance values to a normal distribution was several orders of magnitude better than any of the other distributions studied. This suggested that the population of n! volume distance values tended toward normality for any set of material flow parameters used in these line layouts. The implication of the findings was that for static line layout problems, designers can usually assume that the corresponding volume distance distribution is normally distributed and its parameters can be estimated through a reasonably low volume of random sampling. In a follow-up study, Bukhari et.al. (1998) analyzed the volume distance distributions for 231,200 line layout problems representing a carefully constructed cross section of material flow and travel distance parameters. Order of magnitude differences observed in fit statistics from that study also supported the extension of the normality result to more general cases of line layout problems.

To assess whether analogous inferences could be made for line layout problems with varying workcenter space requirements, another study investigated the feasibility of mapping the form of volume distance functions associated with more general forms of line layout problems (Malmborg 1999). This investigation considered a range of material flow and space requirements distributions. Using random samples representing between 0.25% and 2.5% of the solution space for problems with n = 8, and 0.014% to 0.28% of the solution space for problems with n = 10, it was shown that reasonably accurate estimates of the form of the volume distance distribution could be generated. Accuracy in this case was measured by the proportion of the true volume distance distribution replicated by the estimated distribution for a given sample size and resolution of the histogram describing the volume distance distribution. Although the results of the latter investigation suggested that volume distance distributions for line layout problems with dynamic distance functions do not generally follow a normal distribution, the ease and accuracy with which the form of the volume distance distribution could be empirically estimated was insensitive to both the distribution of space requirements and material flow parameters.

The significance of the three studies investigating the feasibility of mapping volume distance distributions is that simulation techniques may provide a viable means for generating "context" for the evaluation of line layout solutions. This could provide a basis for quickly identifying "good" quality solutions for line layout problems associated with individual production scenarios and therefore yield a method to support risk averting line layout strategies aimed at finding robust solutions. This possibility is explored in more detail in the following section.

3. A robust line layout procedure

Building on the studies described in the previous section, a robustness based line layout procedure is described below:

Step 1. Identify the production scenarios associated with a problem including; n, S, m_ijs and p_s for i, j = 1,...,n and s = 1,...,S.

Step 2. For each production scenario, select a sample size m, and use simulation to map the form of the corresponding volume distance distribution. Do this by randomly generating m line layouts and computing:

$$$$

$$v_{xs} ={\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^n{m}_{ijs}{d}_x\left(i,j\right) forx=1,\mathrm{...},m}},$$

$$$$

where d_x(i,j) denotes the distance between workcenters i and j in randomly generated line layout x. This step yields the values h_ys for y = 1,...,r and s = 1,...,S where r denotes the number of cells of equal width used to characterize the histogram of all possible volume distance values, and h_ys denotes the proportion of observations in cell y of the estimated volume distance distribution for y = 1,...,r and s = 1,...,S. For each scenario, cell y is characterized by an upper bound UB_ys, and a lower bound LB_ys, which correspond to the maximum and minimum volume distance values defining the range for cell y. Compute the expected volume distance distribution characterized by the objective function:

$$$$

$$v_x = p_s{\displaystyle \sum _{i=1}^n{\displaystyle \sum _{j=1}^n{m}_{ijs}d{\left(i,j\right)}^k fork=1,\mathrm{...},n! and x=1,\mathrm{...},m}}.$$

$$$$

and compute h_y for y = 1,...,r.

Step 3. Define the minimum performance criterion for each scenario, β_s for s = 1,...,S and 0≤ β _s≤ 1, and the minimum overall performance criterion for the expected value, β, 0 ≤β ≤ 1. To satisfy the minimum performance criterion for scenario s, the volume distance value of a candidate solution, v_s, must place it in the lower (1-β_s)×100 percentile of estimated volume distance values for all possible line layouts.

Step 4. Using any appropriate procedure, generate candidate solutions. One example naïve procedure can be the following. First, randomly select one workcenter from n workcenters and assign it to location 1. Second, randomly select one workcenter from the remaining n – 1 workcenters and assign it to location 2. Repeat the above step until only one workcenter remains, which will be assigned to location n. This is a simple unbiased procedure to generate one candidate solution. It can be repeated as many times as needed to obtain more candidate solutions. However, we should note that identical solutions are possible when this procedure is repeated.

For each candidate, compute v_s and c_s where c_s = y if LB_ys≤ v_s < UB_ys and 1 ≤ c_s≤ r for s = 1,...,S. Compute analogous measures for the expected volume distance case, v and c. Terminate the search when a solution satisfies:

$$$$

$${\displaystyle \sum _{y=c_s}^r{h}_{ys}}\ge {\beta }_{ s} fors=1,\mathrm{...},S and {\displaystyle \sum _{y=c}^r{h}_s\ge \beta }.$$

$$$$

The procedure described above defines a robust solution as one where the percentile volume distance value falls within a pre-specified range for each production scenario. It could be applied whether or not the p_s probability values are known. If these values are known, they can be used, along with other considerations, to guide the determination of the β_s aspiration values for s = 1,...,S. The expected value case is equivalent to the weighted flow matrix approach as described in Rosenblatt and Kropp (1992). In that study, it is argued that solving this problem directly tends, in itself, to yield a surprisingly robust solution. This possibility is investigated in further detail in the section below.

4. Applications of the robust line layout procedure

To study the procedure described in the preceding section, variations of two sample problems introduced in Malmborg (1999) are utilized. The paragraphs below illustrate the implementation of the four step procedure for the two sample problems.

4.1. Sample problem 1

Step 1. The first sample problem is based on the uniformly distributed, ten workcenter problem presented in Malmborg (1999). To generate a stochastic variation of this problem, nine additional material flow scenarios were randomly generated using the uniform distribution with n = 10 workcenters. Thus, Problem 1 consists of S = 10 production scenarios where it is assumed that p_s = 1/n = 0.10 for s = 1,...,10. Workcenter areas, (denoted as aⁱ for i = 1,...,n), are generated using the "ABC curve" concept as described in Graves, et.al., (1977). For all sample problems, a total facility area of 1000 square yards and a workcenter space requirements rank ordering of a₁≥ a₂≥...≥ a₁₀ is assumed. For randomly generated Problem 1, a 25%/75% distribution of space requirements holds, i.e., 25% of the workcenters require 75% of the total area in the facility. Thus, a fit parameter of w = 0.2075 results from solving, 0.25^w = 0.75, and space requirements for individual workcenters are given by:

$$a_i=1000\left[ {\left(i/10\right)}^w–{\left(\left(i-1\right)/10\right)}^w \right] for i=1,\mathrm{...},10,\text{ yielding}:$$

$$\left\{a_1,a_2,\mathrm{...},a_{10}\right\}=\left\{620,96, 63, 48, 39, 33, 29, 26, 24, 22\right\}.$$

(To facilitate performance validation of the procedure, each workcenter in the two sample problems is assumed to have a width of exactly one unit with unit load travel originating and terminating at centroids. This assumption reduces the sample problem for each scenario to a line layout with exactly 10! = 3,628,800 decision alternatives where the global optimal solution can be ascertained.)

Step 2. For the first sample problem, a sample size of m = 10,000 representing 0.275% of the size of the solution space for each scenario was selected based on recommendations reported in Malmborg (1999). A total of r = 100 cells were defined for the histogram associated with each scenario. The sampling procedure involved random generation of 10,000 sequences of size 10, i.e., line layouts, and then constructing a corresponding frequency histogram of volume distance values for each scenario. Sampling was done with replacement. A sample size of m = 10,000 provides reasonably accurate estimates of the volume distance histogram as measured by the fit performance measure:

$$

$$F_s ={\displaystyle \sum _{y=1}^{r}min\left\{f_{ys},h_{ys}\right\}},$$

$$$$

where f_ys denotes the proportion of observations in cell y of the actual volume distance distribution for scenario s. The results from using m = 10,000 and r = 100 with sample Problem 1 are:

$$F_1=0.966,F_2=0.966,F_3=0.964,F_4=0.969,F_5=0.963$$

$$F_6=0.972,F_7=0.962,F_8=0.956,F_9=0.960,F_{10}=0.966,$$

with F = 0.964 for the overall expected value of volume distance function. The F_s fit statistics summarized above are normalized for the actual distributions. That is, they represent the proportion of observations in the estimated distribution for each scenario which fall within the correct cells of the actual distributions for that scenario. For the estimated volume distance distributions, cell widths were obtained using (UB_ms – LB_1s)/m with:

$${\text{LB}}_{ys}={\text{ LB}}_{1s}+\left(y-1\right)\left({\text{UB}}_{ms}–{\text{ LB}}_{1s}\right)/mand{\text{UB}}_{ys}={\text{ LB}}_{ys}+\left({\text{UB}}_{ms}–{\text{ LB}}_{1s}\right)/m.$$

For the first sample problem, the values of LB_1s and UB_ms for the estimated and actual volume distance distributions are summarized in Figure 1. The "actual" values of LB_1s in Figure 1 correspond to the volume distance values for the global optimal solutions for the line layout problem associated with each operating scenario.

Step 3. The minimum performance criteria for sample Problem 1 were fixed to be β_s = 0.98 for s = 1,...,10 with β = 0.995.

Step 4. The equivalent of a simple random sampling procedure was used to generate alternative line layouts. This was based on using the same 10,000 random sequences of size 10 used to generate the mapping of the volume distance distributions for each scenario. By programming the procedure to retain solutions meeting the above criteria, 11 line layout solutions were generated. The ranked percentile values (i.e., c values), for these of these 11 solutions are summarized in Figure 2. For all of these solutions, volume distance values associated with individual scenarios are in the lowest percentile of the estimated population of all possible solutions while the expected volume distance value lies within the lowest one half percentile of the estimated population of all possible solutions.

Figure 1.

Comparison of Estimated and Actual Bounds for Each Scenario: Problem 1

Figure 2.

Ranked percentile Values for Problem 1 Solutions Meeting the Volume Distance Criteria

4.2. Sample problem 2

Step 1. The second sample problem was designed to illustrate a situation where both material flow parameters and workcenter area requirements are uncertain. In this ten workcenter problem, a total of twelve operating scenarios are based on the four sets of material flow parameters based on the uniform, normal, exponential and gamma distributions, and the three values of w illustrated below:

$$w=0.75: \left\{a_1,a_2,\mathrm{...},a_{10}\right\}=\left\{178,121,106,98,92,87,84,81,78,76\right\}$$

$$w=0.50: \left\{a_1,a_2,\mathrm{...},a_{10}\right\}=\left\{316,131,101,85,75,67,62,58,54,51\right\}$$

$$w=0.25:\left\{a_1,a_2,\mathrm{...},a_{10}\right\}=\left\{562,106,71,55,46,39,35,31,28,26\right\}$$

The four material flow matrices used in Problem 2 are taken directly from Malmborg (1999). Equal probability scenarios are assumed with p_s = 1/12 = 0.0833 for s = 1,...,12.

Step 2. Once again, a sample size of m = 10,000 representing 0.275% of the size of the solution space for each scenario was selected where r = 100 and sampling was done with replacement. Relative to the accuracy of estimates of the volume distance histogram as measured by the F_s fit performance measure, the results from sample Problem 2 are:

$$F_1=0.962,F_2=0.967,F_3=0.965,F_4=0.966,F_5=0.967,F_6=0.961$$

$$F_7=0.968,F_8=0.936,F_9=0.947,F_{10}=0.967,F_{11}=0.971,F_{12}=0.966,$$

with F = 0.962 for the overall expected value of volume distance function. As with sample Problem 1, the F_s fit statistics summarized above are normalized for the actual distributions. For each of the twelve scenarios associated with sample Problem 2, Figure 3 summarizes the cell boundaries associated with the estimated and actual volume distance distributions. In the figure, "actual" values of LB_1s correspond to the volume distance values for the global optimal solutions for the line layout problem associated with each operating scenario.

Step 3. The minimum performance criteria for sample Problem 2 were fixed to be β_s = 0.99 for s = 1,...,12 with β = 0.998.

Step 4. Once again using a simple random sampling procedure to generate 10,000 alternative line layouts, line layout solutions meeting the minimum performance were identified. A total of nine solutions were found meeting these criteria with their ranked c values summarized in Figure 4.

Figure 3.

Comparison of Estimated and Actual Bounds for Each Scenario: Problem 2

Figure 4.

Ranked Percentile Values for Problem 2 Solutions Meeting the Volume Distance Criteria

Table 1 summarizes how each of the best solutions obtained from the method for Problems 1 and 2 compares to the global optimal solution for each scenario. For all scenarios, the best solution is within 10% of the global optimal solution. Clearly, the significance of these results depends on the extent to which the underlying volume distance distributions have been accurately estimated. However, based on the results in Figures 1 and 3, the empirical estimation of volume distance functions appears to be within reasonable accuracy for most practical problems where secondary criteria normally result in some tradeoffs of volume distance anyway. In addition, the results generally support the assertion of Rosenblatt and Kropp (1992) that solving dynamic line layout problems using the weighted average flow matrix tends to yield robust solutions.

Sample Problem 1:
Global	Best				Percent
Scenario:	Optimal Solution		Discovered Solution		Deviation
1	19012		20573		8.21%
2	18382		19404		5.56%
3	18284		19003		3.93%
4	19429		21060		8.39%
5	17850		19026		6.59%
6	20028		20784		3.77%
7	19869		20347		2.41%
8	20722		22186		7.06%
9	20626		21262		3.08%
10	18901		19752		4.50%
Sample Problem 2:
Global		Best			Percent
Scenario:		Optimal Solution		Discovered Solution	Deviation
1		20276		21498	6.03%
2		25291		27322	8.03%
3		27344		30023	9.80%
4		21103		21483	1.80%
5		27025		27559	1.98%
6		29862		30434	1.92%
7		21065		21335	1.28%
8		26754		27415	2.47%
9		28608		30170	5.46%
10		20901		21529	3.00%
11		26239		27195	3.64%
12		28644		29793	4.01%

Table 1.

Comparison of Global Optimal and Best Observed Volume Distance Objective Functions By Individual Problem Scenarios for Sample Problems 1 and 2.

5. Nonlinear materials handling costs

When materials handling costs are nonlinear, the dynamic line layout problem cannot be reduced to the single QAP described in equation (1). This section assumes that four conventional materials handling devices are used in a facility, (i.e., four non-automated but possibly mechanized types of equipment) [Chan and Malmborg, 2010b]. Adapting a variation of the ergonomics-based device selection criteria similar to that presented in, [Al-Araidah et al., 2006], we use the following volume and distance based rules to drive device selection in the current study and arbitrarily assume the unit movement costs as shown below:

Based on these distance ranges and capacity limits, the version of the dynamic line layout problem addressed in the current study can be summarized as:

$$\begin{array}{l}\underset{\text{k}}{\text{Min}}{\text{ v}}_k={\displaystyle \sum _{\text{s=1}}^{\text{S}}{\displaystyle \sum _{\text{i=1}}^{\text{n}}{\displaystyle \sum _{j=1}^{n}f{(i,j,s)}^k}{p}_s}}\text{, for }k=1,\mathrm{...},n!\text{ where}\\ \\ f{(}^i=\left\{\begin{array}{l}0.18d{(}^i\text{ for }d{(}^i\le 25{\text{ and m}}_{\text{ijs}}\le 4,\\ 0.25d{(}^i\text{ for }d{(}^i\le 25\text{ and 4}\le {\text{m}}_{\text{ijs}}\le 6,\\ 0.25d{(}^i\text{ for 25<}d{(}^i\le 63{\text{ and m}}_{\text{ijs}}\le 6,\\ 0.28d{(}^i\text{ for 25<}d{(}^i\le 63{\text{ and m}}_{\text{ijs}}>6,\\ 0.28d{(}^i\text{ for 63<}d{(}^i\le 125,\\ 0.30d{(}^i\text{ for }d{(}^i>125\end{array}\right\}\end{array}$$E2

Apart from nonlinear materials handling costs precluding the reduction of the line layout problem to a single QAP, variation in work center space requirements limits the use of optimization procedures that exploit a static parameter set describing the distances between the candidate locations in a facility. As described in, [Malmborg, 1999], the n(n – 1)/2 parameters representing distances between pair wise combinations of work center locations in a facility remains fixed in a line layout problem when work centers have equal areas. When work centers have unequal areas, the set of d(i,j)^k parameter values change with each change in the assignment of work centers to locations in a facility. To illustrate, consider a simple line layout with three work centers A, B, C having areas, a₁ = 20, a₂ = 10, a₃ = 30 and arranged along a line with bidirectional travel, work center widths equal to one, and movement between work center centroids. The work center line layout sequences, {A-B-C} and {A-C-B} would respectively yield the distances between work centers given by:

$$\begin{array}{l}Sequence:\left\{A-B-C\right\}\to \left[\begin{array}{l}d{(}^A=0,d{(}^A=15,d{(}^A=35\\ d{(}^B=15,d{(}^B=0,d{(}^B=20\\ d{(}^C=35,d{(}^C=20,d{(}^B=0\end{array}\right]\\ \\ Sequence:\left\{A-C-B\right\}\to \left[\begin{array}{l}d{(}^A=0,d{(}^A=45,d{(}^A=25\\ d{(}^B=45,d{(}^B=0,d{(}^B=20\\ d{(}^C=25,d{(}^C=20,d{(}^B=0\end{array}\right]\end{array}$$

This dynamic shifting in the d(i,j)^k parameter set prevents the use of solution procedures that exploit static distance between location parameters, [Heragu and Kusiak, 1991, Bukhari et al., 1998].

The robust procedure described in Section 3 is used to solve this dynamic line layout problem with nonlinear materials handling costs and unequal work centers areas. The effectiveness of this simple procedure lies in the degree to which small vs. large random samples can identify a significant number of candidate solutions satisfying the candidacy conditions for acceptable values of β. The extent to which small sample sizes can accurately represent the distribution of cost values in a layout problem relative to large samples can be illustrated using a histogram fitting approach described in, [Malmborg, 1999]. To assess the extent to which small samples can be used to accurately estimate the distribution of materials handling cost values, the sample problem summarized in Table 2 is examined where n=9 and S=8. Table 2 presents the eight material flow matrices, scenario probabilities, and work center space requirements for this sample problem. The space requirements for the problem are generated based on an approximate total of 400 unit areas for the facility, i.e., a₁ + a₂ + … + a_n = A = 400. Space requirements for individual areas are generated using the fit parameter, w, 0 ≤ w ≤ 1, where:

$$a_i=A\left[{\left(i/n\right)}^w–{\left(\left(i–1\right)/n\right)}^w\right],\text{ for}i=1,\dots ,n\text{and}w=\mathrm{0.25.}$$

The w fit parameter imposes alternative distributions of space requirements in a facility and can be used to control the disparity between the largest and smallest work centers. For example, to approximate a space distribution where 20% of work centers consume 80% of total space in a facility, the fit parameter is obtained by solving, i^w = 0.2^w = 0.8  w = ln(0.8)/ln(0.2) ≈ 0.139. The above equation is then used to estimate points along the curve resulting in the work center area values shown in the example of Table 2 where a fit parameter of w = 0.25 is used, (application of this definition yields a total of 404 unit areas after rounding off ). The advantage of this representation is that it enables variation in the distribution of space requirements in computational studies using a single parameter.

$$\begin{array}{l}s=1\left[\begin{array}{l}\text{0,5,4,8,1,2,6,2,8}\\ \text{4,0,6,4,7,3,4,5,4}\\ \text{6,7,0,9,1,7,6,4,9}\\ \text{9,2,5,0,9,4,4,6,8}\\ \text{4,7,8,3,0,4,3,5,8}\\ \text{3,5,1,7,9,0,1,5,6}\\ \text{4,3,4,7,2,7,0,6,9}\\ \text{4,6,2,2,1,1,4,0,7}\\ \text{5,3,5,7,6,6,8,4,0}\end{array}\right]s=2\left[\begin{array}{l}\text{0,3,2,3,7,4,8,9,3}\\ \text{4,0,6,2,1,6,4,9,8}\\ \text{6,1,0,9,3,9,4,6,3}\\ \text{1,7,6,0,8,8,8,4,3}\\ \text{7,1,8,8,0,1,8,1,3}\\ \text{2,4,2,9,3,0,7,2,3}\\ \text{4,9,1,3,8,2,0,7,3}\\ \text{6,6,9,7,4,7,3,0,8}\\ \text{1,8,7,4,2,3,7,3,0}\end{array}\right]s=3\left[\begin{array}{l}\text{0,2,4,8,1,6,6,4,4}\\ \text{2,0,2,7,6,6,8,2,4}\\ \text{3,5,0,5,6,6,9,7,4}\\ \text{5,1,8,0,5,6,9,1,5}\\ \text{8,7,5,4,0,1,3,2,3}\\ \text{6,4,2,1,5,0,8,4,7}\\ \text{3,5,5,8,9,4,0,1,3}\\ \text{6,4,9,5,7,5,2,0,5}\\ \text{8,9,3,9,2,5,4,3,0}\end{array}\right]s=4\left[\begin{array}{l}\text{0,4,6,8,1,1,8,7,6}\\ \text{9,0,7,2,2,1,7,6,7}\\ \text{3,1,0,6,9,5,5,9,5}\\ \text{5,3,3,0,4,7,9,1,6}\\ \text{7,7,4,9,0,1,9,2,8}\\ \text{7,7,7,2,2,0,7,2,2}\\ \text{8,5,4,1,4,1,0,4,4}\\ \text{3,9,7,1,3,2,4,0,9}\\ \text{4,4,4,5,7,8,6,8,0}\end{array}\right]\\ \\ s=5\left[\begin{array}{l}\text{0,3,2,7,3,3,5,2,5}\\ \text{2,0,4,4,4,3,7,7,3}\\ \text{2,6,0,6,7,2,6,4,8}\\ \text{7,3,8,0,4,6,7,7,1}\\ \text{3,5,6,4,0,1,6,2,4}\\ \text{5,1,9,2,8,0,6,5,2}\\ \text{8,2,6,9,1,9,0,7,9}\\ \text{7,6,3,8,6,6,3,0,2}\\ \text{6,8,1,4,1,5,8,2,0}\end{array}\right]s=6\left[\begin{array}{l}\text{0,6,4,8,1,9,4,9,5}\\ \text{5,0,4,7,9,8,2,8,6}\\ \text{1,7,0,4,8,4,8,9,6}\\ \text{2,4,2,0,2,9,5,7,2}\\ \text{5,9,5,4,0,6,1,7,2}\\ \text{8,8,9,2,3,0,9,7,5}\\ \text{9,5,7,1,1,1,0,2,5}\\ \text{4,4,2,5,2,3,7,0,9}\\ \text{1,6,3,8,3,2,3,1,0}\end{array}\right]s=7\left[\begin{array}{l}\text{0,9,2,9,2,4,5,6,2}\\ \text{4,0,9,5,2,2,2,7,3}\\ \text{1,3,0,7,5,7,3,8,2}\\ \text{2,2,2,0,8,1,9,5,3}\\ \text{4,4,3,7,0,6,1,4,2}\\ \text{1,6,4,1,6,0,8,3,7}\\ \text{4,1,5,5,7,4,0,3,5}\\ \text{1,7,6,9,6,6,9,0,3}\\ \text{1,3,3,1,6,1,5,3,0}\end{array}\right]s=8\left[\begin{array}{l}\text{0,2,5,6,8,6,3,5,5}\\ \text{7,0,6,9,5,7,2,9,6}\\ \text{5,2,0,8,1,9,3,7,9}\\ \text{4,3,4,0,9,5,1,5,2}\\ \text{9,5,9,1,0,1,2,3,8}\\ \text{6,2,7,6,9,0,5,9,2}\\ \text{3,9,1,6,3,1,0,9,2}\\ \text{1,3,9,2,8,1,6,0,5}\\ \text{7,5,5,9,6,8,1,6,0}\end{array}\right]\\ \text{with}\\ \\ p_1=0.0436,p_2=0.1515,p_3=0.0759,p_4=0.1366,p_5=0.1732,p_6=0.1867,p_7=0.0748,p_8=0.1586\\ a_1=232,a_2=44,a_3=28,a_4=24,a_5=20,a_6=16,a_7=16,a_8=12,a_9=12\\ \end{array}$$

Table 2.

Sample Dynamic Line Layout Problem with n=9, S=8.

Assuming that the nine work centers each have a width of exactly one unit area, work centers are arranged along a line where bidirectional travel is used, and load transfer points correspond to work center centroids, the histograms of the materials handling cost values for the sample problem are obtained for the eight material flow scenarios using a resolution of r = 50 cells. Table 3 presents the b^sj values for s = 1,…, S and j = 1,…, r. A line plot of these values is presented in Figure 5 which clearly illustrates the discontinuous nature of the materials handling cost distribution resulting from the materials handling device selection rule. Using the alternative sample sizes of q=1000, 2500, 5000, 7500 and 10000, 20000, 50000 and 90000, (respectively representing 0.275%, 0.689%, 1.378%, 2.067%, 2.75%, 5.5%, 13.75%, and 24.75% of the sample space for n=9), sequences are randomly generated and the h_sj estimates are obtained. Table 4 presents the F_s values resulting from each of the eight random samples. The results in Table 4 suggest that larger samples do little to improve the fit of estimated cost distributions relative to smaller samples. This finding is consistent with that reported in, [Malmborg, 1999], where a similar phenomenon is observed with volume distance distributions. A similar observation has also been made in other studies [Chan and Malmborg, 2010a, 2011]

Material Flow Scenarios:
12345678
0.0050.0040.0040.0040.0040.0040.0040.004
0.0180.0170.0170.0170.0160.0170.0170.017
0.0180.0190.0200.0190.0190.0190.0190.019
0.0230.0220.0220.0220.0230.0210.0220.023
0.0370.0370.0390.0370.0370.0360.0370.039
0.0450.0450.0460.0460.0460.0450.0450.046
0.0420.0430.0420.0430.0430.0430.0440.043
0.0270.0280.0260.0270.0280.0290.0280.026
0.0070.0080.0060.0070.0070.0080.0070.006
0.0000.0000.0000.0000.0000.0000.0000.000
0.0000.0000.0000.0000.0000.0000.0000.000
0.0000.0000.0000.0000.0000.0000.0000.000
0.0000.0000.0000.0000.0000.0000.0000.000
0.0000.0000.0000.0000.0000.0000.0000.000
0.0000.0000.0000.0000.0000.0000.0000.000
0.0000.0000.0000.0000.0000.0000.0000.000
0.0000.0000.0000.0000.0000.0000.0000.000
0.0040.0040.0040.0040.0040.0050.0030.004
0.0120.0120.0130.0120.0120.0120.0120.012
0.0200.0200.0210.0210.0200.0200.0210.021
0.0240.0240.0250.0240.0240.0240.0240.024
0.0210.0210.0220.0200.0220.0200.0200.021
0.0310.0310.0330.0320.0320.0310.0320.033
0.0410.0410.0430.0420.0420.0410.0410.042
0.0370.0370.0360.0370.0370.0370.0380.037
0.0240.0240.0220.0230.0230.0240.0240.022
0.0080.0070.0060.0060.0060.0070.0070.006
0.0000.0000.0000.0000.0000.0000.0000.000
0.0000.0000.0000.0000.0000.0000.0000.000
0.0000.0000.0000.0000.0000.0000.0000.000
0.0050.0050.0060.0060.0050.0060.0050.006
0.0130.0140.0150.0140.0140.0150.0130.014
0.0230.0230.0240.0240.0240.0240.0230.024
0.0280.0280.0290.0290.0290.0280.0280.029
0.0260.0260.0260.0250.0260.0250.0260.026
0.0320.0330.0340.0340.0340.0340.0330.034
0.0380.0380.0390.0390.0390.0380.0390.038
0.0310.0320.0300.0310.0310.0310.0320.031
0.0260.0250.0250.0250.0250.0260.0250.025
0.0210.0210.0210.0210.0210.0210.0200.021
0.0260.0270.0280.0270.0270.0280.0270.027
0.0340.0360.0370.0360.0360.0360.0350.036
0.0400.0400.0420.0410.0410.0410.0400.042
0.0520.0520.0540.0540.0540.0530.0530.053
0.0520.0520.0500.0510.0510.0510.0520.051
0.0430.0430.0420.0420.0430.0420.0430.042
0.0330.0320.0300.0310.0310.0310.0320.030
0.0190.0170.0160.0160.0160.0160.0170.016
0.0100.0090.0080.0080.0090.0080.0090.008
0.0020.0020.0010.0010.0020.0010.0020.001

Table 3.

Parameter Values, b_sj for s=1,…,S and j=1,…,r for the Nine Work Center Sample Problem with n=9, S=8, r=50.

Figure 5.

Materials Handling Cost Histograms for the Eight Material Flow Scenarios: n=9, S=8, r=50.

	q=1000	q=2500	q=5000	q=7500	q=10K	q=20K	q=50K	q=90K
1	0.839	0.819	0.806	0.808	0.823	0.826	0.826	0.823
2	0.833	0.823	0.809	0.808	0.822	0.825	0.817	0.816
3	0.837	0.821	0.806	0.807	0.820	0.824	0.820	0.818
4	0.834	0.822	0.804	0.805	0.819	0.822	0.814	0.813
5	0.834	0.819	0.802	0.804	0.817	0.820	0.817	0.816
6	0.835	0.816	0.804	0.806	0.819	0.823	0.821	0.814
7	0.835	0.818	0.801	0.803	0.819	0.821	0.817	0.817
8	0.836	0.824	0.810	0.810	0.823	0.826	0.816	0.816
9	0.836	0.824	0.807	0.809	0.823	0.827	0.822	0.822

Table 4.

F_s Values for Various q and s Parameters With r = 50 for the Nine Work Center Problem.

6. Summary and conclusions

A procedure has been proposed for finding robust solutions to dynamic line layout problems. It is based on finding line layout solutions that meet minimum aspiration criteria for each operating scenario associated with a line layout problem. Following the simulation based strategy reported in Malmborg (1999), the procedure is to estimate the form of the volume distance distribution corresponding to each parameter set associated with a line layout problem. These estimates provide context for evaluating the performance of line layout solutions associated with the different operating scenarios that describe a line layout problem. Candidate layouts are then identified which meet minimum performance standards for all possible scenarios. Two sample problems with ten workcenters and one same problem with nonlinear material handling costs were studied which involved variation in material flow parameters and the distribution of space among workcenters. In each case, reasonably accurate estimates of volume distance distributions were obtained using just 10,000 random samples of line layout alternatives. Candidate solutions with expected volume distance values within roughly 5% of the global optimal solution were easily obtained in both cases.

The results from this study suggest a reasonable strategy for dealing with some dynamic line layout problems. Since these problems are generally unmanageable from a computational perspective, solution strategies based on optimization of volume distance for a static parameter set do not generally provide an attractive course of action. More importantly, such an approach may not adequately address the risks associated with inflexibility in the face of dynamically changing production conditions and/or under-performance resulting from stochastic variation in the production environment. Solutions exhibiting robustness provide a more effective alternative for dealing with the variation found in the majority of practical situations. The results from this study strongly suggest that finding such solutions, in many instances, should not prove particularly difficult.

Acknowledgments

The author expresses thanks for thoughtful reviewer comments that have improved this paper.