Unrelated Parallel Machine Scheduling with Resource Dependent Processing Times

Alexander Grigoriev, Maxim Sviridenko, Marc Uetz

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

19 Citations (Scopus)

Abstract

We consider unrelated parallel machine scheduling problems with the objective to minimize the schedule makespan. In addition to its machine-dependence, the processing time of any job is also dependent on the usage of a scarce renewable resource. An amount of k units of that resource, e.g. workers, can be distributed over the jobs in process, and the more of that resource is allocated to a job, the smaller its processing time. The model generalizes the classical unrelated machine scheduling problem, adding a resource-time tradeoff. It is also a natural variant of a generalized assignment problem studied previously by Shmoys and Tardos, the difference lying in the fact the resource is renewable and not a total budget constraint. We use a two-phased LP rounding technique to assign resources to jobs and jobs to machines. Combined with Graham's list scheduling, we thus prove the existence of a (4+2√2)-approximation algorithm. We show how our approach can be adapted to scheduling problems with dedicated machines as well, with an improvement of the performance bound to (3+2√2). Moreover, we derive a lower bound of 2 for the employed LP-based analysis, and we prove a (3/2)-inapproximability result.
Original languageEnglish
Title of host publicationInteger Programming and Combinatorial Optimization
EditorsMichael Jünger, Volker Kaibel
Place of PublicationBerlin, Heidelberg
PublisherSpringer
Pages182-195
Number of pages14
ISBN (Electronic)978-3-540-32102-6
ISBN (Print)978-3-540-26199-5
DOIs
Publication statusPublished - May 2006
Event11th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2005 - Berlin, Germany
Duration: 8 Jun 200510 Jun 2005
Conference number: 11

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume3509
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2005
Abbreviated titleIPCO
CountryGermany
CityBerlin
Period8/06/0510/06/05

Keywords

  • Schedule problem
  • Integer linear programming
  • Feasible schedule
  • Idle period
  • Fractional solution

Fingerprint Dive into the research topics of 'Unrelated Parallel Machine Scheduling with Resource Dependent Processing Times'. Together they form a unique fingerprint.

Cite this