Scheduling jobs with time-resource tradeoff via nonlinear programming

We consider a scheduling problem where the processing time of any job is dependent on the usage of a discrete renewable resource, e.g. personnel. An amount of kk units of that resource can be allocated to the jobs at any time, and the more of that resource is allocated to a job, the smaller its processing time. The objective is to find a resource allocation and a schedule that minimizes the makespan. We explicitly allow for succinctly encodable time-resource tradeoff functions, which calls for mathematical programming techniques other than those that have been used before. Utilizing a (nonlinear) integer mathematical program, we obtain the first polynomial time approximation algorithm for the scheduling problem, with performance bound (3+ε)(3+ε) for any ε>0ε>0. Our approach relies on a fully polynomial time approximation scheme to solve the nonlinear mathematical programming relaxation. We also derive lower bounds for the approximation.