含释放时间的同类机问题的可变邻域搜索算法

Variable neighborhood search algorithm for uniform parallel machine scheduling with release dates

研究了目标函数是最小化完成时间和的同类机调度问题,其中作业释放时间可能不同.此问题被证明是强NP-hard问题.为此问题构造了一种启发式算法HRS,进而以HRS算法求解结果为初始解构造了问题的可变邻域搜索算法HRS-VNS.大量的随机数据实验用于验证算法的性能和效率.

The uniform parallel machine scheduling problem with unequal release dates and minimizing total completion time is considered. This problem has been proved to be NP-hard in the strong sense. A new heuristic algorithm （HRS） is proposed and a variable neighborhood search approach （HRS-VNS） is constructed to improve the quality of the HRS solutions. The performance and effi- ciency of HRS and HRS-VNS are tested on a set of randomly generated instances. The results and analysis of experiments are also given.