| 有准备时间无等待流水车间调度的搜索算法 |
| |
| 引用本文： | 王初阳,李小平,王茜,苑迎春.有准备时间无等待流水车间调度的搜索算法[J].计算机研究与发展,2010,47(4). |
| |
| 作者姓名： | 王初阳 李小平 王茜 苑迎春 |
| |
| 作者单位： | 1. 东南大学计算机科学与工程学院,南京,210096;计算机网络和信息集成教育部重点实验室(东南大学),南京,210096
2. 河北农业大学信息科学与技术学院,河北保定,071001 |
| |
| 基金项目： | 国家“八六三”高技术研究发展计划基金项目(2008AA04Z103);;国家自然科学基金项目(60504029,60672092,60873236);;河北省自然科学基金项目(F2009000653)~~ |
| |
| 摘 要： | 利用迭代变化邻域搜索算法(IVNS)求解最小化总完工时间的有准备时间无等待流水车间调度问题.设计局部搜索算法需要考虑3个关键因素:所用邻域、解评估和局部最优的克服.因此,定义了3个较大规模邻域以扩大搜索范围.为加速解评估,利用目标增量来避免重新计算每个解的目标函数值,使相邻解比较只需常量时间,NEH插入算法的时间复杂度降低一阶.IVNS通过切换邻域和扰动重启,来克服局部搜索易于陷入局部最优解的缺点.通过与求解该问题的当前最好算法在5400个标准算上,以相同CPU时间进行的实算比较,实验结果统计分析验证了IVNS的寻优性能明显优于参照算法.
|
| 关 键 词： | 局部搜索 无等待流水车间 调度 准备时间 总完工时间 邻域 |
A New Local Search Algorithm for No-Wait Fowshops with Setup Time |
| |
| Abstract: | A new local search algorithm called IVNS (iterated variable neighborhood search) is proposed for the no-wait flowshop scheduling problem with setup time to minimize the total completion time.Three key factors are taken into consideration when designing local search algorithms like IVNS:neighborhoods,neighboring solution evaluations and strategies for escaping local optima.Firstly,three new neighborhoods with larger sizes are introduced to enhance the chance of finding high quality solutions.The neighborhood... |
| |
| Keywords: | local search no-wait flowshop scheduling setup time total completion time neighborhood |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
