邻域解集裁剪方法和作业车间调度问题的局部搜索方法

摘要

本发明公开邻域解集裁剪方法和作业车间调度问题的局部搜索方法，属于车间调度领域。包括：对当前可行调度解中的关键工序按照邻域结构进行移动，得到一组关键工序的移动组合；采用以下方式对每个关键工序的移动组合进行评估：若移动组合对应的关键工序的移动不能够减小至少一个关键块的开始时间，该移动组合对应的邻域解的制造期将不会减小；将邻域解的制造期增大的移动组合裁剪，剩余移动组合对应的邻域解构成邻域解集。本发明通过关键路径变化特征分析邻域解质量下降原因，剔除无法减小制造期的关键工序的移动组合，细化对邻域解质量的管理；经过裁剪，生成的邻域解数量减少，从而有效提高局部搜索的计算速度和计算效率，更快地得到局部最优解。