Home About Upload Latest Additions Statistics Contact
UT Proceedings
UT Student Theses
Dutch Academic Output Dutch Dissertations EU Publications (OpenAIRE)
Printversion
Advanced search

Scheduling Parallel Jobs with Time-Resource Tradeoff via Nonlinear Programming

Share/Save/Bookmark

Grigoriev, A. and Uetz, M.J. (2008) Scheduling Parallel Jobs with Time-Resource Tradeoff via Nonlinear Programming. [Report]

[img]
Preview
PDF
192Kb
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.
Item Type:Report
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/65415
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 256465