混合进化算法优化并行机调度：降低总完工时间

"陈海潮,程文明,郭鹏,王丽敏.混和进化算法求解具有分段恶化效应的并行机调度问题.计算机系统应用,2020,29(4):10–17." 在并行机调度问题中，存在一种特殊的情况，即分段恶化效应，这指的是任务的处理时间随着延迟的增加而线性恶化。为了解决这类问题，研究人员提出了一种创新的混合进化算法，旨在最小化总完工时间。该算法结合了对立策略、最小比率优先规则、种群多样度指标以及3-opt扰动算子的变邻域搜索算法，以提高优化效率和结果质量。 首先，算法利用对立策略来生成初始种群。对立策略是一种优化方法，它通过创建与当前解决方案相反的解来探索搜索空间的不同区域，从而避免陷入局部最优。结合最小比率优先规则，可以更有效地分配机器资源，使得初始种群的多样性得以保证，有利于算法的全局搜索能力。 接着，算法引入了种群多样度指标，这是为了监控和维持种群中的个体差异，防止过早收敛。保持种群多样性对于遗传算法来说至关重要，因为它有助于探索更广阔的解决方案空间，增加找到全局最优解的可能性。 然后，算法结合了3-opt扰动算子的变邻域搜索算法，用于对遗传算法得到的解进行局部优化。3-opt是一种改进的局部搜索技术，它在旅行商问题等优化问题中广泛应用，通过交换三个边来改变路径，以寻找可能的更优解。这种技术能够对已经生成的解进行精细调整，寻找潜在的性能改进空间，从而提升算法的局部搜索能力。 实验部分，研究者对比了不同规模的实例，将新提出的混合进化算法与传统的遗传算法（GA）和变邻域搜索算法（VNS）进行了比较。实验结果显示，新算法在减少总完工时间方面取得了优于传统算法的效果，表明其在应对分段恶化效应的并行机调度问题上具有更高的效率和精度。 该混合进化算法通过综合运用多种优化策略，有效地解决了具有分段恶化效应的并行机调度问题，对于实际生产环境中的任务调度优化有着重要的理论与实践意义。