基于混合蝙蝠算法的多约束双边装配线平衡问题研究
|
摘要
包含位置约束、区域约束、同步约束等额外约束的双边装配线平衡问题,称为多约束双边装配线平衡问题,与双边装配线第I类平衡问题相比,复杂度显著提升,目前研究成果还很少。而现实中的装配线平衡问题往往包含额外约束,因而,研究多约束双边装配线平衡问题更具有实际意义。针对以上问题,本研究在分析额外约束的数学表达的基础上,建立了多约束双边装配线平衡问题的优化模型,提出了拓扑排序矩阵编码方法、面向位置约束的解码方法、变邻域搜索策略,与标准蝙蝠算法相结合,形成了混合算法的求解机制。以标杆算例为对象,与多种典型的启发式算法进行了比对实验研究,实验结果表明了所提算法的可靠性和优越性。
Bilateral assembly line balancing problem with additional constraints, such as position constraints, region constraints and synchronization constraints, is called multi-constrained bilateral assembly line balancing problem, which complexity is significantly improved compared with type I bilateral assembly line balancing problem, and thus there are few research results. In real world, the assembly line balancing problem often contains additional constraints, so it is more practical to study the bilateral assembly line balancing problem with multiple constraints. Based on the analysis of the mathematical expression of additional constraints, the optimization model of bilateral assembly line balancing problem with multiple constraints is established. Coding method of topological ranking matrix, location constraints oriented decoding method and variable neighborhood search strategy are proposed. A hybrid algorithm is realized through combining these proposed methods and strategy with standard bat algorithm. Comparison experiments are done on benchmarks compared with several typical heuristic algorithms. The experimental results demonstrate the reliability and superiority of the proposed algorithm.
Bilateral assembly line balancing problem with additional constraints, such as position constraints, region constraints and synchronization constraints, is called multi-constrained bilateral assembly line balancing problem, which complexity is significantly improved compared with type I bilateral assembly line balancing problem, and thus there are few research results. In real world, the assembly line balancing problem often contains additional constraints, so it is more practical to study the bilateral assembly line balancing problem with multiple constraints. Based on the analysis of the mathematical expression of additional constraints, the optimization model of bilateral assembly line balancing problem with multiple constraints is established. Coding method of topological ranking matrix, location constraints oriented decoding method and variable neighborhood search strategy are proposed. A hybrid algorithm is realized through combining these proposed methods and strategy with standard bat algorithm. Comparison experiments are done on benchmarks compared with several typical heuristic algorithms. The experimental results demonstrate the reliability and superiority of the proposed algorithm.
引文
[1] 彭运芳,范庆彬,张丽玉,等.带有逻辑选择关系的单边装配线平衡问题[J].工业工程与管理,2017(05):65-73.
[2] 查靓,徐学军,余建军,等.多类约束下U型装配线平衡建模研究[J].工业工程与管理,2011(01):59-63+69.
[3] 侯东亮.工作研究在双边装配线平衡中的应用[J].工业工程与管理,2008(03):121-124.
[4] Kim Y K,Kim Y,Kim Y J.Two-sided assembly line balancing:A genetic algorithm approach[J].Production Planning & Control,2000,11(1):44-53.
[5] Baykasoglu A,Dereli T.Two-sided assembly line balancing using an ant-colony-based heuristic[J].International Journal of Advanced Manufacturing TE,2008,36(5-6):582-588.
[6] Simaria A S,Vilarinho P M.2-ANTBAL:an ant colony optimisation algorithm for balancing two-sided assembly lines[J].Computers & Industrial Engineering,2009,56(2):489-506.
[7] Yuan B,Zhang C,Shao X.A late acceptance hill-climbing algorithm for balancing two-sided assembly lines with multiple constraints[J].Journal of Intelligent Manufacturing,2013,26(1):1-10.
[8] Tang Q,Li Z,Zhang L,et al.Effective hybrid teaching-learning-based optimization algorithm for balancing two-sided assembly lines with multiple constraints[J].Chinese Journal of Mechanical Engineering,2015,28(5):1067-1079.
[9] Mladenovi N,Hansen P.Variable neighborhood search[J].Computers & Operations Research,1997,24(11):1097-1100.
[10] 李大双,张超勇,邵新宇,等.基于殖民竞争算法的多约束双边装配线平衡[J].机械工程学报,2015(02):183-189.
[11] Tang Q,Li Z,Zhang L P,et al.Balancing stochastic two-sided assembly line with multiple constraints using hybrid teaching-learning-based optimization algorithm[J].Computers & Operations Research,2017,82(1):102-113.
[12] Yang X S.A new metaheuristic Bat-Inspired algorithm[J].Computer Knowledge & Technology,2010,284(2):65-74.
[13] Lee T O,Kim Y,Kim Y K.Two-sided assembly line balancing to maximize work relatedness and slackness[J].Computers & Industrial Engineering,2001,40(3):273-292.
[14] 李梓响,唐秋华,张利平,等.求解第Ⅰ类双边装配线平衡问题的改进离散人工蜂群算法[J].计算机集成制造系统,2016(04):974-982.
[15] Luo Y.Topological Sorting-based Two-stage nested ant colony algorithm for Job-shop scheduling problem[J].Journal of Mechanical Engineering,2015,51(8):178.
[16] Chiang W C,Urban T L,Luo C.Balancing stochastic two-sided assembly lines[J].International Journal of Production Research,2015,54(20):6232-6250.
[17] Li D,Zhang C,Shao X,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.
[18] Bartholdi J J.Balancing two-sided assembly lines:a case study[J].International Journal of Production Research,1993,31(10):2246-2447.
[19] Xue F,Cai Y,Cao Y,et al.Optimal parameter settings for bat algorithm[J].International Journal of Bio-Inspired Computation,2015,7(2):125-128.
[20] 吴尔飞,金烨,续爱民,等.基于改进遗传算法的双边装配线平衡[J].计算机集成制造系统,2007(02):268-274.
[2] 查靓,徐学军,余建军,等.多类约束下U型装配线平衡建模研究[J].工业工程与管理,2011(01):59-63+69.
[3] 侯东亮.工作研究在双边装配线平衡中的应用[J].工业工程与管理,2008(03):121-124.
[4] Kim Y K,Kim Y,Kim Y J.Two-sided assembly line balancing:A genetic algorithm approach[J].Production Planning & Control,2000,11(1):44-53.
[5] Baykasoglu A,Dereli T.Two-sided assembly line balancing using an ant-colony-based heuristic[J].International Journal of Advanced Manufacturing TE,2008,36(5-6):582-588.
[6] Simaria A S,Vilarinho P M.2-ANTBAL:an ant colony optimisation algorithm for balancing two-sided assembly lines[J].Computers & Industrial Engineering,2009,56(2):489-506.
[7] Yuan B,Zhang C,Shao X.A late acceptance hill-climbing algorithm for balancing two-sided assembly lines with multiple constraints[J].Journal of Intelligent Manufacturing,2013,26(1):1-10.
[8] Tang Q,Li Z,Zhang L,et al.Effective hybrid teaching-learning-based optimization algorithm for balancing two-sided assembly lines with multiple constraints[J].Chinese Journal of Mechanical Engineering,2015,28(5):1067-1079.
[9] Mladenovi N,Hansen P.Variable neighborhood search[J].Computers & Operations Research,1997,24(11):1097-1100.
[10] 李大双,张超勇,邵新宇,等.基于殖民竞争算法的多约束双边装配线平衡[J].机械工程学报,2015(02):183-189.
[11] Tang Q,Li Z,Zhang L P,et al.Balancing stochastic two-sided assembly line with multiple constraints using hybrid teaching-learning-based optimization algorithm[J].Computers & Operations Research,2017,82(1):102-113.
[12] Yang X S.A new metaheuristic Bat-Inspired algorithm[J].Computer Knowledge & Technology,2010,284(2):65-74.
[13] Lee T O,Kim Y,Kim Y K.Two-sided assembly line balancing to maximize work relatedness and slackness[J].Computers & Industrial Engineering,2001,40(3):273-292.
[14] 李梓响,唐秋华,张利平,等.求解第Ⅰ类双边装配线平衡问题的改进离散人工蜂群算法[J].计算机集成制造系统,2016(04):974-982.
[15] Luo Y.Topological Sorting-based Two-stage nested ant colony algorithm for Job-shop scheduling problem[J].Journal of Mechanical Engineering,2015,51(8):178.
[16] Chiang W C,Urban T L,Luo C.Balancing stochastic two-sided assembly lines[J].International Journal of Production Research,2015,54(20):6232-6250.
[17] Li D,Zhang C,Shao X,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.
[18] Bartholdi J J.Balancing two-sided assembly lines:a case study[J].International Journal of Production Research,1993,31(10):2246-2447.
[19] Xue F,Cai Y,Cao Y,et al.Optimal parameter settings for bat algorithm[J].International Journal of Bio-Inspired Computation,2015,7(2):125-128.
[20] 吴尔飞,金烨,续爱民,等.基于改进遗传算法的双边装配线平衡[J].计算机集成制造系统,2007(02):268-274.