具有优先关系的累积调度问题的约束传播算法

Constraint Propagation for Cumulative Scheduling Problems with Precedences

约束传播是约束规划成功应用的关键技术之一.针对累积调度问题提出一种结合工作间优先关系和工作最早开始/最晚完成时间约束的约束传播算法,给出了算法的理论依据.引用资源受限项目调度问题库PSPLIB中的典型问题对算法进行了测试,结果表明:针对测试问题新的约束传播算法在总体约减效果上优于现有约束传播算法,新算法与基于能量推理的约束传播算法可以互补,两者结合推理效果更好.

Constraint propagation is one of the key elements of constraint programming. After presenting supporting theories of constraint propagation for cumulative scheduling problems （CUSP）, the authors propose a constraint propagation algorithm in which both precedence constraints and activity time bound constraints are taken into consideration. By citing two sets of benchmark problems of PSPLIB to test the algorithm, experimental results show that the new algorithm outperforms existing constraint propagation algorithms for the testing problems. Moreover, the new algorithm and the energetic reasoning algorithm may complement each other. A hybrid one of the two algorithms is promising.