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

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

作　　者：姜涛 梁振宇 程然 金耀初 JIANG Tao;LIANG Zhenyu;CHENG Ran;JIN Yaochu(Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen Guangdong 518055,China;Peng Cheng Laboratory,Shenzhen Guangdong 518055,China;Westlake University,Hangzhou Zhejiang 310012,China)

机构地区：[1]南方科技大学计算机科学与工程系,广东深圳518055 [2]鹏城实验室,广东深圳518055 [3]西湖大学,杭州310012

出　　处：《计算机应用》2024年第5期1364-1371,共8页journal of Computer Applications

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

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]