摘要
利用约束规划(constraint programming,CP)与数学规划(mathematical programming,MP)结合的方法求解调度问题已经获得了一些较好的研究成果,正成为调度问题研究领域的一个新的热点研究方向.本文针对求解资源受限项目调度问题(RCPSP)的整数规划模型,设计了基于CP技术的问题和模型预处理方法,证明了整数规划模型的有效不等式定理,提出了通过将项目子网络图转化为加权最大团问题求解后获得有效不等式的方法.引用标准问题库PSPLIB中的一组典型问题进行求解实验,结果表明本文提出的有效不等式可以明显改进模型的求解质量和时间性能.论文最后对实验结果进行了深入讨论,讨论了未来的研究方向.
Combining constraint programming（CP） and mathematical programming（MP） to solve scheduling problems has been an interesting topic for researchers, and promising results are obtained. We propose a preprocessing approach for solving resource-constrained project-scheduling problems（RCPSP） with integer programming（IP） model, and prove an effective inequality theory for the IP model. The effective inequality can be obtained by solving a maximum clique problem which is built on a sub-network of the original project. A detailed computational experiment is performed using the well-known standard instances in PSPLIB. Computational results show that the proposed effective inequality remarkably improves the performances of the IP model. Finally, the computational results are analyzed and future research directions are discussed.
出处
《控制理论与应用》
EI
CAS
CSCD
北大核心
2011年第8期1113-1120,共8页
Control Theory & Applications
基金
国家自然科学基金资助项目(71021061
70771020)
"863"计划/先进制造技术领域专题资助项目(2007AA04Z194)
中央高校基础科研业务费资助项目(N100504001)
关键词
项目调度
资源受限
整数规划
约束规划
有效不等式
最大团问题
project scheduling
resource-constrained
integer programming
constraint programming
effective inequality
maximum clique problem
