基于动态一致性增强技术的Job Shop调度算法研究

A Method for Job Shop Scheduling Based on Dynamic Consistency Enforcing Technique

为降低CSP调度算法的计算复杂度和减少搜索过程中回溯发生概率,采用动态一致性增强技术来预先修剪和过滤搜索空间。通过基于顺序约束的动态一致性增强算法,将当前搜索状态下的工序取值结果沿工艺路线向上下游工序传播,从而有效修剪了同一零件内剩余待调度工序的开工时间窗;针对Job Shop调度问题中最难满足的能力约束,采用基于能力约束的动态一致性增强算法,根据当前搜索空间的工序取值对竞争同一机床的其它剩余待调度工序的开工时间窗实施修剪。仿真实验证明:这2种方法的综合运用可以显著提高CSP调度算法的搜索效率,从而为CSP调度算法求解大规模Job Shop调度问题提供可能。

For improving the average efficiency and reducing the average complexity of the basic backtrack search procedure,Dynamic Consistency Enforcing Technique（DCET） is put forward to prune the search space by eliminating local inconsistencies that cannot participate in a global scheduling solution.The DCET includes two algorithms,i.e.precedence and capacity consistency enforcing algorithm.Precedence consistency enforcing algorithm can effectively prune reservations of unscheduled operations upstream or downstream within the same job by earlier reservation assignments.For more difficult capacity constraints,capacity consistency enforcing algorithm is carried out to prune possible reservations of the remaining unscheduled operations which compete for the same resource with scheduled operation in current search space.The simulation indicates that DCET can greatly reduce both the frequency and the amount of backtrack,thus greatly improving the search efficiency of job shop scheduling.