A memetic differential evolution algorithm for energy-efficient parallel machine scheduling
A memetic differential evolution algorithm for energy-efficient parallel machine scheduling
复制标题
一种节能并行机调度的模因差分进化算法
DOI：
10.1016/j.omega.2018.01.001
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Ada Che
中科院分区：
文献类型：
--
作者：
Xueqi Wu;Ada Che
本文研究了一类能量高效的双目标无关并行机调度问题，该问题的目标是最小化完工时间和总能耗。并行机正在进行速度调整。为了解决这个问题，我们提出了一种模因差异进化(MDE)算法。由于该问题涉及到将作业分配给机器并为每个作业选择适当的处理速度水平，因此我们用两个向量来描述每个个体：一个作业机器分配向量和一个速度向量。为了加快算法的收敛速度，只对每个个体的速度向量进行进化，并利用列表调度启发式算法根据个体的速度向量来获得其作业机器分配向量。为了进一步提高算法的性能，我们提出了高效的速度调整和作业-机器交换启发式算法，并通过自适应的亚-拉马克学习策略将它们作为局部搜索方法集成到算法中。计算结果表明，列表调度启发式算法和局部搜索算法的结合大大增强了算法的性能。计算实验还表明，该算法的性能明显优于SPEA-II和NSGA-II。
This paper considers an energy-efficient bi-objective unrelated parallel machine scheduling problem to minimize both makespan and total energy consumption. The parallel machines are speed-scaling. To solve the problem, we propose a memetic differential evolution (MDE) algorithm. Since the problem involves assigning jobs to machines and selecting an appropriate processing speed level for each job, we characterize each individual by two vectors: a job-machine assignment vector and a speed vector. To accelerate the convergence of the algorithm, only the speed vector of each individual evolves and a list scheduling heuristic is applied to derive its job-machine assignment vector based on its speed vector. To further enhance the algorithm, we propose efficient speed adjusting and job-machine swap heuristics and integrate them into the algorithm as a local search approach by an adaptive meta-Lamarckian learning strategy. Computational results reveal that the incorporation of list scheduling heuristic and local search greatly strengthens the algorithm. Computational experiments also show that the proposed MDE algorithm outperforms SPEA-II and NSGA-II significantly.