混合离散差分进化算法在单机批处理调度中的应用

？本文研究单机批处理调度问题,批处理机有批次容量限制,批处理时间由每个批次所含作业中的最长作业处理时间决定。每个作业具有不同的大小、处理时间、提前拖期惩罚权重,所有作业具有公共交货期,且交货期无限晚。目标函数为最小化所有作业的加权提前拖期惩罚之和。该问题已被证明为NP难题,本研究找到了其最优解具有的一些性质,在此基础上利用它们提出了一种动态规划(DP)与差分进化(DE)算法相结合的混合离散差分进化(HDDE)算法来求解该问题,通过与传统的遗传算法、模拟退火算法和迭代贪婪算法进行对比,HDDE算法显示了更加强大的全局搜索能力。