基于CSP的Job shop调度算法研究

A Job shop Scheduling Algorithm Based on Constraint Satisfaction Problem

针对一类典型的约束满足问题--Job shop调度问题,提出一种CSP调度算法框架,详细讨论CSP 调度算法中的工序开始时间窗、一致性预处理、搜索空间概率模型、工序排序启发、开工时间排序启发的求解 方法。仿真结果表明CSP调度算法在较小的计算时间代价下,获得了FT10标准调度问题的近优解。

For the job shop scheduling problem, scheduling model and scheduling algorithm based on constraint satisfaction problem are proposed. Operation start time window, consistent enforcing, probabilistic model of the search space, operation ordering heuristics and start time ordering heuristics are introduced. The simulation indicates that this new scheduling algorithm yields a approximate result of FT10 benchmark problem under small time cost.