Approximate algorithm for solving resource levelling problems in project scheduling

Through analyzing similarities and differences between the resource levelling problem (RLP) and the resource constrained project scheduling problem (RCPSP), we develop a branch-and-bound strategy based approximate algorithm for solving the RLP based on a genetic algorithm for solving the RCPSP. Every node in search tree corresponds to an 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 nodes 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.