基于关键路径求解作业车间调度问题的收敛性分析

来源：计算机集成制造系统杂志2014年第5期北京时间：

作者：刘刚,王瑛,张发

单位：空军工程大学装备管理与安全工程学院

摘要：为深入研究基于关键路径求解作业车间调度问题的算法收敛性理论,在构建状态空间与明确算法收敛性充要条件的基础上划分方案转化途径,在参与转换的工序数量与移动方式方面对Van Laarhoven,Nowicki,DellAmico,Balas与Nasiri,Zhang五种邻域结构的部分性质进行拓展,得到相应推论并明确转化途径与完工时间的关系。将五种邻域结构与状态寻优路径相对比,得出结论:五种邻域结构的应用不能满足算法收敛直接连通性的充要条件,利用五种邻域结构求解作业车间调度问题无法保证收敛。所提方案转化途径与工序在关键工序集与非关键工序集间的移动方式,为基于关键路径的邻域结构设计提供了新的思路。

关键词：关键路径,邻域结构,作业车间调度问题,收敛性分析,Markov链

基金资助：国家自然科学基金资助项目(71171199)。