Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Mathematical formulation and two-phase optimisation methodology for the constrained double-row layout problem

  • Original Article
  • Published:
Neural Computing and Applications Aims and scope Submit manuscript

Abstract

The double-row layout problem (DRLP) was previously investigated as an unconstrained optimisation problem without enforcing any limits on the arrangement of the machines. However, in reality, a DRLP is required to respect certain facility constraints imposed on the arrangement of its machines. To address these limits in the scientific literature, we originally proposed a constrained DRLP (cDRLP). A mixed-integer linear programming model with three types of constraints: positioning, ordering, and relation, is constructed for the cDRLP. We decompose the cDRLP into two subproblems: a combinatorial optimisation problem and a continuous optimization problem. To further deal with larger instances, a two-phase methodology is designed to solve the cDRLP. In our algorithm, the differential evolution with a novel discrete framework is applied to seek local and global feasible solutions. Finally, a series of benchmark instances obtained from the literature are added to meet the constraint requirements of our developed cDRLP, and these 40 test instances with different sizes (n = 9 ~ 42) are employed to assess the performance of our proposed methodology. The results of computational experiments tested clearly demonstrate that our proposed two-phase optimisation methodology is effective for handling the problem considered and also help in producing good quality solutions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Ahmadi A, Pishvaee MS, Jokar MRA (2017) A survey on multi-floor facility layout problems. Comput Ind Eng 107:158–170. https://doi.org/10.1016/j.cie.2017.03.015

    Article  Google Scholar 

  2. Hosseini S, Al Khaled A, Vadlamani S (2014) Hybrid imperialist competitive algorithm, variable neighborhood search, and simulated annealing for dynamic facility layout problem. Neural Comput Appl 25(7–8):1871–1885. https://doi.org/10.1007/s00521-014-1678-x

    Article  Google Scholar 

  3. Kaveh M, Dalfard VM, Amiri S (2014) A new intelligent algorithm for dynamic facility layout problem in state of fuzzy constraints. Neural Comput Appl 24(5):1179–1190. https://doi.org/10.1007/s00521-013-1339-5

    Article  Google Scholar 

  4. Salas-Morera L, Garcia-Hernandez L, Antoli-Cabrera A, Carmona-Munoz C (2020) Using eye-tracking into decision makers evaluation in evolutionary interactive UA-FLP algorithms. Neural Comput Appl 32(17):13747–13757. https://doi.org/10.1007/s00521-020-04781-2

    Article  Google Scholar 

  5. Ou-Yang C, Utanilma A (2013) Hybrid estimation of distribution algorithm for solving single row facility layout problem. Comput Ind Eng 66(1):95–103. https://doi.org/10.1016/j.cie.2013.05.018

    Article  Google Scholar 

  6. Leno IJ, Sankar SS, Ponnambalam SG (2018) MIP model and elitist strategy hybrid GA-SA algorithm for layout design. J Intell Manuf 29(2):369–387. https://doi.org/10.1007/s10845-015-1113-x

    Article  Google Scholar 

  7. Hungerländer P, Anjos MF (2015) A semidefinite optimization-based approach for global optimization of multi-row facility layout. Eur J Oper Res 245(1):46–61. https://doi.org/10.1016/j.ejor.2015.02.049

    Article  MathSciNet  MATH  Google Scholar 

  8. Liu ZC, Hou LY, Shi YJ, Zheng XJ, Teng HF (2018) A co-evolutionary design methodology for complex AGV system. Neural Comput Appl 29(4):959–974. https://doi.org/10.1007/s00521-016-2495-1

    Article  Google Scholar 

  9. Sadrzadeh A (2012) A genetic algorithm with the heuristic procedure to solve the multi-line layout problem. Comput Ind Eng 62(4):1055–1064. https://doi.org/10.1016/j.cie.2011.12.033

    Article  Google Scholar 

  10. Wang KP, Gao L, Li XY (2020) A multi-objective algorithm for U-shaped disassembly line balancing with partial destructive mode. Neural Comput Appl 32(16):12715–12736. https://doi.org/10.1007/s00521-020-04721-0

    Article  Google Scholar 

  11. Heragu SS, Kusiak A (1988) Machine layout problem in flexible manufacturing systems. Oper Res 36(2):258–268. https://doi.org/10.1287/opre.36.2.258

    Article  Google Scholar 

  12. Chung J, Tanchoco JMA (2008) The double row layout problem. Int J Prod Res 48(3):709–727. https://doi.org/10.1080/00207540802192126

    Article  MATH  Google Scholar 

  13. Zhang ZQ, Murray CC (2012) A corrected formulation for the double row layout problem. Int J Prod Res 50(15):4220–4223. https://doi.org/10.1080/00207543.2011.603371

    Article  Google Scholar 

  14. Zuo XQ, Murray CC, Smith AE. (2012) An extended double row layout problem. The 12th International Material Handling Research Colloquium

  15. Amaral ARS (2013) Optimal solutions for the double row layout problem. Optim Lett 7(2):407–413. https://doi.org/10.1007/s11590-011-0426-8

    Article  MathSciNet  MATH  Google Scholar 

  16. Murray CC, Smith AE, Zhang ZQ (2013) An efficient local search heuristic for the double row layout problem with asymmetric material flow. Int J Prod Res 51(20):6129–6139. https://doi.org/10.1080/00207543.2013.803168

    Article  Google Scholar 

  17. Zuo XQ, Murray CC, Smith AE (2014) Solving an extended double row layout problem using multiobjective tabu search and linear programming. IEEE Trans Autom Sci Eng 11(4):1122–1132. https://doi.org/10.1109/tase.2014.2304471

    Article  Google Scholar 

  18. Zuo XQ, Murray CC, Smith AE (2016) Sharing clearances to improve machine layout. Int J Prod Res 54(14):4272–4285. https://doi.org/10.1080/00207543.2016.1142134

    Article  Google Scholar 

  19. Wang SL, Zuo XQ, Zhao XC. (2014) Solving dynamic double-row layout problem via an improved simulated annealing algorithm. 2014 Ieee Congress on Evolutionary Computation. New York: Ieee.

  20. Tang LL, Zuo XQ, Wang CL, Zhao XC, Ieee. (2015) A MOEA/D based approach for solving robust double row layout problem. 2015 Ieee Congress on Evolutionary Computation. New York: Ieee

  21. Wang SL, Zuo XQ, Liu XQ, Zhao XC, Li JQ (2015) Solving dynamic double row layout problem via combining simulated annealing and mathematical programming. Appl Soft Comput 37:303–310. https://doi.org/10.1016/j.asoc.2015.08.023

    Article  Google Scholar 

  22. Amaral ARS (2019) A mixed-integer programming formulation for the double row layout of machines in manufacturing systems. Int J Prod Res 57(1):34–47. https://doi.org/10.1080/00207543.2018.1457811

    Article  Google Scholar 

  23. Secchin LD, Amaral ARS (2019) An improved mixed-integer programming model for the double row layout of facilities. Optim Lett 13(1):193–199. https://doi.org/10.1007/s11590-018-1263-9

    Article  MathSciNet  MATH  Google Scholar 

  24. Gulsen M, Murray CC, Smith AE (2019) Double-row facility layout with replicate machines and split flows. Comput Oper Res 108:20–32. https://doi.org/10.1016/j.cor.2019.03.009

    Article  MathSciNet  MATH  Google Scholar 

  25. Fischer A, Fischer F, Hungerländer P (2019) New exact approaches to row layout problems. Math Program Comput 11(4):703–754. https://doi.org/10.1007/s12532-019-00162-6

    Article  MathSciNet  MATH  Google Scholar 

  26. Chae J, Regan AC (2020) A mixed integer programming model for a double row layout problem. Comput Ind Eng. https://doi.org/10.1016/j.cie.2019.106244

    Article  Google Scholar 

  27. Guan J, Lin G, Feng HB, Ruan ZQ (2020) A decomposition-based algorithm for the double row layout problem. Appl Math Model 77:963–979. https://doi.org/10.1016/j.apm.2019.08.015

    Article  MathSciNet  MATH  Google Scholar 

  28. Amaral ARS (2020) A heuristic approach for the double row layout problem. Ann Oper Res. https://doi.org/10.1007/s10479-020-03617-5

    Article  Google Scholar 

  29. Amaral ARS (2012) The corridor allocation problem. Comput Oper Res 39(12):3325–3330. https://doi.org/10.1016/j.cor.2012.04.016

    Article  MATH  Google Scholar 

  30. Kalita Z, Datta D (2014) Solving the bi-objective corridor allocation problem using a permutation-based genetic algorithm. Comput Oper Res 52:123–134. https://doi.org/10.1016/j.cor.2014.07.008

    Article  MathSciNet  MATH  Google Scholar 

  31. Liu SL, Zhang ZQ, Guan C, Gong JH (2020) An improved fireworks algorithm for the corridor allocation problem with facility depth. Control and Decision 35(01):45–54. https://doi.org/10.13195/j.kzyjc.2018.0720

    Article  Google Scholar 

  32. Kalita Z, Datta D, Palubeckis G (2019) Bi-objective corridor allocation problem using a permutation-based genetic algorithm hybridized with a local search technique. Soft Comput 23(3):961–986. https://doi.org/10.1007/s00500-017-2807-0

    Article  Google Scholar 

  33. Amaral ARS (2013) A parallel ordering problem in facilities layout. Comput Oper Res 40(12):2930–2939. https://doi.org/10.1016/j.cor.2013.07.003

    Article  MathSciNet  MATH  Google Scholar 

  34. Yang XH, Cheng WM, Smith AE, Amaral ARS (2020) An improved model for the parallel row ordering problem. J Operat Res Soc 71(3):475–490. https://doi.org/10.1080/01605682.2018.1556570

    Article  Google Scholar 

  35. Gong J, Zhang Z, Liu J, Guan C, Liu S (2021) Hybrid algorithm of harmony search for dynamic parallel row ordering problem. J Manuf Syst 58:159–175. https://doi.org/10.1016/j.jmsy.2020.11.014

    Article  Google Scholar 

  36. Liu S, He X, Guan C, Gong J, Zhang Z. (2021) Mixed-integer programming formulation for constrained double-row Layout Problem. 2021 The 8th International Conference on Industrial Engineering and Applications (Europe). Barcelona, Spain: Association for Computing Machinery pp. 159–65

  37. Palubeckis G (2015) Fast simulated annealing for single-row equidistant facility layout. Appl Math Comput 263:287–301. https://doi.org/10.1016/j.amc.2015.04.073

    Article  MathSciNet  MATH  Google Scholar 

  38. Anjos MF, Fischer A, Hungerlander P (2018) Improved exact approaches for row layout problems with departments of equal length. Eur J Oper Res 270(2):514–529. https://doi.org/10.1016/j.ejor.2018.04.008

    Article  MathSciNet  MATH  Google Scholar 

  39. Jankovits I, Luo CM, Anjos MF, Vannelli A (2011) A convex optimisation framework for the unequal-areas facility layout problem. Eur J Oper Res 214(2):199–215. https://doi.org/10.1016/j.ejor.2011.04.013

    Article  MathSciNet  MATH  Google Scholar 

  40. Asl AD, Wong KY (2017) Solving unequal-area static and dynamic facility layout problems using modified particle swarm optimization. J Intell Manuf 28(6):1317–1336. https://doi.org/10.1007/s10845-015-1053-5

    Article  Google Scholar 

  41. Chae J, Regan AC (2016) Layout design problems with heterogeneous area constraints. Comput Ind Eng 102:198–207. https://doi.org/10.1016/j.cie.2016.10.016

    Article  Google Scholar 

  42. Mohammadi M, Forghani K (2016) Designing cellular manufacturing systems considering S-shaped layout. Comput Ind Eng 98:221–236. https://doi.org/10.1016/j.cie.2016.05.041

    Article  Google Scholar 

  43. Liu JF, Liu SY, Liu ZX, Li B (2020) Configuration space evolutionary algorithm for multi-objective unequal-area facility layout problems with flexible bays. Appl Soft Comput. https://doi.org/10.1016/j.asoc.2019.106052

    Article  Google Scholar 

  44. Sahin R, Ertogral K, Turkbey O (2010) A simulated annealing heuristic for the dynamic layout problem with budget constraint. Comput Ind Eng 59(2):308–313. https://doi.org/10.1016/j.cie.2010.04.013

    Article  Google Scholar 

  45. Baykasoglu A, Dereli T, Sabuncu I (2006) An ant colony algorithm for solving budget constrained and unconstrained dynamic facility layout problems. Omega-Int J Manag Sci 34(4):385–396. https://doi.org/10.1016/j.omega.2004.12.001

    Article  Google Scholar 

  46. Kalita Z, Datta D (2018) A constrained single-row facility layout problem. Int J Adv Manuf Technol 98(5–8):2173–2184. https://doi.org/10.1007/s00170-018-2370-6

    Article  Google Scholar 

  47. Kalita Z, Datta D (2020) The constrained single-row facility layout problem with repairing mechanisms. In: Bennis F, Bhattacharjya RK (eds) Nature-inspired methods for metaheuristics optimization: algorithms and applications in science and engineering. Springer International Publishing, Cham, pp 359–383

    Chapter  Google Scholar 

  48. Liu SL, Zhang ZQ, Guan C, Zhu LX, Zhang M, Guo P (2021) An improved fireworks algorithm for the constrained single-row facility layout problem. Int J Prod Res 59(8):2309–2327. https://doi.org/10.1080/00207543.2020.1730465

    Article  Google Scholar 

  49. Kalita Z, Datta D (2020) Corridor allocation as a constrained optimization problem using a permutation-based multi-objective genetic algorithm. In: Bennis F, Bhattacharjya RK (eds) Nature-inspired methods for metaheuristics optimization: algorithms and applications in science and engineering. Springer International Publishing, Cham, pp 335–358

    Chapter  Google Scholar 

  50. Liu JQ, Zhang ZQ, Chen F, Liu SL, Zhu LX (2020) A novel hybrid immune clonal selection algorithm for the constrained corridor allocation problem. J Intell Manuf. https://doi.org/10.1007/s10845-020-01693-9

    Article  Google Scholar 

  51. Liu S, Zhang Z, Guan C, Liu J, Dewil R (2021) Mathematical formulation and a new metaheuristic for the constrained double-floor corridor allocation problem. J Manuf Syst 61:155–170. https://doi.org/10.1016/j.jmsy.2021.08.013

    Article  Google Scholar 

  52. Zhang ZQ, Cheng WM (2014) Decomposition strategies and heuristic for double row layout problem. Comput Integr Manuf Syst 20(3):559–568

    Google Scholar 

  53. Anjos MF, Fischer A, Hungerländer P. (2016) Solution approaches for the double-row equidistant facility layout problem. Springer International Publishing

  54. Zuo XQ, Liu XQ, Zhang QF, Li WP, Wan X, Zhao XC (2019) MOEA/D with linear programming for double row layout problem with Center-Islands. IEEE Trans Cybernet. https://doi.org/10.1109/tcyb.2019.2937115

    Article  Google Scholar 

  55. Salum L (2000) The cellular manufacturing layout problem. Int J Prod Res 38(5):1053–1069. https://doi.org/10.1080/002075400189013

    Article  MATH  Google Scholar 

  56. Bazargan-Lari M, Kaebernick H, Harraf A (2000) Cell formation and layout designs in a cellular manufacturing environment - a case study. Int J Prod Res 38(7):1689–1709. https://doi.org/10.1080/002075400188807

    Article  MATH  Google Scholar 

  57. Diego-Mas JA, Santamarina-Siurana MC, Alcaide-Marzal J, Cloquell-Ballester VA (2009) Solving facility layout problems with strict geometric constraints using a two-phase genetic algorithm. Int J Prod Res 47(6):1679–1693. https://doi.org/10.1080/00207540701666253

    Article  MATH  Google Scholar 

  58. Xiao Y, Seo Y, Seo M (2013) A two-step heuristic algorithm for layout design of unequal-sized facilities with input/output points. Int J Prod Res 51(14):4200–4222. https://doi.org/10.1080/00207543.2012.752589

    Article  Google Scholar 

  59. Paes FG, Pessoa AA, Vidal T (2017) A hybrid genetic algorithm with decomposition phases for the unequal area facility layout problem. Eur J Oper Res 256(3):742–756. https://doi.org/10.1016/j.ejor.2016.07.022

    Article  MathSciNet  MATH  Google Scholar 

  60. Guan C, Zhang ZQ, Liu SL, Gong JH (2019) Multi-objective particle swarm optimization for multi-workshop facility layout problem. J Manuf Syst 53:32–48. https://doi.org/10.1016/j.jmsy.2019.09.004

    Article  Google Scholar 

  61. Storn R, Price K (1997) Differential evolution - A simple and efficient heuristic for global optimization over continuous spaces. J Global Optim 11(4):341–359. https://doi.org/10.1023/A:1008202821328

    Article  MathSciNet  MATH  Google Scholar 

  62. Das S, Suganthan PN (2011) Differential evolution: a survey of the State-of-the-Art. IEEE Trans Evol Comput 15(1):4–31. https://doi.org/10.1109/Tevc.2010.2059031

    Article  Google Scholar 

  63. Ho-Huu V, Nguyen-Thoi T, Truong-Khac T, Le-Anh L, Vo-Duy T (2018) An improved differential evolution based on roulette wheel selection for shape and size optimization of truss structures with frequency constraints. Neural Comput Appl 29(1):167–185. https://doi.org/10.1007/s00521-016-2426-1

    Article  Google Scholar 

  64. Tanabe R, Fukunaga A (2020) Reviewing and benchmarking parameter control methods in differential evolution. Ieee Trans Cybernet 50(3):1170–1184. https://doi.org/10.1109/tcyb.2019.2892735

    Article  Google Scholar 

  65. Gong WY, Cai ZH, Liang DW (2015) Adaptive ranking mutation operator based differential evolution for constrained optimization. Ieee Trans Cybernet 45(4):716–727. https://doi.org/10.1109/tcyb.2014.2334692

    Article  Google Scholar 

  66. Tan YY, Jiao YC, Li H, Wang XK (2012) A modification to MOEA/D-DE for multiobjective optimization problems with complicated Pareto sets. Inf Sci 213:14–38. https://doi.org/10.1016/j.ins.2012.06.007

    Article  MathSciNet  MATH  Google Scholar 

  67. Halder U, Das S, Maity D (2013) A Cluster-based differential evolution algorithm with external archive for optimization in dynamic environments. Ieee Trans Cybernet 43(3):881–897. https://doi.org/10.1109/tsmcb.2012.2217491

    Article  Google Scholar 

  68. Yuan SP, Li TK, Wang BL (2020) A discrete differential evolution algorithm for flow shop group scheduling problem with sequence-dependent setup and transportation times. J Intell Manuf. https://doi.org/10.1007/s10845-020-01580-3

    Article  Google Scholar 

  69. Ting CK, Su CH, Lee CN (2010) Multi-parent extension of partially mapped crossover for combinatorial optimization problems. Expert Syst Appl 37(3):1879–1886. https://doi.org/10.1016/j.eswa.2009.07.082

    Article  Google Scholar 

  70. Simmons D (1969) One-dimensional space allocation an ordering algorithm. Operat Res 17(5):812–826

    Article  MathSciNet  Google Scholar 

  71. Amaral ARS (2006) On the exact solution of a facility layout problem. Eur J Oper Res 173(2):508–518. https://doi.org/10.1016/j.ejor.2004.12.021

    Article  MathSciNet  MATH  Google Scholar 

  72. Anjos MF, Yen G (2009) Provably near-optimal solutions for very large single-row facility layout problems. Optimiz Methods & Softw 24(4–5):805–817. https://doi.org/10.1080/10556780902917735

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This research was partially supported by the National Natural Science Foundation of China (No.51205328, 51675450), Sichuan Science and Technology Programme (No. 2019YFG0285), Youth Foundation for Humanities, Social Sciences of Ministry of Education of China (No. 18YJC630255) and China Scholarship Council (NO.202007000124).

Author information

Authors and Affiliations

  1. School of Mechanical Engineering, Southwest Jiaotong University, Chengdu, 610031, China

    Silu Liu, Zeqiang Zhang, Chao Guan, Junqi Liu & Juhua Gong

  2. Centre for Industrial Management/Traffic & Infrastructure, KU Leuven, 3000, Leuven, Belgium

    Silu Liu, Chao Guan & Reginald Dewil

  3. Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province, Chengdu, 610031, China

    Silu Liu, Zeqiang Zhang, Junqi Liu & Juhua Gong

Authors
  1. Silu Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zeqiang Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Chao Guan
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Junqi Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Juhua Gong
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Reginald Dewil
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zeqiang Zhang.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Liu, S., Zhang, Z., Guan, C. et al. Mathematical formulation and two-phase optimisation methodology for the constrained double-row layout problem. Neural Comput & Applic 34, 6907–6926 (2022). https://doi.org/10.1007/s00521-021-06817-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00521-021-06817-7

Keywords

Search

Navigation