工业工程

工业工程 ›› 2019, Vol. 22 ›› Issue (5): 68-74.doi: 10.3969/j.issn.1007-7375.2019.05.009

• 专题论述 • 上一篇    下一篇

求解考虑顺序相关调整时间的双边装配线平衡问题的变邻域搜索算法

杨武成, 程文明   

  1. 西南交通大学 机械工程学院, 四川 成都 610031
  • 收稿日期:2018-12-25 出版日期:2019-10-31 发布日期:2019-10-29
  • 通讯作者: 程文明(1963-),男,浙江省人,教授,博士生导师,主要研究方向为起重机轻量化与智能化控制研究,E-mail:wmcheng@home.swjtu.edu.cn. E-mail:wmcheng@home.swjtu.edu.cn
  • 作者简介:杨武成(1991-),男,湖南省人,博士研究生,主要研究方向为制造系统和智能优化
  • 基金资助:
    国家自然科学基金资助项目（51675450）

A Variable Neighborhood Search Algorithm for Solving Two-sided Assembly Line Balancing Problem with Sequence-dependent Setup Times

YANG Wucheng, CHENG Wenming   

  1. School of Mechanical Engineering, Southwest Jiaotong University, Chengdu 610031, China
  • Received:2018-12-25 Online:2019-10-31 Published:2019-10-29

PDF

5846

摘要： 为有效解决带有顺序相关调整时间的双边装配线平衡问题，提出了一种简单高效的变邻域搜索算法。该算法通过将优先关系约束融入到交换、插入、交叉、变异等算子中，分别得到4个不同的邻域结构来保证搜索过程中解的可行性，避免过多重复邻域解的生成。4个邻域结构的搜索空间依次变大，以增强算法搜索能力。同时，结合装配线的特点，提出基于作业序列的编码和解码方式，在解码过程中，优先选择空闲时间较多的边，引入启发式目标加快算法收敛。分配结束后，对装配线末端的工作站组进行局部调整。通过将该算法先后用于求解无/有顺序相关调整时间的双边装配线平衡第一类问题，并与已有的算法进行对比，验证了所提的变邻域搜索算法的优越性和有效性。

关键词: 顺序相关调整时间, 双边装配线平衡问题, 变邻域搜索算法

Abstract: To efficiently solve the two-sided assembly line balancing problem with sequence-dependent setup times, an effective and simple variable neighborhood search algorithm is proposed.To enhance the diversity of the variable neighborhood search algorithm and avoid generating too many replicated solutions, four precedence based neighborhood structures are designed, which include swap, insert, crossover and mutation operators. The search space of the four structures are getting larger successively to enhance the searching ability of the local search. What's more, a task permutation decoding and coding method are adopted based on the features of assembly lines. For decoding, a side which has larger capacity is preferred to be selected. Some new heuristic objectives were added to speed up the convergence of the algorithm. When all tasks have been assigned, an adjustment for final mated workstation is made. The proposed algorithm is firstly applied to solving the two-sided assembly line balancing type-1 problem without considering the setup times and then two-sided assembly line balancing type-1 problem with sequence-dependent setup times is solved. A comprehensive comparative study is conducted and the results demonstrated that the proposed variable neighborhood search showed superiority performance over the compared ones.

Key words: sequence-dependent setup times, two-sided assembly line balancing problem, variable neighborhood search algorithm

中图分类号: