带释放时间的并行机调度问题的ILS & SS算法

研究工件带释放时间的两类并行机最小化总完成时间的调度问题.针对问题提出了一种新的基于变深度环交换邻域结构的Iterated local search(ILS)算法.1)提出了变深度环交换邻域结构.2)基于变深度环交换和传统Swap的混合邻域,提出了带有两种kick策略的ILS算法.3)为了加强ILS逃出局部最优的能力,将Scatter search (SS)搜索方法引入了ILS算法中;算法将当前最好解和次好解进行分散处理,再从处理后的解开始继续迭代.为了验证算法的有效性,对两类并行机问题分别随机产生100组数据进行试验.实验结果表明:对于同构并行机问题,引入SS的ILS算法的计算结果与下界的平均偏差为0.99%,而没有引入SS的ILS算法的为1.06%;对于无关并行机问题,引入SS搜索方法后,ILS算法的计算结果 改进了6.06%,并明显优于多点下降算法.

A New ILS & SS Algorithm for Parallel-machine Scheduling Problem

The problems of scheduling jobs with different ready time on parallel machines to minimize the total completion time are addressed. A new iterated local search (ILS) is proposed based on a new neighborhood structure named variable-depth cycle exchange. First, we define the variable-depth cycle exchange neighborhood structure. Based on the variable-depth cycle exchange neighborhood and the traditional Swap neighborhood, a new ILS algorithm with two kick strategies is then proposed. Scatter search (SS) is embedded into ILS to enhance its power of getting away from the local optima, in which the algorithm continues work after combining the best and the second best solutions found so far. Computational experiments on 10 problems with up to 50 jobs and 20 machines for unrelated parallel machines and identical machines respectively are carried out to test the performance of the algorithm. For the identical parallel-machine scheduling problem, the average deviation of the ILS with SS to the lower bound obtained by Lagrangian Relaxation is 0.99%, but 1.06% for the ILS without SS. For the unrelated parallel-machine scheduling problem, the average performance of the ILS with SS make an improvement 6.06% over that of the ILS without SS, and also is better than that of multi-start descent algorithm.