Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (5): 1364-1371.DOI: 10.11772/j.issn.1001-9081.2024010028
Special Issue: 进化计算专题(2024年第5期“进化计算专题”导读,全文已上线)
• Special issue on evolutionary calculation • Previous Articles Next Articles
Tao JIANG1,2, Zhenyu LIANG1, Ran CHENG1(), Yaochu JIN3
Received:
2024-01-15
Revised:
2024-02-20
Accepted:
2024-02-21
Online:
2024-04-26
Published:
2024-05-10
Contact:
Ran CHENG
About author:
JIANG Tao, born in 1997, Ph. D. candidate. His research interests include intellligent scheduling, evolutionary computation.通讯作者:
程然
作者简介:
姜涛(1997—),男,安徽马鞍山人,博士研究生,主要研究方向:智能调度、演化计算CLC Number:
Tao JIANG, Zhenyu LIANG, Ran CHENG, Yaochu JIN. GPU-accelerated evolutionary optimization of multi-objective flow shop scheduling problems[J]. Journal of Computer Applications, 2024, 44(5): 1364-1371.
姜涛, 梁振宇, 程然, 金耀初. GPU加速的演化算法求解多目标流水车间调度问题[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1364-1371.
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.11772/j.issn.1001-9081.2024010028
变量 | 定义 | 变量 | 定义 | 变量 | 定义 |
---|---|---|---|---|---|
机器数目 | 机器加工速度等级数目 | 总加工能耗(total Processing Energy Consumption, PEC) | |||
工件数目 | 工件 | 总空闲能耗(total Idle Energy Consumption, IEC) | |||
机器索引号 | 工件 | 机器空闲时的平均功率(average Power at Idle, PI) | |||
工件索引号 | 第 | 机器加工时的平均功率(average Power during Processing, PP) | |||
工件序列中工件的索引号 | 工件 | 工件 | |||
指派工件的加工序列 | 工件 | 工件 否则为 | |||
机器加工速度等级 | 总能耗(Total Energy Consumption, TEC) |
Tab. 1 Variable symbols and definitions
变量 | 定义 | 变量 | 定义 | 变量 | 定义 |
---|---|---|---|---|---|
机器数目 | 机器加工速度等级数目 | 总加工能耗(total Processing Energy Consumption, PEC) | |||
工件数目 | 工件 | 总空闲能耗(total Idle Energy Consumption, IEC) | |||
机器索引号 | 工件 | 机器空闲时的平均功率(average Power at Idle, PI) | |||
工件索引号 | 第 | 机器加工时的平均功率(average Power during Processing, PP) | |||
工件序列中工件的索引号 | 工件 | 工件 | |||
指派工件的加工序列 | 工件 | 工件 否则为 | |||
机器加工速度等级 | 总能耗(Total Energy Consumption, TEC) |
时间开销 | 加速比 | |||||
---|---|---|---|---|---|---|
CPU | GPU | Tensor-noJIT- CPU | Tensor-CPU | Tensor-GPU | ||
合计/均值 | 78 998.97 | 143 611.21 | 210.29 | 81.01 | 43.29 | 1 825.06 |
412.15 | 829.02 | 15.75 | 5.93 | 3.85 | 107.07 | |
752.93 | 1 449.78 | 16.25 | 5.73 | 3.42 | 220.18 | |
1 498.14 | 2 657.13 | 16.41 | 5.85 | 3.37 | 445.15 | |
931.54 | 1 760.22 | 17.59 | 5.65 | 3.72 | 250.32 | |
1 775.66 | 3 293.61 | 17.31 | 5.77 | 3.49 | 508.19 | |
3 717.38 | 6 541.58 | 17.77 | 5.95 | 3.47 | 1 071.90 | |
1 888.71 | 3 447.26 | 16.31 | 6.29 | 3.87 | 487.51 | |
3 675.49 | 6 609.47 | 16.54 | 5.97 | 3.63 | 1 012.74 | |
7 134.09 | 13 131.29 | 16.68 | 6.33 | 3.51 | 2 032.36 | |
6 978.79 | 13 135.42 | 17.38 | 7.63 | 3.71 | 1 878.73 | |
14 026.84 | 25 956.58 | 19.15 | 7.82 | 3.53 | 3 972.75 | |
36 207.25 | 64 799.84 | 23.17 | 12.09 | 3.71 | 9 761.75 |
Tab. 2 Time consumption of NSGA-Ⅱ in various environments
时间开销 | 加速比 | |||||
---|---|---|---|---|---|---|
CPU | GPU | Tensor-noJIT- CPU | Tensor-CPU | Tensor-GPU | ||
合计/均值 | 78 998.97 | 143 611.21 | 210.29 | 81.01 | 43.29 | 1 825.06 |
412.15 | 829.02 | 15.75 | 5.93 | 3.85 | 107.07 | |
752.93 | 1 449.78 | 16.25 | 5.73 | 3.42 | 220.18 | |
1 498.14 | 2 657.13 | 16.41 | 5.85 | 3.37 | 445.15 | |
931.54 | 1 760.22 | 17.59 | 5.65 | 3.72 | 250.32 | |
1 775.66 | 3 293.61 | 17.31 | 5.77 | 3.49 | 508.19 | |
3 717.38 | 6 541.58 | 17.77 | 5.95 | 3.47 | 1 071.90 | |
1 888.71 | 3 447.26 | 16.31 | 6.29 | 3.87 | 487.51 | |
3 675.49 | 6 609.47 | 16.54 | 5.97 | 3.63 | 1 012.74 | |
7 134.09 | 13 131.29 | 16.68 | 6.33 | 3.51 | 2 032.36 | |
6 978.79 | 13 135.42 | 17.38 | 7.63 | 3.71 | 1 878.73 | |
14 026.84 | 25 956.58 | 19.15 | 7.82 | 3.53 | 3 972.75 | |
36 207.25 | 64 799.84 | 23.17 | 12.09 | 3.71 | 9 761.75 |
时间开销 | 加速比 | 时间开销 | 加速比 | 时间开销 | 加速比 | 时间开销 | 加速比 | |||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
500-CPU | 500-GPU | 1 000-CPU | 1 000-GPU | 5 000-CPU | 5 000-GPU | 10 000-CPU | 10 000-GPU | |||||
11.74 | 4.12 | 2.85 | 12.70 | 4.28 | 2.97 | 106.10 | 11.31 | 9.38 | 511.90 | 37.52 | 13.64 | |
8.90 | 3.67 | 2.42 | 12.13 | 3.74 | 3.24 | 129.28 | 13.28 | 9.73 | 690.14 | 50.52 | 13.66 | |
8.64 | 3.73 | 2.32 | 11.33 | 3.87 | 2.93 | 169.27 | 17.84 | 9.49 | 967.98 | 72.57 | 13.34 | |
10.55 | 3.98 | 2.65 | 17.23 | 4.14 | 4.17 | 111.28 | 10.53 | 10.57 | 506.69 | 33.98 | 14.91 | |
9.67 | 3.86 | 2.50 | 12.68 | 3.96 | 3.20 | 130.83 | 12.48 | 10.48 | 629.94 | 45.30 | 13.91 | |
9.86 | 3.92 | 2.52 | 13.00 | 4.04 | 3.21 | 172.34 | 16.82 | 10.25 | 933.98 | 66.14 | 14.12 | |
16.84 | 4.26 | 3.95 | 18.36 | 4.22 | 4.35 | 124.41 | 10.47 | 11.88 | 524.37 | 33.14 | 15.82 | |
12.46 | 3.99 | 3.12 | 16.82 | 4.02 | 4.18 | 145.15 | 12.32 | 11.79 | 669.89 | 43.84 | 15.28 | |
12.26 | 4.11 | 2.98 | 18.02 | 4.09 | 4.40 | 193.41 | 16.55 | 11.68 | 946.25 | 64.61 | 14.65 | |
17.98 | 4.36 | 4.12 | 28.43 | 4.37 | 6.51 | 187.21 | 12.61 | 14.84 | 742.74 | 43.91 | 16.92 | |
18.45 | 4.18 | 4.41 | 30.72 | 4.24 | 7.24 | 235.95 | 17.01 | 13.87 | 1027.14 | 64.76 | 15.86 | |
36.10 | 4.47 | 8.08 | 67.12 | 4.48 | 14.97 | 400.18 | 18.95 | 21.12 | 1360.48 | 68.82 | 19.77 |
Tab. 3 Time consumption comparison on Tensor-CPU and Tensor-GPU
时间开销 | 加速比 | 时间开销 | 加速比 | 时间开销 | 加速比 | 时间开销 | 加速比 | |||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
500-CPU | 500-GPU | 1 000-CPU | 1 000-GPU | 5 000-CPU | 5 000-GPU | 10 000-CPU | 10 000-GPU | |||||
11.74 | 4.12 | 2.85 | 12.70 | 4.28 | 2.97 | 106.10 | 11.31 | 9.38 | 511.90 | 37.52 | 13.64 | |
8.90 | 3.67 | 2.42 | 12.13 | 3.74 | 3.24 | 129.28 | 13.28 | 9.73 | 690.14 | 50.52 | 13.66 | |
8.64 | 3.73 | 2.32 | 11.33 | 3.87 | 2.93 | 169.27 | 17.84 | 9.49 | 967.98 | 72.57 | 13.34 | |
10.55 | 3.98 | 2.65 | 17.23 | 4.14 | 4.17 | 111.28 | 10.53 | 10.57 | 506.69 | 33.98 | 14.91 | |
9.67 | 3.86 | 2.50 | 12.68 | 3.96 | 3.20 | 130.83 | 12.48 | 10.48 | 629.94 | 45.30 | 13.91 | |
9.86 | 3.92 | 2.52 | 13.00 | 4.04 | 3.21 | 172.34 | 16.82 | 10.25 | 933.98 | 66.14 | 14.12 | |
16.84 | 4.26 | 3.95 | 18.36 | 4.22 | 4.35 | 124.41 | 10.47 | 11.88 | 524.37 | 33.14 | 15.82 | |
12.46 | 3.99 | 3.12 | 16.82 | 4.02 | 4.18 | 145.15 | 12.32 | 11.79 | 669.89 | 43.84 | 15.28 | |
12.26 | 4.11 | 2.98 | 18.02 | 4.09 | 4.40 | 193.41 | 16.55 | 11.68 | 946.25 | 64.61 | 14.65 | |
17.98 | 4.36 | 4.12 | 28.43 | 4.37 | 6.51 | 187.21 | 12.61 | 14.84 | 742.74 | 43.91 | 16.92 | |
18.45 | 4.18 | 4.41 | 30.72 | 4.24 | 7.24 | 235.95 | 17.01 | 13.87 | 1027.14 | 64.76 | 15.86 | |
36.10 | 4.47 | 8.08 | 67.12 | 4.48 | 14.97 | 400.18 | 18.95 | 21.12 | 1360.48 | 68.82 | 19.77 |
1 | ZHONG R Y, XU X, KLOTZ E, et al. Intelligent manufacturing in the context of Industry 4.0: a review[J]. Engineering, 2017, 3(5): 616-630. 10.1016/j.eng.2017.05.015 |
2 | MITTAL S, KHAN M A, ROMERO D, et al. A critical review of smart manufacturing & Industry 4.0 maturity models: implications for Small and Medium-sized Enterprises (SMEs)[J]. Journal of Manufacturing Systems, 2018, 49: 194-214. 10.1016/j.jmsy.2018.10.005 |
3 | ZHAO Z, ZHOU M, LIU S. Iterated greedy algorithms for flow-shop scheduling problems: a tutorial[J]. IEEE Transactions on Automation Science and Engineering, 2021, 19(3): 1941-1959. 10.1109/tase.2021.3062994 |
4 | KOMAKI G, SHEIKH S, MALAKOOTI B. Flow shop scheduling problems with assembly operations: a review and new trends[J]. International Journal of Production Research, 2019, 57(10): 2926-2955. 10.1080/00207543.2018.1550269 |
5 | ZHAO F, JIANG T, WANG L. A reinforcement learning driven cooperative meta-heuristic algorithm for energy-efficient distributed no-wait flow-shop scheduling with sequence-dependent setup time[J]. IEEE Transactions on Industrial Informatics, 2023, 19(7): 1-12. 10.1109/tii.2022.3218645 |
6 | PAN Q-K, WANG L, ZHAO B-H. An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion[J]. The International Journal of Advanced Manufacturing Technology, 2008, 38: 778-786. 10.1007/s00170-007-1120-y |
7 | 李浩然,高亮,李新宇.基于离散人工蜂群算法的多目标分布式异构零等待流水车间调度方法[J].机械工程学报,2023,59(2):291-306. 10.3901/jme.2023.02.291 |
LI H R, GAO L, LI X Y. Discrete artificial bee colony algorithm for multi-objective distributed heterogeneous no-wait flowshop scheduling problem[J]. Journal of Mechanical Engineering, 2023, 59(2): 291-306. 10.3901/jme.2023.02.291 | |
8 | WEI Y-M, CHEN K, KANG J-N, et al. Policy and management of carbon peaking and carbon neutrality: a literature review[J]. Engineering, 2022, 14: 52-63. 10.1016/j.eng.2021.12.018 |
9 | LI M, WANG G-G. A review of green shop scheduling problem[J]. Information Sciences, 2022, 589: 478-496. 10.1016/j.ins.2021.12.122 |
10 | WANG J-J, WANG L. A cooperative memetic algorithm with learning-based agent for energy-aware distributed hybrid flow-shop scheduling [J]. IEEE Transactions on Evolutionary Computation, 2021, 26(3): 461-475. 10.1109/tevc.2021.3106168 |
11 | 罗聪,龚文引.混合分解多目标进化算法求解绿色置换流水车间调度问题[J/OL].控制与决策,2023 (2023-07-20) [2024-02-19]. . |
LUO C, GONG W Y. A hybrid multi-objective evolutionary algorithm based on decomposition for green permutation flow shop-scheduling problem[J]. Control and Decision, 2023 (2023-07-20) [2024-02-19]. . | |
12 | ZHAO F, HE X, WANG L. A two-stage cooperative evolutionary algorithm with problem-specific knowledge for energy-efficient scheduling of no-wait flow-shop problem [J]. IEEE Transactions on Cybernetics, 2020, 51(11): 5291-5303. 10.1109/tcyb.2020.3025662 |
13 | GAREY M R, SETHI J R. The complexity of flowshop and jobshop scheduling [J]. Mathematics of Operations Research, 1976, 1(2): 117-129. 10.1287/moor.1.2.117 |
14 | 闫红超,汤伟,姚斌.求解置换流水车间调度问题的混合鸟群算法[J].计算机应用,2022,42(9):2952-2959. 10.11772/j.issn.1001-9081.2021091650 |
YAN H C, TANG W, YAO B. Hybrid bird swarm algorithm for solving permutation flowshop scheduling problem[J]. Journal of Computer Applications, 2022, 42(9): 2952-2959. 10.11772/j.issn.1001-9081.2021091650 | |
15 | ZHAO F, XU Z, WANG L, et al. A population-based iterated greedy algorithm for distributed assembly no-wait flow-shop scheduling problem [J]. IEEE Transactions on Industrial Informatics, 2022, 19(5): 6692-6705. 10.1109/tii.2022.3192881 |
16 | DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. 10.1109/4235.996017 |
17 | OWENS J D, HOUSTON M, LUEBKE D, et al. GPU computing [J]. Proceedings of the IEEE, 2008, 96(5): 879-899. 10.1109/jproc.2008.917757 |
18 | LEI S-C, XIAO X, GONG Y-J, et al. Tensorial evolutionary computation for spatial optimization problems [J]. IEEE Transactions on Artificial Intelligence, 2022, 5(1): 154-166. |
19 | VAN LUONG T, MELAB N, E-G TALBI. GPU-based approaches for multiobjective local search algorithms. a case study: the flowshop scheduling problem[C]// Proceedings of the 11th European Conference on Evolutionary Computation in Combinatorial Optimization. Berlin: Springer, 2011: 155-166. 10.1007/978-3-642-20364-0_14 |
20 | GMYS J. Exactly solving hard permutation flowshop scheduling problems on peta-scale GPU-accelerated supercomputers[J]. INFORMS Journal on Computing, 2022, 34(5): 2502-2522. 10.1287/ijoc.2022.1193 |
21 | HUANG L-T, S-S JHAN, LI Y-J, et al. Solving the permutation problem efficiently for Tabu search on CUDA GPUs[C]// Proceedings of the 2014 International Conference on Computational Collective Intelligence, LNAI 8733. Cham: Springer, 2014: 342-352. |
22 | CZAPIŃSKI M, BARNES S. Tabu search with two approaches to parallel flowshop evaluation on CUDA platform [J]. Journal of Parallel and Distributed Computing, 2011, 71(6): 802-811. 10.1016/j.jpdc.2011.02.006 |
23 | HUANG B, CHENG R, LI Z, et al. EvoX: a distributed GPU-accelerated library towards scalable evolutionary computation [EB/OL]. [2023-10-25]. . 10.1109/tevc.2024.3388550 |
24 | BRADBURY J, FROSTIG R, HAWKINS P, et al. JAX: composable transformations of Python+NumPy programs [EB/OL]. [2023-10-11]. . |
25 | TAILLARD E. Benchmarks for basic scheduling problems [J]. European Journal of Operational Research, 1993, 64(2): 278-285. 10.1016/0377-2217(93)90182-m |
26 | WANG J-J, WANG L. A knowledge-based cooperative algorithm for energy-efficient scheduling of distributed flow-shop [J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2018, 50(5): 1805-1819. |
[1] | Lin GAO, Yu ZHOU, Tak Wu KWONG. Evolutionary bi-level adaptive local feature selection [J]. Journal of Computer Applications, 2024, 44(5): 1408-1414. |
[2] | Ye TIAN, Jinjin CHEN, Xingyi ZHANG. Hybrid optimizer combining evolutionary computation and gradient descent for constrained multi-objective optimization [J]. Journal of Computer Applications, 2024, 44(5): 1386-1392. |
[3] | Kaiwen ZHAO, Peng WANG, Xiangrong TONG. Two-stage search-based constrained evolutionary multitasking optimization algorithm [J]. Journal of Computer Applications, 2024, 44(5): 1415-1422. |
[4] | Jianqiang LI, Zhou HE. Hybrid NSGA-Ⅱ for vehicle routing problem with multi-trip pickup and delivery [J]. Journal of Computer Applications, 2024, 44(4): 1187-1194. |
[5] | Yongjian MA, Xuhua SHI, Peiyao WANG. Constrained multi-objective evolutionary algorithm based on two-stage search and dynamic resource allocation [J]. Journal of Computer Applications, 2024, 44(1): 269-277. |
[6] | Saijuan XU, Zhenyu PEI, Jiawei LIN, Genggeng LIU. Constrained multi-objective evolutionary algorithm based on multi-stage search [J]. Journal of Computer Applications, 2023, 43(8): 2345-2351. |
[7] | Canghong JIN, Yuhua SHAO, Qinfang HE. Long-tail recommendation model based on adaptive group reranking [J]. Journal of Computer Applications, 2023, 43(4): 1122-1128. |
[8] | Junyan LIU, Feibo JIANG, Yubo PENG, Li DONG. Multi-objective optimization model for unmanned aerial vehicles trajectory based on decomposition and trajectory search [J]. Journal of Computer Applications, 2023, 43(12): 3806-3815. |
[9] | Chunfeng LIU, Zheng LI, Jufeng WANG. Multi-objective optimization of minicells in distributed factories [J]. Journal of Computer Applications, 2023, 43(12): 3824-3832. |
[10] | Erchao LI, Shenghui ZHANG. Dynamic multi-objective optimization algorithm based on adaptive prediction of new evaluation index [J]. Journal of Computer Applications, 2023, 43(10): 3178-3187. |
[11] | LI Xingjia, YANG Qiuhui, HONG Mei, PAN Chunxia, LIU Ruihang. Test case prioritization approach based on historical data and multi-objective optimization [J]. Journal of Computer Applications, 2023, 43(1): 221-226. |
[12] | MA Yanfang, ZHANG Wen, LI Zongmin, YAN Fang, GUO Lingyun. Two-echelon location-routing model and algorithm for waste recycling considering obnoxious effect [J]. Journal of Computer Applications, 2023, 43(1): 289-298. |
[13] | Xiangyu ZHANG, Yang YANG, Guohui FENG, Chuan QIN. Reversible data hiding in encrypted image based on multi-objective optimization [J]. Journal of Computer Applications, 2022, 42(6): 1716-1723. |
[14] | Jinquan ZHANG, Shouwei XU, Xincheng LI, Chongyang WANG, Jingzhi XU. Cloud computing task scheduling based on orthogonal adaptive whale optimization [J]. Journal of Computer Applications, 2022, 42(5): 1516-1523. |
[15] | Jing ZHANG, Aihong ZHU. Optimization method of automatic train operation speed curve based on genetic algorithm and particle swarm optimization [J]. Journal of Computer Applications, 2022, 42(2): 599-605. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||