ИСТИНА

One of the main scheduling theory problems is the Resource-Constrained Project Scheduling Problem (RCPSP). Existing makespan lower bound es- timation approaches are based on either polynomial algorithms, which are not able to provide a satisfactory estimation when precedence relations graph is complicated, or exponential algorithms, which are not applica- ble for large-scaled instances due to their extremely high computational complexity. In this paper we consider the case of time-dependent resource capac- ities. We present a new pseudo-polynomial lower bound estimation al- gorithm with complexity O(n 3 r(n + m + r)H logH) operations (n is the number of jobs, r - number of different resources, H - planning time hori- zon, m - number of breakpoints of resource capacity function). Numerical experiments using real data and PSPLIB benchmark (5 lower bounds im- proved) showed that our algorithm provides a satisfactory lower bound in a reasonable time, and is useful in case of large-scaled instances.