CAJ | 학술논문

研究了目标函数是最小化完成时间和的同类机调度问题,其中作业释放时间可能不同.此问题被证明是强NP-hard问题.为此问题构造了一种启发式算法HRS,进而以HRS算法求解结果为初始解构造了问题的可变邻域搜索算法HRS-VNS.大量的随机数据实验用于验证算法的性能和效率.
연구료목표함수시최소화완성시간화적동류궤조도문제,기중작업석방시간가능불동.차문제피증명시강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 efficiency of HRS and HRS-VNS are tested on a set of randomly generated instances. The results and analysis of experiments are also given.