Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2025, Vol. 59 Issue (11): 2248-2258    DOI: 10.3785/j.issn.1008-973X.2025.11.003
    
Modeling and optimization of human-robot collaborative U-shaped disassembly line problem with multi-constraint
Haiye CHEN1(),Zeqiang ZHANG1,2,*(),Wei LIANG1,Lei GUO1,Qiyao DUAN2
1. Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province, Southwest Jiaotong University, Chengdu 610031, China
2. Tangshan Institute, Southwest Jiaotong University, Tangshan 063000, China
Download: HTML     PDF(1077KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

A multi-constrained human-robot collaborative disassembly line balancing problem was proposed for U-shaped disassembly lines in order to address the issues that existing studies on human-robot collaborative disassembly lines neither simultaneously consider differences in human and robotic task time and task attribute constraint, nor incorporate robot procurement costs into the long-term costs of collaboration. An integer programming model for the U-shaped disassembly line was constructed, with the objectives of minimizing the number of workstations, the idle time balancing index, and the long-term cost. Constraints considering various problem characteristics, including human-robot task attributes, human-robot task time, and AND/OR precedence relations were incorporated. An improved hybrid clonal simulated annealing algorithm was proposed. Double-layer encoding and decoding were designed, along with mutation and crossover operations specifically considering the problem characteristics. Cloning operations were introduced to enhance the local search capability of the algorithm, and a two-stage annealing process was implemented to accelerate convergence speed. Gurobi software was applied to solve small and medium-scale problems, and the results were compared with those obtained by the algorithm to verify the correctness and effectiveness of the model and algorithm. The cost variations of different disassembly line modes with the estimated operational time of the disassembly line were calculated and compared. Results demonstrate that the proposed model possesses the advantage of agile disassembly line planning.

Key words： U-shaped disassembly line balancing problem      human-robot collaborative disassembly line      improved hybrid clone selection simulated annealing algorithm      integer programming model      multi-objective optimization     
Received: 30 October 2024      Published: 30 October 2025
CLC:  TH 165  
  TP 301  
Fund:  国家自然科学基金资助项目(52375268, 52342505, 72401239); 教育部人文社会科学研究规划基金资助项目(23YJA630139); 河北省自然科学基金资助项目(E2024105031); 四川省自然科学基金资助项目(2025ZNSFSC0425, 2024NSFSC1048, 2024ZHCG0059).
Corresponding Authors: Zeqiang ZHANG     E-mail: 1627508814@qq.com;zhangzq@home.swjtu.edu.cn
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Haiye CHEN
Zeqiang ZHANG
Wei LIANG
Lei GUO
Qiyao DUAN
Cite this article:

Haiye CHEN,Zeqiang ZHANG,Wei LIANG,Lei GUO,Qiyao DUAN. Modeling and optimization of human-robot collaborative U-shaped disassembly line problem with multi-constraint. Journal of ZheJiang University (Engineering Science), 2025, 59(11): 2248-2258.

URL:

https://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2025.11.003     OR     https://www.zjujournals.com/eng/Y2025/V59/I11/2248


多约束人机协作U型拆卸线问题建模与优化

针对现有人机协作拆卸线研究中未同时考虑人机任务时间差异和任务属性约束，且未将机器人购置成本考虑在人机协作长期成本中的问题，结合U型拆卸线，提出多约束人机协作拆卸线平衡问题. 以工作站数量、空闲时间均衡指标和长期成本为目标函数，构建考虑人机任务属性、人机任务时间、AND/OR优先关系等多种问题特征约束的U型拆卸线整数规划模型. 提出改进混合克隆模拟退火算法，设计双层编码、解码和考虑问题特性的变异和交叉操作. 引入克隆操作增强算法的局部搜索能力，通过两阶段退火加快算法的收敛速度. 应用Gurobi软件求解中小规模问题，与算法的求解结果进行对比，验证了模型和算法的正确性和有效性. 通过分别计算和对比不同模式拆卸线的成本随拆卸线预估运行时间的变化情况，验证了该模型具有柔性拆卸线规划的优点.


关键词： U型拆卸线平衡问题,  人机协作拆卸线,  改进混合克隆模拟退火算法,  整数规划模型,  多目标优化 
Fig.1 Schematic diagram of human-robot collaborative U-shaped disassembly line
Fig.2 Schematic diagram of IHCSSA encoding process
Fig.3 Flowchart of IHCSSA encoding
Fig.4 Flowchart of IHCSSA decoding
Fig.5 Schematic diagram of index cooling stage variation operation
Fig.6 Schematic diagram of crossover operation
Fig.7 Schematic diagram of IHCSSA cloning operation
Fig.8 Schematic diagram of cross operation in linear cooling stage
Fig.9 Flow chart of IHCSSA algorithm
任务t1, t2/sc1, c2/元任务t1, t2/sc1, c2/元
114, 100.70, 0.30514, 150.70, 0.45
220, —1.00, —615, 110.75, 0.33
3—, 8—, 0.24710, 120.50, 0.36
420, 141.00, 0.42813, 110.65, 0.33
Tab.1 Disassembly information of P8 example
任务t1, t2/sc1, c2/元任务t1, t2/sc1, c2/元
147, 332.35, 0.991420, 221.00, 0.66
2—, 17—, 0.511525, 181.25, 0.54
310, 70.50, 0.211618, 130.90, 0.39
420, 141.00, 0.421718, 130.90, 0.39
516, 200.80, 0.60187, —0.35, —
620, 241.00, 0.721915, 170.75, 0.51
720, 141.00, 0.422010, 70.50, 0.21
8—, 53—, 1.59215, 40.25, 0.12
930, 211.50, 0.602225, 181.25, 0.54
107, —0.35, —2340, 282.00, 0.84
1115, 180.75, 0.5424—, 42—, 1.26
1210, 70.50, 0.212528, 201.40, 0.60
13—, 20—, 0.6———
Tab.2 Disassembly information of P25 example
P8精确解t/s改进混合克隆模拟退火算法t/s
f1f2f3f1f2f3
3——0.103451042720.32
—37—0.47337105024
——1005840.243136100584
P25精确解t/s改进混合克隆模拟退火算法t/s
f1f2f3f1f2f3
6——0.766235480811.71
—2—1919.9162359368
——31282411.4971321312824
Tab.3 Comparison of Gurobi solver and IHCSSA solution result
IANSGA-II
f1f2f3f1f2f3
6$\underline{{\rm{67}}}$355312648355512
6$\underline{{\rm{68}}}$3547606$\underline{{\rm{83}}}$355008
61153530086100354760
6$\underline{{\rm{189}}}$3512006101353328
62223501206$\underline{{\rm{157}}}$351728
62613495686$\underline{{\rm{173}}}$351200
7113031500871075317368
$\underline 7$1186314480$\underline 7$1263315560
71253313928$\underline 7$1355313928
$\underline 7$1374313200$\underline 7$1546313200
SAIHCSSA
f1f2f3f1f2f3
6$\underline{{\rm{66}}}$40692862359368
6$\underline{{\rm{89}}}$40584867358768
6105353328610358216
6135353008659355008
61423522806151351728
$\underline 7$$\underline{{\rm{828}}}$3197286163351200
78433191767764319728
7113431500871170314480
7127731392871318313200
$\underline 7$139031320071321312824
Tab.4 Result of four algorithms solving P25 problem
Fig.10 Box plot of IGD indicator for solving P25 result using four algorithms
Fig.11 Precedence constraint graph of instance P74
任务t1, t2/sc1, c2/元任务t1, t2/sc1, c2/元任务t1, t2/sc1, c2/元任务t1, t2/sc1, c2/元
12, 10.10, 0.03203, 20.15, 0.06393, 20.15, 0.06574, 30.20, 0.09
23, 20.15, 0.06213, —0.15, —403, 20.15, 0.06584, 20.20, 0.06
33, 10.15, 0.03223, 20.15, 0.06414, 30.20, 0.095912, 100.60, 0.30
44, 20.20, 0.06232, 10.10, 0.03425, —0.25, —604, 31.60, 0.93
53, 20.15, 0.06242, 10.10, 0.03433, 20.15, 0.06615, 50.25, 0.15
68, —0.40, —253, 10.15, 0.03449, 70.45, 0.21623, 20.15, 0.06
76, 50.30, 0.15262, 10.10, 0.03455, 40.25, 0.12634, 20.40, 0.18
83, 20.15, 0.06274, 40.20, 0.12462, 10.10, 0.03645, 40.10, 0.06
92, 20.10, 0.0628—, 11—, 0.33472, 10.10, 0.06654, 30.20, 0.09
1011, 90.55, 0.27297, 60.35, 0.18484, 20.20, 0.06664, 30.20, 0.09
118, —0.40, —304, 30.20, 0.09493, 10.15, 0.03673, 10.15, 0.03
124, 30.20, 0.09313, 20.15, 0.06502, 10.10, 0.036813, 110.65, 0.33
136, 50.30, 0.15325, 40.25, 0.12512, 10.10, 0.03697, —0.35, —
14—, 30.50, 0.27336, —0.25, —522, 10.10, 0.03705, 40.25, 0.12
153, 20.15, 0.06347, 50.35, 0.15533, 20.15, 0.06714, 30.20, 0.09
166, 60.30, 0.183512, 120.60, 0.36542, 10.10, 0.03726, 50.30, 0.15
176, 50.30, 0.15364, 30.20, 0.0955—, 2—, 0.06733, 20.15, 0.06
184, 30.20, 0.09375, 30.25, 0.09566, 50.30, 0.15744, 30.20, 0.09
1912, 100.60, 0.3038—, 5—, 0.15——————
Tab.5 Disassembly information for P74 instance
Fig.12 HV convergence plot of five algorithms on P74
Fig.13 Operating cost of disassembly line under different operator mode
[1]   XU X, LU Y, VOGEL-HEUSER B, et al Industry 4.0 and Industry 5.0: inception, conception and perception[J]. Journal of Manufacturing Systems, 2021, 61: 530- 535
doi: 10.1016/j.jmsy.2021.10.006
[2]   GUNGOR A, GUPTA S M A solution approach to the disassembly line balancing problem in the presence of task failures[J]. International Journal of Production Research, 2001, 39 (7): 1427- 1467
doi: 10.1080/00207540110052157
[3]   GUO X, FAN C, ZHOU M, et al Human–robot collaborative disassembly line balancing problem with stochastic operation time and a solution via multi-objective shuffled frog leaping algorithm[J]. IEEE Transactions on Automation Science and Engineering, 2024, 21 (3): 4448- 4459
doi: 10.1109/TASE.2023.3296733
[4]   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
[5]   WANG W, GUO X, LIU S, et al. Multi-objective discrete chemical reaction optimization algorithm for multiple-product partial U-shaped disassembly line balancing problem [C]// IEEE International Conference on Systems. Melbourne: IEEE, 2021: 2322-2327.
[6]   WU K, GUO X, LIU S, et al. Multi-objective discrete brainstorming optimizer for multiple-product partial U-shaped disassembly line balancing problem [C]//33rd Chinese Control and Decision Conference. Kunming: IEEE, 2021: 305-310.
[7]   KHEIRABADI M, KEIVANPOUR S, CHINNIAH Y A, et al Human-robot collaboration in assembly line balancing problems: review and research gaps[J]. Computers and Industrial Engineering, 2023, 186: 109737
doi: 10.1016/j.cie.2023.109737
[8]   HARTONO N, RAMÍREZ F J, PHAM D T A multiobjective decision-making approach for modelling and planning economically and environmentally sustainable robotic disassembly for remanufacturing[J]. Computers and Industrial Engineering, 2023, 184: 109535
doi: 10.1016/j.cie.2023.109535
[9]   LOU S, TAN R, ZHANG Y, et al Personalized disassembly sequence planning for a human-robot Hybrid disassembly cell[J]. IEEE Transactions on Industrial Informatics, 2024, 20 (9): 11372- 11383
doi: 10.1109/TII.2024.3403254
[10]   张则强, 许培玉, 蒋晋, 等 站间操作者不同的并行拆卸线平衡问题优化[J]. 浙江大学学报: 工学版, 2021, 55 (10): 1795- 1805
ZHANG Zeqiang, XU Peiyu, JIANG Jin, et al Optimization of parallel disassembly line balancing problem with different operators between workstations[J]. Journal of Zhejiang University: Engineering Science, 2021, 55 (10): 1795- 1805
[11]   WU T, ZHANG Z, YIN T, et al Multi-objective optimisation for cell-level disassembly of waste power battery modules in human-machine hybrid mode[J]. Waste Management, 2022, 144: 513- 526
doi: 10.1016/j.wasman.2022.04.015
[12]   GUO L, ZHANG Z, WU T, et al Green and efficient-oriented human-robot hybrid partial destructive disassembly line balancing problem from non-disassemblability of components and noise pollution[J]. Robotics and Computer-Integrated Manufacturing, 2024, 90: 102816
doi: 10.1016/j.rcim.2024.102816
[13]   CHUTIMA P, KHOTSAENLEE A Multi-objective parallel adjacent U-shaped assembly line balancing collaborated by robots and normal and disabled workers[J]. Computers and Operations Research, 2022, 143: 105775
doi: 10.1016/j.cor.2022.105775
[14]   丁力平, 谭建荣, 冯毅雄, 等 基于Pareto蚁群算法的拆卸线平衡多目标优化[J]. 计算机集成制造系统, 2009, 15 (7): 1406- 1413
DING Liping, TAN Jianrong, FENG Yixiong, et al Multiobjective optimization for disassembly line balancing based on Pareto ant colony algorithm[J]. Computer Integrated Manufacturing Systems, 2009, 15 (7): 1406- 1413
[15]   郭磊, 张秀芬 多重故障驱动的再制造并行拆卸序列规划方法[J]. 浙江大学学报: 工学版, 2020, 54 (11): 2233- 2246
GUO Lei, ZHANG Xiufen Remanufacturing parallel disassembly sequence planning method driven by multiple failures[J]. Journal of Zhejiang University: Engineering Science, 2020, 54 (11): 2233- 2246
[16]   脱阳, 张则强, 张裕, 等 考虑可变时间的双边机器人拆卸线平衡问题建模与优化[J]. 计算机集成制造系统, 2023, 29 (12): 4073- 4088
TUO Yang, ZHANG Zeqiang, ZHANG Yu, et al Modeling and optimization for two-sided robots disassembly line balancing problems considering variable time[J]. Computer Integrated Manufacturing Systems, 2023, 29 (12): 4073- 4088
[17]   黄家骏, 腾来, 张朝杰, 等 基于模拟退火算法的I/Q不平衡校正[J]. 浙江大学学报: 工学版, 2018, 52 (11): 2218- 2225
HUANG Jiajun, TENG Lai, ZHANG Chaojie, et al I/Q imbalance calibration based on simulated annealing algorithm[J]. Journal of Zhejiang University: Engineering Science, 2018, 52 (11): 2218- 2225
[18]   WU T, ZHANG Z, ZENG Y, et al Techno-economic and environmental benefits-oriented human–robot collaborative disassembly line balancing optimization in remanufacturing[J]. Robotics and Computer-Integrated Manufacturing, 2024, 86: 102650
doi: 10.1016/j.rcim.2023.102650
[19]   JIN X, DU H, HE W, et al. Optimizing the weights of neural networks based on antibody clonal simulated annealing algorithm [C]// Advances in Neural Networks. Berlin: Springer, 2004: 299-304.
[20]   ZHANG X, TIAN G, FATHOLLAHI-FARD A M, et al A chance-constraint programming approach for a disassembly line balancing problem under uncertainty[J]. Journal of Manufacturing Systems, 2024, 74: 346- 366
doi: 10.1016/j.jmsy.2024.03.014
[21]   YIN T, ZHANG Z, JIANG J A Pareto-discrete hummingbird algorithm for partial sequence-dependent disassembly line balancing problem considering tool requirements[J]. Journal of Manufacturing Systems, 2021, 60: 406- 428
doi: 10.1016/j.jmsy.2021.07.005
[22]   KALAYCI C B, GUPTA S M A tabu search algorithm for balancing a sequence-dependent disassembly line[J]. Production Planning and Control, 2014, 25 (2): 149- 160
doi: 10.1080/09537287.2013.782949
[23]   XU Z, HAN Y Two sided disassembly line balancing problem with rest time of works: a constraint programming model and an improved NSGA II algorithm[J]. Expert Systems with Applications, 2024, 239: 122323
doi: 10.1016/j.eswa.2023.122323
[24]   ZHOU B, BIAN J A bi-objective salp swarm algorithm with sine cosine operator for resource constrained multi-manned disassembly line balancing problem[J]. Applied Soft Computing, 2022, 131: 109759
doi: 10.1016/j.asoc.2022.109759
[25]   ZHANG Z, LIANG W, JI D, et al Mixed integer programming and multi-objective enhanced differential evolution algorithm for human–robot responsive collaborative disassembly in remanufacturing system[J]. Advanced Engineering Informatics, 2024, 62: 102895
doi: 10.1016/j.aei.2024.102895
[1] Yabo LUO,Shaolong YU,Feng ZHANG,Cunrong LI. Improved migrating bird algorithm for re-entrant hybrid flowshop scheduling problem with lot streaming[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(8): 1598-1607.
[2] Yu WANG,Chunrong MA,Mingyue ZHAO. Collaborative multi-task assignment of heterogeneous UAVs based on hybrid strategies based multi-objective particle swarm[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(4): 821-831.
[3] Yong LI,Yue WANG,Fuqiang LIU,Baiqing SUN,Kairu LI. Multi-task allocation framework in context of caregiver-robot collaborative elderly care[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(2): 375-383.
[4] Yingfei ZHANG,Xiaobing HU,Hang ZHOU,Xuzeng FENG. Three-dimensional sector automatic design based on improved NSGA-II algorithm[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(2): 413-422.
[5] Mengyuan HAO,Leike ZHANG,Xiaolian LIU,Xueni WANG,Yu TIAN. Pumps and valves joint optimization control in complex water conveyance system based on artificial rabbits optimization algorithm[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(10): 2115-2124.
[6] Tingfang YU,Genli ZHANG,Jiapeng ZHOU,Yicun TANG. Performance analysis and optimization of supercritical CO2 Brayton cycle coupled with organic flash cycle[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(1): 130-140.
[7] Ruoqiong LI,Yuan WENG,Xin LI. Parameter optimization of fractional-order magnetically-coupled resonant bidirectional wireless power transfer system[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(1): 141-151.
[8] Qianlin YE,Wanliang WANG,Zheng WANG. Survey of multi-objective particle swarm optimization algorithms and their applications[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(6): 1107-1120.
[9] Yan ZHAN,Jieya CHEN,Weiguang JIANG,Jiansha LU,Hongtao TANG,Xinyu SONG,Lili XU,Saimiao LIU. Multi-objective workshop material distribution method based on improved NSGA-Ⅱ[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(12): 2510-2519.
[10] Xiao-yan CAO,Min YU,Jin ZHOU,Yun-zhi WANG. Multi-objective optimization design of adjustable rotary fluid damper parameter[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(7): 1439-1449.
[11] Jing-shuai YANG,Yu-e YANG,Man-man LI,Yuan-yuan LI. Joint optimization of terminal distribution service mode and distribution routing[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(5): 900-910.
[12] Ting-fang YU,Ling SONG. Performance analysis and optimization of supercritical CO2 Brayton cycle waste heat recovery system[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(2): 404-414.
[13] Wan-liang WANG,Zhong-kui CHEN,Fei WU,Zheng WANG,Meng-jiao YU. Dynamic multi-objective optimization algorithm based on individual prediction[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(11): 2133-2146.
[14] Wan-liang WANG,Ya-wen JIN,Jia-cheng CHEN,Guo-qing LI,Ming-zhi HU,Jian-hang DONG. Multi-objective particle swarm optimization algorithm with multi-role and multi-strategy[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(3): 531-541.
[15] Jun-heng XU,Xiao-jun YANG,Bing LI. Design of wing mechanism with variable camber based on cross-spring flexural pivots[J]. Journal of ZheJiang University (Engineering Science), 2022, 56(3): 444-451, 509.