fake 5

The design of multi-objective facility layout model by using particles optimization algorithm (PSO)
(Case study: automotive parts supplier factory)
Abstract
Facility layout design is a new field of research that is appeals to researchers. Also, due to its impact on the production process, on efficiency, and profitability of the production unit, it has always been the focused by the industries’ owner. The main point of facility layout is finding the perfect template for machinery, equipment or other resources which are used as a facility in order to optimize production flow, while the total cost is reduced. There are many applications for layout problems including organize work stations; construction of new production unit; equipment allocation, etc. In this paper, the practical prospects of the facility layout by applying meta-heuristic methods are proposed. Thus, from a variety of available models to consider facility layout with two factors of distance and interaction between them, exponential allocation model is used. The model was presented according to the workstations of production unit of automotive parts supplier factory, in order to minimize transportation costs and maximize value of workstations’ nearness rate. In the end, since this type of problem is classified as NP-Hard problems, particle swarm optimization (PSO) algorithm is used. PSO algorithm is one of the important meta-heuristic methods, which ws designed to achieve the best solutions on the feasible space of hybrid problems. The computational results show the effectiveness of the proposed algorithm in solving presented model.
Keywords:
Particle swarm optimization algorithm, Facility layout, NP-Hard problems, meta-heuristic algorithms, multi-objective optimization problems, exponential allocation problems
1. Introduction
Facility layout problem as one of the main issues in designing the facilities, is a strategic decisions in business. These issues are known in many types of production systems. Developing and constructing a production unit needs planning and implementation of many projects and their subordinates, which is very costly and time consuming. The most basic actions such as the identification of potential, suitable and with the capacity locations; estimate the incurred cost, etc. in fact are long-term investment projects for the industries’ owner. The facilities that proper places are selected for them today, will be used for a long period of time. So determining the optimal locations for them, is an important strategic challenge for any organization. (Owen and Daskin,1998) In particular, those issues that are concerned to the facility layout (such as machinery, departments) in the factory, have a huge impact on system’s performance. Their impact on production costs, the volume of goods in process, the production time and efficiency, is undeniable. In such matters, by considering the required space for facility layout in production unit based on a number of determined indicators, and the available space constraint, at least one objective function will be met. [1,22]
What proposed in real-world of facility layout, are set of factors that can play a significant role in choosing the appropriate model. Presenting a model that fitted with factory’s space, while adding a facility consequently changes the production line, requires many factors to be considered. [12,21,27] Providing a model that can assess all aspects of issues such as the feasibility of the future expansion of the factory, ideal transportation system of the factory; considering the physical deployment of equipment and facilities; reduce activities’ time through the balance of the production line; considering machinery arrangement according to the number of them and interaction between them; and their relation with exist equipment in terms of the number of candidate places for the establishment of facilities and specialization of activities, facilitating the flow of materials in a way that minimum staffs is required, increased efficiency and operator efficiency and maximize safety and productivity, is necessary more than ever because of the importance of these issues. [25] A proper layout of facility in the production unit can increase operators’ efficiency and even reduce operating costs to 50%. (Tompkins, 1996)[37] At facility layout problems, layout admits in a way that a series of factors in production line such as material flow, the transportation path, used space, interactions between machines or departments and costs associated with them will optimize.[2]
2. Literature Review
According to the multi-objective nature of the model in this study, it seems necessary to considering literature of multi-objective optimization problems and methods used by researchers to solve them. Accordingly, it can be generally cited researches about facility layout optimization problems by considering the variety of them as follows:
QAP issues has been defined by Beckman and Koopman initially in 1957 for economic activity. [35] QAP is one of the difficult hybrid optimization problems that generally these issues with the size of n>30 cannot be solved in reasonable time. Shani and Gonzales in 1976 showed that the QAP is NP-Hard problem. [37] The objective function of these problems is arranging facilities in order to minimize the cost of materials’ transportation between them. Steinberg (1987) used QAP to minimize the number of connections between components of wiring boards; Heffley (1972-1980) used QAP model for economic problems. Fransis and White (1974), presented a decision framework to allocate a new facility (in police stations, supermarkets, schools) in order to meet the specific demands of customers (Zanjirani, 1987). Yavuz A. Bozer et al. (1996), developed a discrete facility layout problems that its layout was in the shape of a circle. [37] Meller et al. (1999), offered a kind of facility layout problems that arrangement of facilities was orthogonal, two surface and non-overlapping. Lee (2002), defined a facility layout problem in the form of setting N facilities with different dimensions in unequal and limited space, then solved the model by using annealing simulated algorithm. G.Aiello et al. (2005), solved multi-objective problems of facility layout by using genetic algorithms and Electre multi-criteria decision method. In this method, the objective functions are in conflict with each other. [38] R.Christapaul et al. (2005), examined the problem of facility layout in their study, where space was unequal. [39] Güneş Erdoğan et al. (2005) by using a branch-and-bound algorithm focused on basic formula of Beckman Koopman and used flow-distance matrix in solving exponential allocation problem. [11] Zvi Drezner (2006), in his study, solved exponential allocation problem as a sort of facility layout problems by using evolutionary genetic algorithm and a new taboo search method (the simple taboo Search). [9] Komaradin and Kuan yew wong (2009), considered facility layout problem with unequal space (UA-FLPs) and solved the problem by using the ACO, one of the ant colony optimization algorithms, and also used several types of local search methods. Hui Li and Dario Landa-Silva (2009), used GRASP meta-heuristic algorithm for solving multi-objective exponential allocation problem. [19] S Jannat et al. (2010), used genetic algorithms to solve multi- objective facility layout problem [16]. Abraham and et all. (2010), for solving multi-objective exponential allocation (MQAP) used fuzzy PSO algorithm. [33] Chen (2012), focused on the model of localization problem, as a dynamic facility layout problems (DFLP) with large dimensions in their research. [32] L.Garcia et al. (2013), used the small dimensions to solve the (UA-FLP) problem -the facility layout problem with unequal space. To this, they applied genetic algorithms. [12] Ozkale et al.(2013), considered multi-objective exponential allocation problems and used ant colony optimization algorithm to solve it. [24]. Karasakal and Silav (2015), have solved multi-objective facility layout problem with partial coverage by using genetic algorithm. Matai (2015) used annealing simulation algorithms to solve multi-objective facility layout problem.

3. Materials and Methods
3.1 Exponential allocation model
Facility layout problem has various models, which are classified based on their applications and sizes. But the most general classification include: the middle locating problem (single facility) or (multi-facilities), the center layout problem, [11] the coverage layout problem, allocation problem, the layout- allocation problem, etc. (Gunesh,2003)‬‬‬‬‬‬‬‬‬‬‬
What is discussed in this paper is exponential allocation problem which is classified in layout problems category. In such cases, the goal is that to allocate facilitates to places in a way that any facility allocated only to one place and vice versa, and the distance between locations, the demand flows between the facilities, and generally minimize the places allocation costs per facility. 21](Loiola et al,2005)
The QAP problem is the allocation of n objects to n cases, where total allocation cost of each pair be minimized (Erdoğan et al,2007). [11] The general form of the exponential allocation is as follows:
According to this model, if we suppose Cijkh as the cost of transporting materials in distance units for allocating facility i in place k and allocating facility j in place h. Also, xik would be obtain 1, if facility i allocated to place k. In that case, in order to allocating h new facilities to a certain locations, the input matrix must be symmetric. We want to minimize the following function due to related constraints:
3.2 multi-objective optimization models
Multi-objective optimization models have been raised almost two decades ago, and their performance in real-world’s problems is steadily rising. Some theoretical background of this topic can be found in some researchers such as Edgeworth (1881), Koopmans (1951), Kuhn and Tucker (1951), Pareto (1896) and (1906). Although real-world’s problems can be formulated as a single goal, but firstly, often it is very difficult to define all aspects of problem in a single objective function. Secondly, defining a multi-objective model can provide a better idea to solve real-world’s problems. Because of these problems’ characteristic, there is no unique solution for them. But it can be identified a set of proper solutions for these problems. These solutions are known as non-dominance, efficient, high quality, in other words Pareto optimal solutions. Pareto level, is a level that includes all of the solutions, which are worth to explore. [28]
The purpose of solving multi-objective optimization problems is help to the decision maker (DM) to consider several objectives simultaneously. Pareto-optimal solutions were defining to bring the desired satisfaction for the decision maker. [2] So the precedence and priorities of each objective function that intended by decision maker, have key role in selection of the optimal solution. (Hartmanis, Leeuwen Goos, 2008). The main challenge in multi-objective optimization problems is minimizing distance between new solutions and available set of solutions, and maximize the diversity of the Pareto-solution set. (Miettinen, Ruiz et al2008)
In the same way, as several related objective functions can be optimized simultaneously, an optimal solution cannot be better than a possible and same quality solution set. When we are trying to optimize several goals simultaneously, search space is divided based on each target. One solution can be optimal, bad or neutral (or dominant or recessive) that all these cases will depend on the value of the objective function. [40]
"Optimal solution means that the solution will not be bad to any of the objective functions, and at least be better for one objective function than any other solution."[24]
The optimal solution is a solution that does not dominated by other solutions in the search space. Such optimum solution called Pareto, and a whole set of such alternative optimal solutions is called Pareto optimal set.
A multi-objective optimization problem can be considered in the form of a minimizing [f1 (x), f2 (x), ..., fk (x)] set for k number of objective functions, so that fi: Rn → R are set of goals that can have several qualitative and quantitative constraints. For x = [x1, x2, ..., xn] which is a vector of decision variables, our goal is to determine the function F of all vectors that provides all their constraints.
Evolutionary algorithms due to be equipped by a set of elected solutions, have operators that regularly produce solution. This gives ability to solution process to create a new solutions set by combining existing solutions. As a result, several members of the Pareto optimal solutions set were generated by run the algorithm for once instead of run the algorithm for several times separately. (M.Bashiri,2016) [42] . A number of stochastic optimization methods such as simulated annealing, taboo search, ant colony optimization, etc. can be used to create Pareto front. Simply, because of these algorithms procedure, resulting solutions are often have a significant power of approximation.
3.3 The proposed mathematical model
Since the presented model is based on the exponential allocation model, in accordance with the specification of these types of model, parameters are defined as follows:
n: number of candidate locations for locating
m: number of available machines in production unit
Xij: is a binary variable that takes the value 1 when the machine i is allocated to location j, otherwise is zero.
Chm: cost of transporting raw materials per unit of distance
CAP (c): The maximum dedicated cost for machines layout
fij: The materials transaction between machine i and j
jkl: the distance between departments / location k and department l
ҩ (i) = l and ҩ (j) = k definition means that the machine i dedicated to location l. Symbol ҩ, means any ҩ movement of the set N = {1,2, ..., n} which display as a matrix n × n, X = (xij).
Rij: the weight that assigned to the nearness priority of departments i and j to each other
According to the definition of model’s parameters, objective function is defined as follows:
What is considered as the objective function in this model, consists of two parts. [41]
3-3-1- The first objective function:
This function, was provided based on general form of QAP, and the goal is to minimize the total associated costs with allocation simultaneously. According to this fact that model considered as a case study, the functions’ components are fitted and presented based on the conditions that governing the production unit of study. Paul et al. (2006) to meet the required space for workstations in their model, used range, and set upper and lower bonds. However, in this study PSO algorithm is used in discrete form [39]. Therefore, the components of first objective function which is formulated to minimize total costs, stated as follows:
- The cost of transporting materials between departments (where identified for locating)
This cost will be obtained from the following equation:
Distance between the departments × flow of material (transaction volume between machines) × cost of transport per unit of distance
- Cost of transportation per unit distance will be obtained from the following equation:
Driver wages + fuel costs+ depreciation costs
In this model, since parts is carried by labors during operation and working with associated machine, so they are carried Non-automatically and carried manually, fuel costs in equation (2) will not calculate.
In mentioned objective function if Chmikjh called as a cost of allocating facility i to place k and facility j to place h simultaneously, the model can be offer as follows:
3-3-2-second objective function:
The second objective function was modeled to maximize the amount of nearness score of the machines to each other:
Scores table which are sorted based on machines nearness will be presented in next section.
Constraints of the model can be defined as follows:
Constraint (7) shows that every facility can be allocated only to one place, and the constraint (8) indicates that any place can accommodate only one facility. Constraint (9) means that allocation cost of both i and k facilities to two places j and h should not be greater than the CAP (C) (the maximum allocated budget), and do not exceed it. Therefore, the proposed model includes equations (5) to (10).
It should also be noted that the proposed model includes assumptions as follows:
1. Material flows takes places between the departments’ center (midpoint).
2. The cost of transportation is directly depends on the distance.
3. All information about material flow are certain (non- probable).
4. Waste and similar items are not considered.
5. All movements are done in two dimensions.
In addition, the cost of facilities’ layout is not considered individually in this model.
4. The particle swarm optimization algorithm (PSO)
Particle swarm optimization algorithm introduced by Kennedy and Eberhart in 1995 for the first. This algorithm is based on the metaphor of the collective and food flocking behavior of birds, and optimization problems are solved based on that.
Particle swarm optimization algorithm (pso) is a type of evolutionary algorithms and derived from the particle behavior like groups of birds. In this behavior, the collective of particles (as an optimization problem’s variables) are scattered in search space. Typically, a bird (leader), holds the best position, and the rest of birds according to their position and the adjacent birds trying to make their position better and closer to leader. [4] Meanwhile, if a member found a better position than leader, it would elected as leader. It is worth noting that the position changing of each particle is occurs based on its own experience in previous movements and the experience of neighbor particles.(Bratton& Kennedy,2007) Simulating all mentioned concepts, needs to define parameters as follows:
The best personal memory (pbest), the best global memory (gbest), individual recognition parameters (c1), global cognition parameter (c2), the inertia coefficient (ω), the velocity of each particle (vi). So that, the motion of each particles will accordance with the equation (11) .
Each particle is updated by adding velocity variable to location variable in each iteration. And is shown as follow:
Based on equation (11) parameter D, ....., 2,1 = d, indicates the feasible zone that each particle is placed there or will be placed and N, ...... , 2,1 = i indicates the number of particles (variables). In order to solve the model and running algorithm, parameters such as coefficients C1 and C2 need to be initialized. In this study, respectively 0/7 and 1/5 is considered for them. And the value of φ_1 and φ_2 are also random numbers with uniform distribution between zero and one. Inertia factor (ω) is considered equal to 0/4. All these parameters are considered after increasing or decreasing them and observing their Impact on the performance of the algorithm. [4,6,8,17]
Component of vector Vi must be about [Vmax, Vmax] where Vmax determined by the permissible range for movement of each particle or by algorithm designer to organize the distribution and search carefully. Typically, lower and upper bonds of this range will change about 10% to 20% of its particle velocity.
At the multi-objective particle swarm optimization algorithm, archive concept is arises, particles movement in each iteration is based on the leader. Each of the solution space’s houses that have non-dominance solution are archived, then between the each houses’ member of archive population, one of them was conducted as a leader. However, leader selection steps was done based on algorithms ΠPESA-II . In this algorithm, selection is done according to the houses, and then according to the selected of houses’ members. In a way that, the Houses that have fewer members, have more chance to be selected. [43]
As mentioned, the presented model is in accordance with automotive parts supplier’s production unit. The number of work stations and allocated places are equal to 28. According to the parameters and assumptions, to run the model some real data such as matrix of distances between workstations, material flow matrix, and materials/parts transportation cost required to be provided in order to solve the first objective function. As well, to resolve the second objective function, the matrix of quantitative amounts of nearness rate needs to be presented.
Matrix of distances between departments was calculated by using Euclidean method from equation (13), as table ().
Another parameter which requires the real data is the material flow matrix. Procedure of computing this matrix is as follows:
1. First, in accordance with the process control diagram, the priority and posteriority of each stage’s activities of the production process are examined.
2. After determining the stages of the production process, the daily average production rate at production unit is calculated
3. The type and number of parts or raw materials required in each work station, is estimated according to the consume coefficient table.
4. In order to calculate the amount of the transaction between workstations, maintenance table, transportation and installation will be also examined.
5. Finally, with regard to all the previous stages, the number of interactions between workstations will be calculated. [39] Another parameter that is needed to resolve a first objective function, and also is the aim of minimizing the first objective function is the cost of materials / parts transporting per each unit (one meter). The second objective function, requires the nearness matrix to be resolved. According to the provided explanations, work stations’ nearness rate relative to each other are ranked based on the table (2) and its detailed is provided in table (3). This ranking criteria is evaluated based on some characteristics such as volume flow of material, facilitate the movement of materials, sequence of activities in the production process, evaluation of the favorable / unfavorable effect of each station’s performance on each other, remove the parallel activities in the production process.
Generally, to solve the exponential allocation problem, all required parameters and their values are as follows:
• Size of population
• Maximum iteration (Num of Itr)
• Maximum allocation capacity cost (Cap) c = 000, 000,10 USD
• The number of machines (Num of Fac): 2
• The number of selected places in order to allocation (Num of Place): 28
• The number of the archive population (nRep): 40
• Personal learning coefficient (C1): 7 /
• global learning coefficient (C2): 5/1
• The number of houses of solution space (nGride): 5
According to the provided explanations and dedicated real data to solve the model (with emphasis on being multi-objective functions), MOPSO algorithm is shown in Figure (1).
5. The results of the model’s solution by using PSO algorithm
According to the aforementioned steps and proposed model, the results of the model solution by using PSO algorithms are as follows. It should be noted that the present algorithm was implemented and run in MATLAB and computer with the following specification:
CPU Specifications: Intel (R) Core (TM) 2Duo CPU P8800
RAM Specifications: 4.00 GB
Typically, to display graphical form of non-dominance Pareto solutions set in meta-heuristic algorithms, the Pareto frontier is used. In the current problem, non-dominance Pareto solutions with the 50, 100, 150, 200 and finally 250 iteration number is shown in figures (1). These figures reflect the Pareto front trends toward the optimality of both objective functions by increasing the number of iterations of the algorithm.
Due to the convergence trend of the algorithm, the result of algorithm’s performance can be observed in Figure 1 and Table (3). Figure (1) shows an overview scheme of the factory’s workstations.
Results of table 3 indicates the set of Pareto solutions frontier by considering both objective functions. Due to the nature of multi-objective problems, it cannot be obtained any solution superior over another, so decision-makers can select any of the resulting solutions according to their preferences. However, if consider any of the objective function separately, the results of model’s solution will be as table (4). This table indicates the success of algorithm’s performance in improving each of the objective functions.
In the present study, as the proposed model is defined based on MQAP and particularly for automotive parts supplier, and the solution method, the PSO algorithm, thus doing comparative study with other studies will be limited to implementing the same conditions which is impossible, because of the difference conditions. Therefore, we have tried to compare elements that have been treated the same in selecting model or solution method.
Paul et al. (2006), in a similar study, examined one type of facility layout under the condition that facilities establishment consist of hallways and interior walls and were unequal. Their model examined both targets as same as the present study, and the PSO algorithm was used to solve the model. Then to evaluate the performance of their algorithm, compared results with other algorithms such as genetic algorithm, and the Islier algorithm. The results of this comparison shows the superiority of pso algorithm for solving the model.
In another study, Helal et al. (2015) used the PSO algorithm to solve QAP problem. The only difference is that the model was single-objective function and the Tabu search algorithm is used in combination with pso algorithm. Also, Pso algorithm was hierarchical. (HPSO), use of Tabu search algorithm leads to increase the search diversity and particles (solutions) selected randomly, in contrast to usual state of HPS that research done at the particles’ tree roots. Mvntryv and Lopez (2015), solved some QAP problems in multi-objective function version by using ant algorithm combined with annealing simulation algorithm. The comparison results show the superiority of this hybrid optimization algorithm to solve such problems.
Conclusion
The aim of this study was provided a proper model for the locating the facilities by using particle swarm optimization algorithm (PSO). So that, the proposed model In addition to efficiency of solution method, meet the goals which were set.
In this regard, the proposed model were provided with proportionate to exponential allocation problems in order to locating facilities, and be more suited to the establishment conditions. Due to classifying these problems is in the category of NP-Hard problems, in order to achieve the most optimal possible solution, meta-heuristic algorithms has been used. As the particle swarm algorithm in comparison with other meta-heuristic algorithm has higher convergence speed, and reach to the solution in shorter time, selected as a superior algorithms to solve the model. On the other hand, in the proposed model, two objective functions were intended. So that, the transportation cost and distance between the selected locations for facilities simultaneously, are minimized. Nearness degrees of selected location are weighted equivalent to their priority. Thus, the allocation of facilities to the selected places optimized with regarding to two objective functions.
In the first place, but what is more important for the industry. Economic advantage optimal facility location and actually reduce costs. and It can be concluded that Despite the goal that would normally be considered for the facility location issues such as:
Minimize the cost of transportation to maximize the workstations close to each other; Minimizing total production time, maximum use of available space; improve the flexibility in manufacturing operations; The establishment of facilities improvement plan based on the minimum space requirements for each workstation and .....
All of it will be directed to where they can make a variety of minimizing the costs associated with the manufacturing process.[41]
Also, performance of pso algorithm in solving the model according to the results of Table 5, reveals the superiority of this method in order to improve objective functions. Each objective function in terms of optimizing its own, is independent of the other objective function, and is optimized at one of the obtained solutions. First objective function with purpose of minimizing the materials transportation cost, will obtain the most optimal value in 3th, 4th and 5th solutions. Of course, reaffirms that if the problem to be solved only with the first objective function. Whereas, if we consider only second objective, the 23th solution, in other words, 23th layout will be the best solution. It should be noted that all obtained solutions are met optimality conditions. In other words, none of the objective function will not dominance, and at least has superiority to one of two objectives. But if we want to consider both objective functions where optimal conditions will be met for both objective functions, we can use multi-objective optimization methods for solving problems. But in the case that the obtained Pareto solution set optimizes multi objective functions, one of them cannot be chose as the most optimal choice. Because none of the obtained solutions are not superior to another one, and all of them are non-dominance. In addition, to evaluate the progress trend of each objective functions, the progress diagram of algorithm’s performance based on the each objective functions is shown in Figure 3.
Some indicators and methods are used to assess the performance of the algorithm. Presented indicators’ results reflect the favorable performance of algorithms in providing high optimal solutions. In addition, increasing the efficiency of each objective function is visible by comparing the values before and after resolving the model. Also, the obtained solutions by optimizing both of the objective functions based on input data and providing multiple facility layout design, met the specified goals in order to provide a new design for the facility layout. [45] In order to evaluate the performance of the algorithm and compare the results that obtained by other meta-heuristic algorithms, the following indicators are used and their corresponding values are also presented.
Indicators results express the algorithm’s fairly success in solving model. Where at the MID indicator, the closer frontier to the center coordinates, the better. So obviously for compared sets, the smaller value of this leads to the more desirable. Also, RAS and SNS indicators show the non-dominance solutions’ diversity based on their definition. Where the higher value of indicators show solutions’ more diversity
Now, with regards to obtained results, algorithm’s performance can be compared with other meta-heuristic algorithms. It should be noted that the first parameter NPS is not part of the assessment indicators, but represents the best non-dominance solution number of Pareto frontier. Since in each iteration, the initial population is created by random approach.