On Some Realizations of Solving the Resource Constrained Project Scheduling Problems

Abstract

We consider the resource-constrained project scheduling problem with respect to the makespan minimization criterion. The problem accounts for technological constraints of activities precedence together with resource constraints. Activities preemptions are not allowed. We consider renewable and cumulative resources. The problem with renewable resources is NP-hard in the strong sense, but the problem with cumulative resources can be solved in polynomial time. We propose two methods for solving the problem with renewable resources. One of them is the exact branch and bound algorithm with a new branching scheme based on the presentation of a schedule in the form of a activity list. We use two variants of constructing the lower bound. In another method we use metaheuristics. We present the results of numerical experiments illustrating the quality of the proposed algorithm. The test instances were used from the library of test instances PSPLIB. Numerical experiments demonstrated the algorithm's competitiveness. We have found the best solutions for a few instances from the dataset j120.