Approximability results for the resource-constrained project scheduling problem with a single type of resources

What is it about?

This paper considers the well-known resource-constrained project scheduling problem. Some arguments are given that already a special case of this problem with a single type of resources is not approximable in polynomial time with an approximation ratio bounded by a constant. There exist instances for which the optimal makespan values for the non-preemptive and the preemptive problems have a ratio of O(logn), where n is the number of jobs. This means that there exist instances for which the lower bound of Mingozzi et al. has a bad relative error of O(logn), and the calculation of this bound is an NP-hard problem.

Featured Image