An Improved Ant Colony Optimization for Two-Sided Assembly Line Balancing Problem
ZHENG Qiao-xian1,2, LI Ming3,4, LI Yuan-xiang2, TANG Qiu-hua4
1. College of Mathematic and Computer Science, Hubei University, Wuhan, Hubei 430062, China;
2. College of Computer, Wuhan University, Wuhan, Hubei 430072, China;
3. College of Science, Wuhan University of Science and Te chnology, Wuhan, Hubei 430065, China;
4. College of Mechanics and Automation, Wuhan University of Science and Technology , Wuhan, Hubei 430081, China
Abstract：According to the characteristics of the type 2 two-sided assembly line balancing problem,an improved ant colony optimization is proposed.A novel pheromone between two adjacent tasks in the same side station is defined to describe the order relation between them.A new bound strategy is proposed to reduce the search space of ants,by decreasing the upper bound of station times according to the current best solution,and bounding their lower bounds with the mean processing time of assigned stations.An improved task assignment rule is applied to assign the suitable task to station,in which three kinds ideal task with different prior permissions are used.A side station determination rule is proposed to balance the increase speed of both side times.Computational results show the effectiveness and stability of proposed algorithm.
郑巧仙, 李明, 李元香, 唐秋华. 求解双边装配线平衡问题的改进蚁群算法[J]. 电子学报, 2014, 42(5): 841-845.
ZHENG Qiao-xian, LI Ming, LI Yuan-xiang, TANG Qiu-hua. An Improved Ant Colony Optimization for Two-Sided Assembly Line Balancing Problem. Chinese Journal of Electronics, 2014, 42(5): 841-845.
[1] J J Barthodi.Balancing two-sided assembly lines:A case study[J].International Journal of Production Research,1993,31(10):2447-2461.[2] W Erfei,J Ye,B Jinsong et al.A branch-and-bound algorithm for two-sided assembly line balancing[J].Int J Adv Manuf Technol,2008,39(9-10):1009-1015.[3] H Xiaofeng,et al.A branch-and-bound algorithm to minimize the line length of a two-sided assembly line[J].European Journal of Operational Research,2010,206(3):703-707.[4] U Özcan,B.Toklu.A tabu search algorithm for two-sided assembly line balancing[J].Int J Adv Manuf Technol,2009,43(7-8):822-829.[5] 吴尔飞,金烨,汪峥.双边装配线第二类平衡问题研究[J].计算机集成制造系统,2005,11(11):1604-1608. WU Er-fei,et al.Research on balancing problem of type 2 of two-sided assembly line [J].Computer Integrated Manufacturing Systems,2005,11(11):1604-1608.(in Chinese)[6] Y K Kim,Y Kim,Y J Kim.Two-sided assembly line balancing:a genetic algorithm approach[J].Production Planning & Control,2000,11(1):44-53.[7] Y K Kim,W S Song,J H Kim.A mathematical model and a genetic algorithm for two-sided assembly line balancing[J].Computers& Operations Research,2009,36(3):853-865.[8] A.Colorni,M.Dorigo and V.Maniezzo.Distributed optimization by ant colonies[A].Proceedings of ECAL91-European Conference on Artificial Life[C].Paris Publishing Elsevier,1991.134-142.[9] 孙伟峰,等.QIACO：一种多Qos约束网格任务调度算法[J].电子学报,2011,39(5):1115-1120. SUN Wei-feng,et al.QIACO:An algorithm for grid task scheduling of multiple Qos dimensions[J].Acta Electronica Sinica,2011,39(5):1115-1120.(in Chinese)[10] [JP3]Z Qiaoxian,L Ming,L Yuanxiang,T Qiuhua.Station ant colony optimization for the type 2 assembly line balancing problem[J].Int J Adv Manuf Technol,2013,66:1859-1870.[11] W C Chiang.The application of a tabu search metaheuristic to the assembly line balancing problem[J].Annals of Operations Research.1998,77(0):209-227.[12] 吴春明,陈治,姜明.蚁群算法中系统初始化及系统参数的研究[J].电子学报,2006,34(8):1530-1533. WU Chun-ming,CHEN Zhi,JIANG Ming.The research on initialization of ants system and configuration of parameters for different TSP problems in ant algorithm [J].Acta Electronica Sinica,2006,34(8):1530-1533.(in Chinese)
2014, Vol. 42 
