摘要
针对一类典型的约束满足问题--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.
出处
《系统工程》
CSCD
北大核心
2004年第11期15-18,共4页
Systems Engineering
基金
国家863高技术研究发展计划资助项目(2003AA41110)航空基金资助项目(01H53061)
关键词
JOB
shop调度
约束满足问题
工序开始时间窗
概率模型
工序排序启发
开工时间排序启发
Job shop Scheduling
Constraint Satisfaction Problem
Operation Start Time Window
Probabilistic Model
Operation Ordering Heuristics
Start Time Ordering Heuristics