基于优先权规则的大规模同顺序问题调度算法
大规模同顺序问题(flowshop)难于找到较好解,将同顺序问题转化为完全有向图的最短Hamilton路问题;提出基于优先权规则的邻域搜索法NS(Neighborhood Search),将优先权规则产生的作业序列作为NS的输入,在输入的邻域中搜索最短Hamilton路作为输出,如果输出长度小于输入,则以输出作为输入重复搜索,直到输出长度大于输入长度为止.分别以Insertion、Gupta、Pamler和CDS等算法作为NS的优先权规则,在120个不同规模的Benchmark实例上运行,试验结果表明:NS可将相应的优先权规则的性能分别平均提高约18.27﹪、16.27﹪、7.92﹪和6.84﹪,基本优于模拟退火算法OS、略劣于禁忌搜索算法BF,但运行时间远小于OS和BF.
大规模同顺序问题 启发式算法 优先权规则 模拟退火 禁忌搜索
李小平 刘连臣 吴澄
清华大学自动化系(北京);哈尔滨理工大学计算机系(哈尔滨) 清华大学自动化系(北京)
国内会议
贵阳
中文
295-298
2004-10-20（万方平台首次上网日期，不代表论文的发表时间）