Scheduling on two identical machines with a speed-up resource

Haifeng Xu, Lin Chen, Deshi Ye, Guochuan Zhang

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

We address a variant of scheduling problem on two identical machines, where we are given an additional speed-up resource. If a job uses the resource, its processing time may decrease. However, at any time the resource can only be used by at most one job. The objective is to minimize the makespan. For the offline version, we present an FPTAS. For the online version where jobs arrive over list, we propose an online algorithm with competitive ratio of 1.781, and show a lower bound of 1.686 for any online algorithm.

Original languageEnglish
Pages (from-to)831-835
Number of pages5
JournalInformation Processing Letters
Volume111
Issue number17
DOIs
StatePublished - Sep 15 2011

Keywords

  • FPTAS
  • Online algorithms
  • Scheduling

Fingerprint

Dive into the research topics of 'Scheduling on two identical machines with a speed-up resource'. Together they form a unique fingerprint.

Cite this