Enhanced Estimation of Distribution Algorithm for the Two-Side Assembly Line Balancing Problem of Type-Ⅱ

ZHANG Teng-fei; HU Rong; QIAN Bin; ZHANG Zi-qi; LÜ Yang

doi:10.12263/DZXB.20211345

您当前的位置：

首页 >

文章列表页 >

Enhanced Estimation of Distribution Algorithm for the Two-Side Assembly Line Balancing Problem of Type-Ⅱ

PAPERS | 更新时间：2025-12-08

- Enhanced Estimation of Distribution Algorithm for the Two-Side Assembly Line Balancing Problem of Type-Ⅱ
- ACTA ELECTRONICA SINICA Vol. 50, Issue 8, Pages: 1937-1942(2022)
- 作者机构：
  
  1.昆明理工大学信息工程与自动化学院, 云南昆明 650500
  2.昆明理工大学机电工程学院, 云南昆明 650500
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20211345
  CLC： TP278
- Received：08 October 2021，
  
  Revised：2022-05-16，
  
  Published：25 August 2022
- 稿件说明：
移动端阅览
张腾飞,胡蓉,钱斌等.增强分布估计算法求解双边装配线第二类平衡问题[J].电子学报,2022,50(08):1937-1942.

ZHANG Teng-fei,HU Rong,QIAN Bin,et al.Enhanced Estimation of Distribution Algorithm for the Two-Side Assembly Line Balancing Problem of Type-Ⅱ[J].ACTA ELECTRONICA SINICA,2022,50(08):1937-1942.
张腾飞,胡蓉,钱斌等.增强分布估计算法求解双边装配线第二类平衡问题[J].电子学报,2022,50(08):1937-1942. DOI： 10.12263/DZXB.20211345.

ZHANG Teng-fei,HU Rong,QIAN Bin,et al.Enhanced Estimation of Distribution Algorithm for the Two-Side Assembly Line Balancing Problem of Type-Ⅱ[J].ACTA ELECTRONICA SINICA,2022,50(08):1937-1942. DOI： 10.12263/DZXB.20211345.

摘要

针对汽车等制造业存在的双边装配线第二类平衡问题，本文建立以生产节拍和平滑指数为主次优化目标的排序模型，提出增强分布估计算法（Enhanced Estimation of Distribution Algorithm，EEDA）进行求解.算法初始化阶段，采用自适应策略生成初始节拍来提升初始解的质量.全局搜索阶段，设计三维概率模型学习生成解中工序的排列信息，并采样三维概率模型来生成新解，引导算法较快到达优质解区域.局部搜索阶段，设计适合主次目标的搜索策略对优质解区域进一步细致搜索，能增强算法局部搜索能力.此外，通过分析问题特点，提出确定生成解是否可行的快速判断方法以提升算法搜索效率.对不同规模问题实例进行仿真实验和算法比较，验证了考虑主次目标的重要性和增强分布估计算法的有效性.

Abstract

Aiming at the two-side assembly line balancing problem of type-Ⅱ in manufacturing

this paper establishes a model whose primary and secondary optimization objectives are cycle time and smoothing index

and proposes an enhanced estimation of distribution algorithm(EEDA) for it. In the initialization

an adaptive strategy is devised to generate the initial cycle time for improving the quality of initial solutions. In the global search

the probability model is used to learn the information of solution

and sample the probability model to generate a new solution. In the local search

a strategy suitable for primary and secondary objectives is developed to further execute a thorough search in promising regions. Meanwhile

by analyzing the characteristics of the problem

a fast judgment method that can determine whether the solutions are feasible is proposed. Simulation experiments verify the effectiveness of the EEDA and the importance of primary and secondary objectives.

关键词

Keywords

references

苑明海 , 许焕敏 . 可重构装配线建模及优化调度控制 [M]. 北京 : 国防工业出版社 , 2011 : 9 - 11 .

YUAN Ming-hai , XU Huan-min . Reconfigurable Assembly Line Modeling and Optimal Scheduling Control [M]. Beijing : National Defense Industry Press , 2011 : 9 - 11 . (in Chinese)

张明超 , 孙新波 , 王永霞 . 数据赋能驱动精益生产创新内在机理的案例研究 [J]. 南开管理评论 , 2021 , 24 ( 3 ): 102 - 116 .

ZHANG Ming-chao , SUN Xin-bo , WANG Yong-xia . Case study on the internal mechanism of lean production innovation driven by data empowerment [J]. Nankai Management Review , 2021 , 24 ( 3 ): 102 - 116 . (in Chinese)

TANG Q H , LI Z X , ZHANG L P . An effective discrete artificial bee colony algorithm with idle time reduction techniques for two-sided assembly line balancing problem of type-II [J]. Computers & Industrial Engineering , 2016 , 97 ( 3 ): 146 - 156 .

LI Z X , TANG Q H , ZHANG L P . Minimizing the cycle time in two-sided assembly lines with assignment restrictions: Improvements and a simple algorithm [J]. Mathematical Problems in Engineering , 2016 ( 7 ): 1 - 15 .

LEI D M , GUO X P . Variable neighborhood search for the second type of two-sided assembly line balancing problem [J]. Computers and Operations Research , 2016 , 72 ( 9 ): 183 - 188 .

李大双 , 张超勇 , 邵新宇 , 等 . 基于殖民竞争算法的多约束双边装配线平衡 [J]. 机械工程学报 , 2015 , 51 ( 2 ): 183 - 189 .

LI Da-shuang , ZHANG Chao-yong , SHAO Xin-yu , et al . Hybrid colonial competitive algorithm for the two-sided assembly line balancing problem with multiple constraints [J]. Journal of Mechanical Engineering , 2015 , 51 ( 2 ): 183 - 189 . (in Chinese)

郑巧仙 , 李明 , 李元香 , 等 . 求解双边装配线平衡问题的改进蚁群算法 [J]. 电子学报 , 2014 , 42 ( 5 ): 841 - 845 .

ZHENG Qiao-xian , LI Ming , LI Yuan-xiang , et al . An improved ant colony optimization for two-sided assembly line balancing problem [J]. Acta Electronica Sinica , 2014 , 42 ( 5 ): 841 - 845 . (in Chinese)

王凌 , 王圣尧 , 方晨 . 分布估计调度算法 [M]. 北京 : 清华大学出版社 , 2017 : 2 - 3 .

WANG Ling , WANG Sheng-yao , FANG Chen . Distribution Estimation Scheduling Algorithm [M]. Beijing : Tsinghua University Press , 2017 : 2 - 3 . (in Chinese)

GU L , HENNEQUIN S , SAVA A , et al . Assembly line balancing problems solved by estimation of distribution [C]// IEEE International Conference on Automation Science & Engineering . Scottsdale : IEEE , 2007 : 123 - 127 .

SUN B Q , WANG L . An estimation of distribution algorithm with branch-and-bound based knowledge for robotic assembly line balancing [J]. Complex & Intelligent Systems , 2020 , 7 ( 2 ): 1 - 14 .

SUN B Q , WANG L , PENG Z P . Bound-guided hybrid estimation of distribution algorithm for energy-efficient robotic assembly line balancing [J]. Computers &Industrial Engineering , 2020 , 146 ( 3 ): 106604 .

SUN B Q , WANG L . A decomposition-based matheuristic for supply chain network design with assembly line balancing [J]. Computers & Industrial Engineering , 2019 , 131 ( 5 ): 408 - 417 .

邓超 , 钱斌 , 胡蓉 , 等 . 融合规则的HEDA求解带工件批量运输的三阶段装配集成调度问题 [J]. 控制与决策 , 2020 , 35 ( 10 ): 2507 - 2513 .

DENG Chao , QIAN Bin , HU Rong , et al . Rule-based hybrid EDA for three-stage assembly integrated scheduling problem with job batches transportation [J]. Control and Decision , 2020 , 35 ( 10 ): 2507 - 2513 . (in Chinese)

WANG S Y , WANG L . An estimation of distribution algorithm-based memetic algorithm for the distributed assembly permutation flow-shop scheduling problem [J]. IEEE Transactions on Systems Man & Cybernetics Systems , 2015 , 46 ( 1 ): 139 - 149 .

KIM Y K , SONG W S , KIM J H . A mathematical model and a genetic algorithm for two-sided assembly line balancing [J]. Computers and Operations Research , 2007 , 36 ( 3 ): 853 - 865 .

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 .

杨海军 , 李建武 , 李敏强 . 进化算法的模式、涌现与困难性研究 [M]. 北京 : 科学出版社 , 2012 : 155 - 156 .

YANG Hai-jun , LI Jian-wu , LI Min-qiang . Evolutionary Algorithms: Schema, Emergence and Hardness [M]. Beijing : Science Press , 2012 : 155 - 156 . (in Chinese)

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Enhanced Artificial Bee Colony Algorithm to Solve Semiconductor Final Test Scheduling Problem

An Enhanced Coverage Control Algorithm for Wireless Sensor Networks Based on Adjustable Parameters

Related Author

LÜ Yang

QIAN Bin

HU Rong

ZHANG Zi-qi

SUN Ze-yu

WU Wei-guo

WANG Huan-zhao

CHEN Heng

Related Institution

Yunnan Key Laboratory of Artificial Intelligence, Kunming University of Science and Technology

School of Electronics and Information Engineering, Xi'an Jiaotong University

Department of Computer and Information Engineering, Luoyang Institute of Technology

School of Computer Science and Educational Software, Guangzhou University

School of Electronics and Information Engineering Xi'an Jiaotong University Xi'an Shaanxi China

⁰