Please wait a minute...
浙江大学学报(工学版)
浙江大学学报(工学版)  2023, Vol. 57 Issue (9): 1804-1813    DOI: 10.3785/j.issn.1008-973X.2023.09.012
机械工程、能源工程     
考虑工人疲劳的双资源柔性作业车间调度优化
郭鹏1,2(),郝东辉1,郑鹏1,王祺欣1
1. 西南交通大学 机械工程学院，四川 成都 610031
2. 轨道交通运维技术与装备四川省重点实验室，四川 成都 610031
Scheduling optimization of dual resource-constrained flexible job shop considering worker fatigue
Peng GUO1,2(),Dong-hui HAO1,Peng ZHENG1,Qi-xin WANG1
1. School of Mechanical Engineering, Southwest Jiaotong University, Chengdu 610031, China
2. Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province, Chengdu 610031, China
 全文: PDF(833 KB)   HTML
摘要：

针对生产制造过程中的工人疲劳问题，在人机双资源约束柔性作业车间调度问题的基础上，以最小化完工时间为目标，构建混合整数规划模型，保证工人疲劳不超过限定水平. 提出改进的自适应大规模邻域搜索算法，以解决工件排序、机器分配、工人指派和工人疲劳等高度复杂的子问题. 所提算法使用8种启发式规则生成初始解，引入6类破坏算子和6类修复算子实现对解空间的高效搜索. 通过不同规模的算例对比，验证所提算法的有效性. 相较于Gurobi求解器、遗传算法、Jaya算法和标准ALNS算法，所提算法具有良好的寻优性能，能够有效解决作业车间调度过程中的工人疲劳问题.
关键词： 双资源约束;  柔性作业车间;  工人疲劳;  混合整数规划;  自适应大邻域搜索    
Abstract:

The flexible job shop scheduling problem with human-machine dual resource limitations was studied. A mixed integer programming model was developed to minimize the completion time ensuring the worker fatigue was below the limited level in the manufacturing process. An improved adaptive large neighborhood search algorithm was proposed to resolve highly complex sub-problems such as job sequencing, machine assignment, worker assignment and worker fatigue. Eight heuristic rules were used to build the initial solutions, and six types of destruction operators and six types of repair operators were introduced to achieve an efficient search of the solution space in the proposed algorithm. The effectiveness of the proposed algorithm was demonstrated by comparing the numerical examples of various scales. Compared with the Gurobi optimizer, genetic algorithm, Jaya algorithm and standard ALNS algorithm, the proposed algorithm has good optimization performance and can successfully address the issue of worker fatigue in the job shop scheduling.
Key words: dual resource constraints    flexible job shop    worker fatigue    mixed integer programming    adaptive large neighborhood search
收稿日期: 2022-09-19 出版日期: 2023-10-16
CLC:  TH 181  
基金资助: 国家重点研发计划资助项目(2020YFB1712202)；四川省自然科学基金资助项目(2022NSFSC0459)
作者简介: 郭鹏（1988—），男，副教授，从事智能优化调度研究. orcid.org/0000-0001-5520-7701. E-mail： pengguo318@swjtu.edu.cn
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章　　
郭鹏
郝东辉
郑鹏
王祺欣

引用本文:

郭鹏,郝东辉,郑鹏,王祺欣. 考虑工人疲劳的双资源柔性作业车间调度优化[J]. 浙江大学学报(工学版), 2023, 57(9): 1804-1813.

Peng GUO,Dong-hui HAO,Peng ZHENG,Qi-xin WANG. Scheduling optimization of dual resource-constrained flexible job shop considering worker fatigue. Journal of ZheJiang University (Engineering Science), 2023, 57(9): 1804-1813.

链接本文:

https://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2023.09.012    或    https://www.zjujournals.com/eng/CN/Y2023/V57/I9/1804

图 1  作业车间示意图
图 2  工人工作和休息时的疲劳曲线
图 3  可行解的编码示意图
图 4  操作算子的破坏和修复过程
图 5  改进自适应大邻域搜索算法流程图
规模 算例 A n 工件编号 W w M m
小规模 D1 2 10 J1~J10 3 [2,1] 6 [4,2]
D2 2 10 J21~J30 3 [2,1] 6 [4,2]
D3 2 15 J1~J15 3 [2,1] 6 [4,2]
D4 2 15 J31~J45 3 [2,1] 6 [4,2]
中规模 D5 3 25 J1~J25 5 [2,2,1] 10 [4,4,2]
D6 3 25 J51~J75 5 [2,2,1] 10 [4,4,2]
D7 3 30 J1~J30 5 [2,2,1] 10 [4,4,2]
D8 3 30 J61~J90 5 [2,2,1] 10 [4,4,2]
大规模 D9 4 40 J1~J40 8 [3,2,2,1] 14 [5,4,3,2]
D10 4 40 J81~J120 8 [3,2,2,1] 14 [5,4,3,2]
D11 4 50 J1~J50 8 [3,2,2,1] 14 [5,4,3,2]
D12 4 50 J101~J150 8 [3,2,2,1] 14 [5,4,3,2]
超大规模 D13 5 70 J1~J70 11 [3,3,2,2,1] 20 [6,5,4,3,2]
D14 5 70 J101~J170 11 [3,3,2,2,1] 20 [6,5,4,3,2]
D15 5 90 J1~J90 11 [3,3,2,2,1] 20 [6,5,4,3,2]
D16 5 90 J81~J170 11 [3,3,2,2,1] 20 [6,5,4,3,2]
表 1  算例的规模、工人及机器定义表
算例 C1 C2 C3 C4 C5 C6 C7 C8
D1 213 213 195 195 188 200 198 198
D2 249 249 221 221 217 217 219 219
D3 304 304 341 341 293 305 263 263
D4 305 302 282 282 280 293 279 279
D5 283 286 281 302 288 285 266 246
D6 280 285 336 382 319 340 286 286
D7 333 324 360 345 338 349 308 321
D8 302 312 323 330 315 294 317 300
D9 314 278 295 276 303 306 286 272
D10 283 283 353 301 307 297 297 297
D11 329 329 396 394 336 335 341 340
D12 361 394 398 399 397 375 374 369
D13 335 335 438 465 413 355 345 346
D14 398 429 421 402 369 390 355 359
D15 411 422 557 535 433 484 412 401
D16 414 435 500 507 445 432 430 420
表 2  规则和算例的比较实验结果
算例 OPT/min AVE/min STD CV ART/s
D1 171 171.8 0.40 0.002 1.9
D2 178 179.1 0.83 0.005 1.9
D3 237 238.5 1.02 0.004 4.7
D4 231 232.3 0.90 0.004 4.7
D5 235 237.4 1.80 0.008 13.8
D6 230 233.1 1.92 0.008 13.6
D7 284 285.2 1.17 0.004 20.3
D8 274 275.4 1.02 0.004 20.1
D9 259 261.2 1.83 0.007 35.8
D10 253 258.5 2.69 0.010 35.8
D11 308 312.1 2.39 0.008 57.0
D12 319 319.2 0.40 0.001 57.3
D13 304 307.9 2.66 0.009 115.5
D14 322 326.2 2.14 0.007 116.1
D15 376 380.8 1.99 0.005 194.9
D16 390 395.3 3.10 0.008 195.2
表 3  改进自适应大邻域搜索算法重复实验的结果
算例 CS1/min CS2/min CS3/min
D1 176 173 171
D2 180 178 178
D3 248 242 237
D4 232 231 231
D5 242 241 235
D6 247 243 230
D7 284 289 284
D8 283 281 274
D9 265 265 259
D10 265 261 253
D11 320 322 308
D12 327 323 319
D13 319 329 304
D14 329 333 322
D15 401 388 376
D16 409 398 390
表 4  不同策略下自适应大邻域搜索算法对比实验结果
算例 Gurobi求解器 生成规则 遗传算法 Jaya算法 标准ALNS算法 本研究算法
C/min RT/s C/min RT/s C/min RT/s C/min RT/s C/min RT/s C/min RT/s
D1 174 10800 188 <1 174 4.1 172 15.0 176 0.5 171 1.9
D2 183 10800 217 <1 180 4.3 187 15.1 180 0.5 178 1.9
D3 271 10800 263 <1 238 6.3 242 33.1 243 1.1 237 4.7
D4 338 10800 279 <1 236 6.1 243 34.3 238 1.2 231 4.7
D5 356 10800 246 <1 251 10.4 246 91.1 246 3.5 235 13.8
D6 368 10800 280 <1 249 10.2 253 89.3 239 3.1 230 13.6
D7 — 10800 308 <1 297 12.5 291 126.4 290 5.0 284 20.3
D8 — 10800 294 <1 294 12.4 280 122.7 288 5.0 274 20.1
D9 — 10800 272 <1 270 16.5 269 220.7 265 8.7 259 35.8
D10 — 10800 283 <1 270 16.4 267 221.5 264 8.4 253 35.8
D11 — 10800 329 <1 329 20.4 321 321.3 319 12.7 308 57.0
D12 — 10800 361 <1 337 20.7 329 377.0 332 14.6 319 57.3
D13 — 10800 335 <1 336 29.5 336 769.6 335 27.3 304 115.5
D14 — 10800 355 <1 344 30.1 342 769.2 332 29.4 322 116.1
D15 — 10800 401 <1 426 38.8 425 1159.0 401 46.1 376 194.9
D16 — 10800 414 <1 438 39.9 416 1105.3 420 51.1 390 195.2
表 5  6种优化算法的求解结果与耗时
算例 Gurobi 遗传算法 Jaya算法 标准ALNS算法 本研究算法
C/min RT/s C/min RT/s C/min RT/s C/min RT/s C/min RT/s
X1 141 1800 141 1.1 141 3.2 141 0.4 141 0.8
X2 138 1800 138 1.1 138 3.2 138 0.4 138 0.8
表 6  超小规模算例的求解结果与耗时
1 LERMAN S E, ESKIN E, FLOWER D J, et al Fatigue risk management in the workplace[J]. Journal of Occupational and Environmental Medicine, 2012, 54 (2): 231- 258
doi: 10.1097/JOM.0b013e318247a3b0
2 CAVUOTO L, MEGAHED F. Understanding fatigue and the implications for worker safety [C]// ASSE Professional Development Conference and Exposition. Atlanta: [s.n.], 2016: 1457-1465.
3 SAWATZKY S Worker fatigue: understanding the risks in the workplace[J]. Professional Safety, 2017, 62 (11): 45- 51
4 BALAS J. How you could pay the price for exhausted employees [EB/OL]. (2018-06-18)[2022-08-30]. https://www.constructionbusinessowner.com/safety/how-you-could-pay-price-exhausted-employees.
5 EL MOUAYNI I, ETIENNE A, LUX A, et al A simulation-based approach for time allowances assessment during production system design with consideration of worker's fatigue, learning and reliability[J]. Computers and Industrial Engineering, 2020, 139: 105650
doi: 10.1016/j.cie.2019.01.024
6 SUN W, PAN Y, LU X, et al Research on flexible job-shop scheduling problem based on a modified genetic algorithm[J]. Journal of Mechanical Science and Technology, 2010, 24 (10): 2119- 2125
doi: 10.1007/s12206-010-0526-x
7 赵诗奎, 方水良, 顾新建 柔性车间调度的新型初始机制遗传算法[J]. 浙江大学学报: 工学版, 2013, 47 (6): 1022- 1030
ZHAO Shi-kui, FANG Shui-liang, GU Xin-jian Genetic algorithm with new initialization mechanism for flexible job shop scheduling[J]. Journal of Zhejiang University: Engineering Science, 2013, 47 (6): 1022- 1030
8 王雷, 蔡劲草, 唐敦兵, 等 基于改进遗传算法的柔性作业车间调度[J]. 南京航空航天大学学报, 2017, 49 (6): 779- 785
WANG Lei, CAI Jin-cao, TANG Dun-bing, et al Flexible job shop scheduling problem based on improved genetic algorithm[J]. Journal of Nanjing University of Aeronautics and Astronautics, 2017, 49 (6): 779- 785
9 NOUIRI M, BEKRAR A, JEMAI A, et al An effective and distributed particle swarm optimization algorithm for flexible job-shop scheduling problem[J]. Journal of Intelligent Manufacturing, 2018, 29 (3): 603- 615
doi: 10.1007/s10845-015-1039-3
10 ZHANG G, LU X, LIU X, et al An effective two-stage algorithm based on convolutional neural network for the bi-objective flexible job shop scheduling problem with machine breakdown[J]. Expert Systems with Applications, 2022, 203: 117460
doi: 10.1016/j.eswa.2022.117460
11 TEYMOURIFAR A, OZTURK G A neural network-based hybrid method to generate feasible neighbors for flexible job shop scheduling problem[J]. Universal Journal of Applied Mathematics, 2018, 6 (1): 1- 16
doi: 10.13189/ujam.2018.060101
12 JAMSHIDI R Maintenance and work-rest scheduling in human-machine system according to fatigue and reliability[J]. International Journal of Engineering, 2017, 30 (1): 85- 92
13 FERJANI A, AMMAR A, PIERREVAL H, et al A simulation-optimization based heuristic for the online assignment of multi-skilled workers subjected to fatigue in manufacturing systems[J]. Computers and Industrial Engineering, 2017, 112: 663- 674
doi: 10.1016/j.cie.2017.02.008
14 MENG L, ZHANG C, ZHANG B, et al Mathematical modeling and optimization of energy-conscious flexible job shop scheduling problem with worker flexibility[J]. IEEE Access, 2019, 7: 68043- 68059
doi: 10.1109/ACCESS.2019.2916468
15 MOKHTARI G, ABOLFATHI M Dual resource constrained flexible job-shop scheduling with lexicograph objectives[J]. Journal of Industrial Engineering Research in Production Systems, 2021, 8 (17): 295- 309
16 ZHANG S, DU H, BORUCKI S, et al Dual resource constrained flexible job shop scheduling based on improved quantum genetic algorithm[J]. Machines, 2021, 9 (6): 108- 123
doi: 10.3390/machines9060108
17 TAN W, YUAN X, WANG J, et al A fatigue-conscious dual resource constrained flexible job shop scheduling problem by enhanced NSGA-II: an application from casting workshop[J]. Computers and Industrial Engineering, 2021, 160: 107557
doi: 10.1016/j.cie.2021.107557
18 DEFERSHA F M, OBIMUYIWA D, YIMER A D Mathematical model and simulated annealing algorithm for setup operator constrained flexible job shop scheduling problem[J]. Computers and Industrial Engineering, 2022, 171: 108487
doi: 10.1016/j.cie.2022.108487
19 FARJALLAH F, NOURI H E, BELKAHLA DRISS O. Multi-start Tabu agents-based model for the dual-resource constrained flexible job shop scheduling problem [C]// International Conference on Computational Collective Intelligence. [S.l.]: Springer, 2022: 674-686.
20 孙宝凤, 任欣欣, 郑再思, 等 考虑工人负荷的多目标流水车间优化调度[J]. 吉林大学学报: 工学版, 2021, 51 (3): 900- 909
SUN Bao-feng, REN Xin-xin, ZHENG Zai-si, et al Multi-objective flow shop optimal scheduling considering worker’s load[J]. Journal of Jilin University: Engineering and Technology Edition, 2021, 51 (3): 900- 909
21 ROPKE S, PISINGER D An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. Transportation Science, 2006, 40 (4): 455- 472
doi: 10.1287/trsc.1050.0135
22 伍国华, 毛妮, 徐彬杰, 等 基于自适应大规模邻域搜索算法的多车辆与多无人机协同配送方法[J]. 控制与决策, 2023, 38 (1): 201- 210
WU Guo-hua, MAO Ni, XU Bin-jie, et al The cooperative delivery of multiple vehicles and multiple drones based on adaptive large neighborhood search[J]. Control and Decision, 2023, 38 (1): 201- 210
23 徐倩, 熊俊, 杨珍花, 等 基于自适应大邻域搜索算法的外卖配送车辆路径优化[J]. 工业工程与管理, 2021, 26 (3): 115- 122
XU Qian, XIONG Jun, YANG Zhen-hua, et al Route optimization of takeout delivery vehicles based on adaptive large neighborhood search algorithm[J]. Industrial Engineering and Management, 2021, 26 (3): 115- 122
24 MARA S T W, NORCAHYO R, JODIAWAN P, et al A survey of adaptive large neighborhood search algorithms and applications[J]. Computers and Operations Research, 2022, 146: 105903
doi: 10.1016/j.cor.2022.105903
25 RIFAI A P, NGUYEN H T, DAWAL S Multi-objective adaptive large neighborhood search for distributed reentrant permutation flow shop scheduling[J]. Applied Soft Computing, 2016, 40: 42- 57
doi: 10.1016/j.asoc.2015.11.034
26 DU H, QIAO F, WANG J, et al. A hybrid metaheuristic algorithm with novel decoding methods for flexible flow shop scheduling considering human fatigue [C]// 2021 IEEE International Conference on Systems, Man, and Cybernetics (SMC). Melbourne: IEEE, 2021: 2328-2333.
27 Gurobi Optimization. Gurobi optimizer quick start guide, [EB/OL]. [2022-08-30]. https://www.gurobi.com/documentation/quickstart.html.
28 郭鹏, 赵文超, 雷坤 基于改进Jaya算法的双资源约束柔性作业车间优化调度[J]. 吉林大学学报: 工学版, 2023, 53 (2): 480- 487
GUO Peng, ZHAO Wen-chao, LEI Kun Dual-resource constrained flexible job shop optimal scheduling based on an improved Jaya algorithm[J]. Journal of Jilin University: Engineering and Technology Edition, 2023, 53 (2): 480- 487
[1] 李嫚嫚,孙加辉,丁楠,杨京帅. 考虑服务定价的选择性众包配送优化[J]. 浙江大学学报(工学版), 2023, 57(8): 1495-1504.
[2] 牛昊一,吴维敏,章庭棋,沈微,张涛. 自适应樽海鞘群算法求解考虑运输时间的柔性作业车间调度[J]. 浙江大学学报(工学版), 2023, 57(7): 1267-1277.
[3] 杨京帅,杨玉娥,李嫚嫚,李园园. 末端配送服务模式与路径联合优化[J]. 浙江大学学报(工学版), 2023, 57(5): 900-910.
[4] 余佳洁,季彦婕,卜卿,郑岳标. 考虑断点成本的长干线分段绿波控制方法[J]. 浙江大学学报(工学版), 2022, 56(4): 640-648.
[5] 张则强,许培玉,蒋晋,张裕. 站间操作者不同的并行拆卸线平衡问题优化[J]. 浙江大学学报(工学版), 2021, 55(10): 1795-1805.
[6] 周健, 石德晓. 基于中断应急的集成弹性供应链网络[J]. 浙江大学学报(工学版), 2018, 52(2): 240-246.
[7] 裴植, 张雪芳, 陆海旻, 杜蕊, 鲁建厦. 多阶段连续型柔性制药车间调度[J]. 浙江大学学报(工学版), 2018, 52(12): 2253-2261.
[8] 周炳海, 赵猛. 柔性Job Shops集成调度启发式算法[J]. 浙江大学学报(工学版), 2016, 50(6): 1073-1079.
[9] 赵诗奎, 方水良, 顾新建. 柔性车间调度的新型初始机制遗传算法[J]. J4, 2013, 47(6): 1022-1030.
[10] 王云, 冯毅雄, 谭建荣, 高一聪. 柔性作业车间分批调度多目标优化方法[J]. J4, 2011, 45(4): 719-726.