基于一致性预处理技术的作业车间调度算法研究

Job Shop Scheduling Algorithm Based on Consistency Enforcing Technique

为降低CSP调度算法的计算复杂度和减少搜索过程中回溯发生概率,采用一致性预处理技术来预先修剪和过滤搜索空间。仿真实验证明:两种方法的综合运用可以显著提高CSP调度算法的搜索效率,从而为CSP调度算法求解大规模作业车间调度问题提供可能。

For improving the average efficiency and reducing the average complexity of the basic backtrack search procedure, consistency preprocessing technique (CPT) is put forward to prune the search space by eliminating local inconsistencies that cannot participate in a global scheduling solution.The simulation indicates that CPT can greatly reduce both the frequency and the amount of backtrack,thus greatly improving the search efficiency of job shop scheduling.