带准备时间的单机调度问题的混合进化算法研究

Hybrid evolutionary algorithm for solving single-machine scheduling problem with setup times

提出了一种混合进化算法(HEA)用于求解具有序列相关依赖且带准备时间的单机调度问题,其优化目标为最小化总延迟。该混合进化算法由局部搜索和进化算法框架混合而成。HEA具有一些新的特点,例如在局部搜索中采用了一种新提出的基于块移动的邻域结构,这种邻域结构合理地限制了搜索空间,提高了算法的搜索效率;在HEA中采用了一种新的组合算子———块顺序交叉算符(BOX)来产生新的子代工作序列。用本算法对当前国际文献中公开的两组共64个算例进行了测试,HEA改进了9个算例在当前文献中的最优解,表明了所提出的HEA算法的优越性。与之前的国际文献中最好的四个启发式算法进行了详细比较,表明了HEA算法的优势。

This paper presented a hybrid evolutionary algorithm （HEA） for solving the single-machine scheduling problem with sequence-dependent setup times to minimize the total tardiness. By incorporating a local search procedure into the framework of evolutionary algorithms, the proposed approach exhibited several distinguishing features, including adopting a newly presented neighbourhood structure, called block move, and restricting the search space to traverse towards more promising search regions, and generating a new combination operator, called block order crossover, to generate new offspring solutions. Applying the proposed algorithm to solve the two sets of 64 public instances widely used in the literature, HEA outperforms the previous best known results for 9 instances, which demonstrate the superiority of the proposed HEA. The proposed HEA achieves highly competitive results over the 4 previous state-of-the-art metaheuristic algorithms in the literature.