Template-type: ReDif-Paper 1.0
Author-Name: Grigoriev Alexander
Author-Name: Uetz Marc
Author-workplace-name: METEOR
Title: Scheduling Parallel Jobs with Linear Speedup
Abstract: We consider a scheduling problem where a set of jobs is 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+e)-approximation algorithm for that problem, for any e>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 in general. We also briefly discuss variants of the problem and derive lower bounds.
Keywords: operations research and management science; 
Series: Research Memoranda
Creation-Date: 2005
Number: 014
File-URL: http://digitalarchive.maastrichtuniversity.nl/fedora/objects/guid:fdef7036-c893-4f69-b67b-25d23652e8c5/datastreams/ASSET1/content
File-Format: application/pdf
File-Size: 168866
Handle: RePEc:unm:umamet:2005014