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

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

A Hybrid Discrete Differential Evolution Algorithm for Minimizing Weighted Earliness and Tardiness on A Single Batch Scheduling Problem

This paper considers a single batch scheduling problem,where the batch processing machine has restricted capacity.The processing time of a batch is equal to the longest time among all the jobs contained in the batch.All jobs have different sizes,different earliness and tardiness punishing weights,but the same due date which is unrestri-ctively late.The objective is to minimize the sum of weighted earliness and tardiness of all jobs,which are the absolute deviations of completion times from the common due date. This problem is proved to be NP-complete.In this paper,we identify several properties of the optimal scheduling.According to these properties,we propose a hybrid discrete differential evolution algorithm (HDDE)based on differential evolution(DE)and dynamic programming(DP)to solve this scheduling problem.Compared to three traditional heuristicalg orithm(genetic algorithm(GA),simulated annealing (SA),it erated greedy(IG)),HDDE shows a subst antially better global searching ability for the batch scheduling problem.