Grobelny J., Michalski R. (2017). A novel version of simulated annealing based on linguistic patterns for solving facility layout problems. Knowledge-based Systems, 124, 55-69.   Cited (JCR): 0, Other Cites: 0 IF:8.8 5yIF: Pt:200
Abstract
The paper presents a novel version of the simulated annealing algorithm based on linguistic patterns (LP) and fuzzy theory approach. The article describes shortly the linguistic patterns and shows on a simple illustrative example the idea of using the Łukasiewicz formula as a criterion for the facility layout optimization. Next, the detailed description of our LP version of simulated annealing is presented. The influence of the proposed algorithm parameters on the effectiveness of our approach is then examined in a simulation experiment involving four different types of facility layout problems. The outcomes from the first experiments are used for optimally setting the parameters of our proposal in the second simulation study focused on verifying its effectiveness for objects with uniform and variable sizes. The obtained results show that the presented procedure, apart from producing decent results in terms of the classic goal function and the linguistic pattern criterion, provided solutions that were qualitatively different than those generated by a crisp version.
Keywords:
facility layout problem, linguistic patterns, fuzzy sets, simulated annealing, optimization
1. Introduction
The facility layout problem (FLP) is commonly related with arranging various types of objects in possible locations taking into account their connections. Sometimes, additional restrictions regarding either objects’ dimensions or their target places are also involved in the optimization process. Researchers and practitioners come across these types of problems in diverse situations. In such areas as industrial engineering or logistics, the main goal is to minimize transport costs that are considered to account from 20 up to 50% of all production operating expenses (Tompkins and White, 1984). According to the same authors, one can decrease these material handling expenses by as much as 10 to 30% by improving facility layouts. In studies regarding man-machine system designs, the optimization is focused on minimizing psycho-physical costs of human work. Efficiency criteria in this regard may involve a number of performed body parts movements, distance covered by a person, visual work intensity measured by means of fixations and saccades, etc. (e.g., Sargent et al., 1997).
Generally, the optimization task may be formulated in such a way:
Minimize: (1)
where Lij is the relationship strength between two objects and Dp(i)p(j) is the distance between item location places p(i)p(j).
Despite the simplicity of the problem description, finding the best solution is not a trivial task. Sahni and Gonzalez (1976) proved that the FLP is an NP-hard problem and, thus, it is impossible to obtain an optimal layout in polynomial time. As a consequence, a great number of various sub-optimal methods have been developed through years. In practice, these techniques provide satisfactory solutions in acceptable time. Various mathematical formulations of this problem are surveyed by Loiola et al. (2007). Extensive reviews of different methods of finding solutions were presented in numerous works, for example, Kusiak and Heragu (1987), Liggett (2000), Drira et al. (2007) or lately Kundu and Dan (2012) and Moslemipour et al. (2012).
Many approaches to solving FLP may be generally divided into two classes: constructive and improvement-based. In the former group, consecutive objects are inserted into the layout one by one (e.g., ALDEP proposed by Seehof et al., 1966 or CORELAP created by Parsaei and Galbiati, 1987) whereas in the latter case, the initial arrangement of all items is repeatedly improved by exchanging their locations (e.g., CRAFT). Hybrid methods involve both techniques. It was initially proved by Liggett (1981) that using results from constructive algorithms as an initial layout for an improvement procedure yields better results than starting from a random layout. For more discussion in this regard see Liggett (2000). Metaheuristics constitute another category of hybrid optimization methods. Many proposals in this respect appeared in the last three decades. Among them there are: tabu search (Taillard, 1991; Skorin-Kapov, 1994), simulated annealing (Heragu and Alfa, 1992; Jajodia et al., 1992; Matai, 2015; Palubeckis, 2015), particle swarm approach (Önüt et al., 2008; Ohmori et al., 2010; Samarghandi et al., 2010), artificial immune system algorithms (Kumar et al., 2008; Haktanirlar Ulutas and Kulturel-Konak, 2012), genetic algorithms (Sadrzadeh, 2012; Aiello et al. 2012, 2013; Gonçalves & Resende, 2015; Lim et al., 2017; Paes et al., 2017; Palomo-Romero et al., 2017), or ant colony optimizations (Komarudin and Wong, 2010; Guan & Lin, 2016).
The described above FLP classes of models have a quantitative nature which can be regarded as an advantage from the computational point of view. However, preparing a good model of a real FLP in such a perspective is not easy. The difficulties arise, generally, from two reasons: the necessity of including qualitative parameters and imprecision of quantitative data. These problems inclined researchers to seek solutions that use experts’ knowledge in different stages of making decisions about objects’ locations. One of the first approaches in this spirit was the proposal of Muther (1961) in which the inter-relations are determined by experts who subjectively assess the importance of objects’ closeness. The importance and benefits of the collaboration between quantitative algorithms and experts’ feedback were shown, for instance, by Babbar-Sebens & Minsker (2012) in their interactive genetic algorithm. Recently, a different approach of applying expert’s knowledge and preferences while solving facility layout problems was proposed by García-Hernández et al. (2013). They put forward a specific version of the genetic algorithm, in which the designer was repetitively involved in subjectively assessing representative solutions derived by clustering from a given population. This interactive technique was further extended in the work of García-Hernández et al. (2015a) where a multi-objective version of their genetic algorithm was put forward. Improvements of the original idea from the paper García-Hernández et al. (2013) were also presented in the study of García-Hernández et al. (2015b). The authors additionally included two niching techniques into the approach to prevent presenting similar solutions in the same iteration of their interactive genetic algorithm. A work of Zhao et al. (2014) can also be included in this research direction. The particle swarm optimization-based immune algorithm proposed in this paper allows for including in the initial population possible solutions (individuals) supplied by an expert. However, in this case, the expert’s knowledge and experience are not used in further steps of the procedure.
Models of FLP for inexact data, intensively developed in recent decades, often involve fuzzy sets theory components. Evans et al. (1987), for instance, developed a fuzzy heuristic of constructive nature based only on qualitative data. The procedure aimed at determining the order of departments while the placement was conducted manually. Dweiri and Meier (1996), in turn, used the fuzzy decision-making system to produce activity relationship charts that were later applied to develop layouts of departments in a plant. Cheng et al. (1995) proposed a genetic algorithm where the material flow was represented by trapezoidal fuzzy members. Another version of a genetic algorithm involving fuzzy logic was developed by Karray et al. (2000) to deal with temporary facilities on a construction site. The work of Aiello and Enea (2001) focuses on solving facility layout problems in the uncertainty of the market demand condition which was modeled by triangular fuzzy numbers. They took into account departments’ production capacities. A comprehensive, fuzzy based, decision support system was proposed by Deb and Bhattacharyya (2005). In their multi-factor fuzzy system, they included material flow, as well as supervision, information, and environmental links. Bashiri & Hosseininezhad (2008) examined the optimal location of new facilities with respect to a set of existing ones by mixing the fuzzy analytic hierarchy process approach with fuzzy linear programming.
Some studies proposed hybrid approaches combining both qualitative data and linguistic components provided by experts: e.g., Sangwan (2010) solved three plant layout problems by means of his multi-criteria approach, Mohamadghasemi & Hadi-Vencheh (2012) integrated fuzzy judgments and nonlinear programming to assess facility layout structures, and recently Altuntas et al. (2014) applied their proposal to solve a real problem in a machinery industry company. Another multi-criteria approach including a mix of various techniques for solving problems with non-crisp, operational, qualitative, and dependent indicators was proposed by Azadeh et al. (2016). They combined fuzzy simulations and fuzzy data envelopment analysis with Fuzzy Analytic Hierarchy Process which was used to take advantage of expert’s knowledge of imprecise data.
A specific application of the multi-valued logic in conjunction with fuzzy sets components was proposed in the works of Grobelny (1987a, 1987b, 1988). The framework called Linguistic pattern method (LP) allows utilizing logical expressions as criteria in solving facility layout problems. Imprecise data can be formulated as expressions similar to a natural language. Raoot and Rakshit (1991, 1993) developed multiple criteria constructive algorithm based on subjective experts’ opinions by taking advantage of this framework. Recently, in the work of Grobelny (2016), it was shown how to apply the concept of linguistic patterns to determining the objects’ hierarchy based on a linguistic assessment of pairwise comparisons.
This work presents a novel implementation of the simulated annealing involving the idea of linguistic patterns. The new algorithm is applied to solve facility layout problems on regular grids where objects may be modeled by a single cell or a group of cells. As far as we are aware none of the previous studies used linguistic patterns representing either experts’ subjective knowledge or imprecise data as a goal function in the simulated annealing algorithm. In experiments involving real-life and artificial examples, we show that our method yields not only logical, reasonable, and satisfactory solutions but also provides results that are comparable with layouts produced by a classic procedure for crisp and exact input.
Next sections explain the concept of linguistic patterns on some simple examples and describe in detail our simulated annealing modification. Further, we show the results of simulation experiments regarding the proposed approach. The goal of the first set of experiments was meant to identify parameters’ values that maximize the effectiveness of the algorithm. The obtained outcomes are then used in the follow-up, set of experiments that examine how our proposal performs in various problem types involving approximate experts’ assessments of objects’ relationships. These investigations include objects both with uniform and variable sizes. The results of our LP approach are directly compared with an analogous crisp version of the simulated annealing procedure. The discussion is specifically focused on the conceptual differences between these two versions.
2. Linguistic pattern as a criterion in facility layout problems
There are many sources of imprecision in facility layout problems. From one hand side, while searching for an optimal layout in practical tasks it is necessary to use qualitative criteria or variables that are difficult to measure. For instance, Garcia et al. (2013) included into this category: the preferred location, a division of free space or environmental conditions. In turn, Altuntas et al. (2014) mention: personnel, equipment, and information flow or supervision. On the other hand, during the layout design, sometimes even quantitative data can be determined only approximately. They may be specified according to the knowledge, intuition, and experience of experts. It applies, for example, to degrees of relationships between objects being placed. Muther (1961) proposed a RelCharts technique that addresses this issue. In this approach, experts assess the necessity of locating objects next to each other on a scale based on six linguistic expressions. For some facility layout criteria, the assessment of a physical variable may be flexible which means that a specific value may have a different meaning for various criteria. For instance, a given distance between two objects has a different meaning for transport costs and for the supervision process quality. In contrast to the role of an expert in Garcia et al. (2013, 2015a, 2015b), the LP approach is generally directed to the use of expert’s knowledge for modeling imprecise criteria and data before performing the optimization algorithms.
Generally, the linguistic pattern can be specified as a logical phrase including linguistic variables. The characteristic feature of these variables is that one can assign verbal values to them like in a natural language. The adjective logical implies that it is possible to assess the truth or a degree of truth for a given sentence like in the expression IF A THEN B. In the domain of facility layout problems, the basic optimization task defined in (1) can also be formulated by natural language expressions. For instance, one may say that in a good arrangement, for any pair of objects, the following relation is true: if the positive relationship between items is strong, then they are located close to each other. By putting this rule in a more formal form we get the following linguistic pattern:
IF Link_between_objects(i, j) is STRONG THEN Distance_between_objects(i, j) is SMALL (2)
Since formula (2) presents an implication, we can evaluate the level of its truth. For example, if strongly connected items are placed distant from each other, the whole sentence is false.
In the current paper, Truth_of(l) and Truth_of(r) refer to truth values of left and right sides of linguistic pattern (2), that is Link_between_objects(i, j) is STRONG and Distance_between_objects(i, j) is SMALL, respectively. The most general approach to determining the left and right-hand side truths was proposed by Zadeh (1978a, 1978b). He introduced the consistency term specified as a relative truth level for the expression “E is A” with respect to “E is B.” where expressions are represented by fuzzy numbers or sets. Such a definition of consistency can be computed as a possibility value according to the following formula:
CONSISTENCY(E is B, E is A) = POSSIBILITY(E is B | E is A) = maximumx(minimum(B(x), A(x)) (3)
where X is the universe of discourse, B(x) and A(x) are the membership functions of B and A, respectively, and | denotes with respect to. Thus, for the left side of pattern (2), we may write the following.
Truth_of(l) = POSSIBILITY (Link_between_objects(a, b) is STRONG | Link_between_objects(a, b) is A) (4)
Truth_of(l) = maximumx(minimum(STRONG(x), A(x)) (5)
The right side of pattern (2) can be expressed analogically. A graphical illustration of obtaining the consistency value for A = MEDIUM is given in Fig. 1.
Fig. 1. Graphical illustration of exemplary definitions of linguistic variables and the calculation of Truth_of(l) according to equation (5).
As it was shown in a series of works published by Grobelny (1987a, 1987b, 1988, and 2016), one can assess the truth of pattern (2) by means of the Łukasiewicz formula which takes the following form:
Truth_of(pattern (2)) = minimum{1, 1 - Truth_of(l) + Truth_of(r)} (6)
It seems that, in practical applications, the easiest way of obtaining truth assessments for expressions on the right side of formula (6) is to directly ask experts. The quality of the given layout configuration may be then measured by computing values from formula (6) for all pairs of objects and calculating their arithmetic average. This is treated as a goal function in our version of simulated annealing.
Maximize pattern mean truth: (∑_(i=1)^(n-1)▒∑_(j=i+1)^n▒(〖Truth_of(2)〗_(i,j) ) )/((n^2-n)/2) (7)
Since for a specific arrangement it is often unfeasible to obtain the full mean truth which is equal one, it is a good idea to relate the current solution mean truth to the maximum possible truth for a given facility layout problem. Grobelny (1987b) provided a theorem showing how such an upper bound should be determined.
The following, very simple, illustrative example shows how to use pattern (2) as an optimization criterion in facility layouts where relationships are approximated and distances between objects have linear meaning. Let us assume that there are three machines arranged in a row. It is also known how many transport operations between these machines need to take place during a specific period (e.g., one hour). Exemplary data along with two possible layout solutions are provided in Fig. 2.
L U V W
U × 9 6
V × 1
W ×
Layout 1: U W V
Layout 2: W V U
Fig. 2. An exemplary, simple facility layout problem where relationships between objects are based on the number of transport operations between each pair of facilities in the sequence ij or ji, and two possible layouts on a modular grid (1×3).
An expert directly assessed truth values of the linguistic expression STRONG depending on the number of possible transport operations as well as the expression SMALL for the distance which, in this specific layout context, is defined as the number of machines between the given pair. The data are illustrated in Figs. 3 and 4 respectively.
Fig. 3. The pattern STRONG for a degree of relationships (e.g., number of transport operations) between two objects in a form of fuzzy set singletons that were intuitively defined by directly assigning the truth values.
Fig. 4. The pattern SMALL for a distance between machines in a form of fuzzy set singletons that were defined by directly assigning the truth values.
Given the problem data specified in Fig. 2 and linguistic pattern definitions shown in Figs. 3 and 4, we can compute truth values for all pairs of objects in both layouts using Łukasiewicz formula (6). Assuming unitary distances between adjacent machines we get:
U W V
Layout 1: W V U
Layout 2:
Truth_of {U, V} minimum{1, 1 – 1 + .5} = .5 minimum{1, 1 – 1 + 1} = 1
Truth_of {U, W} minimum{1, 1 – .6 + 1} = 1 minimum{1, 1 – .6 + .5} = .9
Truth_of {V, W} minimum{1, 1 – .2 + 1} = 1 minimum{1, 1 – .2 + 1} = 1
The average truth for Layout 1 amounts to 2.5/3 = .83 while for Layout 2: 2.9/3 = .97, thus, the second arrangement fulfills the pattern (2) better than the first configuration which means that Layout 2 is better in terms of the mean truth value from equation (7).
The linguistic pattern methodology allows also for taking into account most of the earlier mentioned cases in modeling facility layout tasks. It results from the fact that usually imprecise and indistinct criteria may be described by logical sentences. Furthermore, the majority of variables used in these criteria can be represented by degrees of intensity expressed linguistically. One may approximate physical values as well as use diverse meanings of linguistic expressions in various design contexts by applying fuzzy sets for these expressions. Therefore, it is possible to apply optimization based on the greatest mean truth value of specified criteria defined by linguistic patterns. Analyzing, for instance, the qualitative criteria postulated by Altuntas et al. (2014), it is easy to notice that they may be depicted by implication expressions (IF A THEN B). If one assumed that information flow relates to the intensity of necessary personal contacts between machines’ operators i and j, then the layout quality pattern could be described as follows:
IF Degree_of_contacts(between operators of objecti and objectj) is HIGH
THEN (objecti and objectj are located NEAR)
In turn, if the environmental condition criterion denotes inconvenience or danger resulting from the adjacency of objects i and j, then a possible pattern may take the following form:
IF Degree_of_hazard(adjacency of objecti and objectj) is HIGH
THEN (objecti and objectj are NOT ADJACENT)
To compute truth values according to formula (6), it is necessary to define appropriate patterns for left and right sides of implications as well as values of levels for variables: Degree_of_contacts(between operators of objecti and objectj) and Degree_of_hazard(objecti and objectj adjacency), respectively, for all ij objects’ pairs. The same applies to expressions NEAR and NOT_ADJACIENT.
Undoubtedly, all the mentioned parameters are of an imprecise nature and their definitions can be provided by experts. It is clear that models obtained in such a way would include components of subjective knowledge and experience of the decision maker. This, in turn, may have an impact on the precision and representation of linguistic pattern items. Figs. 5 and 6 show possible definitions of patterns for left sides of described linguistic expressions while Figs. 7 and 8 present examples for their right side counterparts. From one hand side, they show the flexibility of defining the model in linguistic pattern categories and, on the other, present how to take advantage of the more or less precise experts’ knowledge.
Fig. 5. An exemplary truth value definition of HIGH Degree_of_hazard(y) (or Number_of_contacts(y)) in a form of fuzzy set singletons defined by directly assigning truth values.
Fig. 6. An exemplary truth value definition of HIGH Degree_of_hazard(y) (or Number_of_contacts(y)) in a form of a continuous fuzzy set function specified by experts.
Fig. 7. Exemplary truth value definitions of NEAR and NOT_ADJACENT objects’ locations in a form of fuzzy set singletons defined by directly assigning truth values.
Fig. 8. Exemplary truth value definitions of NEAR and NOT_ADJACENT in a form of a continuous fuzzy set function specified by experts.
3. Linguistic pattern based simulated annealing
The classic simulated annealing initially proposed by Kirkpatrick et al. (1983) is inspired by the way, the metal particles behave during the annealing process. This movement is simulated by changing items’ locations. Generally, the change in objects’ locations takes place if it improves the goal function value. However, the algorithm allows also for making an unfavorable change with a given probability (P).
P(accept unfavorable change) = , (8)
In practice, apart from defining this probability, other parameters need to be specified, that is, the initial temperature (Ti), epoch length, cooling schedule, and termination criterion.
A number of recommendations concerned with setting these values are comprehensively reviewed by Singh and Sharma (2008). We have taken advantage of these suggestions while implementing our approach. Kirkpatrick et al. (1983) proposed to set the probability of accepting worse solutions at approximately .8 while starting the procedure, which should help in avoiding getting stuck in local optima. In our algorithm, before the simulated annealing procedure begins, first, N2 (N is the number of all objects) random changes of objects pairs are made and the mean value of ∆s is computed. Based on this and any predefined probability value, we calculate the initial temperature Ti individually for a specific facility layout problem. A comparable procedure was also applied by Singh and Sharma (2008). In the current implementation the Epoch Length, which specifies the number of objects’ location changes in each temperature, can be set either arbitrarily or as a multiplier of the number of objects in the current problem (k × N). The latter solution was used in Wilhelm and Ward (1987) or Heragu and Alfa (1992). Regarding the cooling scheme, we applied the formula used by Heragu and Alfa (1992), that is: Tj = r × Tj 1, where r is usually set at .9 and can be freely specified in our application. The final temperature is obtained after i steps (usually 100) according to the following formula: Tf = .9(i - 1)×Ti.
As compared to the conventional simulated annealing algorithm, our main extension is the possibility of entering data and calculating the objective function according to the idea of linguistic patterns (Grobelny 1987a, 1987b, 1988, 2016) described in the previous section. More specifically, one can define appropriate linguistic variables in fuzzy set terms as it was illustrated in examples from section 2. Our implementation of the LP based simulated annealing algorithm allowed for conducting experiments focused on properties of the proposed approach in various contexts and definitions of the facility layout tasks.
Drira (2007) proposed a sophisticated system for FLP classification based on three groups of factors, namely the workshop characteristics, problem formulation, and the approach to finding the solution. The workshop characteristics usually include production and transport systems (Kusiak and Heragu, 1987). The problem definition involves objects and design data representations while the solution approach is specified by various types of optimization algorithms.
In the developed application, a discrete representation of objects placed on the modular grid was assumed. Thus, the constraints of our approach concern objects’ locations, their sizes, and available space modeled as a regular and rectangular grid with fixed dimensions H(No of Cells × W(No of Cells), where grid height (H) and width (W) are expressed as a number of cells. Naturally, the number of available cells in a grid must be equal or bigger than the sum of cells representing objects (O) or objects’ components. This is mathematically expressed by formula (9). Additionally, objects should not overlap.
∑_(i=1)^n▒〖O_(i(No of Cells))≤H_((No of Cells)) × W_((No of Cells)) 〗 (9)
This type of representation is the most suitable for modeling cellular layouts with an open field transportation system. An optimization of the mutual arrangement of cells having identical dimensions is the simplest case that can be analyzed under such assumptions. Jajodia et al. (1992) showed that it is possible to consider layouts consisting of objects with various sizes by appropriately defining cells’ relationships. In our proposed application, such a functionality can also be achieved by constructing complex objects from elementary cells. The software calculates both Manhattan and Euclidean distances. They correspond to a basic transport system that is, conveyors or Automatically Guided Vehicle (AGV) and gantry robots in the latter case (Kusiak and Heragu, 1987). The computer program also enables modeling other transportation systems by means of inserting artificial objects and blocking their positions. The quality criterion in the proposed algorithm has the form of implication (IF A THEN B).
Data in the relationship matrix can have either the form of physical quantities or linguistic expressions whereas left and right side pattern definitions are constructed by means of providing trapezoidal membership functions. Fig. 9 shows a part of the user interface where exemplary membership functions for the left and right side of pattern (2) are specified linearly, that is, for the expressions Link_between_objects(i, j) is STRONG and Distance_between_objects(i, j) is SMALL respectively.
Fig. 9. Defining fuzzy number shapes used for computing the fuzzy goal function values.
The mean truth value of the pattern (2), calculated for all pairs of linked objects, constitutes the criterion (formula (7)) being analyzed at every step of the proposed simulated annealing procedure.
Using the simulated annealing algorithm for analyzing problems where objects have unequal sizes requires special numerical solutions. Jajodia et al. (1992) suggested that object building blocks should be connected with each other with artificial links of the magnitude being 1.5 - 2 times bigger than the maximum link value from the initial matrix. Such a solution should keep objects’ components together while applying the algorithm.
We propose a slightly different approach in our application. We treat one of the building blocks of a given object (facility) as the input/output point. Relationships between these components reflect the transportation system inside this object. Such a model allows for analyzing patterns’ truths both for relationships between objects and inside them. Examples are given in Figs. 10 and 11.
Fig. 10. A possible way of relating two objects consisting of 5 and 4 building blocks (grid cells) with links expressing the truth value of the pattern (2) left side for the open field type of transportation model.
Fig. 11. A possible way of relating two objects consisting of 5 and 4 building blocks (grid cells) with links expressing the truth value of the pattern (2) left side for the loop type of transportation model.
The prepared software provides truth values for both types of transportation systems. It is also possible to perform a local optimization of layouts inside objects both in the classic simulated annealing and in its version based on linguistic expressions. Objects represented by a number of smaller items may disintegrate during the optimization process. Therefore, an additional algorithm is being used to check their integrity. The software registers the best solutions from a series of automatically repeated simulations along with measures of objects’ disintegration degrees.
For the sake of making comparisons between the traditional and the LP approach available, the software computes classic goal functions for solutions obtained by means of the algorithm using linguistic patterns and vice versa.
4. Simulation experiments
The objectives of the experiments reported here were twofold. Because it is possible to determine the upper bound for the pattern (2) mean truth value according to the maximal mean truth theorem (Grobelny 1987b), one can assess the quality of the given solution in relation to this upper bound mean truth values. Thus, in the first research perspective is focused on examining the sensitivity of solutions to parameters controlling the simulated annealing process. Secondly, it is essential to investigate relationships between variables and functions in the presented novel approach and a classic, crisp version of the simulated annealing algorithm. Both sets of experiments investigate the behavior of our LP implementation with the goal function in a form of equation (7). These experiments and obtained simulation results are presented and described in the following subsections.
4.1. Properties of the proposed algorithm
The first experiment was designed to investigate the influence of algorithm parameters on the effectiveness of finding solutions measured by the mean truth value (7), that is, the average truth value of pattern (2) computed for all pairs of objects, where Truth_of(l) > 0. Examined parameters included the probability of accepting worse solutions (P), the multiplier used for determining the Epoch Length (k) as well as the r parameter which is responsible for the cooling speed scheme. For each of these factors, two levels were specified: small and big.
A specific version of the typical facility layout problem was prepared to compare LP and crisp types of simulated annealing algorithms. The idea is as follows. Let us assume that there is a system of machines or tools with a given relationship matrix that includes data about the intensity of interactions for each objects’ pair (Lij) in a form of physical values (e.g., transportation operations). Such a problem formulation may be described as objective. On the other hand, an expert, based on his experience and knowledge of this system, is capable of determining the relationship matrix by means of linguistically expressed levels of links on an ordinal scale with a granularity equal five (Very Small, Small, Medium, Big, Very Big) or three (Small, Medium, Big). The expert is rational in such a sense that his linguistic assessments cover appropriate succeeding ranges of physical values divided into five or three equal parts. When Lij values are natural numbers from one to ten, then the more precise expert distinguishing five levels will assign the Very Small level to values one and two, the Small to two and three, etc.
For simplicity, in all experiments, the left side of pattern (2) is operationalized by a linear assignment of truth levels Truth_of(l) to expressions obtained as in Fig. 3. This means that in simulations for granularity five it was assumed that Truth_of(Very Small) = .2, Truth_of(Small) = .4 etc. whereas for granularity three: Truth_of(Small) = .1, Truth_of(Medium) = .5, and Truth_of(Big) = 1. The truth value of the right side of pattern (2) is generally determined in accordance with the idea presented in Fig. 4, but here we used a continuous linear function specifying the maximal possible Manhattan distance on a regular grid applied in a given problem type.
Likewise other metaheuristics, the simulated annealing procedure belongs to the improvement type of algorithms. This category of techniques performs better than construction methods in difficult facility layout problems with a small value of flow dominance and a big density of links (Kusiak & Heragu 1987). Therefore, for our experiments, we chose well-known Nugent 30 and Nugent 16 problems structures from the work of (Nugent et al., 1968), where relationships are expressed by natural numbers from one to ten, their density amounts to about 70%, and the flow dominance - approximately 1.2. Additionally, we generated two problems with a comparable number of objects to the selected Nugent’s examples, that is, 4×4 and 6×6 with randomly assigned link values from the range of 1 – 10, a similar flow dominance value but with a lower link matrix density (40%). Linguistic patterns for objects’ relationships, in all examined examples, were specified for granularity five and three according to rational expert rules described above.
Formally, the full factorial, within subjects design produced 16 different experimental conditions, namely P{.1, .8} × k{10, 20} × r{.90, .99} × Gr{3, 5}. For each of the four problem types {Nugent 16, Nugent 30, Random 16, Random 36}, and experimental condition the algorithm was repeated 100 times. Table 1 and Figs. 12-15 present the main results obtained by the classic factorial analysis of variance.
The lack of significant difference between two employed levels of probability of accepting worse solutions (P) is rather surprising (Fig. 14). Such a result has not been previously reported and, to authors’ knowledge, this factor has not been yet systematically analyzed in the literature on the simulated annealing algorithm and its modifications. A distinct and strong (a high value of partial η2) impact of the r value, which controls the cooling process has not been earlier demonstrated. Usually, the parameter is set at .9 without any broader discussion while the result illustrated in Fig. 13 suggests that the level of .99 provides meaningfully better solutions in our implementation of simulated annealing. Obtaining considerably higher mean values of the corrected truth for the smaller granularity (3) is rather intuitive since the algorithm searches, in this case, a smaller problem space than in the bigger granularity condition (Fig. 12). Similarly, better results observed for the higher Epoch Length Multiplier (k = 20) were also expected as the bigger value of Epoch Length signifies that the algorithm performs more pairwise changes for every temperature and, thus, the probability of finding a better layout increases (Fig. 15). It is worth noting that the investigated parameters do not interact with each other (Table 1).
Table 1. Four-way ANOVA results for the first experiment. The effects of Granularity (Gr), Cooling Scheme (r), Probability (P) of accepting worse solutions, and Epoch Length Multiplier (k) on the mean corrected truth value for pattern (2) in four types of facility layout problems {Nugent 16, Nugent 30, Random 16, Random 36}.
Effect SS df MSS F p η2
Granularity (Gr) .064 1 .064 589 <.0001 .11
Cooling Scheme (r) .0046 1 .0046 43 <.0001 .0089
Probability (P) 0 1 .000 0 1
Epoch Length Multiplier (k) .00059 1 .00059 5.4 .020 .0011
Gr × r .00015 1 .0001481 1.4 .24
Gr × P .0000028 1 .0000028 .026 .87
r × P .0000022 1 .0000022 .020 .89
Gr × k .0000027 1 .0000027 .025 .87
r × k .000068 1 .0000676 .62 .43
P × k .00000094 1 .00000094 .0087 .93
Gr × r × P .0000012 1 .0000012 .011 .92
Gr × r × k .00000063 1 .00000063 .0058 .94
Gr × P × k .0000065 1 .0000065 .060 .81
r × P × k .00000035 1 .00000035 .0033 .95
Gr × r × P × k .00000052 1 .00000052 .0048 .94
Error .52 4784 .00011
Fig. 12. The influence of Granularity on mean corrected truth values for pattern (2).
F(1, 4784) = 589, p < .0001, η2¬¬ = .11.
Vertical bars denote .95 confidence intervals.
Fig. 13. The influence of Cooling Scheme r parameter on mean corrected truth values for pattern (2).
F(1, 4784) = 43, p < .0001, η2 = .0089.
Vertical bars denote .95 confidence intervals.
Fig. 14. The influence of Probability of accepting worse solutions on mean corrected truth values for pattern (2). F(1, 4784) = 0, p = 1.
Vertical bars denote .95 confidence intervals.
Fig. 15. The influence of Epoch Length Multiplier (k) on mean corrected truth values for pattern (2).
F(1, 4784) = 5.4, p = .020; η2 = .0011.
Vertical bars denote .95 confidence intervals.
4.2. Comparison of LP and crisp simulated annealing
The main goal of the second set of experiments was to verify the quality of algorithmic solutions based on the experts’ knowledge expressed by means of linguistic patterns and linguistic expressions. In the proposed approach we assumed that there exists an objective system of assessing costs expressed by function (1). The expert doesn’t exactly know that system but has experience and approximate knowledge in this regard that can be formulated as logical patterns similar to a natural language. He can specify the intensity of transportation with a given precision in linguistic terms. Such an assessment can be made on an ordinal scale.
The confrontation of solutions obtained for our linguistic input and results provided for classic, objective data can be treated as a practical verification of the quality and usability of the proposed approach. Since broadly defined transportation costs may be used as a strict indicator of the layout quality, our experiments’ relationship matrices include transportation operations’ intensities. Function (1) computes the cost of these operations whereas formula (7) is its linguistic counterpart.
The first experiment, in this second research perspective, investigates examples representing intracellular transportation tasks for cells of identical shapes and dimensions and the open field transportation type, where the distance is computed according to the Manhattan measure.
The second experiment deals with more sophisticated models including objects with unequal areas. Additionally, we try to optimize transportation costs not only between objects but also inside them. Here, we also assumed the open field type of transportation, but distances were calculated not only by the Manhattan measure but also according to the Euclidean formula which simulates the gantry robot behavior.
4.2.1. Objects with uniform sizes
This experiment was designed to investigate the behavior of the proposed method in comparison with the classical optimization approach which minimizes function (1) and assumes that objects have equal dimensions. For this purpose, we used again the same well-known examples Nugent 16 and Nugent 30 along with random matrices 4×4 and 6×6 as in the first set of experiments. In addition, we used an 8×8 matrix with randomly generated links from the 1-10 range, similar density (40%) and flow dominance (1.4). For these matrices, the best solutions were found by means of classic simulated annealing with a standard goal function defined according to formula (1) and distances measured by a Manhattan metric. Taking advantage of the first set of experiments’ results, the parameters were set at P = 0.8, r = .99 and k = 20. For each experimental condition, the procedure was repeated 100 times. Next, the link data were transformed to expert’s opinions like in the first set of experiments by means of three and five levels of linguistic assessments of links. Again, for each type of examined problems, the best solutions in terms of pattern (2) mean truth value were searched for. For these best layouts, we computed values of function (1) for original link data. The obtained results were compared with the best classic solutions (optimal for Nugent 16 and Nugent 30) and put together in Table 2.
These outcomes primarily show that the layout solutions, obtained by the algorithm with linguistic patterns, not only exhibit high mean truth levels but are also good in terms of objective data and goal functions computed according to formula (1). This is especially evident for more precise experts assessing with granularity five, where they differ by merely two to six percent from the best solutions produced by the classic simulated annealing algorithm. What is quite interesting, these differences seem not to depend on the problem size, which apparently is the case for mean truth levels.
Table 2. Results for examples with uniform objects’ sizes. Upper bounds were computed according to the theorem about maximal mean truth (Grobelny, 1987b). The corrected values are calculated as a difference between mean Truth_of(pattern (2)) and the upper bound.
Problem type Granularity Mean Truth Values
for LP approach Goal Function Values LP to Crisp Deviation [%] Mean Truth Values for Best Crisp Solutions
Pattern (2) Upper
bound Corrected LP Best
Crisp Pattern (2) Corrected
4×4 3 .934 .955 .979 424 382 11.0 .917 .962
5 .957 .973 .984 390 382 2.1 .921 .948
6×6 3 .935 .964 .971 4130 3851 7.2 .925 .961
5 .931 .982 .949 4037 3851 4.8 .922 .940
8×8 3 .920 .964 .956 19870 18835 5.5 .908 .944
5 .919 .973 .947 19400 18835 3.0 .911 .939
Nug_16 3 .973 .978 .995 681 620 9.8 .967 .989
5 .962 .978 .984 660 620 6.5 .958 .980
Nug_30 3 .981 .989 .992 3196 3062 4.4 .977 .988
5 .974 .989 .985 3123 3062 2.0 .969 .980
The observed discrepancies between compared simulated annealing approaches do not result solely from the approximations concerned with transforming real data to experts’ opinions having predefined granularity levels. A comparison of the results for classic and fuzzy implementations presented in columns 3 and 9 of Table 2, indicates that both optimization criteria do not work identically, despite reflecting a similar idea. The linguistic pattern version, along with its parameters and definitions of expressions, is not a simple generalization of the classic approach. It may be noticed that optimal solutions in a classic sense are not the best in terms of the mean truth and conversely. The main reason probably lies in a nonlinear character of the assessment model expressed in a form of the truth level of pattern (2). One can easily note that the pattern (2) truth level criterion computed according to the Łukasiewicz (6) formula is sensitive to changes in the mutual arrangement of a given pair only if Truth_of(l) > Truth_of(r). This means, for instance, that the relative location of objects (i, j) with a link level equal Medium, for which Truth_of(l) = .5 is evaluated exactly the same for distances from the range of 1% to 50% of the maximum possible distance. In the current paper experiments, we used regular grid model with unitary distances between cells. For the Manhattan measure used in our experiments, the maximal distance can be determined by the formula: (p + q) – 2, where p and q specify the grid dimensions. In the example with a 4 × 4 grid, the maximal distance equals six, so the full truth of pattern (2) will occur if the distance between objects would be one, two, or even three units because Truth_of(3) = .5. The calculations assume a linear way of evaluating the truth of pattern Distance_between_objects(i, j) is SMALL.
Obviously, the biggest sensitivity to locations’ changes will occur for pairs with the maximum truth of the left-hand side of pattern (2) (Truth_of(l) = 1). In such an event, the distance one is optimal and any increase of this value would decrease the truth of pattern (2) for a given pair. This effect is observable in structures of the obtained solutions. Figs. 16 and 17 present a juxtaposition of solutions found for Nugent 16 by means of both a classic crisp algorithm and the simulated annealing based on linguistic patterns with a five step granularity. By comparing these layouts, it can be effortlessly observed that the LP algorithm produced a solution where the full truth was present for all pairs with Truth_of(l) = 1. In the layout from Fig. 16, which is optimal in crisp terms, four out of 11 pairs have locations worse than optimal, when the Truth_of(pattern (2)) is concerned. However, on the other hand, the layout demonstrated in Fig. 17 has a 6% worse function (1) value than the solution from Fig. 16.
Fig. 16. An optimal solution for Nugent 16 on a 4×4 grid. Only maximal links between objects are displayed. Objects number 2, 3, and 4 were slightly moved to show the appropriate relationships.
Fig. 17. The best solution for Nugent 16 obtained by the proposed method for experts’ opinions expressed on the five steps scale. All links with the maximal Truth_of(l) = 1.
4.2.2. Objects with variable sizes
The second experiment was conducted to check the usability of the proposed approach for problems involving items of variable sizes. Each object was modeled by an appropriate number of unitary building blocks in such a way that their aggregate area was equal or slightly bigger than the object area provided in the problem description. For each object, one of its components was denoted as an input and output place. This item was linked with all other inner object building blocks with the relationship value being twice as big as the largest link in the original relationship matrix. Connections between input/output items of consecutive objects corresponded directly to the links between initial objects.
For comparisons, we took two data sets from literature, namely: a simple example examined by Jajodia et al. (1992) and more sophisticated based on a real life data example analyzed by Tompkins (1978). Both analyzed examples are similar in terms of the number of objects involved (7, 8) but they differ significantly in the number of building blocks used for approximating areas covered by objects (from one to three in the first, and from three to eight in the second example).
The experimental procedure started with arranging objects according to the best solutions reported in referenced works and presented in Figs. A.1., and A.3 in Appendix. Tables A.1. and A.2. from Appendix include link values and the number of components in every object. Since original optimizations were carried out for distances between objects’ centroids, therefore, we first optimized locations of input/output building blocks within objects without changing their shapes. This was done by applying classic simulated annealing ten times. Results with the smallest transportation costs of this local optimization are demonstrated in the first column of Table 3. Next, the same crisp version of the algorithm was used ten times for all building blocks in a given example. Objects’ integrity was controlled during this global optimization process. The best solutions are put into the second column of Table 3.
Table 3. Results of the second set of experiments for objects with variable sizes.
Example Crisp data Characteristics of LP
solutions for best layouts Comparisons
Original layout after local opti-mization (Q1) Layout after global optimi¬zation (Q2) Mean truth upper bound Mean
truth
value Mean
truth corrected Crisp value for LP solu-tion (Q3) (Q3-Q1)/Q1
[%] (Q2-Q1)/Q1
[%]
Jajodia et al. (1992)
Euclidean 154.5 153.2 .894 .888 .992 154.2 -.2 .6
Jajodia et al. (1992)
Manhattan 165 157 .925 .917 .986 163 -1.2 3.8
Tompkins (1978)
Euclidean 423 356.5 .905 .891 .985 365.4 -15 1.9
Tompkins (1978)
Manhattan 496 410 .933 .911 .976 423 -14.7 3.1
Likewise in the previous set of experiments, it was assumed that the expert is rational and capable of assessing relationship intensities on a five-step scale from Very Small to Very Big. The truth values of increasing levels of links increase linearly. For increasing distances, the truth values decrease linearly in such a way that truth value of the SMALL expression equals one for directly adjacent cells and zero for items located at the ends of the layout area diagonals. Links between components of the same object were set at the Very Big level. Under these assumptions, we ran the linguistic expression based simulated annealing algorithm ten times.
From among the solutions where none of the objects was disintegrated, we selected layouts with the highest mean truth. Parameters of the best results obtained according to the described procedure are put together in Table 3. As in previous experiments, the quality of results was assessed by comparing mean truths with maximal mean truths (upper bounds). These values are put together in columns three-five of Table 3. They include upper bounds for the mean truth of pattern (2), mean truths of the best solution, and corrected mean truth for the best layout, respectively. The corrected mean truth was computed as a percentage difference between the upper bound and the highest mean truth. For the best layouts in terms of the mean truth, we calculated the classic goal function (1) for crisp data (column six of Table 3) which enabled comparisons between linguistic-based and crisp solutions - columns seven and eight of Table 3.
The comparison of the results presented in columns one and two indicates the superiority of the global optimization over the local one, especially in the Tompkins’ (1978) example. Since the mean truth value is very close to one in both cases, the algorithm finds almost ideal solutions, that is, such layouts that meet fully pattern (2).
Columns seven and eight of Table 3 contain comparisons between results from columns one and two and the LP approach. The most reliable indicators are included in column eight of Table 3. They confront global optimization data (column two of Table 3) with the sixth column containing linguistic pattern algorithm outcomes. The appropriateness of this comparison results from the fact that solutions presented in original works were obtained under different constraints and assumption from ours. For instance, Tompkins (1978) provided results for regular rectangular objects while in the present study, objects could take any shapes consisting of adjacent building blocks. In this example, the LP methodology provided solutions differing from the traditional one by less than 2% (Euclidean) and 3.1% (Manhattan). For the Jajodia et al. (1992) problem the discrepancy amounted to barely .6% (Euclidean) and 3.8% (Manhattan). What is interesting, in all trials, none of the objects was disintegrated except for a single solution of the Tompkins’ (1978) example, where one object fell apart. However, this problem can be easily solved by manually rearranging two cells in a way demonstrated in Fig. 18.
Fig. 18. One of the solutions for the Tompkins’ (1978) example with one disintegrated object. Red arrows indicate how to fix the problem.
Such a change produces a solution by 4% worse than the best outcome for crisp data. This situation suggests that decision makers may also consider solutions with some degree of objects’ disintegration. Thus, the schematic diagram of using the LP approach may look as in Fig. 19.
Fig. 19. A schematic diagram of using the LP approach for solving facility layout problems.
5. Conclusions
The proposed implementation of the simulated annealing algorithm with linguistic patterns is promising. First of all, the procedure allows finding solutions with high mean truth for complex facility layout problems. The presented simulation experiments show that optimizations based on linguistic data, retrieved from a rational expert, provide solutions consistent to a high extent with the best crisp layouts. The examination of the influence of algorithm parameters on the solution quality, yielded rather unexpected outcomes. Surprisingly, different values of the probability of accepting worse solutions (P) did not influence the mean truth of pattern (2). This preliminary result, leaning to hypothesize that linguistic pattern based results are independent of the probability P requires, naturally, further research and a confirmation for facility layout problems having other characteristics than these examined in the current study. This direction of future investigations seems to be important as decreasing the P distinctly shortens calculation times. The effect of obtaining better mean results for a slower cooling scheme (r = .99) also needs to be further analyzed. Applying this value, unfortunately, markedly increase computation times. Though the time needed to complete the procedure was not subject to this study examination, a middle-class computer needed about 15 minutes to complete the algorithm with r = .99 for the biggest 8×8 problem. Therefore, the proposed here method with the optimal high value of the cooling scheme parameter can be in practice applied, at most, to medium-sized facility layout problems. On the other hand, such problem sizes are prevailing in the design practice.
The outcomes involving objects with unequal dimensions indicate an interesting area of further studies. The presented concept of modeling transportation systems within complex objects provided solutions in which the building blocks fall apart rarely and generate concentrated structures for the open field model. Thus, it may be interesting to examine other concepts of intracellular transportation models (e.g., loop) and their influence on objects’ shapes while applying the proposed approach.
The presented simulation results involve one of the easiest possible applications of the LP concept with only a single pattern used as a criterion and with the assumption of linear relationships between truth assessments of consecutive levels of linguistic expressions. The software developed for conducting current experiments could be redesigned to take into account multiple criteria and various ways of defining linguistic expressions and patterns. However, in the case of multiple criteria, it would be very difficult to use the same as in the present study idea involving comparisons of the LP approach with a hypothetical objective system. From one hand side, the mean truth upper bound could not be directly applied and, from the other, it might be problematic to find clear crisp counterparts of subjectively defined variables and patterns. Undoubtedly, developing an appropriate research methodology in this regard will constitute a challenging direction of further investigations.
References
Aiello, G., & Enea, M. (2001). Fuzzy approach to the robust facility layout in uncertain production environments. International Journal of Production Research, 39(18), 4089–4101. doi: 10.1080/00207540110061643
Aiello, G., La Scalia, G., & Enea, M. (2012). A multi objective genetic algorithm for the facility layout problem based upon slicing structure encoding. Expert Systems with Applications, 39(12), 10352–10358. doi: 10.1016/j.eswa.2012.01.125
Aiello, G., La Scalia, G., & Enea, M. (2013). A non dominated ranking Multi Objective Genetic Algorithm and ELECTRE method for unequal area facility layout problems. Expert Systems with Applications, 40(12), 4812–4819. doi: 10.1016/j.eswa.2013.02.026
Altuntas, S., Selim, H., & Dereli, T. (2014). A fuzzy DEMATEL-based solution approach for facility layout problem: a case study. The International Journal of Advanced Manufacturing Technology, 73(5-8), 749–771. doi: 10.1007/s00170-014-5826-3
Azadeh, A., Moghaddam, M., Nazari, T., & Sheikhalishahi, M. (2016). Optimization of facility layout design with ambiguity by an efficient fuzzy multivariate approach. The International Journal of Advanced Manufacturing Technology, 84(1–4), 565–579. doi:10.1007/s00170-015-7714-x
Babbar-Sebens, M., & Altuntas, B. S. (2012). Interactive Genetic Algorithm with Mixed Initiative Interaction for multi-criteria ground water monitoring design. Applied Soft Computing, 12(1), 182–195. doi: 10.1016/j.asoc.2011.08.054
Bashiri, M., & Hosseininezhad, S. J. (2008). A fuzzy group decision support system for multifacility location problems. The International Journal of Advanced Manufacturing Technology, 42(5–6), 533–543. doi: 10.1007/s00170-008-1621-3
Cheng, R., Gent, M., & Tozawa, T. (1995). Genetic search for facility layout design under interflows uncertainty. In, IEEE International Conference on Evolutionary Computation, 1995 (V. 1, s. 400-). doi: 10.1109/ICEC.1995.489181
Deb, S. K., & Bhattacharyya, B. (2005). Fuzzy decision support system for manufacturing facilities layout planning. Decision Support Systems, 40(2), 305–314. doi: 10.1016/j.dss.2003.12.007
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
Dweiri, F., & Meier, F. A. (1996). Application of fuzzy decision-making in facilities layout planning. International Journal of Production Research, 34(11), 3207–3225. doi: 10.1080/00207549608905085
Evans, G. W., Wilhelm, M. R., & Karwowski, W. (1987). A layout design heuristic employing the theory of fuzzy sets. International Journal of Production Research, 25(10), 1431–1450. doi: 10.1080/00207548708919924
García-Hernández, L., Arauzo-Azofra, A., Salas-Morera, L., Pierreval, H., & Corchado, E. (2015a). Facility layout design using a multi-objective interactive genetic algorithm to support the DM. Expert Systems, 32(1), 94–107. doi: 10.1111/exsy.12064
García-Hernández, L., Palomo-Romero, J. M., Salas-Morera, L., Arauzo-Azofra, A., & Pierreval, H. (2015b). A novel hybrid evolutionary approach for capturing decision maker knowledge into the unequal area facility layout problem. Expert Systems with Applications, 42(10), 4697–4708. doi: 10.1016/j.eswa.2015.01.037
García-Hernández, L., Pierreval, H., Salas-Morera, L., & Arauzo-Azofra, A. (2013). Handling qualitative aspects in Unequal Area Facility Layout Problem: An Interactive Genetic Algorithm. Applied Soft Computing, 13(4), 1718–1727. doi: 10.1016/j.asoc.2013.01.003
Gonçalves, J. F., & Resende, M. G. C. (2015). A biased random-key genetic algorithm for the unequal area facility layout problem. European Journal of Operational Research, 246(1), 86–107. doi: 10.1016/j.ejor.2015.04.029
Grobelny, J. (1987a). The fuzzy approach to facilities layout problems. Fuzzy Sets and Systems, 23(2), 175–190. doi: 10.1016/0165-0114(87)90057-1
Grobelny, J. (1987b). On one possible „fuzzy” approach to facilities layout problems. International Journal of Production Research, 25(8), 1123.
Grobelny, J. (1988). The ‘linguistic pattern’ method for a workstation layout analysis. International Journal of Production Research, 26(11), 1779–1798. doi: 10.1080/00207548808947991
Grobelny, J. (2016). Fuzzy-based linguistic patterns as a tool for the flexible assessment of a priority vector obtained by pairwise comparisons. Fuzzy Sets and Systems. doi: 10.1016/j.fss.2015.05.012
Guan, J., & Lin, G. (2016). Hybridizing variable neighborhood search with ant colony optimization for solving the single row facility layout problem. European Journal of Operational Research, 248(3), 899–909. doi: 10.1016/j.ejor.2015.08.014
Haktanirlar Ulutas, B., & Kulturel-Konak, S. (2012). An artificial immune system based algorithm to solve unequal area facility layout problem. Expert Systems with Applications, 39(5), 5384–5395. doi: 10.1016/j.eswa.2011.11.046
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
Jajodia, S., Minis, I., Harhalakis, G., & Proth, J.-M. (1992). CLASS: Computerized LAyout Solutions using Simulated annealing. International Journal of Production Research, 30(1), 95–108. doi:10.1080/00207549208942880
Karray, F., Zaneldin, E., Hegazy, T., Shabeeb, A. H. M., & Elbeltagi, E. (2000). Tools of soft computing as applied to the problem of facilities layout planning. IEEE Transactions on Fuzzy Systems, 8(4), 367–379. doi: 10.1109/91.868944
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
Komarudin, & Wong, K. Y. (2010). Applying Ant System for solving Unequal Area Facility Layout Problems. European Journal of Operational Research, 202(3), 730–746. doi: 10.1016/j.ejor.2009.06.016
Kumar, R. M. S., Asokan, P., & Kumanan, S. (2008). Artificial immune system-based algorithm for the unidirectional loop layout problem in a flexible manufacturing system. The International Journal of Advanced Manufacturing Technology, 40(5-6), 553–565. doi: 10.1007/s00170-008-1375-y
Kundu, A., & Dan, P. K. (2012). Metaheuristic in facility layout problems: current trend and future direction. International Journal of Industrial and Systems Engineering, 10(2), 238–253. doi: 10.1504/IJISE.2012.045182
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
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
Liggett, R. S. (2000). Automated facilities layout: past, present and future. Automation in Construction, 9(2), 197–215. doi: 10.1016/S0926-5805(99)00005-9
Lim, Z. Y., Ponnambalam, S. G., & Izui, K. (2017). Multi-objective hybrid algorithms for layout optimization in multi-robot cellular manufacturing systems. Knowledge-Based Systems. doi: 10.1016/j.knosys.2016.12.026
Loiola, E. M., de Abreu, N. M. M., Boaventura-Netto, P. O., Hahn, P., & Querido, T. (2007). A survey for the quadratic assignment problem. European Journal of Operational Research, 176(2), 657–690. doi: 10.1016/j.ejor.2005.09.032
Matai, R. (2015). Solving multi objective facility layout problem by modified simulated annealing. Applied Mathematics and Computation, 261, 302–311. doi: 10.1016/j.amc.2015.03.107
Mohamadghasemi, A., & Hadi-Vencheh, A. (2012). An Integrated Synthetic Value of Fuzzy Judgments and Nonlinear Programming Methodology for Ranking the Facility Layout Patterns. Comput. Ind. Eng., 62(1), 342–348. doi: 10.1016/j.cie.2011.10.004
Moslemipour, G., Lee, T. S., & Rilling, D. (2011). 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
Muther, R., (1961), Systematical Layout Planning (Boston, MA: Industrial Education Institute).
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
Ohmori, S., Yoshimoto, K., & Ogawa, K. (2010). Solving Facility Layout Problem via Particle Swarm Optimization. In: 2010 Third International Joint Conference on Computational Science and Optimization (CSO) (V. 1, pp. 409–413). doi: 10.1109/CSO.2010.242
Önüt, S., Tuzkaya, U. R., & Doğaç, B. (2008). A particle swarm optimization algorithm for the multiple-level warehouse layout design problem. Computers & Industrial Engineering, 54(4), 783–799. doi: 10.1016/j.cie.2007.10.012
Paes, F. G., Pessoa, A. A., & Vidal, T. (2017). A hybrid genetic algorithm with decomposition phases for the Unequal Area Facility Layout Problem. European Journal of Operational Research, 256(3), 742–756. doi: 10.1016/j.ejor.2016.07.022
Palomo-Romero, J. M., Salas-Morera, L., & García-Hernández, L. (2017). An island model genetic algorithm for unequal area facility layout problems. Expert Systems with Applications, 68, 151–162. doi: 10.1016/j.eswa.2016.10.004
Palubeckis, G. (2015). Fast simulated annealing for single-row equidistant facility layout. Applied Mathematics and Computation, 263, 287–301. doi: 10.1016/j.amc.2015.04.073
Parsaei, H. R., & Galbiati III, L. J. (1987). Facilities planning and design with microcomputers. Computers & Industrial Engineering, 13(1–4), 332–335. doi:10.1016/0360-8352(87)90109-4
Raoot, A. D., & Rakshit, A. (1991). A ‘fuzzy’ approach to facilities lay-out planning. International Journal of Production Research, 29(4), 835–857. doi: 10.1080/00207549108930105
Raoot, A. D., & Rakshit, A. (1993). A ‘linguistic pattern’ approach for multiple criteria facility layout problems. International Journal of Production Research, 31(1), 203–222. doi: 10.1080/00207549308956721
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
Samarghandi, H., Taabayan, P., & Jahantigh, F. F. (2010). A particle swarm optimization for the single row facility layout problem. Computers & Industrial Engineering, 58(4), 529–534. doi: 10.1016/j.cie.2009.11.015
Sahni, S., & Gonzalez, T. (1976). P-Complete Approximation Problems. Journal of the ACM, 23(3), 555–565. doi: 10.1145/321958.321975
Sangwan, K. S. (2010). Fuzziness in Materials Flow and Plant Layout. In: C. Kahraman & M. Yavuz (Ed.), Production Engineering and Management under Fuzziness (pp. 359–380). Springer Berlin Heidelberg. doi: 10.1007/978-3-642-12052-7_15
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
Seehof, J. M., Evans, W. O., Friederichs, J. W., & Quigley, J. J. (1966). Automated Facilities Layout Programs. In: Proceedings of the 1966 21st National Conference (pp. 191–199). New York, NY, USA: ACM. doi: 10.1145/800256.810696
Skorin-Kapov, J. (1994). Extensions of a tabu search adaptation to the quadratic assignment problem. Computers & Operations Research, 21(8), 855–865. doi: 10.1016/0305-0548(94)90015-9
Taillard, E. (1991). Robust taboo search for the quadratic assignment problem. Parallel Computing, 17(4–5), 443–455. doi: 10.1016/S0167-8191(05)80147-4
Tompkins, J.A. (1978). How to gather the data you need. Modern Materials Handling, June, 50-56.
Tompkins, J.A., White, J.A.A. (1984). Facilities Planning, New York: John Wiley & Sons.
Wilhelm, M. R., Ward, T. L. (1987). Solving quadratic assignment problems by ‘Simulated Annealing’. IIE Transactions, 19(1), 107–119. doi:10.1080/07408178708975376
Zadeh, L.A. (1978a). Fuzzy sets as a basis for a theory of possibility, Fuzzy sets and Systems, 1(1), 3-28. doi: 10.1016/0165-0114(78)90029-5
Zadeh, L.A. (1978b). PRUF—a meaning representation language for natural languages. International Journal of Man-Machine Studies, 10(4), 395–460. doi: 10.1016/S0020-7373(78)80003-0
Zhao, F., Li, G., Yang, C., Abraham, A., & Liu, H. (2014). A human computer cooperative particle swarm optimization based immune algorithm for layout design. Neurocomputing, 132(0), 68–78. doi: 10.1016/j.neucom.2013.03.062
AppendixAppendix
Data for Jajoda et al. (1992) and Tompkins (1978) examples with variable objects’ sizes.
Example from Jajodia et al. (1992)
The links between building blocks of the same object were specified as twice as big as the maximum value from the objects’ relationships matrix, that is 18.
Table A.1. Links between objects and the number of building blocks for every object in the Jajodia et al. (1992) example.
Object
number Number of blocks 1 2 3 4 5 6 7
1 3 0
2 2 9 0
3 2 6 4 0
4 2 0 4 0 0
5 1 0 4 0 4 0
6 1 0 4 4 0 4 0
7 1 3 0 0 4 0 0 0
Fig. A.1. The original best solution reported in Jajodia et al. (1992).
Fig. A.2. The best solution obtained by means of our LP approach for Jajodia et al. (1992) example.
Example from Tompkins (1978)
In this example, the area of a building block was set at 1000 units and RelCharts weight values were set at A=4, E=3, I=2, O=1. The links between building blocks of the same object were specified as twice as big as the maximum value from the objects’ relationships matrix, that is eight.
Table A.2. Links between objects and the number of building blocks for every object in the Tompkins (1978) example.
Object
number Area
(blocks) 1 2 3 4 5 6 7 8
1 7500 (8) ×
2 7000 (7) 2 ×
3 3000 (3) 0 2 ×
4 5000 (5) 1 1 0 ×
5 4500 (5) 0 0 0 2 ×
6 3000 (3) 1 2 1 2 3 ×
7 7000 (7) 0 0 0 0 0 3 ×
8 3000 (3) 2 0 0 0 0 0 4 ×
Fig. A.3. The original best solution for centroids reported in Tompkins (1978). 00 denotes an empty cell.
Fig. A.4. The best solution obtained by means of our LP approach for Tompkins (1978) example. 00 denotes an empty cell.
|