Please wait a minute...
浙江大学学报(工学版)
Journal of ZheJiang University (Engineering Science)  2023, Vol. 57 Issue (9): 1804-1813    DOI: 10.3785/j.issn.1008-973X.2023.09.012
    
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
Download: HTML     PDF(833KB) HTML
Export: BibTeX | EndNote (RIS)      

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     
Received: 19 September 2022      Published: 16 October 2023
CLC:  TH 181  
Fund:  国家重点研发计划资助项目(2020YFB1712202)；四川省自然科学基金资助项目(2022NSFSC0459)
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Peng GUO
Dong-hui HAO
Peng ZHENG
Qi-xin WANG
Cite this article:

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.

URL:

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


考虑工人疲劳的双资源柔性作业车间调度优化

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


关键词： 双资源约束,  柔性作业车间,  工人疲劳,  混合整数规划,  自适应大邻域搜索 
Fig.1 Diagram of job shop
Fig.2 Fatigue curve of worker during work and rest
Fig.3 Coding diagram of feasible solution
Fig.4 Destruction and repair process of operator
Fig.5 Flow chart of improved adaptive large neighborhood search algorithm
规模 算例 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]
Tab.1 Table of scale, workers and machine definitions for examples
算例 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
Tab.2 Comparative experimental results of rules and examples min
算例 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
Tab.3 Results of repeated experiments on improved adaptive large neighborhood search algorithm
算例 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
Tab.4 Comparative experimental results of adaptive large neighborhood search algorithm under different strategies
算例 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
Tab.5 Solution results and runtime of six optimization algorithms
算例 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
Tab.6 Solution results and runtime of ultra-small scale example
[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] Man-man LI,Jia-hui SUN,Nan DING,Jing-shuai YANG. Selective crowdsourcing distribution optimization considering service pricing[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(8): 1495-1504.
[2] Hao-yi NIU,Wei-min WU,Ting-qi ZHANG,Wei SHEN,Tao ZHANG. Adaptive salp swarm algorithm for solving flexible job shop scheduling problem with transportation time[J]. Journal of ZheJiang University (Engineering Science), 2023, 57(7): 1267-1277.
[3] 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.
[4] Ze-qiang ZHANG,Pei-yu XU,Jin JIANG,Yu ZHANG. Optimization of parallel disassembly line balancing problem with different operators between workstations[J]. Journal of ZheJiang University (Engineering Science), 2021, 55(10): 1795-1805.
[5] Bao-feng SUN,Yue YANG,Jun-yan SHI,Li-li ZHENG. Dynamic pick-up and delivery problem considering dynamic events in real-world environment[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(8): 1604-1612.
[6] ZHOU Jian, SHI De-xiao. Integrated resilient supply chain with contingency planning for supply disruption[J]. Journal of ZheJiang University (Engineering Science), 2018, 52(2): 240-246.
[7] PEI Zhi, ZHANG Xue-fang, LU Hai-min, DU Rui, LU Jian-sha. Multi-stage no-wait pharmaceutical flexible job shop scheduling[J]. Journal of ZheJiang University (Engineering Science), 2018, 52(12): 2253-2261.
[8] ZHOU Bing hai, ZHAO Meng. Hybrid heuristic algorithm for integrated scheduling in flexible Job Shops[J]. Journal of ZheJiang University (Engineering Science), 2016, 50(6): 1073-1079.
[9] 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.
[10] FANG Shui-liang, YAO Yan-fei, ZHAO Shi-kui. Improved genetic algorithm for flexible job shop scheduling[J]. Journal of ZheJiang University (Engineering Science), 2012, 46(4): 629-635.