求解项目调度中资源水平问题的近似算法

Approximate algorithm for solving resource levelling problems in project scheduling

针对 RL P与 RCPSP的相似之处和自身特点 ,以求解 RCPSP的遗传算法为基础 ,设计了一种求解 RL P的基于分支定界策略的近似算法 .搜索树的每一节点对应一个 RCPSP,通过求解各节点 RCPSP来求得 RL P的最优调度计划 .算法从具有基本资源需求水平的根节点开始 ,采用宽度优先顺序逐渐提高各种资源的可用量 ,既有利于资源的均衡利用 ,又可以通过定界策略有效地控制搜索树的节点数量 .结合实例问题说明了基于分支定界策略的近似算法的求解过程 .最后通过实例问题对该算法与遗传算法进行求解效果和时间效率的对比 。

Through analyzing similarities and differences between the RLP and the RCPSP,we develop a branch and bound strategy based approximate algorithm for solving the RLP based on a GAs for solving the RCPSP. Every node in search tree corresponds a RCPSP, and the RCPSP is solved to obtain schedule for the RLP. From root node with basic resources requirement, the algorithm increases resource levelling in width first order, so that the resources can be utilized in balance, and the number of node in the search tree can be controlled effectively by bound strategy.The solving process is demonstrated by a numerical example.By comparing with GA through a standard set of instances,the results show that this approximate algorithm has better performance than the GA, but when taking into account running time the GA is much better.