Approximation Hardness of Resource Scheduling

We study the precedence-constrained resource scheduling problem [SICOMP'75]. There are n jobs where each job takes a certain time to finish and has a resource requirement throughout the execution time. There are precedence among the jobs. The problem asks that given a resource budget, schedule the jobs obeying the precedence constraints to minimize makespan (maximum completion time of a job) such that at any point in time, the total resource being used by all the jobs is at most the given resource budget. In the offline setting, an important open question is whether a polynomial-time O(1)-factor approximation algorithm can be found. We prove that hardness of constant factor approximation unless P=NP. In fact, we prove a stronger lower bound that for some constant α > 0, there is no o ((log tmax)α)-factor approximation algorithm for the offline version of the problem with maximum job length tmax, even if there is only one type of resource, unless P = NP.