ИСТИНА

Resource Constrained Project Scheduling Problem (RCPSP) is a well-known NP-hard scheduling theory problem. Recent surveys [1], [2] showed that existing estimation approaches for makespan lower bounds are based on polynomial and exponential algorithms. Polynomial algorithms are not able to provide good bounds for instances with complex precedence relations graphs. Exponential algorithms have very high computational complexity for largescaled instances. This research focused on the development of a new makespan lower bound estimation algorithm able to find a good lower bound in reasonable time. For the formulation with time-dependent resource capacities pseudo-polynomial algorithm with the complexity O(n3r(n + m + r)H logH) operations is presented, where n – number of jobs, r – number of resources, H = p_1 + ... + p_n – makespan upper bound, m – number of breakpoints of resource capacity functions in time horizon H. Numerical experiments using well-known PSPLIB benchmark and real data instances show that the suggested algorithm is useful especially for large-scaled instances. For 5 PSPLIB instances algorithm outperforms existed approaches and improves lower bound.