Research On An Approach With Decomposition On Time Windows For RCPSP

In the field of project management, resource-constrained project scheduling problem(RCPSP) is a kind of research issue which attracts long-term concern. This problem is the test bed of all kinds of new high performance optimization methods. In solving such problems, researchers tend to use the time windows properties of activity directly, and obtain the optimal scheduling scheme by search the feasible solution space, but ignor ing the flexibility characteristic of time windows in the search. Through the decomposition of the time windows, the feasible solution space can be reduced appropriately, which contributes to the reduction of the amount and time cost of calculations. Therefore, it is of great significance to explore the time windows decomposition algorithm for solving the RCPSP.In this study, a novel time windows decomposition algorithm is proposed. First, proper strategies to select decomposing activity are designed, to decompose the time windows, to re-calculate feasible solution sub-spaces, and to set sample scales. Then, the feasible solution space of the original problem is decomposed into multiple feasible solution sub-spaces according to the strategy. Subsequently, time windows are updated according to the re-definition, and different sampling sizes, which are positively related to their window sizes, are assigned to different time windows. At last, feasible scheduling schemes are searched in different sub-spaces. The algorithm based on different strategies are validated in this study, and five selecting strategies, three decomposition strategies, and two sampling strategies are specified in our study. Several strategies are combined subsequently, and experimental analyses are performed based on the standard library PSPLIB to validate the effectiveness of the algorithm.Through the experiments on J30, J60, and J120 in PSPLIB, results show that the time windows decomposition algorithm can effectively improve the time cost on solving the RCPSP with all the strategies. which demonstrates the rationality and validity of thealgorithm. In addition, the algorithm has a good scalability. It can be combined with a variety of heuristic algorithm to further improve efficiency, which points out possible paths for future research.