对于NEH启发式方法搜索邻域的研究

摘要

综合考虑所需的计算时间和最终获得的解的质量,研究了NEH启发式方法在以Makespan为目标的置换流水车间调度问题(PFSP)中的应用。由于NEH算法取得成功的一个重要原因在于其迭代式插入邻域搜索过程,因此,着重从它的邻域搜索空间入手,用精简或增强邻域的方法,给出了几种不同的空间结构。实验结果表明,给出的两种增强的结构能取得比以往算法更优的解,即利用这两种算法可以大大缩短完工时间,获得更有效的调度。