Affordable Access

Scheduling parallel jobs with linear speedup

Publication Date
  • Computer Science


Scheduling Parallel Jobs with Linear Speedup Alexander Grigoriev and Marc Uetz Maastricht University, Quantitative Economics, P.O.Box 616, 6200 MD Maastricht, The Netherlands. Email: {a.grigoriev,[email protected] 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 allo- cation 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 gener- alizes 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. 1 Introduction and related work Consider a scheduling problem where n jobs j ∈ V , with integral processing times pj , and each jobs is already assigned to one of m parallel machines. There is a renewable discrete resource, e.g. personnel, that can be allocated to jobs in order to reduce their processing requirements. We assume that the tradeoff between usage of the resource and the resulting processing requirement of a job can be described succinctly by a corresponding linear compression rate bj ≥ 0. In other words, each job has a default processing time of p¯j , and when s resources are assigned to job j, its processing requirement becomes pjs = p¯j − bj s. At any point in time, only k units of that resource are available. Once

There are no comments yet on this publication. Be the first to share your thoughts.