An effective approach with feasible space decomposition to solve resource-constrained project scheduling problems

Resource-constrained project scheduling problem is a classic problem in construction project. Aimed at solving this problem, an effective approach with decomposition on time windows is proposed in this paper. This approach is to select one activity to do decomposition and to partition the feasible space of the original problem into some feasible subspaces, in which solutions are generated by using an extended serial scheduling scheme. Double justification is also performed in the process of searching in subspace. Four strategies for selecting activity to do decomposition, three strategies for decomposition and a strategy on sampling size in various subspaces are designed. The results of experiments on two real construction projects show that the strategy based on degree for selecting activity and the strategy based on initial schedule for decomposition can obtain the best results. When compared with some other exiting algorithms, it is proven that the decomposition-based approach is effective and competitive.