Resource cost aware scheduling

Rodrigo A. Carrasco, Garud Iyengar, Cliff Stein

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

We are interested in the scheduling problem where there are several different resources that determine the speed at which a job runs and we pay depending on the amount of each resource that we use. This work is an extension of the resource dependent job processing time problem and the energy aware scheduling problems. We develop a new constant factor approximation algorithm for resource cost aware scheduling problems: the objective is to minimize the sum of the total cost of resources and the total weighted completion time in the one machine non-preemptive setting, allowing for arbitrary precedence constraints and release dates. Our algorithm handles general job-dependent resource cost functions. We also analyze the practical performance of our algorithms, showing that it is significantly superior to the theoretical bounds and in fact it is very close to optimal. The analysis is done using simulations and real instances, which are left publicly available for future benchmarks. We also present additional heuristic improvements and we study their performance in other settings.

Original languageEnglish
Pages (from-to)621-632
Number of pages12
JournalEuropean Journal of Operational Research
Volume269
Issue number2
DOIs
StatePublished - 1 Sep 2018

Keywords

  • Approximation algorithms
  • Resource aware scheduling
  • Scheduling
  • Speed-scaling

Fingerprint

Dive into the research topics of 'Resource cost aware scheduling'. Together they form a unique fingerprint.

Cite this