Please wait a minute...
浙江大学学报(工学版)  2025, Vol. 59 Issue (11): 2248-2258    DOI: 10.3785/j.issn.1008-973X.2025.11.003
机械工程、能源工程     
多约束人机协作U型拆卸线问题建模与优化
陈海烨1(),张则强1,2,*(),梁巍1,郭磊1,段淇耀2
1. 西南交通大学 轨道交通运维技术与装备四川省重点实验室,四川 成都 610031
2. 西南交通大学唐山研究院,河北 唐山 063000
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
 全文: PDF(1077 KB)   HTML
摘要:

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

关键词: U型拆卸线平衡问题人机协作拆卸线改进混合克隆模拟退火算法整数规划模型多目标优化    
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
收稿日期: 2024-10-30 出版日期: 2025-10-30
:  TH 165  
基金资助: 国家自然科学基金资助项目(52375268, 52342505, 72401239); 教育部人文社会科学研究规划基金资助项目(23YJA630139); 河北省自然科学基金资助项目(E2024105031); 四川省自然科学基金资助项目(2025ZNSFSC0425, 2024NSFSC1048, 2024ZHCG0059).
通讯作者: 张则强     E-mail: 1627508814@qq.com;zhangzq@home.swjtu.edu.cn
作者简介: 陈海烨(2001—),男,硕士生,从事智能制造优化的研究. orcid.org/0009-0008-0456-3632. E-mail:1627508814@qq.com
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章  
陈海烨
张则强
梁巍
郭磊
段淇耀

引用本文:

陈海烨,张则强,梁巍,郭磊,段淇耀. 多约束人机协作U型拆卸线问题建模与优化[J]. 浙江大学学报(工学版), 2025, 59(11): 2248-2258.

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.

链接本文:

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

图 1  人机协作U型拆卸线的示意图
图 2  IHCSSA编码过程的示意图
图 3  IHCSSA编码的流程图
图 4  IHCSSA解码的流程图
图 5  指数冷却阶段变异操作的示意图
图 6  交叉操作的示意图
图 7  IHCSSA克隆操作的示意图
图 8  线性冷却阶段交叉操作的示意图
图 9  IHCSSA算法的流程图
任务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
表 1  P8算例的拆卸信息
任务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
表 2  P25算例的拆卸信息
P8精确解t/s改进混合克隆模拟退火算法t/s
f1f2f3f1f2f3
30.103451042720.32
370.47337105024
1005840.243136100584
P25精确解t/s改进混合克隆模拟退火算法t/s
f1f2f3f1f2f3
60.766235480811.71
21919.9162359368
31282411.4971321312824
表 3  Gurobi求解器与IHCSSA算法的求解结果对比
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
表 4  利用4种算法求解P25问题的结果
图 10  利用4种算法求解P25结果的IGD指标箱型图
图 11  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
表 5  P74实例的拆卸信息
图 12  利用5种算法求解P74的HV迭代图
图 13  不同操作者模式下的拆卸线运行成本
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] 罗亚波,喻少龙,张峰,李存荣. 改进候鸟算法求解可重入混流车间批量流调度[J]. 浙江大学学报(工学版), 2025, 59(8): 1598-1607.
[2] 王昱,马春荣,赵明月. 基于混合策略多目标粒子群的异构无人机协同多任务分配[J]. 浙江大学学报(工学版), 2025, 59(4): 821-831.
[3] 李勇,王跃,柳富强,孙柏青,李恺如. 护工-机器人协作养老情境下的多任务分配框架[J]. 浙江大学学报(工学版), 2025, 59(2): 375-383.
[4] 张盈斐,胡小兵,周航,冯序增. 基于改进的NSGA-II算法的三维扇区自动划设[J]. 浙江大学学报(工学版), 2025, 59(2): 413-422.
[5] 郝梦园,张雷克,刘小莲,王雪妮,田雨. 基于人工兔算法的复杂输水系统泵阀联合优化调控[J]. 浙江大学学报(工学版), 2025, 59(10): 2115-2124.
[6] 余廷芳,张艮离,周嘉鹏,汤一村. 超临界CO2布雷顿循环耦合有机闪蒸循环的性能分析及优化[J]. 浙江大学学报(工学版), 2025, 59(1): 130-140.
[7] 李若琼,翁源,李欣. 分数阶磁耦合谐振双向无线电能传输系统参数优化[J]. 浙江大学学报(工学版), 2025, 59(1): 141-151.
[8] 叶倩琳,王万良,王铮. 多目标粒子群优化算法及其应用研究综述[J]. 浙江大学学报(工学版), 2024, 58(6): 1107-1120.
[9] 詹燕,陈洁雅,江伟光,鲁建厦,汤洪涛,宋新禹,许丽丽,刘赛淼. 基于改进NSGA-Ⅱ的多目标车间物料配送方法[J]. 浙江大学学报(工学版), 2024, 58(12): 2510-2519.
[10] 曹晓彦,于敏,周瑾,王运志. 可调旋转式流体阻尼器参数多目标优化设计[J]. 浙江大学学报(工学版), 2023, 57(7): 1439-1449.
[11] 杨京帅,杨玉娥,李嫚嫚,李园园. 末端配送服务模式与路径联合优化[J]. 浙江大学学报(工学版), 2023, 57(5): 900-910.
[12] 余廷芳,宋凌. 超临界CO2布雷顿循环余热回收系统性能分析与优化[J]. 浙江大学学报(工学版), 2023, 57(2): 404-414.
[13] 王万良,陈忠馗,吴菲,王铮,俞梦娇. 基于个体预测的动态多目标优化算法[J]. 浙江大学学报(工学版), 2023, 57(11): 2133-2146.
[14] 王万良,金雅文,陈嘉诚,李国庆,胡明志,董建杭. 多角色多策略多目标粒子群优化算法[J]. 浙江大学学报(工学版), 2022, 56(3): 531-541.
[15] 徐钧恒,杨晓钧,李兵. 基于交叉簧片式铰链的变弯度机翼机构设计[J]. 浙江大学学报(工学版), 2022, 56(3): 444-451, 509.