Scheduling parallel jobs with linear speedup

Alexander Grigoriev, Marc Uetz

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

8 Citations (Scopus)


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 + ε) -approximation algorithm for that problem, for any ε > 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.
Original languageEnglish
Title of host publicationApproximation and Online Algorithms
Subtitle of host publicationThird International Workshop, WAOA 2005, Palma de Mallorca, Spain, October 6-7, 2005, Revised Papers
EditorsThomas Erlebach, Giuseppe Persinao
Number of pages12
ISBN (Electronic)978-3-540-32208-5
ISBN (Print)978-3-540-32207-8
Publication statusPublished - 2006
Event3rd International Workshop on Approximation and Online Algorithms, WAOA 2005 - Hotel Tryp Bellver, Palma de Mallorca, Spain
Duration: 6 Oct 20057 Oct 2005
Conference number: 3


Workshop3rd International Workshop on Approximation and Online Algorithms, WAOA 2005
Abbreviated titleWAOA
CityPalma de Mallorca

Fingerprint Dive into the research topics of 'Scheduling parallel jobs with linear speedup'. Together they form a unique fingerprint.

Cite this