基于问题性质的分布式低碳并行机调度算法研究

Research on Property-based Distributed Low Carbon Parallel Machines Scheduling Algorithm

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

In this study distributed low carbon parallel machine scheduling problem(DLCPMSP)is considered.Owing to many sub-problems,DLCPMSP is transformed into an extended low carbon unrelated parallel machine scheduling problem to diminish the number of sub-problems.A property-based non-dominated sorting genetic algorithm-II(PNSGA-II)is proposed to minimize total tardiness and total energy consumption.In PNSGA-II,two heuristics based on problem features of the problem are used to initialize population,four properties and related proofs are given and two property-based local searches are applied.Many experiments are conducted to show the effect of strategies and compare PNSGA-II with other algorithms from literature.Computational results validate that PNSGA-II has strong advantages for solving DLCPMSP.