Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2021, Vol. 55 Issue (10): 1795-1805    DOI: 10.3785/j.issn.1008-973X.2021.10.001
    
Optimization of parallel disassembly line balancing problem with different operators between workstations
Ze-qiang ZHANG(),Pei-yu XU,Jin JIANG,Yu ZHANG
Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province, Southwest Jiaotong University, Chengdu 610031, China
Download: HTML     PDF(1087KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

A mixed integer programming model was constructed for parallel disassembly line balancing problem aiming at the problem that the task definition of each disassembly line is unclear and the mathematical models are conceptual models in the existing parallel disassembly line. The difference of operators between workstations was considered. The number of workstations, the number of robots, disassembly cost and idle time balancing index were minimized. An improved brain storm optimization algorithm was proposed. A feasible disassembly sequence was constructed through double-layer coding, and the original operation was discretized. A mutation and crossover mode was designed corresponding to the generation mechanism of a single individual and two individuals. The operation strategy of four-point crossover was designed in order to increase the diversity of population individuals. Pareto solution set and crowding distance were introduced to screen non-inferior solutions of multi-objectives aiming at the multiplicity of optimization objectives. CPLEX and LINGO were used to solve the exact solution of small-scale examples. The correctness of the model and the effectiveness of the algorithm were verified compared with the results of the algorithm. The algorithm was applied to solve P25 classic examples and compared with the results of many existing literatures. The superiority of the algorithm was verified. The proposed model and algorithm were applied to the parallel disassembly line of TV and refrigerator, and the advantages of the proposed algorithm were verified by different comparative experiments.

Key words： parallel disassembly line      difference of operators between workstations      brain storm optimization algorithm      mixed integer programming model     
Received: 20 April 2021      Published: 27 October 2021
CLC:  TH 165  
  TP 301  
Fund:  国家自然科学基金资助项目(51205328,51675450)；教育部人文社会科学研究青年基金资助项目(18YJC630255)；四川省科技计划资助项目(2019YFG0285)
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Ze-qiang ZHANG
Pei-yu XU
Jin JIANG
Yu ZHANG
Cite this article:

Ze-qiang ZHANG,Pei-yu XU,Jin JIANG,Yu ZHANG. Optimization of parallel disassembly line balancing problem with different operators between workstations. Journal of ZheJiang University (Engineering Science), 2021, 55(10): 1795-1805.

URL:

https://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2021.10.001     OR     https://www.zjujournals.com/eng/Y2021/V55/I10/1795


站间操作者不同的并行拆卸线平衡问题优化

针对现有并行拆卸线对各拆卸线任务定义不明确且数学模型均为概念模型，考虑站间操作者不同，构建以最小化工作站数目、机器人数量、拆卸成本和空闲时间均衡指标为优化目标的并行拆卸线平衡问题的混合整数规划模型. 提出适应该问题的改进头脑风暴优化算法，该算法通过双层编码构造可行拆卸序列，离散化原始操作，设计单个个体和2个个体产生机制的变异交叉方式. 为了增加种群个体的多样性，设计四点交叉的操作策略. 针对优化目标的多重性，引入Pareto解集思想和拥挤距离筛选多目标非劣解. 应用CPLEX和LINGO求解小规模算例精确解，与算法求解结果对比，验证了该模型的正确性与算法的有效性. 应用该算法求解P25经典算例，与现有的多篇文献结果对比，验证了该算法求解性能的优越性. 将所建模型和所提算法应用于电视机与电冰箱的并行拆卸线实例中，通过不同的对比实验验证了所提算法的优越性.


关键词： 并行拆卸线,  站间操作者不同,  头脑风暴优化算法,  混合整数规划模型 
Fig.1 Schematic diagram of parallel disassembly line
Fig.2 Parts priority diagram of two products
Fig.3 Schematic diagram of decoding
Fig.4 Generating mechanism diagram based on single individual
Fig.5 Schematic diagram of four-point intersection
Fig.6 Diagram of HV indicator
任务编号 P10 任务编号 P8
tip /s tir /s cost /元 tip /s tir /s cost /元
1 14 10 5.6/3 1 14 10 5.6/3
2 10 12 4/3.6 2 10 7 4/2.1
3 12 8 4.8/2.4 3 12 15 4.8/4.5
4 17 12 6.8/3.6 4 18 13 7.2/3.6
5 23 16 9.2/4.8 5 23 16 9.2/4.8
6 14 15 5.6/4.5 6 16 20 6.4/6
7 19 13 7.6/3.9 7 20 14 8/4.2
8 36 22 14.4/6.6 8 36 25 14.4/7.5
9 14 10 5.6/3 ? ? ? ?
10 10 12 4/3.6 ? ? ? ?
Tab.1 Disassembly information of P10 and P8 examples
精确解 目标类型 求解器 ts /s IBSO算法
f1 f2 f3 f4 f1 f2 f3 f4
7 ? ? ? MILP CPLEX 0.34 7 3 141.56 13
? 0 ? ? MIQP CPLEX 0.28 9 0 144.36 228
? ? 136.12 ? MIQP CPLEX 11.4 7 4 136.12 362
? ? ? 9 MINLP LINGO 183342.7 7 3 142.20 9
Tab.2 Comparison between exact solution and IBSO algorithm
Fig.7 Task allocation diagram of optimal value of each target
算法 f1 f2 f3 f4 HV/108 算法 f1 f2 f3 f4 HV/108
ABC[23] 9 9 81 853 2.774 IBSO 9 9 76 825 5.033
PSO[25] 9 9 80 857 2.814 9 9 77 823
VNS[26] 9 9 76 825 3.905 9 11 75 821
RL[27] 9 9 97 862 0.943 9 15 74 817
9 9 76 825 4.276 9 15 75 815
9 11 75 821 10 157 71 876
GASA[28] 9 15 75 815 11 395 70 870
10 141 73 814 12 559 71 804
10 195 74 811 12 523 73 802
? ? ? ? ? ? 12 559 72 802
Tab.3 Results of solving P25 problem by each algorithm
任务编号 电视机 任务编号 电冰箱
tip /s tir /s cost /元 tip /s tir /s cost /元
1 50 35 20/10.5 1 47 33 18.8/9.9
2 10 7 4/2.1 2 24 17 9.6/5.1
3 3 5 1.2/1.5 3 10 7 4/2.1
4 7 5 2.8/1.5 4 20 14 8/4.2
5 24 30 9.6/9 5 16 20 6.4/6
6 2 4 0.8/1.2 6 20 24 8/7.2
7 10 13 4/3.9 7 20 14 8/4.2
8 18 13 7.2/3.9 8 75 53 30/15.9
9 4 3 1.6/0.9 9 30 21 12/6.3
10 4 3 1.6/0.9 10 7 10 2.8/3
11 4 3 1.6/0.9 11 15 18 65.4
12 4 6 1.6/1.8 12 10 7 4/2.1
13 4 3 1.6/0.9 13 28 20 11.2/6
14 4 3 1.6/0.9 14 20 22 8/6.6
15 4 6 1.6/1.8 15 25 18 10/5.4
16 4 3 1.6/0.9 16 18 13 7.2/3.9
17 4 3 1.6/0.9 17 18 13 7.2/3.9
18 4 3 1.6/0.9 18 7 10 2.8/3
19 17 12 6.8/2.6 19 15 17 6/5.1
20 16 11 6.4/3.3 20 10 7 4/2.1
21 7 5 2.8/1.5 21 5 4 2/1.2
22 3 2 1.2/0.6 22 25 18 10/5.4
23 3 2 1.2/0.6 23 40 28 16/8.4
24 4 3 1.6/0.9 24 60 42 24/12.6
25 2 4 0.8/1.2 25 28 20 11.2/6
26 2 4 0.8/1.2 ? ? ? ?
27 2 4 0.8/1.2 ? ? ? ?
Tab.4 Disassembly information of TV and refrigerator
Fig.8 TV set disassembly priority diagram
Fig.9 Refrigerator disassembly priority diagram
Fig.10 Iterative graph of HV index of four algorithms
序号 f1 f2 f3 f4 拆卸方案
1 7 1 359.16 376 [1，?2，?14，?18，?20]→[Wr: ?3，?15，?4，?16，2，5，4，3，7]→[19，20，?17，?19，6，?1]→[?8，?21，15，10，?10，14，13，?5]→[?6，?9，?11，?22，?12，11，12，9，18，17]→[?13，8，16，21，?7，22，?25，24，25]→[?23，26，23，?24，27]
2 7 2 327.96 4174 [Wr: ?1，1，?2，?16，2，?3，?21]→[?18，3，4，19，20，?20]→[?8，5，7，10，6]→[?4，?9，?5，?19，?10，?11]→[?17，15，9，8，12，?14，18，16，13，17，11，?6]→[?7，14，?15，?12，?13，?22]→[Wr: ?23，?25，?24，21，22，23，25，26，27，24]
3 6 3 309.14 195 [?2，?3，?14，?4，?18，?16，?20]→[Wr: 1，?21，?5，?17，2，?1]→[?19，?8，?10，?6]→[4，7，5，?7，3，?9，15，6，?11，10]→[Wr: ?12，?13，13，9，8，12，16，17，14，19，?23，18，20，21]→[Wr: 22，26，11，23，25，27，24，?24，?15，?22，?25]
4 7 2 333.30 2299 [Wr: ?1，?8]→[1，?9，?2]→[?14，?10，?20，2，7，19，?21，4，3，?11，?12]→[?3，20，?16，?18，?15，?17，?13，?23]→[Wr: ?19，?4，?5，?6，5，15]→[?22，9，8，?24，6]→[?7，?25，10，11，14，13，18，16，21，22，23，24，12，25，26，27，17]
5 7 2 330.16 3708 [1，?1]→[Wr: ?2，?8，?21，?20，?9，?16]→[?10，2，?18，19，5，4，?11，3，?17，?3]→[7，?19，6，?4，?14，10，11，12，14，?15，13，17]→[Wr: ?12，?22，?13，?25，?23]→[?24，15，?5，9，20，8]→[18，16，21，?6，22，23，26，25，?7，27，24]
6 6 6 294.40 507 [Wr: 1，?2，2，19，?1，?3]→[Wr: 7，?18，?8，4，?9，?10]→[Wr: ?14，?11，3，?21，?20，?15，5，?12]→[Wr: ?4，?19，?5，10，13，?13，?23，11，14]→[Wr: ?6，?7，12，15，9，8，17，?16，?17，6，20]→[Wr: ?22，18，16，21，?25，22，24，25，?24，23，27，26]
7 6 4 314.40 7 [Wr: ?2，?20，?18，1，?21，?16，?1]→[Wr: ?3，2，5，?17，?19，?14，19，3，10，11]→[Wr: 7，6，13，?8，?15，?10，?11]→[20，17，?9，?22，?12，4，15，9，?4]→[Wr: 8，14，?25，?5，12，?13，16，21，?23]→[?24，?6，22，?7，24，18，26，25，23，27]
8 6 4 281.88 3774 [Wr: 1，2，19，?2，?1，?3]→[7，5，15，?18，?19]→[Wr: ?8，4，9，18，?4，?9，20，10]→[?5，?10，?14，?11，3，8，12，?6，6，?21，14]→[Wr: ?16，?17，?12，11，?20，?15，13，17，?22，?7，16，21，22，24，23，26]→[Wr: 25，?25，?13，?23，?24，27]
9 7 2 322.22 5040 [?2，?1]→[Wr: 1，?21，?20，?8，?9]→[?16，?10，2，?18，19，5，4，?11，3]→[?17，?3，7，?19，6，?4，?14，10，11，12，14]→[Wr: ?15，?12，13，?13，?22，17，?25，?23]→[?24，15，?5，9，20，8]→[18，16，21，?6，22，23，26，25，?7，27，24]
10 7 0 366.66 111 [?2，1，?20，2，5]→[?14，?1，?21，?15，?18，10，11，14]→[19，?3，4，20，3，15，9，?4，?5，?16]→[?19，?6，?8，?10]→[7，13，12，?17，17，8，16，6，?7，21，?22]→[?11，18，?9，?25，?12，?13]→[?23，?24，22，23，27，26，24，25]
Tab.5 Results of IBSO algorithm for solving examples
[1]   GUNGOR A, GUPTA S M, POCHAMPALLY K, et al. Complications in disassembly line balancing [C]// Proceedings of SPIE International Conference on Environmentally Conscious Manufacturing. Bellingham: SPIE, 2001: 289-298.
[2]   AVIKAL S, JAIN R, YADAV H, et al. A new heuristic for disassembly line balancing problems with AND/OR precedence relation [C]// Proceedings of the 2nd International Conference on Soft Computing for Problem Solving. Lakshmipat: Advances in Intelligent Systems and Computing, 2014: 519-525.
[3]   KOC A, SABUNCUOGLU I, EREL E Two exact formulations for disassembly line balancing problems with task precedence diagram construction using an AND/OR graph[J]. IIE Transactions, 2009, 41 (10): 866- 881
doi: 10.1080/07408170802510390
[4]   REN Y, YU D, ZHANG C, et al An improved gravitational search algorithm for profit-oriented partial disassembly line balancing problem[J]. International Journal of Production Research, 2017, 55 (24): 7302- 7316
doi: 10.1080/00207543.2017.1341066
[5]   丁力平, 谭建荣, 冯毅雄, 等 基于Pareto蚁群算法的拆卸线平衡多目标优化[J]. 计算机集成制造系统, 2009, 15 (7): 1406- 1413
DING Li-ping, TAN Jian-rong, FENG Yi-xiong, et al Multi-objective optimization for disassembly line balancing based on Pareto ant colony algorithm[J]. Computer Integrated Manufacturing Systems, 2009, 15 (7): 1406- 1413
[6]   郭磊, 张秀芬 多重故障驱动的再制造并行拆卸序列规划方法[J]. 浙江大学学报: 工学版, 2020, 54 (11): 2233- 2246
GUO Lei, ZHANG Xiu-fen Remanufacturing parallel disassembly sequence planning method driven by multiple failures[J]. Journal of Zhejiang University: Engineering Science, 2020, 54 (11): 2233- 2246
[7]   徐进, 张树有, 费少梅 基于自适应粒子群的产品再制造拆卸规划[J]. 浙江大学学报: 工学版, 2011, 45 (10): 1746- 1752
XU Jin, ZHANG Shu-you, FEI Shao-mei Product remanufacture disassembly planning based on adaptive particle swarm optimization algorithm[J]. Journal of Zhejiang University: Engineering Science, 2011, 45 (10): 1746- 1752
doi: 10.3785/j.issn.1008-973X.2011.10.008
[8]   朱卓悦, 徐志刚, 沈卫东, 等 基于遗传蝙蝠算法的选择性拆卸序列规划[J]. 浙江大学学报(工学版), 2018, 52 (11): 2120- 2127
ZHU Zhuo-yue, XU Zhi-gang, SHEN Wei-dong, et al Selective-disassembly sequence planning based on genetic-bat algorithm[J]. Journal of Zhejiang University: Engineering Science, 2018, 52 (11): 2120- 2127
doi: 10.3785/j.issn.1008-973X.2018.11.010
[9]   鲁建厦, 翟文倩, 李嘉丰, 等 基于改进混合蛙跳算法的多约束车辆路径优化[J]. 浙江大学学报(工学版), 2021, 55 (2): 259- 270
LU Jian-xia, ZHAI Wen-qian, LI Jia-feng, et al Multi-constrained vehicle routing optimization based on improved hybrid shuffled frog leaping algorithm[J]. Journal of Zhejiang University: Engineering Science, 2021, 55 (2): 259- 270
[10]   王云, 冯毅雄, 谭建荣, 等 柔性作业车间分批调度多目标优化方法[J]. 浙江大学学报: 工学版, 2011, 45 (4): 719- 726
WANG Yun, FENG Yi-xiong, TAN Jian-rong, et al Multi-objective optimization method of flexible job-shop lot-splitting scheduling[J]. Journal of Zhejiang University: Engineering Science, 2011, 45 (4): 719- 726
doi: 10.3785/j.issn.1008-973X.2011.04.022
[11]   任彩乐, 张超勇, 孟磊磊, 等 基于改进候鸟优化算法的混合流水车间调度问题[J]. 计算机集成制造系统, 2019, 25 (3): 643- 653
REN Cai-yue, ZHANG Chao-yong, MENG Lei-lei, et al Hybrid flow-shop scheduling problems based on improved migrating birds optimization algorithm[J]. Computer Integrated Manufacturing Systems, 2019, 25 (3): 643- 653
[12]   OZCEYLAN E, KALAYCI C, GUNGOR A, et al Disassembly line balancing problem a review of the state of the art and future directions[J]. International Journal of Production Research, 2019, 57 (15/16): 4805- 4827
doi: 10.1080/00207543.2018.1428775
[13]   GAO K, HE Z, HUANG Y, et al A survey on meta-heuristics for solving disassembly line balancing, planning and scheduling problems in remanufacturing[J]. Swarm and Evolutionary Computation, 2020, 57: 100719
doi: 10.1016/j.swevo.2020.100719
[14]   LAILI Y, LI Y, FANG Y, et al Model review and algorithm comparison on multi-objective disassembly line balancing[J]. Journal of Manufacturing Systems, 2020, 56: 484- 500
doi: 10.1016/j.jmsy.2020.07.015
[15]   HEZER S, KARA Y A network-based shortest route model for parallel disassembly line balancing problem[J]. International Journal of Production Research, 2015, 53 (6): 1849- 1865
doi: 10.1080/00207543.2014.965348
[16]   GUO J, PU A P, DU B G, et al. Multi-objective optimization of stochastic hybrid production line balancing including assembly and disassembly tasks [EB/OL]. (2021-04-05). https://www.tandfonline.com/doi/full/10.1080/00207543.2021.1905902.
[17]   ZHU L, ZHANG Z, GUAN C Multi-objective partial parallel disassembly line balancing problem using hybrid group neighbourhood search algorithm[J]. Journal of Manufacturing Systems, 2020, 56: 252- 269
doi: 10.1016/j.jmsy.2020.06.013
[18]   SHI Y Brain storm optimization algorithm[J]. Lecture Notes in Computer Science, 2011, 3 (4): 303- 309
[19]   齐元豪, 王凯, 付亚平 基于头脑风暴算法的电动货车路径优化问题[J]. 计算机技术与发展, 2020, 30 (4): 74- 78
QI Yuan-hao, WANG Kai, FU Ya-ping Path optimization problem of electric freight car based on brainstorming algorithm[J]. Computer Technology and Development, 2020, 30 (4): 74- 78
doi: 10.3969/j.issn.1673-629X.2020.04.014
[20]   吴秀丽, 张志强, 李俊青 求解离散调度问题的双机制头脑风暴优化算法[J]. 控制与决策, 2017, 32 (9): 1583- 1590
WU Xiu-li, ZHANG Zhi-qiang, LI Jun-qing A brain storm optimization algorithm integrating diversity and discussion mechanism for solving discrete production scheduling problem[J]. Control and Decision, 2017, 32 (9): 1583- 1590
[21]   DEK K, PRATAP A, AGARWAL S, et al A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6 (2): 182- 197
doi: 10.1109/4235.996017
[22]   BADER J, ZITALER E HypE: an algorithm for fast hypervolume-based many-objective optimization[J]. Evolutionary Computation, 2011, 19 (1): 45- 76
doi: 10.1162/EVCO_a_00009
[23]   KALAYCI C B, GUPTA S M Artificial bee colony algorithm for solving sequence-dependent disassembly line balancing problem[J]. Expert Systems with Applications, 2013, 40 (18): 7231- 7241
doi: 10.1016/j.eswa.2013.06.067
[24]   GUPTA S M, MCGOVERN S M. Disassembly sequencing problem: a case study of a cell phone [C]// 4th International Conference on Environmentally Conscious Manufacturing. Philadelphia: SPIE, 2004: 43-52.
[25]   KALAYCI C, GUPTA S. A particle swarm optimization algorithm for solving disassembly line balancing problem [C]// Proceedings of Northeast Decision Sciences Institute 2012 Annual Conference. Newport, Rhode Island: Northeast Decision Sciences Institute, 2012: 347-357.
[26]   KALAYCI C B, POLAT O, GUPTA S M A variable neighbourhood search algorithm for disassembly lines[J]. Journal of Manufacturing Technology Management, 2015, 26 (2): 182- 194
doi: 10.1108/JMTM-11-2013-0168
[27]   TUNCEL E, ZEID A, KAMARTHI S Solving large scale disassembly line balancing problem with uncertainty using reinforcement learning[J]. Journal of Intelligent Manufacturing, 2014, 25 (4): 647- 659
doi: 10.1007/s10845-012-0711-0
[28]   汪开普, 张则强, 朱立夏, 等 多目标拆卸线平衡问题的Pareto遗传模拟退火算法[J]. 计算机集成制造系统, 2017, 23 (6): 1277- 1285
WANG Kai-pu, ZHANG Ze-qiang, ZHU Li-xia, et al Pareto genetic simulated annealing algorithm for multi-objective disassembly line balancing problem[J]. Computer Integrated Manufacturing Systems, 2017, 23 (6): 1277- 1285
[29]   ZHU L, ZHANG Z, WANG Y, et al On the end-of-life state oriented multi-objective disassembly line balancing problem[J]. Journal of Intelligent Manufacturing, 2020, 31 (6): 1403- 1428
doi: 10.1007/s10845-019-01519-3
[1] YANH Yu-ting, SHI Yu-hui, XIA Shun-ren. Discussion mechanism based brain storm optimization algorithm[J]. Journal of ZheJiang University (Engineering Science), 2013, 47(10): 1705-1711.