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

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

Combination of constraint programming and mathematical programming for solving resources-constrained project-scheduling problems

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.