基于分支定界法的多资源约束下项目进度规划

Project Scheduling under Multiple Resource Constraints Based on Branch and Bound Procedure

基于分支定界法的思想提出了一种新的精确求解多资源约束下项目进度规划问题的最优化算法。首先依据网络图中活动的逻辑关系和资源约束进行分支构建搜索树,然后通过基于广探法思想提出的优选原则对搜索树中的分支节点进行分析比较,淘汰劣解进一步缩小搜索空间并提高求解效率,最终可获得最优解。最后通过实例进行分析表明算法在求解多资源约束条件下项目进度规划问题的有效性,同时对于资源平衡优化问题以及合理权衡项目竣工时间与资源配置两者之间关系都有一定的现实指导意义。

In this paper a new exact algorithm is proposed for solving project scheduling problems under multiple resource constrains which is based on the branch and bound procedure. The enumeration tree is generated by the feasible branches emanating from a parent node subject to precedence and resource constraints in the network. Then the feasible branches are evaluated by using the pruning rules based on the breadth-first search solution strategy, and the worse ones will be eliminated from the enumeration tree while the better will continue branching until they get the best solution. It is proved by examples that this new exact algorithm is efficient, providing a method for resource balance and a reasonable trade-off between resource allocation and duration.