引用本文

潘子肖, 雷德明. 基于问题性质的分布式低碳并行机调度算法研究. 自动化学报, 2020, 46(11): 2427-2438 doi: 10.16383/j.aas.c180581

Pan Zi-Xiao, Lei De-Ming. Research on property-based distributed low carbon parallel machines scheduling algorithm. Acta Automatica Sinica, 2020, 46(11): 2427-2438 doi: 10.16383/j.aas.c180581

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c180581

关键词

分布式调度，低碳调度，启发式算法，问题性质 

摘要

针对分布式低碳并行机调度问题(Distributed low carbon parallel machine scheduling problem, DLCPMSP), 由于该问题子问题众多, 为此, 首先将问题转换为扩展的低碳不相关并行机调度问题以降低子问题的数量; 然后提出了一种基于问题性质的非劣排序遗传算法-Ⅱ(Property-based non-dominated sorting genetic algorithm-Ⅱ, PNSGA-Ⅱ)以同时最优化总延迟时间和总能耗, 该算法运用针对问题特征的两种启发式算法初始化种群, 给出了问题的四种性质及证明, 提出了两种基于问题性质的局部搜索方法.运用大量实例进行了算法策略分析和对比实验, 结果分析表明, PNSGA-Ⅱ在求解DLCPMSP方面具有较强优势.

文章导读

并行机调度问题(Parallel machine scheduling problem, PMSP)是制造过程中一类典型问题, 在云计算、半导体加工、汽车制造等行业具有广泛的应用背景[1]它通过对制造资源的合理分配与调度实现既定目标的最优化.传统PMSP多以总延迟时间等时间指标作为优化目标, 而很少考虑降低能耗或碳排放.随着制造企业的环保压力日益增大, 以及能源短缺、能源需求与供给之间的矛盾日益突出, 因而迫切需要研究低碳调度理论与方法, 在满足企业市场竞争需要的同时, 实现企业和社会的可持续发展[2].

近些年, 低碳并行机调度研究取得了一些进展.文献[3]在能源成本和清理成本之和小于给定值条件下提出了几种启发式算法分别优化makespan和总完成时间. Wang等[4]给出了一种增广εε-约束算法、构造性启发式算法和非劣排序遗传算法-Ⅱ (Non-dominated sorting genetic algorithm-Ⅱ, NSGA-Ⅱ)以同时优化总能耗和makespan. Wu等[5]提出了一种混合差分进化算法以同时最小化makespan和总能耗. Zheng等[6]给出了一种改进的多目标果蝇优化算法. Liang等[7]运用一种蚁群优化算法解决了具有总延迟时间和总能耗加权和的PMSP. Li等[8]描述了低碳PMSP的模型并提出10种启发式算法. Che等[9]提出了一种节能并行机调度方法在给定发电成本下最小化最大完成时间.雷德明等[10]结合字典序的方法, 提出了一种改进的帝国竞争算法以优化总能耗和总延迟时间.

随着经济全球化的发展, 企业为了快速地响应市场变化, 在服装[11]、渔具[12]、汽车[13]、食品和化学品加工[14]等行业中, 生产制造已从单一工厂向多工厂转换, 分布式生产调度研究引起了工业界和学术界的重视和关注[15-16].针对分布式PMSP, Chen[17]等分析了问题的复杂性, 并给出了一种快速算法以解决供应链调度问题.文献[18]给出两种双层分解算法解决了多工厂生产调度与计划. Behnamian等[19]运用一种启发式方法和改进的遗传算法(GA)以最小化makespan. Behnamian[20]提出了一种基于分解的混合变邻域禁忌搜索算法以同时优化部分工厂的总成本和其他工厂的总利润. Behnamian等[21]给出了一种结合了7种局部搜索的Monte Carlo启发式算法.

如上所述, 低碳PMSP研究取得了一些进展, 现有研究从实际生产调度[5]中给出了加工速度与能耗呈负相关的结论, 并验证了总能耗与makespan之间的冲突关系, 但这些研究大都在单工厂环境下进行, 很少考虑多工厂环境下的低碳PMSP.另一方面, 分布式PMSP的相关研究工作较少, 主要应用GA和变邻域搜索等智能算法, 其他智能算法很少用来解决分布式PMSP, 而且所优化的目标以makespan、成本和利润等为主, 很少考虑总延迟时间, 也未同时优化总能耗和总延迟时间.随着低碳制造和分布式制造的不断实施和应用, 有必要开展分布式低碳调度包括分布式低碳并行机调度问题(DLCPMSP)的深入研究.

NSGA-Ⅱ[22]是一种经典的多目标进化算法, 目前已广泛应用于路径规划[23-24]、选址[25-26]、调度[27-30]和参数优化[31-32]等工程领域, 显示出较强的搜索优势[33], 只是在NSGA-Ⅱ的应用和以上两类PMSP研究中, 较少关注问题性质与智能算法的结合, 问题性质的引入可避免无效搜索, 加强对最优解可能区域的高效搜索[34].目前, 基于问题性质的调度还未引起研究者的足够重视, 现有工作主要针对makespan[6, 35-37]展开研究, 而对总延迟时间和能耗等目标的研究相对较少, 同时基于问题性质的并行机调度研究进展也很少.

针对以同时最小化总延迟时间和总能耗为目标的DLCPMSP, 考虑到该问题具有较多子问题, 首先通过直接将工件分配给机器的方式, 将该问题转换成扩展的低碳不相关并行机调度问题以减少子问题的数量; 然后, 运用针对问题特征的两种启发式算法初始化种群, 给出了问题的四种性质及相关证明, 提出了两种基于问题性质的局部搜索方法, 在此基础上, 设计一种基于问题性质的非劣排序遗传算法-Ⅱ (PNSGA-Ⅱ).运用大量实例进行仿真实验, 包括新策略对算法性能的影响实验和对比实验, 结果表明, 启发式算法和基于问题性质的局部搜索有效地改进了算法的搜索性能, 且算法在解决DLCPMSP方面具有较强的搜索优势.

图 1  PNSGA-Ⅱ算法流程图

图 2  均值主效应图

图 3  6种算法关于四个实例的非劣解分布

分布式PMSP和低碳PMSP研究都取得了一定进展, 但很少同时考虑这两种问题.针对分布式低碳PMSP, 提出了一种基于问题性质的调度算法−−PNSGA-Ⅱ以同时最小化总延迟时间和总能耗.首先将问题转换为扩展的低碳不相关PMSP以降低子问题的数量; 然后, 提出基于问题特征的两种启发式算法以初始化种群, 描述了问题的四种性质以及相关证明, 在此基础上, 提出了两种局部搜索方法以增强PNSGA-Ⅱ的局部搜索能力.通过仿真实验验证了启发式算法初始化种群和基于问题性质的局部搜索的有效性, 显示了PNSGA-Ⅱ在求解DLCPMSP方面较强的优势.未来将进一步深入研究分布式低碳调度问题包括分布式低碳混合流水车间调度问题, 并加强对基于问题性质的智能调度算法的设计与应用研究.

作者简介

潘子肖

清华大学控制科学与工程博士研究生.主要研究方向为智能系统优化与调度. E-mail: pzxwhut@126.com

雷德明

武汉理工大学自动化学院教授.主要研究方向为智能系统优化与控制.本文通信作者. E-mail: deminglei11@163.com