Production, Manufacturing and LogisticsApplying Ant System for solving Unequal Area Facility Layout Problems
Introduction
Ant System (AS) is the first variant of Ant Colony Optimization (ACO) which was introduced by Dorigo and his colleagues in the early 1990s (Blum, 2005). ACO works by imitating the foraging behavior of ants when searching for the shortest path to reach their food source. ACO was initially developed for solving the Traveling Salesman Problems (TSPs). Thereafter, its application was extended to solve various kinds of discrete optimization problems including the Quadratic Assignment Problems (QAPs), Vehicle Routing Problems (VRPs), Job-Shop Scheduling Problems (JSPs), etc.
This paper attempts to investigate the performance of AS when solving the Unequal Area Facility Layout Problems (UA-FLPs). To date, a formal ACO-based metaheuristic has not been applied to solve them. Recent research has mainly used it to deal with QAPs (Hani et al., 2007, Stützle and Dorigo, 1999, See and Wong, 2008, Wong and See, 2009a, Wong and See, 2009b). Besides this, it has also been used for solving machine layout problems (Corry and Kozan, 2004). Generally, ACO has been proven to perform outstandingly when solving QAPs, which are the backbone problems for UA-FLPs (Stützle and Dorigo, 1999). This motivates the authors to create a new AS for solving UA-FLPs, and to investigate its performance.
UA-FLPs were originally formulated by Armour and Buffa (1963). Conceptually, the main objective of UA-FLPs is to partition a given area/region into departmental sub-regions so that the total material movement cost between departments could be minimized. The constraints for solving UA-FLPs (Meller and Gau, 1996) are: (1) all departments must be located within a given area or facility, (2) all departments must not overlap with each other, and (3) the layout must fulfill the maximum ratio constraints (or minimum value restrictions) for the dimension of departments (length and width of each department).
This paper is structured as follows: Section 2 describes the fundamentals of AS and current research in UA-FLPs. Section 3 discusses about the new AS formulation created by the authors to solve UA-FLPs. Section 4 mentions the parameter settings and case problems which are used to test the proposed algorithm. Section 5 analyzes and describes the evaluation results obtained. Finally, this paper ends with conclusions in Section 6.
Section snippets
Literature review
ACO is a discrete optimization technique which imitates the foraging behavior of an ant colony. Particularly, it resembles the behavior of an ant colony in finding the shortest path to reach its food source. After the initialization of parameters and input of problem data, every ACO iteration consists of ant solutions construction, local search procedures (optional), and pheromone information update. The explanations of these three components are as follows (Blum, 2005):
ConstructAntSolutions( ).
Formulation
In this section, a detailed explanation of the proposed AS algorithm will be given. Specifically, it describes the ant solution representation used and the three main phases of the proposed algorithm, i.e., ant solutions construction, local search procedures, and pheromone information update.
Numerical experiments
The proposed algorithm was tested using various problem sets taken from the literature. They are O7, O8 and O9 from Meller et al. (1999), vC10 from van Camp et al. (1992), Ba12 and Ba14 from van Camp (1989), AB20 from Armour and Buffa (1963), SC30 and SC35 from Liu and Meller (2007), and Du62 from Dunker et al. (2003). These problem sets are chosen because of their variety in size (from 7 departments until 62 departments). In addition, they are chosen because they are widely used in previous
Results and discussion
The statistical results obtained after running the proposed algorithm are shown in Table 1. From the table, it is shown that the proposed algorithm is robust since the percentage of gap between the best and worst solutions is relatively low. The computation time needed is acceptable considering the fact that various types of local search are used in the algorithm. In addition, facility layout planning is not a time-critical issue (See and Wong, 2008).
The local search procedures contribute to
Conclusions
This paper has proposed an AS algorithm with slicing tree representation for solving UA-FLPs. This is probably the first paper which investigates the use of ACO for solving UA-FLPs. The proposed algorithm is quite robust and has improved several problem instances as compared to previous research. It performs better than GA with flexible bay representation which was proposed by Tate and Smith (1995). In comparison to Liu and Meller (2007)’s and Scholz et al. (2009)’s approaches, the proposed
Acknowledgements
The authors would like to thank the Ministry of Science, Technology and Innovation (MOSTI), Malaysia for funding this research under the E-Science Grant Number: 03-01-06-SF0024. We would also like to thank the three anonymous referees for their valuable comments.
References (23)
Ant colony optimization: introduction and recent trends
Physics of Live Reviews
(2005)- et al.
Optimization of block layout design problems with unequal areas: A comparison of MILP and MINLP optimization methods
Computers and Chemical Engineering
(2005) - et al.
Ant colony optimization for solving an industrial layout problem
European Journal of Operational Research
(2007) - et al.
The facility layout problem: Recent and emerging trends and perspectives
Journal of Manufacturing Systems
(1996) - et al.
Applying the sequence-pair representation to optimal facility layout designs
Operations Research Letters
(2007) - et al.
STaTS: A slicing tree and tabu search based heuristic for the unequal area facility layout problem
European Journal of Operational Research
(2009) - et al.
A nonlinear optimization approach for solving facility layout problems
European Journal of Operational Research
(1992) - et al.
A new minimum pheromone threshold strategy (MPTS) for max–min ant system
Applied Soft Computing
(2009) - et al.
A new mathematical-programming framework for facility layout problem
Informs Journals on Computing
(2006) - et al.
A heuristic algorithm and simulation approach to relative allocation of facilities
Management Science
(1963)
Ant colony optimisation for machine layout problems
Computational Optimization and Applications
Cited by (125)
Integration of material handling devices assignment and facility layout problems
2021, Journal of Manufacturing SystemsAddressing Unequal Area Facility Layout Problems with the Coral Reef Optimization algorithm with Substrate Layers
2020, Engineering Applications of Artificial IntelligenceCitation Excerpt :In this section, the performance of the proposed CRO-SL system is evaluated in a large set of UA-FLPs and compared to existing previous approaches. This way, the following UA-FLPs instances have been tested: Slaughterhouse detailed in Salas-Morera et al. (1996); CartonPacks and ChoppedPlastic from García-Hernández et al. (2013a); O7, O8 and O9 (formulated as Wong and Komarudin, 2010), stated by Meller et al. (1998); VC10 (considering all aspect ratio options) explained in van Camp et al. (1992); MB12 described by Bozer and Meller (1997); Ba12 presented in Bazaraa (1975); Ba14 detailed in Komarudin and Wong (2010) of the UA-FLP stated in Bazaraa (1975); AB20 stated by Armour and Buffa (1963) with different aspect ratio constrains; SC30, considering formulation of Komarudin and Wong (2010) of the UA-FLP explained in Liu and Meller (2007); SC35 described by Liu and Meller (2007); and DU62 detailed by Dunker et al. (2003). An important point in the CRO-SL is the selection of the number of substrate layers and its composition.
A novel multi-objective Interactive Coral Reefs Optimization algorithm for the Unequal Area Facility Layout Problem
2020, Swarm and Evolutionary ComputationCitation Excerpt :In order to address the UA-FLP, different techniques and algorithms have been considered. Following the classification by Komarudin and Wong [26], it is possible to divide them into deterministic methods and heuristics (or meta-heuristics) approaches. Regarding the first category, a first proposal based on a branch and bound method was suggested by Meller et al. [27].
A two-stage solution approach for unequal area facility layout problem with bi-directional relaxed flexible bay structure
2023, Journal of Facilities Management