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

Abstract: 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.

Key words: critical path, neighborhood structure, job shop scheduling problem, convergence analysis, Markov chain