大规模多工位装配线平衡问题的规则组合算法

• 论文 •

大规模多工位装配线平衡问题的规则组合算法

李明1,2,李珊1,夏绪辉2,唐秋华2,郑巧仙3

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

收稿日期:2013-11-25 修回日期:2013-11-25 出版日期:2013-11-25 发布日期:2013-11-25

Rules combination algorithm of assembly line balancing problem for large-scale multiple stations

LI Ming1,2,LI Shan1,XIA Xu-hui2,TANG Qiu-hua2,ZHENG Qiao-xian3

1.College of Science,Wuhan University of Science and Technology,2.College of Mechanics and Automation,Wuhan University of Science and Technology,3.Mathematic and Computer Science College,Hubei University

Received:2013-11-25 Revised:2013-11-25 Online:2013-11-25 Published:2013-11-25

摘要/Abstract

摘要： 针对大规模多工位装配线平衡问题,提出一种基于规则组合的求解算法。将操作的选择规则和分配规则进行组合,求解第1类装配线平衡问题;将所有规则组合用于求解第2类装配线平衡问题。算法以两个大规模算例Arcus-111和Scholl-297为例对两类装配线平衡问题进行求解,并将求解结果与已有的最好结果比较,验证了算法的有效性和高效性;将操作时间进行随机扰动,基于扰动后的数据求解第1类装配线平衡问题的3个算例100次,统计结果表明算法具有较强的鲁棒性。

关键词: 装配线平衡, 规则组合, 操作分配规则, 定界压缩规则

Abstract: Aiming at the Assembly Line Balancing Problem (ALBP) for large-scale multiple stations,a solving algorithm based on rules combination was proposed-.Task selection rule and assignment rule were combined to solve the type 1 ALBP (ALBP-1)-,and four rules were combined to solve the type 2 ALBP (ALBP-2).Two large-scale examples of Arcus-11 and Scholl-297 were solved by proposed algorithm,and the solving result was compared with the best ones in literature to verify the effectiveness and efficiency of algorithm.In addition,three cases of ALBP-1 with the random disturbances task time were solved 100 times,and the statistical results showed that the algorithm had stronger robustness.

Key words: assembly line balancing, rule combination, task assignment rule, bound and compress rule

中图分类号:

TH166
TP18

李明1,2,李珊1,夏绪辉2,唐秋华2,郑巧仙3. 大规模多工位装配线平衡问题的规则组合算法[J]. .

LI Ming1,2,LI Shan1,XIA Xu-hui2,TANG Qiu-hua2,ZHENG Qiao-xian3 . Rules combination algorithm of assembly line balancing problem for large-scale multiple stations[J]. .

参考文献

［1］SALVESON M E.The assembly line balancing problem［J］.Journal of Industrial Engineering,1955,6(3);18-25.
[2]SCHOLL A.Balancing and sequencing of assembly lines［M］.2nd ed.Heidelberg,Germany:Physica-Verlag,1999.
[3]KLEIN R,SCHOLL A.Maximizing the production rate in simple assembly line balancing-a branch and bound procedure［J］.European Journal of Operational Research,1996,91(2);367-385.
[4]SCHOLL A,KLEIN R.SALOME;a bidirectional branch and bound procedure for assembly line balancing［J］.Informs Journal on Computing,1997,9(4);319-334.
[5]SCHOLL A,BECKER C.State-of-the art exact and heuristic solution procedures for simple assembly line balancing［J］.European Journal of Operational Research,2006,168(3);666-693.
[6]BOYSEN N,FLIEDNER M.A versatile algorithm for assembly line balancing［J］.European Journal of Operational Research,2008,184(1);39-56.
[7]LI Ming,TANG Qiuhua,XI Zhongmin,et al.One-sided multi-objective assembly line balancing model based on multi-layer programming［J］.Systems Engineering—Theory & Practice,2011,31(11);2185-2190(in Chinese).［李明,唐秋华,席忠民,等.基于多层规划的单边多目标装配线平衡调度模型［J］.系统工程理论与实践,2011,31(11):2185-2190.］
[8]BAUTISTA J,PEREIRA J.A dynamic programming based heuristic for the assembly line balancing problem［J］.European Journal of Operational Research,2009,194(3):787-794.
[9]SCHOOL A,FLIEDNER M,BOYSEN N.ABSALOM;balancing assembly lines with assignment restrictions［J］.European Journal of Operational Research,2010,200(3):688-701.
[10]ZHANG Zeqiang,CHENG Wenming,ZHONG Bin,et al.Improved ant colony optimization for assembly line balancing problem［J］.Computer Integrated Manufacturing Systems,2007,13(8);1632-1638(in Chinese).［张则强,程文明,钟斌,等.求解装配线平衡问题的一种改进蚁群算法［J］.计算机集成制造系统,2007,13(8);1632-1638.］
[11]YOLMEH A,KIANFAR F.An efficient hybrid genetic algorithm to solve assembly line balancing problem with sequence-dependent setup times［J］.Computers & Industrial Engineering,2012,62(3):936-945.
[12]UURDA H F,RACHAMADUGU R,PAPACHRISTOU C A.Designing paced assembly lines with fixed number of stations［J］.European Journal of Operational Research,1997,102(3);488-501.
[13]CHIANG W C.The application of a tabu search metaheuristic to the assembly line balancing problem［J］.Annals of Operations Research,1998,77(0);209-227.
[14]SCHOLL A,KLEIN R.Balancing assembly lines effectively a computational comparison［J］.European Journal of Operational Research,1999,114(1);50-58.
[15]GONCALVES J F,RAIMUDO DE ALMEIDA J.A hybrid genetic algorithm for assembly line balancing［J］.Journal of Heuristics,2002,8(6);629-642.
[16]ZHENG Qiaoxian,LI Yuanxiang,LI Ming,et al.Ant colony optimization for type Ⅱ assembly line balancing problem［J］.Computer Integrated Manufacturing Systems,2012,18(5);999-1005(in Chinese).［郑巧仙,李元香,李明,等.面向第Ⅱ类装配线平衡问题的蚁群算法［J］.计算机集成制造系统,2012,18(5):999-1005.］
[17]LAPIERRE S D,RUIZ A,SORIANO P.Balancing assembly lines with tabu search［J］.European Journal of Operational Research,2006,168(3);826-837.
[18]DOU Jianping,SU Chun,LI Jun.Discrete particle swarm optimization algorithms for assembly line balancing problems of type Ⅰ［J］.Computer Integrated Manufacturing Systems,2012,18(5);1021-1029(in Chinese).［窦建平,苏春,李俊.求解第Ⅰ类装配线平衡问题的离散离子群优化算法［J］.计算机集成制造系统,2012,18(5):1021-1029.］

[1]	蒙凯,唐秋华,张子凯,卢辰灏,邓明星. 基于改进多目标灰狼算法的装配线平衡与预防维护集成优化[J]. 计算机集成制造系统, 2020, 26(12): 3302-3312.
[2]	李爱平,赵亚西,张家骅,刘雪梅. 考虑装配关系复杂性的多目标装配线平衡优化方法[J]. 计算机集成制造系统, 2019, 25(第7): 1665-1675.
[3]	郑巧仙,李明,唐秋华,亓晓莹. 多约束装配线平衡问题的可行解存在性分析[J]. 计算机集成制造系统, 2019, 25(第3): 619-628.
[4]	郑谐,王婷,徐云天. 基于遗传算法的飞机脉动式装配线平衡[J]. 计算机集成制造系统, 2018, 24(第6): 1367-1373.
[5]	唐秋华,饶迪,李梓响,张利平. 改进迭代局部搜索算法求解第Ⅰ类混流双边装配线平衡问题[J]. 计算机集成制造系统, 2018, 24(第2): 390-399.
[6]	潘志豪,郭宇,查珊珊,章诗晨,王彬. 基于混合优化算法的飞机总装脉动生产线平衡问题[J]. 计算机集成制造系统, 2018, 24(第10): 2436-2447.
[7]	李梓响,唐秋华,张利平,郑鹏. 求解第Ⅰ类双边装配线平衡问题的改进离散人工蜂群算法[J]. 计算机集成制造系统, 2016, 22(第4期): 972-980.
[8]	李明,唐秋华,郑巧仙,夏绪辉. 第2类装配线平衡问题的改进规则组合算法[J]. 计算机集成制造系统, 2015, 21(第1期): 88-93.
[9]	徐剑,叶文华,杨斌,刘霞. 基于扩展Petri网的飞机装配线建模及平衡方法[J]. 计算机集成制造系统, 2015, 21(第10期): 2596-2603.
[10]	刘俨后,左敦稳,张丹. 随机作业时间的装配线平衡问题[J]. 计算机集成制造系统, 2014, 20(6): 1372-1378.
[11]	张宏林1，殷复鹏1,2，吴爱华1. 双边多工位装配线平衡问题[J]. , 2013, 19 (02 ): 0-0.
[12]	郑巧仙，，李元香，李明，唐秋华，鲁素丽. 面向第Ⅱ类装配线平衡问题的蚁群算法[J]. , 2012, 18(05): 0-0.
[13]	窦建平,，苏春，李俊. 求解第Ⅰ类装配线平衡问题的离散粒子群优化算法[J]. , 2012, 18(05): 0-0.
[14]	李英德，鲁建厦. 求解第二类装配线平衡问题的改进蚁群算法[J]. , 2012, 18(04): 0-0.
[15]	徐炜达,肖田元. 带有区间不确定任务时间的装配线鲁棒平衡[J]. , 2010, 16(06): 0-0.