摘要
为深入研究基于关键路径求解作业车间调度问题的算法收敛性理论,在构建状态空间与明确算法收敛性充要条件的基础上划分方案转化途径,在参与转换的工序数量与移动方式方面对Van Laarhoven,Nowicki,DellAmico,Balas与Nasiri,Zhang五种邻域结构的部分性质进行拓展,得到相应推论并明确转化途径与完工时间的关系。将五种邻域结构与状态寻优路径相对比,得出结论:五种邻域结构的应用不能满足算法收敛直接连通性的充要条件,利用五种邻域结构求解作业车间调度问题无法保证收敛。所提方案转化途径与工序在关键工序集与非关键工序集间的移动方式,为基于关键路径的邻域结构设计提供了新的思路。
To research algorithm convergence analysis based on critical path for Job Shop Scheduling Problem （JSSP）deeply,the scheme transform ways were differentiated on the basis of constructing state space and confirming sufficient conditions of algorithm convergence.The part properties of Van Laarhoven neighbourhood,Nowicki neighbourhood,Dell＇Amico neighbourhood,Balas＆Nasiri neighbourhood and Zhang neighbourhood were extended in the aspects of operation amount and moving type,and the corresponding corollaries and relationships between schemes transform ways and makespan were also acquired.The structures of five neighbourhoods were compared with the state optimization path,and the sufficient condition that the application of above five neighbourhoods did not meet directed connection condition of algorithm convergence was obtained,and the conclusion that the algorithm convergence for JSSP by using five neighbourhoods could not be promised was proved.The scheme transform ways as well as the operation moving types between critical operation set and non-critical operation set could provide the new ideas for critical path-based neighbourhood structure design.
出处
《计算机集成制造系统》
EI
CSCD
北大核心
2014年第5期1078-1087,共10页
Computer Integrated Manufacturing Systems
基金
国家自然科学基金资助项目(71171199)~~
