Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

A constrained single-row facility layout problem

  • ORIGINAL ARTICLE
  • Published:
The International Journal of Advanced Manufacturing Technology Aims and scope Submit manuscript

Abstract

The single-row facility layout problem (SRFLP) seeks the arrangement of given facilities along a straight row in such a way that the total material handling cost among the facilities is minimized. The SRFLP is studied till date as an unconstrained problem allowing the placement of the facilities in any location in any order without any restriction. However, a practical SRFLP instance may need to satisfy different types of constraints imposed on the placement of its facilities, e.g., the operation sequencing with precedence constraints in a process planning can be modeled as a SRFLP with ordering constraints. Such a SRFLP model, named as the constrained SRFLP (cSRFLP), is introduced here by instructing to place some facilities in fixed positions, and/or in specified orders with or without allowing the placement of other facilities in between two ordered facilities. Since it would be computationally too expensive for any search technique to satisfy such constraints, a permutation-based genetic algorithm (pGA), named as the constrained pGA (cpGA in short), is also proposed with some specially designed operators for exploring only feasible solutions of cSRFLP. In the numerical experimentation, investigating three case studies of the operation sequencing problem of process planning as cSRFLP instances, the cpGA found new sequences of operations with the same best-known objective value for the smaller-size case study, while improved the best-known solutions of the other two case studies of larger sizes. Further, transforming some large-size benchmark instances of SRFLP into cSRFLP, the cpGA found marginally inferior solutions than their best-known SRFLP solutions, which is obvious due to the constraints imposed in the transformed cSRFLP instances.

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

Similar content being viewed by others

References

  1. Aiello G, Scalia GL, Enea M (2012) A multi objective genetic algorithm for the facility layout problem based upon slicing structure encoding. Expert Syst Appl 39:10352–10358

    Article  Google Scholar 

  2. Anjos MF, Vannelli A (2008) Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes. INFORMS J Comput 20:611–617

    Article  MathSciNet  MATH  Google Scholar 

  3. Anjos MF, Yen G (2009) Provably near-optimal solutions for very large single-row facility layout problems. Optim Method Softw 24(4):805–817

    Article  MathSciNet  MATH  Google Scholar 

  4. Ayad AR, Awad HA, Yassin A (2013) Parametric analysis for genetic algorithms handling parameters. Alexandria Eng J 52:99–111

    Article  Google Scholar 

  5. Branke J (2012) Evolutionary optimization in dynamic environments. Hardcover, ISBN: 978-0-7923-7631-6. Springer, US

    Google Scholar 

  6. Datta D, Amaral ARS, Figueira JR (2011) Single row facility layout problem using a permutation-based genetic algorithm. Eur J Oper Res 213(2):388–394

    Article  MathSciNet  MATH  Google Scholar 

  7. Datta D, Figueira JR (2011) Graph partitioning by multi-objective real-valued metaheuristics: a comparative study. Appl Soft Comput 11(5):3976–3987

    Article  Google Scholar 

  8. Deb K (2001) Multi-objective optimization using evolutionary algorithms. Wiley, Chichester

    MATH  Google Scholar 

  9. Deb K, Agarwal S, Pratap A, Meyarivan T (2002) A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197

    Article  Google Scholar 

  10. Drira A, Pierreval H, Hajri-Gabouj S (2007) Facility layout problems: a survey. Annu Rev Control 31:255–267

    Article  Google Scholar 

  11. Heragu SS, Alfa AS (1992) Experiment analysis of simulated annealing based algorithms for the layout problem. Eur J Oper Res 57(2):190–202

    Article  MATH  Google Scholar 

  12. Heragu SS, Kusiak A (1988) Machine layout problem in flexible manufacturing systems. Oper Res 36:258–268

    Article  Google Scholar 

  13. Huang J, Lu X, Zhang G, Qu J (2014) Study on the rheological, thermal and mechanical properties of thermoplastic polyurethane/poly (butylene terephthalate) blends. Polym Test 36:69–74

    Article  Google Scholar 

  14. Huang W, Lin W, Xu S (2017) Application of graph theory and hybrid GA-SA for operation sequencing in a dynamic workshop environment. Comput-Aid Des Appl 14(2):148–159

    Article  Google Scholar 

  15. Javadi G, Aminian E (2017) A new method for tuning mutation and crossover rate in genetic algorithm. In: Proceedings of the 9th International Conference on Machine Learning and Computing, ICMLC 2017. ACM, New York, pp 217–220

  16. Kafashi S (2011) Integrated setup planning and operation sequencing (ISOS) using genetic algorithm. Int J Adv Manuf Technol 56(5):589–600

    Article  Google Scholar 

  17. Kothari R, Ghosh D (2013) Tabu search for the single row facility layout problem using exhaustive 2-opt and insertion neighborhoods. Eur J Oper Res 224(1):93–100

    Article  MathSciNet  MATH  Google Scholar 

  18. Kothari R, Ghosh D (2014) A scatter search algorithm for the single row facility layout problem. J Heuristics 20(2):125– 142

    Article  Google Scholar 

  19. Krishna AG, Rao K (2006) Optimisation of operations sequence in CAPP using an ant colony algorithm. Int J Adv Manuf Technol 29(1–2):159–164

    Article  Google Scholar 

  20. Kumar KR, Hadjinicola GC, Lin TL (1995) A heuristic procedure for the single-row facility layout problem. Eur J Oper Res 87:65–73

    Article  MATH  Google Scholar 

  21. Kumar S, Asokan P, Kumanan S, Varma B (2008) Scatter search algorithm for single row layout problem in FMS. Advan Production Eng Manag 3:193–204

    Google Scholar 

  22. Lafou M, Mathieu L, Pois S, Alochet M (2016) Manufacturing system flexibility: sequence flexibility assessment. In: 49th CIRP Conference on Manufacturing System (CIRP CMS2016)

  23. Li X, Gao L, Wen X (2013) Application of an efficient modified particle swarm optimization algorithm for process planning. Int J Adv Manuf Technol 67(5–8):1355–1369

    Article  Google Scholar 

  24. Love RF, Wong JY (1976) On solving a single row space allocation problem with integer programming. INFOR 14:139–143

    MATH  Google Scholar 

  25. Luo G, Wen X, Li H, Ming W, Xie G (2017) An effective multi-objective genetic algorithm based on immune principle and external archive for multi-objective integrated process planning and scheduling. Int J Adv Manuf Technol 91(9–12):3145–3158

    Article  Google Scholar 

  26. Maadi M, Javidnia M, Ramezani R (2017) Modified Cuckoo Optimization Algorithm (MCOA) to solve Precedence Constrained Sequencing Problem (PCSP). Applied Intelligence. https://doi.org/10.1007/s10489-017-1022-0

  27. Miljković Z, Petrović M (2017) Application of modified multi-objective particle swarm optimisation algorithm for flexible process planning problem. Int J Comput Integr Manuf 30(2–3):271–291

    Article  Google Scholar 

  28. Müller J (2016) MISO: Mixed-integer surrogate optimization framework. Optim Eng 17(1):177–203

    Article  MathSciNet  MATH  Google Scholar 

  29. Nallakumarasamy G, Srinivasan PSS, Raja KV, Malayalamurthi R (2011) Optimization of operation sequencing in CAPP using simulated annealing technique (SAT). Int J Adv Manuf Technol 54(5–8):721–728

    Article  Google Scholar 

  30. Nguyen TT, Yang S, Branke J (2012) Evolutionary dynamic optimization: a survey of the state of the art. Swarm Evolutionary Comput 6:1–24

    Article  Google Scholar 

  31. Ozgormus E (2015) Optimization of block layout for grocery stores. PhD thesis. Auburn University, USA

    Google Scholar 

  32. Padgaonkar AS (2004) Modelling and analysis of the hospital facility layout problem Master’s thesis. Department of Industrial and Manufacturing Engineering, New Jersey Institute of Technology

  33. Petrović M, Mitić M, Vuković N, Miljković Z (2016) Chaotic particle swarm optimization algorithm for flexible process planning. Int J Adv Manuf Technol 85(9–12):2535–2555

    Article  Google Scholar 

  34. Picard J, Queyranne M (1981) On the one dimensional space allocation problem. Oper Res 29(2):371–391

    Article  MathSciNet  MATH  Google Scholar 

  35. Reddy SB (1999) Operation sequencing in CAPP using genetic algorithms. Int J Prod Res 37(5):1063–1074

    Article  MATH  Google Scholar 

  36. Samarghandi H, Eshghi K (2010) An efficient tabu algorithm for the single row facility layout problem. Eur J Oper Res 205:98–105

    Article  MathSciNet  MATH  Google Scholar 

  37. Samarghandi H, Taabayan P, Jahantigh FF (2010) A particle swarm optimization for the single row facility layout problem. Comput Industrial Eng 58:529–534

    Article  Google Scholar 

  38. Simmons DM (1969) Single row space allocation: an ordering algorithm. Oper Res 17(5):812–826

    Article  MATH  Google Scholar 

  39. Solimanpur M, Vrat P, Shankar R (2005) An ant algorithm for the single row layout problem in flexible manufacturing systems. Comput Oper Res 32:583–598

    Article  MATH  Google Scholar 

  40. Sugden SJ (1992) A class of direct search methods for nonlinear integer programming. PhD Thesis, Bond University, Australia

    Google Scholar 

  41. Wang W, Li Y, Huang L (2016) Rule and branch-and-bound algorithm based sequencing of machining features for process planning of complex parts. Journal of Intelligent Manufacturing. https://doi.org/10.1007/s10845-015-1181-y

  42. Wolpert DH, Macready WG (1997) No free lunch theorems for optimization. IEEE Trans Evol Comput 1 (1):67–82

    Article  Google Scholar 

  43. Yun Y, Chung H, Moon C (2013) Hybrid genetic algorithm approach for precedence-constrained sequencing problem. Comput Industr Eng 65(1):137–147

    Article  Google Scholar 

  44. Yun Y, Moon C (2011) Genetic algorithm approach for precedence-constrained sequencing problems. J Intell Manuf 22(3):379–388

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mechanical Engineering, School of Engineering, Tezpur University, Tezpur, 784028, India

    Zahnupriya Kalita & Dilip Datta

Authors
  1. Zahnupriya Kalita
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dilip Datta
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dilip Datta.

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

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00170-018-2370-6

Keywords

Search

Navigation