引用本文:刘士新,宋健海.求解资源受限项目调度问题的约束规划/数学规划混合算法[J].控制理论与应用,2011,28(8):1113~1120.[点击复制]
LIU Shi-xin,SONG Jian-hai.Combination of constraint programming and mathematical programming for solving resources-constrained project-scheduling problems[J].Control Theory and Technology,2011,28(8):1113~1120.[点击复制]
求解资源受限项目调度问题的约束规划/数学规划混合算法
Combination of constraint programming and mathematical programming for solving resources-constrained project-scheduling problems
摘要点击 3698  全文点击 2680  投稿时间：2010-02-05  修订日期：2010-10-09
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  
  2011,28(8):1113-1120
中文关键词  项目调度  资源受限  整数规划  约束规划  有效不等式  最大团问题
英文关键词  project scheduling  resource-constrained  integer programming  constraint programming  effective inequality  maximum clique problem
基金项目  国家自然科学基金资助项目(71021061, 70771020);“863”计划/先进制造技术领域专题资助项目(2007AA04Z194); 中央高校基础科研业务费资助项目(N100504001).
作者单位E-mail
刘士新* 东北大学 信息科学与工程学院 流程工业综合自动化国家重点实验室 sxliu@mail.neu.edu.cn 
宋健海 上海宝信软件股份有限公司  
中文摘要
      利用约束规划(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.