Skip to main content
SpringerLink
Log in

A linear programming embedded simulated annealing in the design of distributed layout with production planning and systems reconfiguration

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

Abstract

In this paper, a linear programming embedded simulated annealing algorithm for solving a comprehensive model in the design and operation of distributed layout -based manufacturing systems is presented. The mathematical model considered incorporates a number of important manufacturing attributes. These attributes include demand fluctuation, system reconfiguration, lot splitting, work load balancing, alternative routing, machine capability, tooling requirements, material handling cost, machine relocation cost, setup cost, inventory carrying cost, in-house production, and subcontracting costs. Optimal solutions for such comprehensive mathematical models can only be found for small size problems due to NP-complexity. To solve the model for large size problems, efficient meta-heuristic algorithm is required. The development of such an algorithm is the main contribution of this paper. Numerical examples are presented to demonstrate the computational performance of the developed algorithm and illustrate a challenge that may be encountered when one tries to embed a linear programming in a metaheuristic.

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

Access this article

Log in via an institution

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. Ah kioon S, Bulgak AA, Bektas T (2009) Integrated cellular manufacturing system design with production planning and dynamic system reconfiguration. Eur J Oper Res 192:414–428

    Article  MathSciNet  MATH  Google Scholar 

  2. Asef-Vaziri A, Laporte G (2005) Loop based facility planning and material handling. Eur J Oper Res 164(1):1–11

    Article  MathSciNet  MATH  Google Scholar 

  3. Askin RG, Lundgren NH, Ciarallo F (1996) A material flow based evaluation of layout alternatives for agile manufacturing. Progress in Material Handling Research:71–90

  4. Balakrishnan J, Cheng CH (2005) Dynamic cellular manufacturing under multiperiod planning horizons. J Manuf Technol Manag 16:516–530

    Article  Google Scholar 

  5. Balakrishnan J, Cheng CH, Conway DG (2000) An improved pair-wise exchange heuristic for the dynamic plant layout problem. Int J Prod Res 38:3067–3077

    Article  Google Scholar 

  6. Baykasoglu A (2003) Capability-based distributed layout approach for virtual manufacturing cells. Int J Prod Res 41(11):2597–2618

    Article  Google Scholar 

  7. Baykasoglu A, Dereli T, Sabuncu I (2006) An ant colony algorithm for solving budget constrained and unconstrained dynamic facility layout problems. Omega 34:385–396

    Article  Google Scholar 

  8. Baykasoğlu A, Göçken M (2010) Capability-based distributed layout and its simulation based analyses. J Intell Manuf 21(4):471–485

    Article  Google Scholar 

  9. Benjaafar S, Heragu SS, Irani SA (2002) Next generation factory layouts: research challenges and recent progress. Interfaces 32:58–77

    Article  Google Scholar 

  10. Benjaafar S, Sheikhzadeh S (2000) Design of flexible plant layouts. IIE Trans 32:309–322

    Google Scholar 

  11. Blum C, Puchinger J, Raidl GR, Roli A (2006) Hybrid metaheuristics in combinatorial optimization: A survey

  12. Chen M (1998) A mathematical programming model for system reconfiguration in a dynamic cellular manufacturing environment. Ann Oper Res 74:109–128

    Article  MATH  Google Scholar 

  13. Defersha F, Chen M (2008) A linear programming embedded genetic algorithm for an integrated cell formation and lot sizing considering product quality. Eur J Oper Res 187:46–69

    Article  MATH  Google Scholar 

  14. Defersha FM, Chen M (2006a) A comprehensive mathematical model for the design of cellular manufacturing systems. Int J Prod Econ 103:767–783

    Article  Google Scholar 

  15. Defersha FM, Chen M (2006b) Machine cell formation using a mathematical model and a genetic-algorithm-based heuristic. Int J Prod Res 44:2421–2444

    Article  MATH  Google Scholar 

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

    Article  Google Scholar 

  17. Drolet J (1989) Scheduling virtual cellular manufacturing systems. Ph.D. thesis, School of Industrial Engineering. Purdue University, West Lafayette

    Google Scholar 

  18. Dunker T, Radons G, Westkämper E (2005) Combining evolutionary computation and dynamic programming for solving a dynamic facility layout problem. Eur J Oper Res 165:55–69

    Article  MathSciNet  MATH  Google Scholar 

  19. Glover F, Kochenberger GA (2003) Handbook of metaheuristics. Kluwer Academic Publisher, Dordrecht

    Book  MATH  Google Scholar 

  20. Goetz WG, Egbelu PJ (1990) Guide path design and location of load pick-up/drop-off points for an automated guided vehicle system. Int J Prod Res 28(5):927–941

    Article  Google Scholar 

  21. Hamedi M, Esmaeilian G (2015) Functional and distributed layouts and their effectiveness on capability-based virtual cellular manufacturing systems performance. IEEE International Conference on Industrial Engineering and Operations Management. Dubai, United Arab Emirates (UAE)

  22. Hamedi M, Ismailand NB, Esmaeilian GR, Ariffin M (2012) Developing a method to generate semi-distributed layouts by genetic algorithm. Int J Prod Res 50(4):953–975

    Article  Google Scholar 

  23. Heragu SS, Kochhar JS (1994) Material handling issues in adaptive manufacturing systems. The Materials Handling Engineering Division 75th Anniversary Commemorative Volume. ASME, New York

    Google Scholar 

  24. Hodiya A (2015) A mathematical model and a simulated annealing algorithm for an integrated facility layout and cell formation. Master’s thesis. University of Guelph, Guelph

    Google Scholar 

  25. IBM (2015) IBM ILOG CPLEX Optimization studio CPLEX user’s manual, Version 12.6. Online Documentation

  26. Kirkpatrick S, Gelatt C, Vecchi M (1983) Optimization by simulated annealing. Science 220:671–680

    Article  MathSciNet  MATH  Google Scholar 

  27. Krishnan KK, Krishnamurthy V, Jithavech I, Motavalli S (2009) Simulation modeling and analysis of distributed and process layouts. California Journal of Operations Management 7(1):65–76

    Google Scholar 

  28. Lahmer M, Benjaafar S (2005) Design of distributed layouts. IIE Trans 37(4):303–318

    Article  Google Scholar 

  29. Lee S-Y, Lee K (1996) Synchronous and asynchronous parallel simulated annealing with multiple markov chains. IEEE Trans Parallel Distrib Sys 7:903–1007

    Google Scholar 

  30. McKendall AR, Shang J (2006) Hybrid ant systems for the dynamic facility layout problem. Comput Oper Res 33:790–803

    Article  MATH  Google Scholar 

  31. McKendall AR, Shang J, Kuppusamy S (2006) Simulated annealing heuristics for the dynamic facility layout problem. Comput Oper Res 33:2431–2444

    Article  MathSciNet  MATH  Google Scholar 

  32. Montreuil B, Venkatadri U (1991) Strategic interpolative design of dynamic manufacturing systems layout. Manag Sci 37(6):682–694

    Article  MATH  Google Scholar 

  33. Moslemipour G, Lee TS, Rilling D (2012) A review of intelligent approaches for designing dynamic and robust layouts in flexible manufacturing systems. Int J Adv Manuf Technol 60:11–27

    Article  Google Scholar 

  34. Mungwattana A (2000) Design of cellular manufacturing systems for dynamic and uncertain production requirements with presence of routing flexibility. Ph.D. thesis. Virginia Polytechnic Institute and State University, Blackburg

    Google Scholar 

  35. Nageshwaraniyer S, Khilwani N, Tiwari M, Shankar R, Ben-Arieh D (2013) Solving the design of distributed layout problem using forecast windows: a hybrid algorithm approach. Robot Comput Integr Manuf 29 (1):128–138

    Article  Google Scholar 

  36. Nsakanda A, Diaby M, WL P (2006) Hybrid genetic approach for solving large scale capacitated cell formation problem with multiple routings. Eur J Oper Res 171:1058–1070

    Article  Google Scholar 

  37. Pillai VM, Hunagund IB, Krishnan KK (2011) Design of robust layout for dynamic plant layout problems. Computers Industrial Engineering 61(3):813–823

    Article  Google Scholar 

  38. Raman D, Nagalingam S, Lin G (2009) Towards measuring the effectiveness of a facilities layout. Robot Comput Integr Manuf 25:191–203

    Article  Google Scholar 

  39. Robotic Parking Systems Inc., n.d. A modular automated parking system. www.roboticparking.com

  40. Rosenblatt MJ (1986) The dynamics of plant layout. Manag Sci 32(1):76–85

    Article  MATH  Google Scholar 

  41. Sahni S, Gonzalez T (1976) P-complete approximation problems. J ACM 23(3):555–565

    Article  MathSciNet  MATH  Google Scholar 

  42. Saidi-Mehrabad N, Safaei N (2006) A new model of dynamic cell formation by a neural approach. The International Journal of Advanced Manufacturing Technology. Online First (10.1007/s00170-006-0518-2)

  43. Shafigh F (2015) Mathematical models and solution procedures in the design and scheduling of manufacturing systems with distributed layouts. Ph.D. thesis. University of Guelph, Guelph. https://atrium.lib.uoguelph.ca/xmlui/handle/10214/9165?show=full

    Google Scholar 

  44. Shafigh F, Defersha F, Moussa S (2015) A mathematical model for the design of distributed layout by considering production planning and system reconfiguration over multiple time periods. Journal of Industrial Engineering International 11(3):283–295

    Article  Google Scholar 

  45. Solimanpur M, Jafari A (2008) Optimal solution for the two-dimensional facility layout problem using a branch-and-bound algorithm. Comput Ind Eng 55(3):606–619

    Article  Google Scholar 

  46. Southwestern Industries Inc., n.d. TRAK QuikCell QCM-1. www.southwesternindustries.com

  47. Taghavi A, Murat A (2011) A heuristic procedure for the integrated facility layout design and flow assignment problem. Comput Ind Eng 61(1):55–63

    Article  Google Scholar 

  48. Tavakkoli-Moghaddam R, Aryanezhad MB, Safaei N, Azaron A (2005a) Solving a dynamic cell formation problem using metaheuristics. Appl Math Comput 170:761–780

    MathSciNet  MATH  Google Scholar 

  49. Tavakkoli-Moghaddam R, Safaei N, Babakhani M (2005b) Solving a dynamic cell formation problem with machine cost and alternative process plan by memetic algorithms. Lect Notes Comput Sci 3777:213–227

    Article  MATH  Google Scholar 

  50. Teghem J, Pirlot M, Antoniadis C (1995) Embedding of linear programming in a simulated annealing algorithm for solving a mixed integer production planning problem. J Comput Appl Math 64:91–102

    Article  MathSciNet  MATH  Google Scholar 

  51. Urban T, Chiang WC, Russel RA (2000) The integrated machine allocation and layout problem. Int J Prod Res 38(13):2911–2930

    Article  Google Scholar 

  52. Wicks EM, Reasor RJ (1999) Designing cellular manufacturing systems with dynamic part populations. IIE Trans 31:11–20

    Google Scholar 

  53. Xambre A, Vilarinho P (2007) Virtual manufacturing cell formation problem (vmcfp) in a distributed layout. Nineteenth International Conference on Production Research

Download references

Author information

Authors and Affiliations

  1. School of Engineering, University of Guelph, 50 Stone Road East, N1G 2W1, Guelph, ON, Canada

    Farhad Shafigh, Fantahun M. Defersha & Soha Eid Moussa

Authors
  1. Farhad Shafigh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Fantahun M. Defersha
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Soha Eid Moussa
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Fantahun M. Defersha.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Shafigh, F., Defersha, F.M. & Moussa, S.E. A linear programming embedded simulated annealing in the design of distributed layout with production planning and systems reconfiguration. Int J Adv Manuf Technol 88, 1119–1140 (2017). https://doi.org/10.1007/s00170-016-8813-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00170-016-8813-z

Keywords

Search

Navigation