Home Publications Software Research Teaching Consulting Contact 
Major articles (JCR)Other articlesCitationsExternal bibliometric databases
This is the preprint version of the following article:
 
Grobelny J., Michalski R. (2019). Effects of scatter plot initial solutions on regular grid facility layout algorithms in typical production models. Central European Journal of Operations Research.
 
Cited (JCR): 0, Other Cites: 0
IF:1.260
5yIF:1.179
Pt:20

Abstract

Two simulation experiments were conducted to verify whether the idea of virtual force scatter plot algorithm, used for searching solutions of the facility layout problems, may be used as an input to the classical CRAFT and simulated annealing (SA) algorithms. The proposed approach employs a regular grid for specifying possible locations of objects. Three independent variables were investigated in the first experiment, namely, (1) the size of the problem: 16, 36 and 64 objects, (2) the type of links between objects: grid, line, and loop, and (3) the shape of the possible places in which the objects can be situated: circle, row and square. The patterns of possible location places were also adapted to the analysis of examples taken from literature, included in the second experiment. The gathered data were statistically analyzed. The results shows substantial decrease in goal function means for all of the examined experimental conditions, if the proposed starting solutions are applied to the CRAFT algorithm. The application of the approach to SA is profitable in specific tasks. The presented comparative numerical results show, in which circumstances the proposed method is superior over various genetic algorithms and other hybrid approaches. Overall, the experimental data investigation demonstrates the usefulness of the proposed method and encourages further research in this direction.

Keywords:

production layout, human factors; facility layout problem; initial solutions; scatter plots; simulated annealing; simulation experiments

1. Introduction

Generally, the facility layout problem (FLP) deals with looking for the best arrangement of objects in available places, subject to existing relationships between objects and various constraints. The problem is certainly of major interest for scientists and practitioners from such areas as logistics, production engineering, or ergonomic workplace design. The main purpose of facilities layout optimization in these areas is the costs minimization of their common functioning. In industrial engineering and, particularly, in logistics, one looks for such locations of machinery, equipment and workplaces in the production space, that ensures material handling and employees’ movement costs minimization.

Facilities layout models may be used in many practical human factors and ergonomics studies for optimizing individual workplaces, especially man-machine interactions. An optimal interface allows for minimizing psychophysical cost of an operator functioning in the man-machine system, by providing best possible locations of control and information devices, in relation to themselves and to the human-being. Optimization criteria in this field often cover the number and the quality of necessary body movements, extremities moves as well as human visual system engagement (e.g. the number and duration of fixations and saccades). Concepts and optimization models in these areas are presented, for instance, in the works of Sargent et al. (1997), Holman et al. (2003), Paquet & Lin (2003), Lin & Wu (2010), Jung et al. (2012). In the domain of human resources management, mutual locations of persons in, e.g., an open space office, based on frequency of their necessary contacts, can rationalize company’s processes. Optimization of employees’ work places can also be performed by taking into account informal contacts extracted from the socio-matrix, called the Moreno matrix (Moreno, 1934). Various types of such matrices are described in Klüver and Stoica (2003). Tompkins and White, already in 1984, specified a number of various types of relationships that could be used as inputs to the facilities layout problem. They identified relationships regarding the following areas: facilities, flow, control, process and service, organization and personnel, environment.

Though the facilities layout concept seems to be simple, it has been shown (Sahni and Gonzalez, 1976) that the optimal solution cannot be obtained in polynomial time, which means that the FLP belongs at least to the class of NP-complete problems. As a result, a number of diverse heuristic approaches have been elaborated. They search for acceptable solutions in reasonable time for problems involving many objects. Systematic and comprehensive reviews of developments and advancements in this regard are provided, for instance, by Kusiak and Hergau (1987), Meller and Gau (1996), Singh and Sharma (2006), Drira et al. (2007), or Moslemipour et al. (2012).

1.1. Hybrid approaches and initial solutions

In approaches classified as improvement algorithms, as well as in most metaheuristics, final solutions depend, to a significant extent, on initial conditions. These initial solutions are generated for traditional algorithms, usually, at random. The need for developing heuristics for creating better starting points is rational and was suggested, among others, by Singh and Sharma (2006), and Drira et al. (2007). One of the first proposals in this trend was demonstrated by Ligett (1981). He showed that a combination of the improvement procedure (a variation of the classical pair exchange algorithm), starting from the initial construction solution, provides better results than for a random starting solution. However, the effectiveness of hybrid algorithms depended on the nature of the relationships matrix. The author examined problems widely known in the literature, introduced by Steinberg (1961) and Nugent et al. (1968), which differed considerably in their flow dominance (FD) values (Volmann and Buffa, 1966). This indicator is computed by dividing the standard deviation of the relationships matrix values by their average. It reflects the variability of the relationships level and, thus, shows how strong the results may be influenced by changes in location of objects, strongly or weakly connected with others. The Liggett’s experimental results demonstrated that the quality of the FLP with a low flow dominance indicator increases, if the hybrid approach is applied. When the flow dominance is high, the construction algorithm gives results that can hardly be improved.

A comparison of 12 algorithms made by Kusiak and Heragu (1987), demonstrated the dominance of four hybrid algorithms in solving Nugent’s et al. (1968) test problems having small flow dominance value over construction and improvement type algorithms with random initial solutions. The solution quality criterion in this work was computed by dividing the goal function value by the lower bound, and expressed in percentages. For instance, for the 30 objects’ problem solved by construction and improvement (CRAFT) methods, the quality criterion amounted to 142.5%. The hybrid FLAC (Facility Layout by Analysis of Clusters) approach (Scriabin and Vergin, 1985) allowed for obtaining a much better value of 137.6%.

Apart from hybrid approaches that link various improvement algorithms based on changing pairs with different ways of obtaining initial solutions, there are also hybrid techniques involving the SA metaheuristic (Kikpatrick, 1983). The SA is similar to improvement methods in that, it is based on a gradual enhancement of the goal function but allows for changes to the worse. Thanks to this feature, it may avoid the entrapment in one local minimum. Originally, and in first applications to FLP (Burkard and Rendl, 1984; Wilhelm and Ward, 1987), SA starts from a random initial solution. Heragu and Alfa (1992) proposed a two-stage algorithm in which the initial solution is generated by a modified penalty (MP) algorithm and only then, SA is applied. A combination of MP and SA proved to be successful as it produced many best solutions to FLP benchmarks problems those days. Similar hybrid approach was published by Singh and Sharma (2008). Their SA application was tested on a widely known Nugent’s et al. (1968) FLP, and occurred to be better than many previous ones. Various hybrid approaches including SA are still being developed. Recently, for instance, Leitold et al. (2018) proposed an algorithm integrating SA and dynamic programming for working time line balancing.

Initial solutions’ generation is also subject to examination by some authors of the latest genetic algorithms. For instance, Liu and Sun (2012) used cluster analysis for creating initial chromosomes’ structures in the first generation of solutions. Their experimental research outcomes showed that this approach provides better results than previous genetic algorithms. Another idea of creating initial chromosomes for a classical genetic algorithm, was put forward by Sadrzadeh (2012). In this case, the facilities with stronger relationships are grouped together. The grouping is used in heuristic crossover and mutation operators. The author demonstrated that his proposal generates better results for two FLP examples, solved earlier by algorithms employing random starting solutions. Moreover, the Sadrzadeh (2012) technique yielded the best known solution for the FLP presented in the Kazerooni et al. (1995) work. Lately, the idea of using other than random starting solutions is applied in many other hybrid approaches, e.g., Kierkosz and Luczak (2014), Hiermann, et al. (2015), or Ranjbar et al. (2018).

1.2. Scatter plot concepts

Unlike other concepts, scatter plot approaches allow for unconstrained location of objects on a plane, instead of placing them in predefined places. Thus, the solution is presented in a form of irregular shapes resembling scatter plots. Objects’ adjacencies in this type of algorithm correspond to objects’ relationships. The idea of scattered plots was originally put forward by Drezner in the article published in 1980 and later developed and analyzed in his further works from 1987 and 2010. In Drezner’s deterministic algorithm for finding optimal scatter plots, the final objects’ coordinates are computed by means of eigenvectors of the specifically transformed flow-matrix.

Similar idea was also proposed by Scriabin and Vergin (1985). In their hybrid approach, they used the modified multidimensional scaling method for finding initial solutions. The multidimensional scaling is usually used for conducting cluster analyses of data structures and is based on finding eigenvectors of the matrix containing dissimilarities between items. In the Scriabin and Vergin (1985) approach the dissimilarities’ matrix was constructed based on the objects’ relationships array.

Another algorithm in this trend was presented by Grobelny (1999). In his approach, the scattered plot is generated by mimicking physical processes in which the final state results from two different forces acting on every object, placed initially at the center of a plane. One vector starts from the center of the plane and, in the first step, is directed towards a randomly chosen point on the plane. The second force depends on strengths of connections with other items. The resultant vectors of these two forces specify positions of objects in the next step. The final scatter plot is produced by repeatedly calculating these forces for all objects, and moving them to their new locations. Since one of the components of the movement direction vector is determined at random, every solution is different but in all cases the objects’ mutual relationships are conserved.

2. The goal and contribution of the research

As it was mentioned in the literature review, heuristics often seem to be sensitive both to the input data structure, and starting conditions. Thus, in this paper, we propose the idea of using virtual force algorithm generated scatter plots (Grobelny, 1999) as initial solutions for two regular modular-grid-based facility layout optimization algorithms, namely CRAFT and SA. We additionally, show in which circumstances such an approach is especially useful.

Effectiveness and optimization results quality of this proposal are thoroughly examined for various types of typical models of production and ergonomic systems as well as practical FLP analyzed extensively in the literature. For this purpose, two simulation experiments were designed and conducted:

  • The first experiment involves systematic investigation of classic production and maintenance processes with known optimal goal function values. They include diverse number of objects, structures of the relationships matrix, and layouts of possible locations of objects.
  • In the second experiment, the proposed hybrid approach is applied to various real-life FLPs taken from literature, for which the best known solutions were available. To compare our results with the previous ones we chose only regular-grid-based examples. We analyze the practical problems not only on their original layouts but also in configurations used in the first experiment.

All the data from both simulation experiments are formally, statistically compared with solutions obtained when the initial arrangement is generated randomly. The obtained results show a significant advantage of the proposed hybrid approach over the classical one, where the starting solution is randomly generated. In particular:

  • Applying the scatter plot algorithm with CRAFT provided optimal solutions in most of the conditions examined in the first experiment, and best known results in the second experiment. In all cases solutions obtained by our approach were better than those with random initial layouts.
  • Scatter plots with SA generated better than randomly initialized results for specific relations between input data and the production system structure. The proposed hybrid approach not only systematically provides optimal and/or best results, but also is stable which manifests itself by smaller values of MSDs.

3. Methodology

3.1. CRAFT and Simulated Annealing implementations

3.1.1. CRAFT

In this study, the CRAFT version proposed in the work of Buffa et al. (1964) was employed. Generally, this relatively simple, and well known algorithm is based on either two way or three way exchanges of objects’ locations. The procedure involves examining all possible changes at each step, and identifying the best one in terms of improving the goal function value. Then, the current layout is updated, and in the next step, again, all possible exchanges are considered. The whole procedure is repeated until it is not possible to obtain any improvement of the goal function value. The classical implementation starts from a random distribution of objects, on a regular grid, where the distance between adjacent objects amounts to one. In our implementation, we included pairwise changes of objects’ locations.

3.1.2. Simulated Annealing

The SA algorithm was implemented in accordance with the idea put forward, for the first time, in the seminal paper of Kirkpatrick et al. (1983) that was directly inspired by the article of Metropolis et al. (1953). In general, the procedure is based on imitating the metal particles’ movements during the annealing process. In the algorithm, the movement is simulated by changing places of objects’ locations, and involves either pairs or triplets. The process runs in a changeable temperature (T) which is decreased in every step. If, in a given step, the change in objects’ places improves the solution then it is accepted. However, even if the change does not decrease the goal function value, it can still be accepted with the following probability P:

P(accept unfavorable change) = ,

where ∆ denotes the value by which the goal function would be increased by this specific change of objects places. In other words, the greater the value of ∆, the greater is the probability of this solution being rejected. This is known as the Metropolis acceptance rule (Metropolis et al., 1953), which implies that the smaller the increase of the ∆ value, the more likely the new solution is selected, and the lower the value of T (and greater the number of trials), the less likely the given solution is accepted (Heragu and Alfa, 1992).

The practical SA implementation requires defining the initial temperature (Ti), the epoch length, the cooling (annealing) schedule, and the termination criterion. The review of various approaches to specifying these parameters is presented by Singh and Sharma (2008), and our SA version is based on these experiences.

Kirkpatrick et al. (1983) recommend accepting worse solutions with the probability of about 0.8 in the first step of the SA procedure. To conform to this suggestion, we used the idea of computing the initial temperature Ti based on the assumed probability and the approximated average ∆ value for a given FLP. The value is established by performing N2 (N is the number of all objects) random changes of objects pairs and computing the mean value of ∆’s. A similar approach was also used by Singh and Sharma (2008).

The number of repetitions (objects’ pair changes) in a given temperature (the epoch length) was proportional to the number of objects in a problem y × N (where y is a multiplicative coefficient). Analogous solution was applied in the works of Wilhelm and Ward (1987) or Heragu and Alfa (1992).

The cooling scheme was specified like in the paper of Heragu and Alfa (1992), namely Tj = r × Tj 1, with r = 0.9. The final temperature Tf is computed taking into account the assumed number of steps i according to the formula Tf = 0.9(i - 1)×Ti. Thus, reaching the final temperature which is achieved after performing the specified number of steps, is the stopping criterion.

A number of preliminary runs of the SA algorithm for experimental conditions, where optimal or best solutions are known, allowed for setting the reasonable values for the remaining two parameters. As a result of these observations i was set at 100 while y at 10.

3.2. Initial solution based on scatter plot generation

The idea of the Links algorithm, originally proposed by Grobelny (1999), is based on a simulation of the physical process inspired by the big bang. All objects at the beginning of the simulation are located in the middle of a square piece of a plane. Then, a randomly chosen target point on a plane is assigned to each item. During next steps, every object moves towards a direction which is a sum of the following two vectors of forces:

  • A dispersing force vector acting along straight line from the middle to a given object is proportional to maximal value in the relationships matrix and a current distance to the randomly determined value in the first step of the algorithm. Also, in the first step, a random target point is assigned to each object, and they move towards these targets by a distance equal to 1% of the plane diagonal length.
  • An attracting force vector acting towards other objects being a sum of vectors, directed towards every other object and proportional to relationship values with these objects and distances between them. The situation between a pair of objects resembles the model of ideal spring, where the relationship between these objects corresponds to the string stiffness constant.

The geometric idea of how the procedure works is illustrated in Figure 1, where AB is a vector of the force proportional to the link between A and B from Table 1; AC denotes a vector of the force proportional to the link between A and C; ABC is the sum of vectors AB and AC; AP is a vector of the force proportional to the maximal value of links from Table 1, directed along the straight line, from the plane center (PC) to the object’s center, and proportional to the distance between the object’s center, and the distance value randomly generated in the first step; F denotes the sum of all vectors in a given step which specifies the movement direction in the next step.

Based on an only very simple example with three objects having relationships presented in Table 1, the graphics demonstrates the way of obtaining the resultant force vector for the A object at a given step of the procedure.

Every object has a circular buffer zone specified as a percentage of the plane dimension. This concept allows taking into account approximate objects’ dimensions. If any object enters this zone the attraction force between these objects stops working. The same mechanism is also applied to distances randomly chosen in the first step. The final distribution of objects on the plane is obtained when neither of objects moves or after the specified number of steps.

The obtained solution depends naturally on the relationship matrix. Generally, the algorithm will tend to place objects with strong relationships close to each other. Given big discrepancies between relationship matrices, such as their extremely different flow dominance values, it was necessary to introduce additional two parameters controlling the objects’ movements: (i) the coefficient specifying a single step distance covered by the object when the unit force vector is applied, and (ii) the relative weights of the dispersing and attracting forces used in the procedure: α and 1 – α, where α takes the values between 0 and 1. The latter coefficients have particular meaning for diverse structures of relationships and their values. For instance, when the FD value is small, which indicates big density of connections between objects along with small variability of their relationships levels, the attracting vector is usually directed towards the center of the group. In this situation, to obtain a reasonable scatter plot solution, the dispersing vector should be relatively stronger to counterbalance the mutual objects’ attractions. In the current research, the abovementioned parameters were determined by means of the trial and error technique.

	Table 1. Exemplary links for 3 objects used in Figure 1.
		B	C
	A	10	5
	B	×	5

Figure 1. The geometric illustration of determining the force F influencing the A object movement in a given step.

3.3. Assigning scatter plot results to regular grids

After performing the Links procedure, it is necessary to convert the obtained solution to the regular grid structure characteristic of the CRAFT and SA algorithms. A similar operation was also necessary in the work of Scriabin and Vergin (1987). In this study, two methods were developed to cope with this problem. In the first approach, we simply successively assigned objects to the nearest empty cell in a regular grid which was superimposed on the earlier obtained scatter plot. The second technique is the extension of the first one. The assignment procedure is repeated after rotating the scatter plot solution plane around its center by the specified angle. In this study, the rotation by 5 degrees was applied. Preliminary simulations proved that this value was a good compromise between the speed and obtaining decent goal function values. From among all of the obtained assignments, the one with the best goal function value is finally accepted. The procedures are illustrated in Figures 2–4.

Figure 2. The assignment procedure of the exemplary scatter plot solution to the regular grid.

Figure 3. The assignment order procedure of objects from Figure 2. after the 45 degrees rotation.

Figure 4. The final solution obtained for the 45 degree rotated scattered plane from the example demonstrated in Figure 3.

3.4. Dependent measures

In all experiments, the following objective function was used as a dependent measure:

Goal function (GF) = ,

where Dp(i)p(j) is obtained according to the Minkowski metric formula (cf. Wikipedia, 2019):

Dp(i)p(j) = ,

where k denotes the dimension and r specifies the particular metric. The latter parameter amounts to one in the current research. This metric is also called rectilinear, city block, or Manhattan. The Lij shows the relationship strength between the given pair of objects.

4. Simulation experiments

All the algorithms and simulation experiments were implemented and run in Borland Delphi 2005, version 9.0.

4.1. Experiment 1: Typical models of production layouts

4.1.1. Independent variables

Three factors were manipulated as the independent variables, that is, (1) the objects’ available locations on the plane, (2) the structure of relationships between objects, and (3) the number of objects in the problem. The levels of these effects are specified in the following paragraphs.

Possible objects’ locations on the plane (OL). Theoretically, the number of available locations for objects is infinite. It is, naturally, not feasible to examine all possibilities, therefore, we restricted our study only to the layouts that have their significant practical meaning. In the current experiment, we focused on the structures reflecting typical organizations of material handling systems (Kusiak and Heragu, 1987; Drira et al., 2007). Three geometrical layouts were taken into consideration, that is: (i) a single straight row arrangement (Row, Figure 5) characteristic, for instance, of the partly or fully automated production or assembly lines, Automated Guided Vehicle or a series of activities performed sequentially by a worker on a control panel, (ii) an open field having the rectangular (or square) shape (Square, Figure 6) typical for visual inspections of information panels or gantry robots in logistics and used when the available space is limited, and finally (iii) the circular arrangement, for example, commonly applied to work organized in cells or when material handling is based on logistics trains (Circle, Figure 7).

Figure 5. The single row layout for possible locations of 16 objects.

Figure 6. The square layout for 16 possible object locations

Figure 7. The circular layout for possible location of 16 objects

The relationship type between objects (RO). For each of the defined geometrical layout of possible objects’ locations, the objects’ links were specified in such a way that the optimal arrangements are known. Elaborated relationships’ matrices contained only values of zero and one and reflected either the situation when the adjacency of the two specific objects is required (1) or not (0). Three versions of objects’ relationships included: (i) the line structure (an example including 16 objects is presented in Figure 8) designed for the single row layout, (ii) the grid type of relationships (Figure 9) prepared for the square layout, and (iii) loop shaped links for the circle layout (Figure 10).

Figure 8. Line type links for the 16 objects problem.

Figure 9. Grid type links for the 16 objects problem.

Figure 10. Loop type links for the 16 objects problem.

The problem size (PS). As it was already mentioned the facility layout issues are difficult to solve optimally, so the problems considered in the literature include, usually, a moderate number of objects. There is a group of rather small problems having typically not more than a dozen or so items for which the optimal solution is known. Somewhat bigger practical problems are used as benchmarks for comparing the effectiveness and efficiency of various algorithms – they generally do not exceed 30 elements. Bigger problems are rarely used. Based on this analysis, and taking into account the nature of the possible location of objects specified in the first variable, we decided to investigate three types of problem sizes (PS): the small one including 16 objects, the medium - with 36 items and, finally, the large one involving as many as 64 elements.

4.1.2. Experimental design and procedure

A full experimental design was applied which means that all combinations of the factors’ levels were studied. Given the factors and their levels described above, 27 experimental test problems were produced: Objects layout (3)  Relationships type (3)  Problem size (3) = 27. The designed examples had a medium and high flow dominance value ranging from 2.0 to 5.6.

For each test problem, we examined the effectiveness of classical CRAFT and our implementation of SA algorithms, starting from three different initial solutions. These two algorithms were applied for (i) random initial layouts, (ii) layouts obtained by applying the Links algorithm followed by a simple conversion to regular grid (Links), and (iii) the conversion involving plane rotations (RotLinks). This produced six different simulation routines: Algorithm (2)  Initial solution (3). The simulations were repeated 100 times for each of Test problems (27)  Simulation routines (6) experimental conditions = 162. All goal function values along with the best layout obtained for a given experimental condition were recorded.

The Links algorithm parameters were determined after a series of pilot simulations, and were selected so that the algorithm was able to best reproduce desired layouts for the test problems with known optimal values. Figures 11 and 12 demonstrate layouts including 36 objects having the grid type of relationship obtained after performing the Links algorithm with different values of the attracting and dispersing force parameters. It can easily be observed that the solution from the second figure is more appropriate as it better reflects the grid nature of the connections between items.

For all experimental conditions the square plane was used and the following Links parameters were applied: the virtual force coefficient – 10% of the plane dimension and dispersing/attracting force coefficients – 0.2 and 0.8 respectively. The neutral zone was set at 5% of the plane dimension for all 16 objects examples and also for 36 and 64 objects examples with squared links connections. The value of neutral zone of 3% was found as the appropriate one for the 36 elements example with linear pattern links connections and 64 elements tasks having circular links patterns. For 64 elements tasks having a linear structure of connections, the neutral zone was fixed at 2% of the plane dimension.

Figure 11. Results of Links algorithm for a grid type links between 36 objects for scattering coefficients: 0.5 and 0.5.

Figure 12. Results of Links algorithm for a grid type links between 36 objects for scattering coefficients: 0.2 and 0.8.

4.1.3 Results and discussion

The basic descriptive statistics obtained in this experiment are put together in Table 2. Generally, the analysis of the results shows considerable improvements in average goal function values for the CRAFT algorithm, if the Links or RotLinks solutions, instead of the random one, were used as starting points. The results exhibit a similar pattern in all of the 27 test problems. Almost every time, the best mean result was registered when the RotLinks initial solution was applied. In couple of cases, the difference between outcomes obtained after Links and RotLinks procedures were statistically irrelevant. The relative discrepancies expressed in percentages between mean goal function values registered for different initial solutions are presented in Table 3. In the same table, statistical significances of differences were also provided.

The results of the Simulated Annealing algorithm were, on average, better than those obtained by the CRAFT algorithm. Only for small layouts with 16 items, the mean goal function values obtained by CRAFT with RotLinks initial solutions were not statistically worse than the solutions provided by SA. The influence of the better than random initial solutions on the final results is in most cases weak or none. However, in two cases, namely the combination of the grid type of relationships on a square layout with 36 and 64 objects, the improvement is large.

 
Table 2. Main descriptive statistics for all 27 conditions in Experiment 1.
No.	Condition	Craft	Simulated Annealing
		Rnd 	Links	RotLinks 	Rnd	Links 	RotLinks 
		Min	Max	Mean	MSE	Min	Max	Mean	MSE	Min	Max	Mean	MSE	Min	Max	Mean	MSE	Min	Max	Mean	MSE	Min	Max	Mean	MSE
1.	16	Grid	Circle	44	60	47	0.56	44	58	45	0.24	44	59	44	0.15	44	44	44	0	44	44	44	0	44	44	44	0
2.			Row	60	90	62	0.48	60	66	61	0.14	60	64	60	0.061	60	60	60	0	60	60	60	0	60	60	60	0
3.			Square	*24	45	35	0.43	*24	39	30	0.42	*24	38	25	0.26	*24	32	24	0.13	*24	32	25	0.20	*24	24	24	0
4.		Line	Circle	*15	30	22	0.47	*15	28	19	0.36	*15	22	16	0.14	*15	15	15	0	*15	15	15	0	*15	15	15	0
5.			Row	*15	43	29	0.61	*15	36	22	0.50	*15	24	16	0.18	*15	15	15	0	*15	15	15	0	*15	15	15	0
6.			Square	*15	26	20	0.21	*15	20	17	0.11	*15	18	16	0.090	*15	17	15	0.031	*15	16	15	0.034	*15	16	15	0.031
7.		Loop	Circle	*16	32	25	0.64	*16	18	17	0.10	*16	26	17	0.13	*16	16	16	0	*16	16	16	0	*16	16	16	0
8.			Row	*30	48	34	0.61	*30	44	30	0.14	*30	30	30	0	*30	30	30	0	*30	30	30	0	*30	30	30	0
9.			Square	18	28	22	0.22	*16	20	18	0.062	*16	18	17	0.090	*16	18	16	0.048	*16	18	16	0.020	*16	18	16	0.028
10.	36	Grid	Circle	152	255	195	2.7	152	215	160	1.4	152	226	159	1.8	152	152	152	0	152	196	152	0.44	152	152	152	0
11.			Row	201	355	243	3.6	201	237	216	0.93	200	224	204	0.38	200	206	201	0.17	200	215	202	0.23	200	207	202	0.21
12.			Square	85	132	110	0.92	*60	114	82	1.1	*60	109	63	0.95	*60	97	76	1.1	*60	91	74	1.0	*60	83	62	0.45
13.		Line	Circle	40	132	87	1.5	*35	73	53	1.1	*35	57	39	0.62	*35	53	36	0.38	*35	54	36	0.31	*35	49	36	0.34
14.			Row	57	173	105	2.2	*35	76	54	1.1	*35	65	36	0.39	*35	56	38	0.58	*35	55	37	0.46	*35	43	35	0.10
15.			Square	44	70	55	0.56	*35	48	40	0.31	*35	46	38	0.26	*35	40	37	0.12	*35	40	37	0.13	*35	41	37	0.11
16.		Loop	Circle	*36	130	89	1.6	*36	94	68	1.3	*36	98	67	1.3	*36	72	50	1.7	*36	72	52	1.7	*36	72	48	1.6
17.			Row	*70	166	110	2.1	*70	132	95	1.8	*70	124	83	1.5	*70	70	70	0	*70	70	70	0	*70	70	70	0
18.			Square	46	72	59	0.51	40	52	46	0.28	40	52	45	0.25	*36	42	38	0.14	*36	44	38	0.17	*36	42	38	0.15
19.	64	Grid	Circle	380	675	538	6.3	362	591	429	5.5	364	544	384	3.2	360	369	360	0.10	360	452	361	0.93	360	362	360	0.044
20.			Row	496	967	682	11	489	693	524	2.6	483	543	493	0.70	472	490	476	0.45	472	491	476	0.44	472	489	475	0.41
21.			Square	183	273	239	1.9	112	223	162	2.0	112	217	122	2.2	112	186	156	1.5	112	181	155	1.2	112	169	135	1.4
22.		Line	Circle	156	335	235	3.8	*63	174	111	2.6	*63	132	85	1.9	*63	126	93	2.0	*63	128	96	1.7	*63	118	87	1.6
23.			Row	201	416	280	4.6	*63	178	104	2.5	*63	105	69	0.88	*63	155	102	2.2	*63	144	96	2.1	*63	113	75	1.5
24.			Square	96	136	117	0.88	*63	93	77	0.68	*63	87	74	0.49	64	77	69	0.27	64	78	69	0.24	65	77	69	0.26
25.		Loop	Circle	176	340	245	3.5	74	218	142	2.3	92	172	128	1.6	*64	152	97	3.2	*64	160	100	3.0	*64	138	101	3.1
26.			Row	168	428	297	5.2	*126	226	137	2.5	*126	218	130	1.5	*126	126	126	0	*126	126	126	0	*126	126	126	0
27.			Square	102	146	121	0.94	*64	94	74	0.71	*64	90	74	0.54	66	78	71	0.21	66	80	71	0.28	66	80	71	0.25
* Known optimal value 
 
Table 3. Relative differences between different initial solutions for CRAFT and SA algorithms applied to all test problems in Experiment 1.
No.	Condition	Craft	Simulated Annealing
		Links/
Rnd (%)	RotLinks/
Rnd (%)	RotLinks/
Links (%)	Links/
Rnd (%)	RotLinks/
Rnd (%)	RotLinks/
Links (%)
1.	16	Grid	Circle	5.2*	5.9*	0.81	0	0	0
2.			Row	2.8*	3.7*	0.89**	0	0	0
3.			Square	15*	30*	17*	-1.6	1.1	2.6
4.		Line	Circle	14*	29*	17*	0	0	0
5.			Row	22*	44*	28*	0	0	0
6.			Square	15*	18*	4.3*	-0.33	-0.20	0.13
7.		Loop	Circle	32*	32*	0.95	0	0	0
8.			Row	10*	11*	0.46	0	0	0
9.			Square	18*	24*	7.4*	0.62	0.50	-0.12
10.	36	Grid	Circle	18*	19*	0.87	-0.29	0	0.29
11.			Row	11*	16*	5.6*	-0.089	-0.27	-0.18
12.			Square	25*	42*	23*	2.6	18*	16*
13.		Line	Circle	39*	55*	26*	1.1	-0.14	-1.3
14.			Row	49*	66*	33*	3.4	7.4**	4.1
15.			Square	27*	32*	6.1*	0.082	-0.027	-0.11
16.		Loop	Circle	24*	24*	1.0	-3.9	4.1	7.7
17.			Row	13*	25*	13*	0	0	0
18.			Square	22*	24*	3.2*	-0.31	-0.47	-0.16
19.	64	Grid	Circle	20*	29*	10*	-0.31	0.028	0.34
20.			Row	23*	28*	5.9*	-0.011	0.14	0.15
21.			Square	32*	49*	24*	0.28	13*	13*
22.		Line	Circle	53*	64*	23*	-3.3	6.4**	9.4*
23.			Row	63*	75*	34*	6.7**	26*	21*
24.			Square	34*	36*	3.5*	-0.029	0.19	0.22
25.		Loop	Circle	42*	48*	10*	-3.4	-4.2	-0.76
26.			Row	54*	56*	5.6*	0	0	0
27.			Square	39*	39*	0.65	0.028	-0.17	-0.20
* 	Fischer’s LSD, α = 0.05
** 	Fischer’s LSD, α = 0.1

For 64 objects and the combination of the line type relationship and row type layout, the influence of initial solution is statistically significant.

Moreover, for the grid on the square test problem with 64 objects, the mean results obtained by CRAFT followed by RotLink are statistically significantly better than the average goal function values in SA for any type of initial solutions. The observed outcomes show that the effectiveness of examined initial solutions is limited when the SA is concerned and depends very much on the test problem structure. The best obtained solutions for each of examined test FLPs in Experiment 1 are provided in Supplementary material A.

4.2. Experiment 2: Comparative analysis with examples from literature

4.2.1. Experimental design and procedure

In the first experiment we systematically examined various types of FLPs with a single value connections. Although we referred to layouts of practical significance, it seemed it would be interesting to investigate how CRAFT and our implementation of SA along with different types of initial solutions perform when applied to real life problems. Therefore, in the second experiment we focused on practical examples widely analyzed in the literature and frequently used as benchmarks. In the second experiment’s conditions we used original numbers of objects along with their relationships structures. Apart from possible locations used in studies reported in earlier papers, we also investigated additional layouts to obtain a variety of test problems similar to those examined in the first experiment. We chose four problems having various flow dominance values ranging from 1.1 to 4.2.

The first example was taken from the work of Chan and Tansri (1994) with the flow dominance value of 1.9. The optimal solution for this problem involving 9 elements on the square 3×3 grid is known. We also analyzed this case on the row and circle layouts. The second problem deals with placing 24 machines on the 5×6 rectangular grid and has the flow dominance value of 4.2, which is the biggest used in the current experiment. The data for this example was taken from Kazerooni et al. (1995). Just like in the previous case, apart from the original possible positions, we also examined row and circle layouts. The third problem was originally analyzed in the work of El-Baz (2004) and entailed arranging 12 objects on the production line. The value of flow dominance amounted to 1.7. We also examined rectangular and circular layouts. As a fourth example, we decided to use the biggest problem investigated by Nugent et al. (1968) including 30 items, arranged in the form of a rectangular 5×6 grid. Problems analyzed in this work have generally small values of the flow dominance coefficient and are often examined in works focused on determining how this parameter influences the solutions from various algorithms (e.g. Kusiak and Heragu, 1987). The selected problem has the flow dominance value equal 1.1, which is the lowest among all examined examples in the second experiment. All of the selected examples were also previously solved by means of genetic algorithms, thus it was interesting to make comparisons between the classical algorithms enhanced with heuristically determined initial solutions, with the outcomes of the latest proposals based on genetic approaches. The problems initially examined by Nugent et al. (1968), were also studied by means of multiple different classical approaches, thus, historical data were also available.

The experimental procedure was identical as the one used in the first experiment, that is, the CRAFT algorithm and SA approach were applied to a random initial layout, the layout obtained by applying Links, and finally to the initial solution provided by Links with a rotation procedure. The simulation was repeated 100 times for each of the test examples. Goal function values and the best layouts were recorded. Like in the first experiment, also in this case the Links and RotLinks approaches required specifying parameters regarding the virtual force and the relationship between the dispersing and contracting forces. The heuristic rule applied here was meant to obtain as stable scatter plots as possible after not more than 200 steps with objects that do not superimpose. After conducting preliminary test experiments we set the virtual force value at 5% of the plane width for all the experiment 2 conditions. The dispersing force weight amounted to 0.2 for examples 1-3 – as a result, the weight attributed to the contracting force amounted to 0.8. For the Nugent et al. (1968) problem with 30 objects, the dispersing force weight was set at 0.8, thus the contracting force weight equaled 0.2.

4.2.2 Results and discussion

Main descriptive statistics for all 12 conditions in Experiment 2 are given in Table 4. The results qualitatively replicate the results from the first experiment showing significant improvements in the mean goal function values for CRAFT when the Links or RotLinks initial solutions were applied. In all cases, this algorithm performed better if the initial solution was provided by the scatter plot algorithm than if the random starting solution was used. Only for some cases, the differences between Links and Rotlinks mapping were statistically irrelevant.

 
Table 4. Main descriptive statistics for all 12 conditions in Experiment 2.
No.	Condition	Craft	Simulated Annealing
		Rnd 	Links	RotLinks 	Rnd	Links 	RotLinks 
		Min	Max	Mean	MSE	Min	Max	Mean	MSE	Min	Max	Mean	MSE	Min	Max	Mean	MSE	Min	Max	Mean	MSE	Min	Max	Mean	MSE
1.	Chan
Tansri (1994)	Rectangle	4818	5564	4938	14	4818	5160	4922	11	4818	5158	4917	12	4818	4818	4818	0	4818	4818	4818	0	4818	4818	4818	0
2.		Circle	5736	5955	5789	6.0	5736	5955	5777	4.7	5736	5955	5771	4.3	5736	5736	5736	0	5736	5736	5736	0	5736	5736	5736	0
3.		Row	6308	7793	6640	36	6308	7793	6520	30	6308	7053	6385	11	6308	6308	6308	0	6308	6308	6308	0	6308	6308	6308	0
4.	Kazerooni et al. (1995)	Rectangle	11972	15982	13969	72	12172	15355	13434	61	12102	14782	13182	48	11572	13252	12343	32	11402	13092	12267	30	11572	13102	12359	32
5.		Circle	16092	25830	19475	208	15602	22907	18115	156	15562	22067	17632	145	15562	17607	16078	50	15562	18502	16087	53	15562	17292	16051	46
6.		Row	17582	28720	22073	266	16872	26516	19978	231	16822	23977	18482	137	16802	20272	17558	62	16802	21062	17551	66	16802	19712	17536	49
7.	El-Baz (2004)	Rectangle	8040	9095	8528	23	8040	9025	8500	20	8040	8890	8445	19	8040	8380	8094	8.6	8040	8375	8097	9.7	8040	8345	8105	8.5
8.		Circle	10765	11705	10896	17	10765	11065	10848	9.0	10765	11065	10854	8.7	10765	10765	10765	0.0	10765	10765	10765	0	10765	10765	10765	0
9.		Row	11055	14730	11820	93	11055	14835	11617	91	11055	12550	11258	27	11055	11205	11066	3.5	11055	11205	11062	2.6	11055	11205	11065	3.2
10.	Nugent et al. 30 (1968)	Rectangle	3103	3321	3191	4.5	3087	3250	3162	4.0	3086	3264	3161	3.7	3062	3148	3095	1.8	3062	3136	3091	1.7	3062	3137	3093	1.5
11.		Circle	6607	7029	6765	9.3	6603	6871	6706	7.0	6606	6961	6688	6.8	6602	6722	6611	1.6	6602	6749	6611	1.5	6602	6626	6609	0.57
12.		Row	8258	8901	8468	15	8247	8889	8389	12	8247	8520	8347	8.0	8247	8410	8265	3.8	8247	8391	8270	3.6	8247	8391	8268	3.5
*Best results
 
Table 5. Relative differences between different initial solutions for CRAFT and SA algorithms applied to all real life problems and their variations in Experiment 2.
No.	Condition	Craft	Simulated Annealing
		Links/
Rnd (%)	RotLinks/
Rnd (%)	RotLinks/
Links (%)	Links/
Rnd (%)	RotLinks/
Rnd (%)	RotLinks/
Links (%)
1.	Chan 
and 
Tansri (1994)	Square	0.31	0.41	0.10	0	0	0
2.		Circle	0.19	0.31*	0.11	0	0	0
3.		Row	1.8*	3.8*	2.1*	0	0	0
4.	Kazerooni et al (1995)	Square	3.8*	5.6*	1.9*	0.62	-0.13	-0.75
5.		Circle	7.0*	9.5*	2.7*	-0.056	0.17	0.22
6.		Row	9.5*	16*	7.5*	0.040	0.13	0.085
7.	El-Baz (2004)	Square	0.33	1.0*	0.65*	-0.040	-0.14	-0.10
8.		Circle	0.44*	0.39*	-0.056	0	0	0
9.		Row	1.7*	4.8*	3.1	0.040	0.0090	-0.031
10.	Nugent et al. 30 (1968) 	Square	0.92*	0.92*	0.0057	0.13	0.086	-0.041
11.		Circle	0.87*	1.1*	0.27*	-0.0017	0.029	0.031
12.		Row	0.93*	1.4*	0.51*	-0.070	-0.040	0.030
							*  Fischer’s LSD  α = 0.05 	**  Fischer’s LSD α = 0.1
 
Table 6. Comparisons of the obtained in this study average and best results with the outcomes of previous investigations dealing with the same real life examples.
No.	Sample problem 
(best result / 
no of items / 
flow dominance)	Best known solutions obtained by means of GA or hybrid algorithms and their sources	Best reported average result 
and its source	This study results from Experiment 2
(Best / Mean in 100 simulations)
				Craft with RotLinks initial solutions	SimAnn with Links or RotLinks initial solutions
(1)	Chan and Tansri (1994)
[4818 / 9 / 1.9]		4818:	Chan and Tansri (1994), Mak et al. (1998), El-Baz (2004) – GA		4822:	El-Baz (2004) – after 10 runs of GA with best parameters		4818	/	4990		4818	/	4818
(2)	Kazeroni et al. (1996)
[11662 / 24 / 4.2]		11662:	Sadrzadeh (2012) – GA
	11862:	El-Baz (2004) – GA
	12890:	Mak et al. (1998) – GA		11676:	Sadrzadeh (2012) – after 30 runs of GA		11672	/	13263		11402	/	12267
(3)	El-Baz (2004)
[11 440 /12/ 1.7]		11440	not reported		11055	/	11443		11055	/	11062
(4)	Nugent et al. 30 (1968)
[3062 / 30 / 1.1]		3064:	Singh and Sharma (2008) – hybrid SA
	3841:	Shayan and Chittilappilly (2007) – GA
	3079:	Scriabin and Vergin (1985) – hybrid algorithm FLAC
	3062:	Picone and Wilhelm (1984) – improved Hillier procedure*
	3148:	Nugent et al. (1968) – CRAFT
	3093:	Nugent et al. (1968) – biased sampling
		3109:	Picone and Wilhelm (1984) – after 6 runs of their improved Hillier procedure		3074	/	3175		3062	/	3091
* Sometimes Nugent’s samples results are reported as doubled. So, this result can be reported as equal 6124

The results obtained by our implementation of SA are somewhat surprising. In all experimental conditions, the results obtained by SA are on average markedly better than CRAFT outcomes with or without the scatter plot prompt, and they do not depend on types of applied initial solutions. The detailed relative improvements in the mean goal function values depending on the starting arrangements obtained randomly and by means of scatter plots are put together in Table 5.

The obtained data for the four classical and based on a regular grid data were contrasted with the results reported in previous research. Naturally, we compared only the original arrangements of possible objects’ locations, since results regarding layouts examined additionally in the present experiment were not analyzed before. Table 6. includes the best and average goal function values from Experiment 2 and previous studies. One may easily observed that mean GF values are comparable but our best results are always either better or equal to the best solutions provided in the literature. The best obtained arrangements for all problems examined in Experiment 2 are presented in figures included in Supplementary material B.

Particular attention should be paid to the advantage of applied in this study approaches over solutions obtained by various versions of genetic algorithms. Only in the case of Kazerooni et al. (1995), the genetic algorithm from the work of Sadrzadeh (2012) gives better mean results than the average values from our investigation, but the best result from 100 runs of the Links + SA procedure is the best solution of all known and amounts to 11402. Moreover, both Rotlinks + CRAFT, and SA with and without prompts provide better solutions for the El-Baz (2004) example than those reported previously. SA gives even better average results than the best GA implementation. The FLP with 30 items described in the work of Nugent (1968) was subject to examination in numerous studies. The proposed in this paper implementation of the SA approach allowed for obtaining the best known solution both with random and scatter plot initial solutions, and the best mean solutions available in earlier research.

5. General discussion and conclusions

In general, the demonstrated experimental results confirm the effectiveness of the presented approach and the implementation of the SA procedure. Though, we examined a limited number of possible locations on a regular grid of relatively moderate complexity, our test problems and real life examples deal with typical situations occurring in logistics. The use of unitary relationships between objects has also its practical relevance, as they may be applicable in situations where the knowledge about the process structure is not very precise. In such a case, the expert knowledge about the relationships may be modeled using ones for denoting the necessary adjacency of objects and zeros, if such an adjacency is not required.

The use of scatter plots for generating initial solutions seem to be especially profitable in combination with CRAFT since, in every case, the average results are better as compared to the random starting arrangements. On the other hand, our implementation of SA does not benefit much from the better than random initial solutions. Notwithstanding, in most cases the mean goal function values obtained with scatter plots are also slightly better than those with random initial solutions but the difference is statistically insignificant.

Very good results obtained for literature examples in the second experiment, suggest that from the practical point of view, one should make about 100 simulations for a given problem. Though the mean values are not always satisfactory, we were able to produce the best known results in each of the examined examples. Such an outcome might probably be possible because of the quality of the generated scatter plot initial solution as well as the random component which is included in the Links procedure. Every time the second algorithm starts with a relatively good solution and, what is important, the initial solution is different each time.

Our implementation of SA provided the best results almost in each of examined problems. The application of scatter plots as initial solutions, apart from some exceptions, had a small effect on the final SA results. This probably results from the general idea included in this algorithm, where the random component allows from jumping out of the local minimum. The concept of the SA presented in the current study is closely related to the proposal of hybrid Modified SA algorithm presented by Singh and Sharma (2008). This research approach with random initial solution allowed for obtaining the same, or in one case even better (Nugent 30), results than those reported by Singh and Sharma (2008). Because our implementation similarly like in the cited work is based on dynamic and automatic determination of the starting temperature and the cooling scheme, it would be interesting to directly compare these versions of SA without the initial solutions. Unfortunately, Singh and Sharma (2008) reported only the results regarding the initial solution generated according to their procedure and final results after applying their implementation of the SA. Because the authors did not show how their version of SA works with random initial solution it is not clear whether or not the initial solutions had any significant effect on the final results. What is more, one may speculate that, given our outcomes, it is quite possible that their initial solutions did not considerably affect the results.

We have not explicitly analyzed the robustness of the proposed approach in terms of its tolerance or resistance to changes in the environment or errors in tasks parameters (e.g., in relationship matrix). However, one of the aspects of robustness is the computational stability of an algorithm (cf. Kuchta, 2011). Tables 2 and 4 include MSE values, which can be treated as a possible measure of such a stability. Given this interpretation, the application of scatter plot initial solutions, in general, increased the robustness of SA, as the MSD values for most experimental conditions were lower in relation to MSDs for random starting layouts.

Although in the presented experiments the efficiency of the applied algorithms, in terms of the time needed to find final solutions, were not precisely analyzed, we have noted the approximate times for the most challenging conditions. For the problems involving 30 and 64 items, a considerable difference was observed between CRAFT and our implementation of SA. The latter case occurred to be more time consuming. Admittedly CRAFT computation complexity confined its practical application to problems with 40 or less objects in the late 1980s (Kusiak and Heragu, 1987), but in our experiments 100 runs for the 64 items problems with random initial solutions lasted less than 40 minutes (2400 s), on an average personal computer with 4MB RAM and Intel Core Duo CPU P7350 2 GHz. When the sequence of RotLinks + CRAFT or Links + CRAFT is applied the time needed decreases to less than 20 minutes (1200 s).

Examples including 30 objects with a random initial arrangement were completed usually after about two minutes and, if scatter plots were used for creating initial solutions, the time necessary for obtaining the final result did not exceed 60 seconds. The huge decrease in completion times along with a considerable improvement in mean goal function values may have a big significance while applying the CRAFT algorithm in practice especially to very large FLPs.

The proposed SA implementation occurred to be decidedly more demanding. Given the parameters used in our experiments and the automatic procedures used for determining initial temperature and the cooling scheme, times for the biggest 64 items problems amounted to about 120 minutes (7200 s). However, from the practical point of view even such times are acceptable in real process designs, all the more that times for 36 objects were much shorter and the procedure was finished in less than 60 minutes (3600 s) The overall time for the SA was not affected by the applied type of initial solutions.

The obtained results, particularly the improvements in the CRAFT algorithm, encourage further investigations of various algorithms in conjunction with the proposed ways of generating starting arrangements.

The examined here, meta-heuristic SA approach provides benefits only in three of our test problems. This, in turn, suggests that SA might be susceptible to various initial solutions for very specific data structures and possible location layouts. In this study, the improvements were observed solely for grid relationships arranged on a square layout involving either 36 or 64 objects, and linear relationships on a row layout for 64 objects. This outcome shows another interesting area of further research which may be focus on identifying such FLP properties that would provide the answer when generating initial solutions for SA helps to obtain better final results. One should also remember that our data shows that the application of scatter plot starting arrangements increase the probability of receiving best solutions, though the average results are not much affected and the completion time is not considerably longer.

In the conducted experiments, the flow dominance level was not strictly controlled, however we put an effort to select real-life examples with diverse values of this parameter ranging from 1.1 to 4.2. A cursory analysis of the results from Table 5. , which shows the percentage decrease of the mean goal function values after applying various types of initial solutions followed by CRAFT partially, confirm the conviction of better effectiveness of improvement type algorithms for problems having small FD values. For instance, in the Nugent et al. (1968) for 30 objects example (FD = 1.1), all improvements obtained by applying scatter plot initial solutions, though statistically significant, are moderate and not bigger than 1.4%. On the other hand, in the case of (Kazerooni et al., 1995) where FD was much bigger (4.2), the improvement level is as big as 22%. Such a relationship was not observed for the SA results. Future research may, thus, be directed to a systematic search for relationships between various parameters characterizing links’ matrix and the effectiveness and efficiency of various heuristics and meta-heuristics.

Our concept of using scatter plots for providing initial solutions to CRAFT and SA might also be applied to other approaches. The verification whether such a hybrid procedure with Links and RotLinks is effective in genetically based algorithms could be especially interesting in prospective studies. Recently, the hybrid proposal in this area was presented by Sadrzadeh (2012). The author elaborated a heuristic based on a table containing flows and costs in descending order for creating starting population of chromosomes. The results provided by Sadrzadeh (2012) are the best found by procedures based on genetic algorithms. Furthermore, the promising results of using scatter based initial arrangements for CRAFT encourage to continue research involving other classical approaches, for example, those described in the review paper of Kusiak and Heragu (1987).

Simulation experiments and performed comparisons could be broaden by including more types of FLPs. However, the specificity of our research involving initial solution generation, regular modular grid, and typical production systems layouts, significantly restrict available approaches that are appropriate for comparison purposes.

The production organization optimization has usually such ergonomic consequences as decreasing accidents threats, reducing biological costs related with material handling, or necessity of contacting with other persons. Though there are numerous potential applications of facilities layout in companies on diverse levels, unfortunately there is little empirical research that analyzes algorithms and their combinations in typical manufacturing and logistic problems. Our research extends the body of knowledge in this regard. From a managerial perspective, the results show that for typical manufacturing or maintenance processes and conventional models of facilities arrangements, the proposed hybrid algorithms, usually, provide optimal solutions. The obtained outcomes also allow us to assume that an efficient and cheap algorithm (CRAFT) supplemented with the scatter-plot-based initial solution generator is as good in the analyzed experimental conditions as computationally complex genetic algorithms.

It should be stressed that this study outcomes are interesting not only for manufacturing, logistics, or production organization context at the factory level, but also reflect problems existing in the human-factors field. A good example here is the human-machine or human-computer interface design where the logic of a single operator task may be modeled as a sequence of activities, parallel activities or individual target movements like switching on or off, performed with a given probability.

One of the reasons that possibly restrict applying sophisticated algorithms developed in the facilities layout domain to typical human factors problems may lie in the lack of knowledge of their very wide potential scope of usage. Possibly another reason that existing mathematical methods are not commonly applied in the human factor field, is the complexity of this type of theoretical problems. Apart from practical and theoretical contribution, the present study may also increase the awareness of human factors and ergonomics experts and researchers of possible applications of formal facilities layout models and extend the knowledge about various methods and approaches in this field.

References

Buffa, E.S., Armour, G.C., & Vollmann, T.E. (1964). Allocating Facilities with CRAFT. Harvard Business Review, 42(2), 136–158.

Burkard, R.E., & Rendl, F. (1984). A Thermodynamically Motivated Simulation Procedure for Combinatorial Optimization Problems. European Journal of Operational Research, 17(2), 169–174. doi:10.1016/0377-2217(84)90231-5

Burkard, R.E., Karisch, S.E., & Rendl, F. (1997). QAPLIB – A Quadratic Assignment Problem Library. Journal of Global Optimization, 10(4), 391–403. doi:10.1023/A:1008293323270. Updated online version available at: http://anjos.mgi.polymtl.ca/qaplib/ (accessed on 03.04.2019)

Chan, K.C., & Tansri, H. (1994). A Study of Genetic Crossover Operations on the Facilities Layout Problem. Computers & Industrial Engineering, 26(3), 537–550. doi:10.1016/0360-8352(94)90049-3

Drezner, Z. (1980). DISCON: A New Method for the Layout Problem. Operations Research, 28(6), 1375–1384. doi:10.1287/opre.28.6.1375

Drezner, Z. (1987). A Heuristic Procedure for the Layout of a Large Number of Facilities. Management Science, 33(7), 907–915. doi:10.1287/mnsc.33.7.907

Drezner, Z. (2010). On the Unboundedness of Facility Layout Problems. Mathematical Methods of Operations Research, 72(2), 205-216. doi: 10.1007/s00186-010-0317-2

Drira, A., Pierreval, H., & Hajri-Gabouj, S. (2007). Facility Layout Problems: A survey. Annual Reviews in Control, 31(2), 255–267. doi:10.1016/j.arcontrol.2007.04.001

El-Baz, M.A. (2004). A Genetic Algorithm for Facility Layout Problems of Different Manufacturing Environments. Computers & Industrial Engineering, 47(2–3), 233–246. doi:10.1016/j.cie.2004.07.001

Grobelny, J. (1999). Some Remarks on Scatter Plots Generation Procedures for Facility Layout. International Journal of Production Research, 37(5), 1119–1135. doi:10.1080/002075499191436

Heragu, S.S., & Alfa, A.S. (1992). Experimental Analysis of Simulated Annealing Based Algorithms for the Layout Problem. European Journal of Operational Research, 57(2), 190–202. doi:10.1016/0377-2217(92)90042-8

Hiermann, G., Prandtstetter, M., Rendl, A., Puchinger, J., & Raidl, G. R. (2015). Metaheuristics for Solving a Multimodal Home-Healthcare Scheduling Problem. Central European Journal of Operations Research, 23(1), 89–113. https://doi.org/10.1007/s10100-013-0305-8

Holman, G.T., Carnahan, B.J., & Bulfin, R.L. (2003). Using Linear Programming to Optimize Control Panel Design from an Ergonomics Perspective. Proceedings of the Human Factors and Ergonomics Society Annual Meeting, 47(10), 1317–1321. doi:10.1177/154193120304701047

Jung, K., Kim, J., You, T., Lee, B., Lee, W., Park, S., & You, H. (2012). A Characteristic Analysis of Ergonomic Console Layout Studies Using Optimization Techniques. Journal of the Ergonomics Society of Korea, 31(6), 733–740.

Kazerooni, M., Luonge, L., & Abhary, K. (1995). Cell Formation Using Genetic Algorithms. International Journal of Flexible Automation and Integrated Manufacturing, 3(3–4), 283–299.

Kierkosz, I., & Luczak, M. (2014). A Hybrid Evolutionary Algorithm for the Two-Dimensional Packing Problem. Central European Journal of Operations Research, 22(4), 729–753. https://doi.org/10.1007/s10100-013-0300-0

Kirkpatrick, S., Gelatt, C.D., & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671–680. doi:10.1126/science.220.4598.671

Klüver, J., & Stoica, C. (2003). Simulations of Group Dynamics with Different Models. Journal of Artificial Societies and Social Simulation, 6(4), http://jasss.soc.surrey.ac.uk/6/4/8.html

Kuchta, D. (2011). A Concept of a Robust Solution of a Multicriterial Linear Programming Problem. Central European Journal of Operations Research, 19(4), 605–613. https://doi.org/10.1007/s10100-010-0150-y

Kusiak, A., & Heragu, S.S. (1987). The Facility Layout Problem. European Journal of Operational Research, 29(3), 229–251. doi:10.1016/0377-2217(87)90238-4

Leitold, D., Vathy-Fogarassy, A., & Abonyi, J. (2018). Empirical Working Time Distribution-Based Line Balancing with Integrated Simulated Annealing and Dynamic Programming. Central European Journal of Operations Research. https://doi.org/10.1007/s10100-018-0570-7

Liggett, R.S. (1981). The Quadratic Assignment Problem: An Experimental Evaluation of Solution Strategies. Management Science, 27(4), 442–458. doi:10.1287/mnsc.27.4.442

Lin, C.-J., & Wu, C. (2010). Improved Link Analysis Method for User Interface Design – Modified Link Table and Optimisation-based Algorithm. Behaviour & Information Technology, 29(2), 199–216. doi:10.1080/01449290903233892

Liu, X., & Sun, X. (2012). A Multi-improved Genetic Algorithm for Facility Layout Optimisation Based on Slicing Tree. International Journal of Production Research, 50(18), 5173–5180. doi:10.1080/00207543.2011.654011

Mak, K.L., Wong, Y.S., & Chan, F.T.S. (1998). A Genetic Algorithm for Facility Layout Problems. Computer Integrated Manufacturing Systems, 11(1–2), 113–127. doi:10.1016/S0951-5240(98)00018-4

Meller, R.D., & Gau, K.-Y. (1996). The Facility Layout Problem: Recent and Emerging Trends and Perspectives. Journal of Manufacturing Systems, 15(5), 351–366. doi:10.1016/0278-6125(96)84198-7

Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of State Calculations by Fast Computing Machines. The Journal of Chemical Physics, 21(6), 1087–1092. https://doi.org/10.1063/1.1699114

Moreno, J.L. (1934): Who Shall Survive. Nervous and Mental Disease Monograph 58. Washington DC

Moslemipour, G., Lee, T.S., & Rilling, D. (2012). A Review of Intelligent Approaches for Designing Dynamic and Robust Layouts in Flexible Manufacturing Systems. The International Journal of Advanced Manufacturing Technology, 60(1-4), 11–27. doi:10.1007/s00170-011-3614-x

Nugent, C.E., Vollmann, T.E., & Ruml, J. (1968). An Experimental Comparison of Techniques for the Assignment of Facilities to Locations. Operations Research, 16(1), 150–173. doi:10.1287/opre.16.1.150

Paquet, V., & Lin, L. (2003). An Integrated Methodology for Manufacturing Systems Design Using Manual and Computer Simulation. Human Factors and Ergonomics in Manufacturing & Service Industries, 13(1), 19–40. doi:10.1002/hfm.10026

Picone, C.J., & Wilhelm, W.E. (1984). A Perturbation Scheme to Improve Hillier’s Solution to the Facilities Layout Problem. Management Science, 30(10), 1238–1249. doi:10.1287/mnsc.30.10.1238

Ranjbar, K., Khaloozadeh, H., & Heydari, A. (2018). A Novel Mixed Spider’s Web Initial Solution and Data Envelopment Analysis for Solving Multi-Objective Optimization Problems. Central European Journal of Operations Research. https://doi.org/10.1007/s10100-018-0566-3

Sadrzadeh, A. (2012). A Genetic Algorithm with the Heuristic Procedure to Solve The Multi-Line Layout Problem. Computers & Industrial Engineering, 62(4), 1055–1064. doi:10.1016/j.cie.2011.12.033

Sahni, S., & Gonzalez, T. (1976). P-Complete Approximation Problems. J. ACM, 23(3), 555–565. doi:10.1145/321958.321975

Sargent, T.A., Kay, M.G., & Sargent, R.G. (1997). A Methodology for Optimally Designing Console Panels for Use by a Single Operator. Human Factors: The Journal of the Human Factors and Ergonomics Society, 39(3), 389–409. doi:10.1518/001872097778827052

Scriabin, M., & Vergin, R.C. (1985). A Cluster-Analytic Approach to Facility Layout. Management Science, 31(1), 33–49. doi:10.1287/mnsc.31.1.33

Shayan, E., & Chittilappilly, A. (2004). Genetic Algorithm for Facilities Layout Problems Based on Slicing Tree Structure. International Journal of Production Research, 42(19), 4055–4067. doi:10.1080/00207540410001716471

Singh, S.P., & Sharma, R.R.K. (2006). A Review of Different Approaches To The Facility Layout Problems. The International Journal of Advanced Manufacturing Technology, 30(5-6), 425–433. doi:10.1007/s00170-005-0087-9

Singh, S.P., & Sharma, R.R.K. (2008). Two-level Modified Simulated Annealing Based Approach for Solving Facility Layout Problem. International Journal of Production Research, 46(13), 3563–3582. doi:10.1080/00207540601178557

Steinberg, L. (1961). The Backboard Wiring Problem: A Placement Algorithm. SIAM Review, 3(1), 37–50. doi:10.1137/1003003

Tompkins, J.A., & White, J.A. (1984). Facilities Planning, John Wiley & Sons.

Vollmann, T.E., & Buffa, E.S. (1966). The Facilities Layout Problem in Perspective. Management Science, 12(10), B–450. doi:10.1287/mnsc.12.10.B450

Wikipedia (2019). Minkowski distance. https://en.wikipedia.org/wiki/Minkowski_distance. (accessed on 04.04.2019).

Wilhelm, M.R., & Ward, T.L. (1987). Solving Quadratic Assignment Problems by ‘Simulated Annealing’. IIE Transactions, 19(1), 107–119. doi:10.1080/07408178708975376  

© 2012-2024 Jerzy Grobelny, RafalMichalski.com All rights reserved.Last modified on: 2019-07-19HTML 4.0! standard CSS standard!