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

来源：计算机应用杂志2024年第5期北京时间：

作者：姜涛, 梁振宇, 程然, 金耀初

单位：1.南方科技大学 计算机科学与工程系，广东 深圳 518055；2.鹏城实验室，广东 深圳 518055；3.西湖大学，杭州 310012

摘要：智能制造和环境可持续性研究中，多目标调度问题对于协调生产效率、成本管理与环境保护之间的平衡具有至关重要的意义，但现有基于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加速,张量化方法