Scheduling jobs with time-resource tradeoff via nonlinear programming

Grigoriev, Alexander and Uetz, Marc (2009) Scheduling jobs with time-resource tradeoff via nonlinear programming. Discrete Optimization, 6 (4). pp. 414-419. ISSN 1572-5286

PDF
Restricted to UT campus only: Request a copy
209Kb

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 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 + \varepsilon)$ for any $\varepsilon > 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.
Item Type:	Article
Copyright:	© 2009 Elsevier
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/67838
Official URL:	http://dx.doi.org/10.1016/j.disopt.2009.05.002
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 263959