CE-GA Co-evolutionary Algorithm for Solving U-shaped Assembly Line Balancing Problem with Man-robot Cooperation

doi:10.3901/JME.2020.09.199

Abstract

Abstract: Aiming at a kind of widely existing production assembly problem, the model of the resource-constraint U-shaped assembly line balancing problem with man-robot cooperation (RCUALBP_MRC) is built. In this model, robots and assistants are limited resources, robots can replace manual operations, and assistants can assist workers in operations. The criteria are to simultaneously minimize the objective of total cost as well as maximize the integrated objective of line efficiency and load variance. Based on the cross-entropy (CE) method and genetic algorithm (GA), a co-evolutionary algorithm (CE-GACEA) is proposed for solving the RCUALBP_MRC. Firstly, according to the characteristics of problem solution, an efficient coding called the "task selection factor based code" (TSFBC) is designed for the task subsequence in solution. Secondly, in the global search phase, the operations of GA and CE are used to collaboratively search the subspaces determined by the task subsequence as well as the robot and assistant subsequence in solution, which can enrich search directions and find promising regions. In the local search phase, the split-merge mechanism of population is adopted, which effectively balances the global and local search of the algorithm and improves the performance of the algorithm. Finally, simulation experiments and comparisons on different instances demonstrate the effectiveness of proposed algorithm.

Key words: U-shaped assembly line balancing, genetic algorithm, cross-entropy method, co-evolution, multi-objective optimization, man-robot cooperation

CLC Number:

TG156

ZHENG Yifan, QIAN Bin, HU Rong, ZHANG Changsheng, XIANG Fenghong. CE-GA Co-evolutionary Algorithm for Solving U-shaped Assembly Line Balancing Problem with Man-robot Cooperation[J]. Journal of Mechanical Engineering, 2020, 56(9): 199-214.

References

[1] 张则强,程文明,钟斌,等. 混合品种装配线平衡问题的一种混合搜索机制的蚁群算法[J]. 机械工程学报, 2009, 45(5):95-101. ZHANG Zeqiang, CHENG Wenming, ZHONG Bin, et al. Hybrid behavior ant colony optimization for mixedmodel assembly line balancing problem[J]. Journal of Mechanical Engineering, 2009, 45(5):95-101.
[2] SALVESON M E. The assembly line balancing problem[J]. Journal of Industrial Engineering, 1955, 29(10):55-101.
[3] SCHOLL A. Balancing and sequencing of assembly lines[M]. 2nd ed. Heidelberg:Physica-Verlag, 1999.
[4] MILTENBURG G J, WIJNGAARD J. The U-line balancing problem[M]. Maryland:INFORMS, 1994.
[5] MILTENBURG J. U-shaped production lines:A review of theory and practice[J]. International Journal of Production Economics, 2001, 70(3):201-214.
[6] 胡中扬. 走进丰田-精益生产的缔造者[EB/OL].[2018-6-26]. http://articles.eworks.net.cn/plmoverview/article141623.htm.
[7] MUKUND N J, PONNAMBALAM S G. Robotic u-shaped assembly line balancing using particle swarm optimization[J]. Engineering Optimization, 2015, 48(2):1-22.
[8] LIU C M, CHEN C H. Multi-section electronic assembly line balancing problems:A case study[J]. Production Planning & Control, 2002, 13(5):451-461.
[9] URBAN T L. Optimal Balancing of U-Shaped Assembly Lines[J]. Management Science, 1998, 44(5):738-741.
[10] GÖKÇEN H, AĞPAK K, GENCER C, et al. A shortest route formulation of simple U-type assembly line balancing problem[J]. Applied Mathematical Modelling, 2005, 29(4):373-380.
[11] 唐秋华,林斌,何晓霞,等. 基于随机机会约束规划的U形装配线平衡优化[J]. 计算机集成制造系统, 2016, 22(4):955-964. TANG Qiuhua, LIN Bin, HE Xiaoxia, et al. Balancing optimization of U-shaped assembly lines based on stochastic chance constraint programing[J]. Computer Integrated Manufacturing Systems, 2016, 22(4):955-964.
[12] WAINWRIGHT D A A R L. Applying genetic algorithms to the U-shaped assembly line balancing problem[C]//IEEE World Congress on Computational Intelligence, May 4-9, 1998, Anchorage. IEEE, 1998:96-101.
[13] BAYKASOĞLU A, OZBAKIR L. Stochastic U-line balancing using genetic algorithms[J]. International Journal of Advanced Manufacturing Technology, 2007, 32(1-2):139-147.
[14] RABBANI M, KAZEMI S M, MANAVIZADEH N. Mixed model U-line balancing type-1 problem:A new approach[J]. Journal of Manufacturing Systems, 2012, 31(2):131-138.
[15] ZHANG Zikai, TANG Qiuhua, HAN Dayong, et al. Enhanced migrating birds optimization algorithm for U-shaped assembly line balancing problems with workers assignment[J]. Neural Computing and Applications, 2019, 31(11):7501-7515.
[16] 张子凯,唐秋华,张利平. 多重资源约束下的多目标U形装配线平衡[J]. 计算机集成制造系统, 2017, 23(11):100-110. ZHANG Zikai, TANG Qiuhua, ZHANG Liping. Multiobjective U-shaped assembly line balancing under multiresource restriction[J]. Computer Integrated Manufacturing Systems, 2017, 23(11):100-110.
[17] OKSUZ M K, BUYUKOZKAN K, SATOGLU S I. U-shaped assembly line worker assignment and balancing problem:A mathematical model and two meta-heuristics[J]. Computers & Industrial Engineering, 2017, 112:246-263.
[18] KARA Y, OZGUVEN C, YALSIN N, et al. Balancing straight and U-shaped assembly lines with resource dependent task times[J]. International Journal of Production Research, 2011, 49(21):6387-6405.
[19] JAYASWAL S, AGARWAL P. Balancing U-shaped assembly lines with resource dependent task times:A simulated annealing approach[J]. Journal of Manufacturing Systems, 2014, 33(4):522-534.
[20] 周济. 智能制造——"中国制造2025"的主攻方向[J]. 中国机械工程, 2015, 26(17):2273-2284. ZHOU Ji. Intelligent manufacturing——main direction of "Made in China 2025"[J]. China Mechanical Engineering, 2015, 26(11):2273-2284.
[21] RUBINSTEIN R Y. Optimization of computer simulation models with rare events[J]. European Journal of Operational Research, 1997, 99(1):89-112.
[22] CASERTA M, RICO E Q. A cross entropy algorithm for the Knapsack problem with setups[J]. Computers & Operations Research, 2008, 35(1):241-252.
[23] CHEPURI K, HOMEM-DE-MELLO T. Solving the vehicle routing problem with stochastic demands using the cross-entropy method[J]. Annals of Operations Research, 2005, 134(1):153-181.
[24] WANG Guirong, LI Qiqiang, WANG Luhao. An improved cross entropy algorithm for steelmaking-continuous casting production scheduling with complicated technological routes[J]. Journal of Central South University, 2015, 22(8):2998-3007.
[25] JEDRZEJOWICZA P, SKAKOVSKI A. A cross-entropybased population-learning algorithm for discrete-continuous scheduling with continuous resource discretization[J]. Neurocomputing, 2010, 73(4-6):655-660.
[26] BUDI S, MUHAMMAD A B, STEFANUS E W. A cross entropy-genetic algorithm form-machines no-wait job-shop scheduling problem[J]. Journal of Intelligent Learning Systems and Applications, 2011, 3:171-180.
[27] 李国成, 肖庆宪. 求解高维函数优化问题的交叉熵蝙蝠算法[J]. 计算机工程, 2014, 40(10):168-174. LI Guocheng, XIAO Qingxian. Cross-entropy bat algorithm for solving high-dimensional function optimization problem[J]. Computer Engineering, 2014, 40(10):168-174.
[28] 王凌,沈婧楠,王圣尧,等. 协同进化算法研究进展[J]. 控制与决策, 2015, 30(2):193-202. WANG Ling, SHENG Jingnan, WANG Shengyao, et al. Advances in co-evolutionary algorithms[J]. Control and Decision, 2015, 30(2):193-202.
[29] LEI D. Co-evolutionary genetic algorithm for fuzzy flexible job shop scheduling[J]. Applied Soft Computing, 2012, 12(8):2237-2245.
[30] WANG Ling, WANG Shengyao, XU Ye, et al. A bipopulation based estimation of distribution algorithm for the flexible job-shop scheduling problem[J]. Computers & Industrial Engineering, 2012, 62:917-926.
[31] 刘冉,楼佩煌,唐敦兵,等. 解决U形装配线平衡调度问题的免疫协同进化算法[J]. 中国机械工程, 2010, 21(7):815-821. Liu Ran, LOU Peihuang, TANG Dunbing, et al. An immune coevolution algorithm for balancing and sequencing on mixed-model U-lines[J]. China Mechanical Engineering, 2010, 21(7):815-821.
[32] KIM Y K, KIM J Y, KIM Y. A coevolutionary algorithm for balancing and sequencing in mixed model assembly lines[J]. Applied Intelligence:The International Journal of Artificial, Intelligence, Neural Networks, and Complex Problem-Solving Technologies, 2000, 13(3):247-258.
[33] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multi objective genetic algorithm:NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):0-197.
[34] ISHIBUCHI H. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling[J]. IEEE Trans. Evol. Comput., 2003, 7(2):204-223.
[35] MONTGOMERY D C. Design and analysis of experiments[M]. Hoboken:John Wiley and Sons, 2005.
[36] LI Dashuang, ZHANG Caoyong, SHAO Xinyu, et al. A multi-objective TLBO algorithm for balancing two-sided assembly line with multiple constraints[J]. Journal of Intelligent Manufacturing, 2016, 27(4):725-739.