@book{e79a2cf6ca164be69f4a17c96c5aed47,

title = "Scheduling Parallel Jobs with Time-Resource Tradeoff via Nonlinear Programming",

abstract = "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 $k$ 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 timeresource 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 + \varepsilon)$ for any $\varepsilon > 0$. Our approach relies on a fully polynomial time approximation scheme to solve the mathematical programming relaxation. This result is interesting in itself, because we also show that the underlying mathematical program is NP-hard to solve. We also derive lower bounds for the approximation.",

keywords = "EWI-15168, IR-65415, METIS-256465",

author = "A. Grigoriev and Uetz, {Marc Jochen}",

year = "2008",

month = apr,

language = "Undefined",

series = "CTIT Technical Report Series",

publisher = "University of Twente",

number = "TR-CTIT-08-78",

address = "Netherlands",

}