Two Points Crossover Genetic Algorithm for Loop Layout Design Problem

Authors: Xu LiYun, Briand Florent, Fan GuoLiang

Abstract:

The loop-layout design problem (LLDP) aims at optimizing the sequence of positioning of the machines around the cyclic production line. Traffic congestion is the usual criteria to minimize in this type of problem, i.e. the number of additional cycles spent by each part in the network until the completion of its required routing sequence of machines. This paper aims at applying several improvements mechanisms such as a positioned-based crossover operator for the Genetic Algorithm (GA) called a Two Points Crossover (TPC) and an offspring selection process. The performance of the improved GA is measured using well-known examples from literature and compared to other evolutionary algorithms. Good results show that GA can still be competitive for this type of problem against more recent evolutionary algorithms.

Keywords: Crossover, genetic algorithm, layout design problem, loop-layout, manufacturing optimization.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1131840

References:

[1] Tompkins J. A., White J. A., Bozer Y. A., Tanchoco J. M. A. (2003) Facilities planning, 3rd edn. Wiley, New York.
[2] Huang, C., Wong, C. K., & Tam, C. M. (2010). Optimization of material hoisting operations and storage locations in multi-storey building construction by mixed-integer programming. Automation in Construction, 19(5), 656–663.
[3] Tompkins J. A., White J. A. (1984) Facilities planning. Wiley, New York
[4] Afentakis, P. (1989): A loop layout design problem for flexible manufacturing systems, International Journal of Flexible Manufacturing Systems, 1, 2 175-196.
[5] Leung, J. (1992) A graph-theoretic heuristic for designing loop-layout manufacturing systems. European Journal of Operational Research, 57, 243-252.
[6] Bozer Y. A., Rim S. C. (1989) Exact solution procedures for the circular layout problem. Technical Report 8933. University of Michigan.
[7] Kouvelis P., Kim M. W. (1992). Unidirectional loop network layout problem in automated manufacturing systems. Oper Res 40:533–550.
[8] Tansel B. C., Bilen C. (1998) Move based heuristics for the unidirectional loop network layout problem. Eur J Oper Res 108(1):36–48.
[9] Cheng, R. and Gen, M. Genetic algorithms for designing loop layout manufacturing systems, in Proceedings of the 18th International Conference on Computer and Industrial Engineering, 1995, pp. 187 191.
[10] Banerjee P., Zhou Y. (1995) Facilities layout design optimization with single loop material flow path configuration. Int J Prod Res 33(1):183–203.
[11] Cheng, R., Gen, M. (1998): Loop layout design problem in flexible manufacturing systems using genetic algorithms, Computers and Industrial Engineering, 34, 1 53-61.
[12] Tian, P., Ma, J., Zhang, D.-Mo., 1999. Application of simulated annealing to the combinatorial optimization problem with permutation property: An investigation of generation mechanism. European Journal of Operational Research 118, 81–94.
[13] Bennell J. A., Potts C. N., Whitehead J. D. (2002) Local search algorithms for the min–max loop layout problem. J Oper Res Soc 53:1109–1117.
[14] Nearchou A. C. (2006): Meta-heuristics from nature for the loop layout design problem. Int J Prod Econ 101:312–328.
[15] Kumar R. M. S., Asokan P., Kumanan S. (2008) Design of loop layout in flexible manufacturing system using non-traditional optimization technique. Int J Adv Manuf Technol 38(5–6):594–599.
[16] Kumar R. M. S., Asokan P., Kumanan S. (2009) Artificial immune system based algorithm for the unidirectional loop layout problem in a flexible manufacturing system. Int J Adv Manuf Technol 40(56):553–565.
[17] Ma S., Liu Z. C., Shi Y. J. (2013) A dual system method with differential evolution and genetic algorithm for loop-based station sequencing problem. Inf Technol J 12(4):728–734.
[18] Hu Zhang, Min-min Xia, Li-ling Jiang, Yi Zhang, Tong-tong Lu, (2009) “Research on Applying Unidirectional Loop Layout to Optimize Facility Layout in Workshop Based on Improved Genetic Algorithm”.
[19] Niroomand S, Vizvari B (2013) A mixed integer linear programming formulation of closed loop layout with exact distances. J Ind Prod Eng 30(3):190–201.
[20] Niroomand S., Vizvari B. (2016) Modified migrating birds optimization algorithm for closed loop layout with exact distances in flexible manufacturing systems. Expert Systems with Applications, Vol.42 (19) :6586-6597.
[21] Ramezani M., Bashiri M., Moghaddam R. T. (2012) A robust design for a closed loop supply chain network under an uncertain environment. Int J Adv Manuf Technol. 1–19 M.
[22] Saravanan & S. Ganesh Kumar (2014): Design and optimisation of loop layout problems flexible manufacturing system using sheep flock heredity algorithm.
[23] Anandaraman C. (2011) An improved sheep flock heredity algorithm for job shop scheduling and flow shop scheduling problems. Int J Ind Eng Comput 2(4):749–764.
[24] Manita G., Korbaa O., (2013), A Min-Max ANT colony algorithm for machine loop layout problem, 21st Mediterranean Conference on Control & Automation 978-1-4799-0997.
[25] Hou L., Liu Z., Shi Y., Zheng X., (2016) Optimizing Machine Assignment and Loop Layout in Tandem AGV Workshop by Co-Evolutionary Methodology, 20th International Conference on Computer Supported Cooperative Work in Design 978-1-5090-1915.
[26] Holland, J. H., (1975). Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, MI.