求解双边装配线平衡问题的改进蚁群算法

doi:10.3969/j.issn.0372-2112.2014.05.002

电子学报 ›› 2014, Vol. 42 ›› Issue (5): 841-845.DOI: 10.3969/j.issn.0372-2112.2014.05.002

求解双边装配线平衡问题的改进蚁群算法

郑巧仙^1,2, 李明^3,4, 李元香², 唐秋华⁴

1. 湖北大学数学与计算机科学学院, 湖北武汉 430062;
2. 武汉大学计算机学院, 湖北武汉 430072;
3. 武汉科技大学理学院, 湖北武汉 430065;
4. 武汉科技大学机械自动化学院, 湖北武汉 430081

收稿日期:2013-04-22 修回日期:2013-06-28 出版日期:2014-05-25 发布日期:2014-05-25
作者简介:郑巧仙 女，1978年生于浙江省衢州市，2013年于武汉大学计算机学院获得工学博士学位，现为湖北大学数学与计算机科学学院讲师，主要研究方向为智能计算. E-mail :zqxlm1978@163.com.李明男，1976年生于山东省潍坊市，武汉科技大学机械与自动化学院在读博士研究生，现为武汉科技大学理学院副教授，主要研究方向为生产调度优化. E-mail :lmzqx@163.com
基金资助:
国家自然科学基金(No.50875190，No.51275366)；武汉科技大学冶金工业过程系统科学湖北省重点实验室开放基金(No.Y201109)

An Improved Ant Colony Optimization for Two-Sided Assembly Line Balancing Problem

ZHENG Qiao-xian^1,2, LI Ming^3,4, LI Yuan-xiang², TANG Qiu-hua⁴

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

Received:2013-04-22 Revised:2013-06-28 Online:2014-05-25 Published:2014-05-25

摘要/Abstract

摘要： 结合第2类双边装配线平衡问题(TALBP-2)的特点，提出了一种改进蚁群算法.针对TALBP-2中操作间的序关系，对分配至同一个边工位中相邻的两项操作间定义了一种新的信息素；提出了一种新的定界策略，根据所得的最好解，减小工位时间的上界，利用已分配工位的平均实际作业时间界定工位时间的下界，缩小蚂蚁的搜索空间；针对TALBP-2提出了一种新的操作分配准则，根据所定义的3种理想操作的优先分配权限分配操作；提出了一种边工位确定原则，平衡两边工位时间的增加速度.算例的比较结果表明算法有较好的求解效果和稳定性.

关键词: 双边装配线, 装配线平衡问题, 蚁群算法, 组合优化

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.

Key words: two-sided assembly line, assembly line balancing problem, ant colony optimization, combinatorial optimization

中图分类号:

TH166
TP18

郑巧仙, 李明, 李元香, 唐秋华. 求解双边装配线平衡问题的改进蚁群算法[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[J]. Acta Electronica Sinica, 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)

[1]	李彦苍, 巩翔宇. 基于信息熵的改进狮群算法及其在组合优化中的应用[J]. 电子学报, 2021, 49(8): 1577-1585.
[2]	孙鑫威, 纪爱敏, 陈曦晖, 林新海, 许行. 强噪声背景下动车组轴承微弱故障信号检测[J]. 电子学报, 2021, 49(11): 2217-2224.
[3]	廖伟志, 夏小云, 贾小军. 基于蚁群算法的多路径覆盖测试数据生成[J]. 电子学报, 2020, 48(7): 1330-1342.
[4]	黄戈文, 蔡延光, 戚远航, 陈厚仁, 王世豪. 自适应遗传灰狼优化算法求解带容量约束的车辆路径问题[J]. 电子学报, 2019, 47(12): 2602-2610.
[5]	王辛, 王晓峰, 李卫民. 一种求解最小割的警示传播算法[J]. 电子学报, 2019, 47(11): 2386-2391.
[6]	许凯波, 鲁海燕, 黄洋, 胡士娟. 基于双层蚁群算法和动态环境的机器人路径规划方法[J]. 电子学报, 2019, 47(10): 2166-2176.
[7]	李媛祯, 杨群, 赖尚琦, 李博涵. 一种Hadoop Yarn的资源调度方法研究[J]. 电子学报, 2016, 44(5): 1017-1024.
[8]	章刚, 陈庆奎. GCTA:一种群组命令传输算法[J]. 电子学报, 2016, 44(2): 413-419.
[9]	李琳, 应时, 赵翀, 董波. 基于蚁群算法的面向服务软件的部署优化方法[J]. 电子学报, 2016, 44(1): 123-129.
[10]	许烁, 王阳, 孙成恺. 模块化可重构服务机器人群的任务规划[J]. 电子学报, 2016, 44(1): 101-109.
[11]	易云飞, 蔡永乐, 董文永, 林晓东. 求解带用户满意度的多目标实时车辆路径问题的改进伊藤算法[J]. 电子学报, 2015, 43(10): 2053-2061.
[12]	邓广宏, 曹万华, 张剑, 冯力, 程雄. DTN网络环境下基于蚁群算法的数据编码分发[J]. 电子学报, 2014, 42(8): 1636-1641.
[13]	钱洁, 郑建国. 引入逆学习的量子自适应禁忌搜索算法[J]. 电子学报, 2013, 41(6): 1069-1075.
[14]	袁述, 袁东辉, 孙基洲, 刘永波, 李晶, 原琳. 蚁群-遗传算法在多传感器多目标跟踪技术中的应用[J]. 电子学报, 2013, 41(3): 609-614.
[15]	刘衍珩;张婧;王健. TrANTHOCNET:信任性蚁群自组织路由算法[J]. 电子学报, 2012, 40(2): 319-326.

求解双边装配线平衡问题的改进蚁群算法

An Improved Ant Colony Optimization for Two-Sided Assembly Line Balancing Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics