Layout design problem is to determine a suitable arrangement for the departments so that the total costs associated with the flow among departments become least. Single Row Facility Layout Problem, SRFLP, is one of the layout problems that have many practical applications. This problem and its specific scenarios are often used to model many of the raised issues in the field of facility location. SRFLP is an arrangement of n departments with a specified length in a straight line so that the sum of the weighted distances between the pairs of departments is minimized. This problem is NP-hard. In this paper, first, a lower bound for a special case of SRFLP is presented. Then, a general case of SRFLP is presented in which some new and real assumptions are added to generate more practical model. Then a lower bound, as well as an algorithm, is proposed for solving the model. Experimental results on some instances in literature show the efficiency of our algorithm.
Kothari, R., and Ghosh, D. (2012) Tabu Search for the Single Row Facility Layout Problem in FMS Using a 3-opt Neighborhood. Technical Report, Institute of Management, Indian.
Simmons, D.M. (1969) One-Dimensional Space Allocation: An Ordering Algorithm. Operations Research, 17, 812-826. https://doi.org/10.1287/opre.17.5.812
Suresh, G. and Sahu, S. (1993) Multiobjective Facility Layout Using Simulated Annealing. International Journal of Production Economics, 32, 239-254. https://doi.org/10.1016/0925-5273(93)90071-R
Heragu, S.S. and Kusiak, A. (1991) Efficient Models for the Facility Layout Problem. European Journal of Operational Research, 53, 1-13. https://doi.org/10.1016/0377-2217(91)90088-D
Koopmans, T.C. and Beckmann, M. (1957) Assignment Problems and the Location of Economic Activities. Journal of the Econometric Society, 25, 53-76. https://doi.org/10.2307/1907742
Picard, J.C. and Queyranne, M. (1981) On the One-Dimensional Space Allocation Problem. Operations Research, 29, 371-391. https://doi.org/10.1287/opre.29.2.371
Love, R. and Wong, J. (1976) On Solving a One-Dimensional Space Allocation Problem with Integer Programming. INFOR: Information Systems and Operational Research, 14, 139-143. https://doi.org/10.1080/03155986.1976.11731633
Kumar, K.R., Hadjinicola, G.C. and Lin, T.L. (1995) A Heuristic Procedure for the Single-Row Facility Layout Problem. European Journal of Operational Research, 87, 65-73. https://doi.org/10.1016/0377-2217(94)00062-H
Amaral, A.R. (2006) On the Exact Solution of a Facility Layout Problem. European Journal of Operational Research, 173, 508-518. https://doi.org/10.1016/j.ejor.2004.12.021
Amaral, A.R. (2009) A New lower Bound for the Single Row Facility Layout Problem. Discrete Applied Mathematics, 157, 183-190. https://doi.org/10.1016/j.dam.2008.06.002
Keller, B. and Buscher, U. (2015) Single Row Layout Models. European Journal of Operational Research, 245, 629-644. https://doi.org/10.1016/j.ejor.2015.03.016
Amaral, A.R. and Letchford, A.N. (2013) A Polyhedral Approach to the Single Row Facility Layout Problem. Mathematical programming, 141, 453-477. https://doi.org/10.1007/s10107-012-0533-z
Yen, G. (2008) Cutting-Plane Separation Strategies for Semidefinite Programming Models to Solve Single-Row Facility Layout Problems. University of Waterloo, Waterloo.
Anjos, M.F., Kennings, A. and Vannelli, A. (2005) A Semidefinite Optimization Approach for the Single-Row Layout Problem with Unequal Dimensions. Discrete Optimization, 2, 113-122. https://doi.org/10.1016/j.disopt.2005.03.001
Anjos, M.F. and Vannelli, A. (2008) Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes. INFORMS Journal on Computing, 20, 611-617. https://doi.org/10.1287/ijoc.1080.0270
Amaral, A.R. (2008) An Exact Approach to the One-Dimensional Facility Layout Problem. Operations Research, 56, 1026-1033. https://doi.org/10.1287/opre.1080.0548
Azadeh, A., Roozbahani, M.N. and Moghaddam, M. (2013) Optimisation of Complex and Large-Sized Single-Row Facility Layout Problems with a Unique Hybrid Meta-Heuristic Framework. International Journal of Operational Research, 16, 38-67. https://doi.org/10.1504/IJOR.2013.050539
Rubio-Sánchez, M., Gallego, M., Gortázar, F. and Duarte, A. (2016) GRASP with Path Relinking for the Single Row Facility Layout Problem. Knowledge-Based Systems, 106, 1-13. https://doi.org/10.1016/j.knosys.2016.05.030
Anjos, M.F. and Yen, G. (2009) Provably Near-Optimal Solutions for Very Large Single-Row Facility Layout Problems. Optimization Methods and Software, 24, 805- 817. https://doi.org/10.1080/10556780902917735
Anjos, M.F. and Vannelli, A. (2006) Globally Optimal Solutions for Large Single- Row Facility Layout Problems. University of Waterloo, Waterloo.
Anjos, M.F. and Vannelli, A. (2006) On the Computational Performance of a Semidefinite Programming Approach to Single Row Layout Problems. In: Hans-Dietrich, H., KopferJörn, H. and Schönberger, J., Eds., Operations Research Proceedings 2005, Bremen, 277-282. https://doi.org/10.1007/3-540-32539-5_44
Sanjeevi, S. and Kianfar, K. (2010) A Polyhedral Study of Triplet Formulation for Single Row Facility Layout Problem. Discrete Applied Mathematics, 158, 1861- 1867. https://doi.org/10.1016/j.dam.2010.07.005
Kothari, R. and Ghosh, D. (2012) A Competitive Genetic Algorithm for Single Row Facility Layout. Technical Report, Indian Institute of Management, India.
Ozcelik, F. (2012) A Hybrid Genetic Algorithm for the Single Row Layout Problem. International Journal of Production Research, 50, 5872-5886. https://doi.org/10.1080/00207543.2011.636386
Datta, D., Amaral, A.R. and Figueira, J.R. (2011) Single Row Facility Layout Problem Using a Permutation-Based Genetic Algorithm. European Journal of Operational Research, 213, 388-394. https://doi.org/10.1016/j.ejor.2011.03.034
Ponnambalam, S. and Ramkumar, V. (2001) A Genetic Algorithm for the Design of a Single-Row Layout in Automated Manufacturing Systems. The International Journal of Advanced Manufacturing Technology, 18, 512-519.
Kothari, R. and Ghosh, D. (2014) An Efficient Genetic Algorithm for Single Row Facility Layout. Optimization Letters, 8, 679-690. https://doi.org/10.1007/s11590-012-0605-2
Ku, M.Y., Hu, M.H. and Wang, M.J. (2011) Simulated Annealing Based Parallel Genetic Algorithm for Facility Layout Problem. International Journal of Production Research, 49, 1801-1812. https://doi.org/10.1080/00207541003645789
Utamima, A. and Ou-Yang, C. (2012) Solving Single Row Facility Layout Problem using Extended Artificial Chromosome Genetic Algorithm. Journal of Technology, 27, 189-194.
Büyüksaatçı, S. (2015) Bat Algorithm Application for the Single Row Facility Layout Problem. In: Yang, X.S., Ed., Recent Advances in Swarm Intelligence and Evolutionary Computation, Springer, Berlin, 101-120. https://doi.org/10.1007/978-3-319-13826-8_6
Guan, J. and 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, 899-909. https://doi.org/10.1016/j.ejor.2015.08.014
Solimanpur, M., Vrat, P. and Shankar, R. (2005) An Ant Algorithm for the Single Row Layout Problem in Flexible Manufacturing Systems. Computers & Operations Research, 32, 583-598. https://doi.org/10.1016/j.cor.2003.08.005
Clauss, M., Bernt, M. and Middendorf, M. (2013) A Common Interval Guided ACO Algorithm for Permutation Problems. 2013 IEEE Symposium on Swarm Intelligence (SIS), Singapore, 16-19 April 2013, 64-71.
Samarghandi, H. and Eshghi, K. (2009) An Efficient Tabu Algorithm for Solving the Single Row Facility Layout Problem. European Journal of Operational Research, 205, 98-105.
Samarghandi, H. and Eshghi, K. (2010) An Efficient Tabu Algorithm for the Single Row Facility Layout Problem. European Journal of Operational Research, 205, 98-105. https://doi.org/10.1016/j.ejor.2009.11.034
Kothari, R. and Ghosh, D. (2013) Tabu Search for the Single Row Facility Layout Problem Using Exhaustive 2-opt and Insertion Neighborhoods. European Journal of Operational Research, 224, 93-100. https://doi.org/10.1016/j.ejor.2012.07.037
Ahonen, H., Alvarenga, A.G. and Amaral, A. (2014) Simulated Annealing and Tabu Search Approaches for the Corridor Allocation Problem. European Journal of Operational Research, 232, 221-233. https://doi.org/10.1016/j.ejor.2013.07.010
Yu, M., Zuo, X. and Murray, C.C. (2014) A Tabu Search Heuristic for the Single Row Layout Problem with Shared Clearances. Proceedings of the IEEE Congress on Evolutionary Computation (CEC), Beijing, 6-11 July 2014, 819-825.
Lenin, N., Kumar, S., Ravindran, D. and Islam, M.N. (2014) A Tabu Search for Multi-Objective Single Row Facility Layout Problem. Journal of Advanced Manufacturing Systems, 13, 17-40. https://doi.org/10.1142/S0219686714500024
Maadi, M., Javidnia, M. and Ghasemi, M. (2016) Applications of Two New Algorithms of Cuckoo Optimization and Forest Optimization for Solving Single Row Facility Layout Problem (SRFLP). Journal of AI and Data Mining, 4, 35-48. https://doi.org/10.5829/idosi.JAIDM.2016.04.01.05
Ning, X. and Li, P. (2018) A Cross-Entropy Approach to the Single Row Facility Layout Problem. International Journal of Production Research, 56, 3781-3794. https://doi.org/10.1080/00207543.2017.1399221
Samarghandi, H., Taabayan, P. and Jahantigh, F.F. (2010) A Particle Swarm Optimization for the Single Row Facility Layout Problem. Computers & Industrial Engineering, 58, 529-534. https://doi.org/10.1016/j.cie.2009.11.015
Ou-Yang, C. and Utamima, A. (2013) Hybrid Estimation of Distribution Algorithm for Solving Single Row Facility Layout Problem. Computers & Industrial Engineering, 66, 95-103. https://doi.org/10.1016/j.cie.2013.05.018
Kaveh, A. and Safari, H. (2014) Charged System Search Adopted for Solution of Traveling Salesman Problem: An Application to Single-Row Facility Layout Problem. International Journal of Civil Engineering, 12, 363-370.
Kothari, R., and Ghosh, D. (2012) A Lin-Kernighan Heurisitic for Single Row Facility Layout. Technical Report, Indian Institute of Management, India.
Amaral, A.R. (2008) Enhanced Local Search Applied to the Single-Row Facility Layout Problem. Brazilian Symposium on Operations Research, 1638-1647.
Ghosh, D. (2011) An Exponential Neighbourhood Local Search Algorithm for the Single Row Facility Location Problem. Technical Report, Indian Institute of Management, India.
Palubeckis, G. (2015) Fast Local Search for Single Row Facility Layout. European Journal of Operational Research, 246, 800-814. https://doi.org/10.1016/j.ejor.2015.05.055
Kothari, R. and Ghosh, D. (2012) Path Relinking for Single Row Facility Layout. Technical Report, Indian Institute of Management, India.
Teo, Y.T. and Ponnambalam, S. (2008) A Hybrid ACO/PSO Heuristic to Solve Single Row Layout Problem. IEEE International Conference on Automation Science and Engineering, Hong Kong, 23-26 August 2008, 597-602.
Lian, K., Zhang, C., Gao, L. and Shao, X. (2011) Single Row Facility Layout Problem Using an Imperialist Competitive Algorithm. Proceedings of the 41st International Conference on Computers & Industrial Engineering, Los Angeles, 23-25 October 2011, 578-586.
Kamali, H.R. (2015) A Hybrid Simulated Annealing algorithm for Single Row Facility Layout Problem. International Journal of Industrial Engineering & Production Research, 26, 243-253.
Ulutas, B.H. (2013) Assessing the Performance of Two Bioinspired Algorithms to Solve Single-Row Layout Problem. International Journal of Manufacturing Engineering, 2013, Article ID: 265904. https://doi.org/10.1155/2013/265904
Hosseini-Nasab, H. and Emami, L. (2012) A Hybrid Clonal Selection for the Single Row Facility Layout Problem with Unequal Dimensions. iBusiness, 4, 216-221. https://doi.org/10.4236/ib.2012.43027
Palubeckis, G. (2017) Single Row Facility Layout Using Multi-Start Simulated Annealing. Computers & Industrial Engineering, 103, 1-16. https://doi.org/10.1016/j.cie.2016.09.026
Palubeckis, G. (2015) Fast Simulated Annealing for Single-Row Equidistant Facility Layout. Applied Mathematics and Computation, 263, 287-301. https://doi.org/10.1016/j.amc.2015.04.073
Amaral, A.R. (2019) A Mixed-Integer Programming Formulation for the Double Row Layout of Machines in Manufacturing Systems. International Journal of Production Research, 57, 34-47. https://doi.org/10.1080/00207543.2018.1457811
Hungerländer, P. (2014) Single-Row Equidistant Facility Layout as a Special Case of Single-Row Facility Layout. International Journal of Production Research, 52, 1257- 1268. https://doi.org/10.1080/00207543.2013.828163
Commander, C.W. (2005) A Survey of the Quadratic Assignment Problem, with Applications. Morehead Electronic Journal of Applicable Mathematics, 4, 1-15.
Rendl, F. and Wolkowicz, H. (1992) Applications of Parametric Programming and Eigenvalue Maximization to the Quadratic Assignment Problem. Mathematical Programming, 53, 63-78. https://doi.org/10.1007/BF01585694
Yang, X.S. and Deb, S. (2009) Cuckoo Search via Lévy Flights. 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC 2009), 210-214.
Roy, S. and Chaudhuri, S.S. (2013) Cuckoo Search Algorithm Using Lévy Flight: A Review. International Journal of Modern Education and Computer Science, 5, 10-15. https://doi.org/10.5815/ijmecs.2013.12.02
Kothari, R. and Ghosh, D. (2014) A Scatter Search Algorithm for the Single Row Facility Layout Problem. Journal of Heuristics, 20, 125-142. https://doi.org/10.1007/s10732-013-9234-x