• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

A new polynomial-time algorithm for calculating upper bounds on resource usage for RCPSP problem

P. 22-25.
Lazarev A. A., Dmitry Arkhipov D., Battaia O. O.

The Resource-Constrained Project Scheduling Problem (RCPSP) is considered. This problem is NP-hard in strong sense (Garey and Johnson 1975). In this paper, a new polynomial-time approach is developed to find an upper bound on resource consumption. This bound can be also used to calaculate a lower bound for makespan. The procedure also helps to increase the efficiency of existed propagators and to improve constraint programming model performances by tightening decision variables domains.