Scheduling parallel jobs with linear speedup


Share/Save/Bookmark

Grigoriev, A. and Uetz, M.J. (2006) Scheduling parallel jobs with linear speedup. In: Approximation and Online Algorithms, Third International Workshop, WAOA 2005, 6-7 October, 2005, Palma de Mallorca, Spain.

[img]PDF
Restricted to UT campus only
: Request a copy
242Kb
Abstract:We consider a scheduling problem where a set of jobs is a-priori distributed over parallel machines. The processing time of any job is dependent on the usage of a scarce 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 dependence of processing times on the amount of resources is linear for any job. The objective is to find a resource allocation and a schedule that minimizes the makespan. Utilizing an integer quadratic programming relaxation, we show how to obtain a $(3 + \varepsilon)$-approximation algorithm for that problem, for any $\varepsilon > 0$. This generalizes and improves previous results, respectively. Our approach relies on a fully polynomial time approximation scheme to solve the quadratic programming relaxation. This result is interesting in itself, because the underlying quadratic program is NP-hard to solve. We also derive lower bounds, and discuss further generalizations of the results.
Item Type:Conference or Workshop Item
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/62215
Official URL:http://dx.doi.org/10.1007/11671411_16
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page