《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (5): 1364-1371.DOI: 10.11772/j.issn.1001-9081.2024010028

所属专题: 进化计算专题(2024年第5期“进化计算专题”导读,全文即将上线)

• 进化计算专题 • 上一篇    

GPU加速的演化算法求解多目标流水车间调度问题

姜涛1,2, 梁振宇1, 程然1(), 金耀初3   

  1. 1.南方科技大学 计算机科学与工程系,广东 深圳 518055
    2.鹏城实验室,广东 深圳 518055
    3.西湖大学,杭州 310012
  • 收稿日期:2024-01-15 修回日期:2024-02-20 接受日期:2024-02-21 发布日期:2024-04-26 出版日期:2024-05-10
  • 通讯作者: 程然
  • 作者简介:姜涛(1997—),男,安徽马鞍山人,博士研究生,主要研究方向:智能调度、演化计算
    梁振宇(1997—),男,广东阳江人,硕士研究生,主要研究方向:多目标优化
    金耀初(1966—),男,江苏吴江人,讲席教授,博士,主要研究方向:人工智能。
    第一联系人:程然(1987—),男,江苏徐州人,副教授,博士,主要研究方向:计算智能、演化计算、表征学习

GPU-accelerated evolutionary optimization of multi-objective flow shop scheduling problems

Tao JIANG1,2, Zhenyu LIANG1, Ran CHENG1(), Yaochu JIN3   

  1. 1.Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen Guangdong 518055,China
    2.Peng Cheng Laboratory,Shenzhen Guangdong 518055,China
    3.Westlake University,Hangzhou Zhejiang 310012,China
  • 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.
    LIANG Zhenyu, born in 1997, M. S. candidate. His research interests include multi-objective optimization.
    JIN Yaochu, born in 1966, Ph. D., chair professor. His research interests include artificial intelligence.

摘要:

智能制造和环境可持续性研究中,多目标调度问题对于协调生产效率、成本管理与环境保护之间的平衡具有至关重要的意义,但现有基于CPU的调度解决方案在处理大规模生产任务时仍面临效率和时效性的限制,而GPU的并行计算能力可为优化大规模流水车间调度问题提供新的解决途径。针对多目标零等待流水车间调度问题(NWFSP),以同时最小化最大完成时间和总能耗(TEC)为优化目标,构建了混合整数线性规划模型(MILP)表征该调度问题,并提出一种基于GPU加速的张量化演化算法(Tensor-GPU-NSGA-Ⅱ)求解该问题。Tensor-GPU-NSGA-Ⅱ的主要创新在于对NWFSP关于最小化最大完成时间和TEC的计算过程的张量化处理,并提出了一种基于GPU的并行种群更新方法。实验结果表明,在500工件和20机器的问题规模下,Tensor-GPU-NSGA-Ⅱ在计算效率上相较于传统NSGA-Ⅱ算法取得了9 761.75的加速比;且随着种群规模的增加,它的加速性能有显著提升。

关键词: 智能制造, 多目标优化, 流水车间调度, GPU加速, 张量化方法

Abstract:

In the realms of intelligent manufacturing and environmental sustainability, the significance of multi-objective scheduling in orchestrating a balance among production efficiency, cost management, and environmental conservation is paramount. Contemporary research indicates that CPU-based scheduling solutions are constrained by suboptimal efficiency and responsiveness, particularly when managing tasks of considerable scale. Consequently, the parallel computational prowess of GPUs heralds a novel avenue for the refinement of extensive flow shop scheduling challenges. For the multi-objective No-Wait Flow shop Scheduling Problem (NWFSP), with the concurrent objectives of minimizing both the makespan and the Total Energy Consumption (TEC), a Mixed-Integer Linear Programming model (MILP) was formulated to delineate the problem, and a bespoke GPU-accelerated tensorized evolutionary algorithm named Tensor-GPU-NSGA-Ⅱ was introduced for problem-solving. The ingenuity of Tensor-GPU-NSGA-Ⅱ resides in its tensorized algorithm for the computation of the makespan and TEC within the NWFSP framework, as well as in converting the conventional CPU-based serial individual updating to a GPU-driven parallel population renewal process. Empirical results demonstrate that for a scenario involving 500 jobs and 20 machines, Tensor-GPU-NSGA-Ⅱ realizes an enhancement in computational efficiency by a speedup of 9 761.75 over the traditional NSGA-Ⅱ algorithm. Furthermore, this acceleration efficacy markedly surges as the population scale expands.

Key words: intelligent manufacturing, multi-objective optimization, flow shop scheduling, GPU acceleration, tensorization method

中图分类号: