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

关键词：批处理 提前拖期 动态规划 差分进化算法 

单位：华中科技大学管理学院 湖北武汉430074