tailieunhanh - On some implementations of solving the resource constrained project scheduling problems

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. The problem with renewable resources is NP-hard in the strong sense. We propose an exact branch and bound algorithm for solving the problem with renewable resources. It uses our new branching scheme based on the representation of a schedule in the form of an activity list. | Yugoslav Journal of Operations Research xx (2017), Number nn, zzz–zzz DOI: ON SOME IMPLEMENTATIONS OF SOLVING THE RESOURCE CONSTRAINED PROJECT SCHEDULING PROBLEMS . GIMADI Sobolev Institute of Mathematics, Novosibirsk, Russia gimadi@ . GONCHAROV Sobolev Institute of Mathematics, Novosibirsk, Russia gon@ . MISHIN Sobolev Institute of Mathematics, Novosibirsk, Russia mishindmv@ Received: November 2017 / Accepted: September 2018 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. The problem with renewable resources is NP-hard in the strong sense. We propose an exact branch and bound algorithm for solving the problem with renewable resources. It uses our new branching scheme based on the representation of a schedule in the form of an activity list. We use two approaches of constructing the lower bound. We present results of numerical experiments illustrating quality of the proposed lower bounds. The test instances are taken from the library of test instances PSPLIB. Keywords: Project management, Resource constrained project scheduling problem, Renewable resources, Cumulative resources, Branch and bound algorithms, PCPLIB. MSC: 90B35, 90C27, 90C59. 1. INTRODUCTION We consider the resource constrained project scheduling problem (RCPSP) with precedence and resource constraints. The RCPSP can be defined as a combinatorial optimization problem. A partial order on the set of activities is defined with a directed acyclic graph. For every activity, we know its duration, the list of resources required for its completion, and the amount of consumed resources. The resources are assumed to be unbounded outside the project horizon Tˆ. Activities preemptions are not