摘要
研究了目标函数是最小化完成时间和的同类机调度问题,其中作业释放时间可能不同.此问题被证明是强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.
出处
《系统工程学报》
CSCD
北大核心
2010年第2期258-263,共6页
Journal of Systems Engineering
基金
国家自然科学基金资助项目(70631003
70871032
90924021
70971035)
国家高技术研究发展计划(863计划)重点资助项目(2008AA042901)
合肥工业大学科学研究发展基金资助项目(071102F)
关键词
同类机
完成时间和
释放时间
可变邻域搜索
uniform parallel machine
total completion times
release date
variable search neighborhood
