论文部分内容阅读
本文研究单机批处理调度问题,批处理机有批次容量限制,批处理时间由每个批次所含作业中的最长作业处理时间决定。每个作业具有不同的大小、处理时间、提前拖期惩罚权重,所有作业具有公共交货期,且交货期无限晚。目标函数为最小化所有作业的加权提前拖期惩罚之和。该问题已被证明为NP难题,本研究找到了其最优解具有的一些性质,在此基础上利用它们提出了一种动态规划(DP)与差分进化(DE)算法相结合的混合离散差分进化(HDDE)算法来求解该问题,通过与传统的遗传算法、模拟退火算法和迭代贪婪算法进行对比,HDDE算法显示了更加强大的全局搜索能力。
This paper studies scheduling problems with single-batch batches, batch batches have capacity limitations, and batching time is determined by the longest job processing time in the jobs contained in each batch. Each job has a different size, processing time, penalties early dragging, all jobs have public delivery, and delivery deadline. The objective function is to minimize the sum of weighted early drag penalties for all jobs. This problem has been proved to be an NP problem. In this study, we find some properties of the optimal solution. Based on this, we propose a mixed discrete difference (DP) algorithm that combines dynamic programming (DP) and differential evolution (DE) HDDE algorithm to solve this problem. Compared with the traditional genetic algorithm, simulated annealing algorithm and iterative greedy algorithm, HDDE algorithm shows a more powerful global search ability.