求解资源受限项目调度问题的约束规划/数学规划混合算法

作者：刘士新; 宋健海

来源：控制理论与应用, 2011, (08): 1113-1120.

• 项目调度
• 资源受限
• 整数规划
• 约束规划
• 有效不等式
• 最大团问题 project scheduling
• resource-constrained
• integer programming
• constraint programming
• effective inequal-ity
• maximum clique problem

利用约束规划(constraint programming,CP)与数学规划(mathematical programming,MP)结合的方法求解调度问题已经获得了一些较好的研究成果,正成为调度问题研究领域的一个新的热点研究方向.本文针对求解资源受限项目调度问题(RCPSP)的整数规划模型,设计了基于CP技术的问题和模型预处理方法,证明了整数规划模型的有效不等式定理,提出了通过将项目子网络图转化为加权最大团问题求解后获得有效不等式的方法.引用标准问题库PSPLIB中的一组典型问题进行求解实验,结果表明本文提出的有效不等式可以明显改进模型的求解质量和时间性能.论文最后对实验结果进行了深入讨论,...

• 单位
  东北大学; 流程工业综合自动化国家重点实验室; 上海宝信软件股份有限公司