Online C-benevolent job scheduling on multiple machines

Research output: Contribution to journalArticlepeer-review

Abstract

We consider scheduling a sequence of C-benevolent jobs on multiple homogeneous machines. For two machines, we propose a 2-competitive Cooperative Greedy algorithm and provide a lower bound of 2 for the competitive ratio of any deterministic online scheduling algorithms on two machines. For multiple machines, we propose a Pairing-m Greedy algorithm, which is deterministic 2-competitive for even number of machines and randomized (2 + 2 / m) -competitive for odd number of machines. We provide a lower bound of 1.436 for the competitive ratio of any deterministic online scheduling algorithms on three machines, which is the best known lower bound for competitive ratios of deterministic scheduling algorithms on three machines.

Original languageEnglish (US)
Pages (from-to)251-263
Number of pages13
JournalOptimization Letters
Volume12
Issue number2
DOIs
StatePublished - Mar 1 2018

Keywords

  • Approximation algorithm
  • C-benevolent jobs
  • Online scheduling

ASJC Scopus subject areas

  • Control and Optimization

Fingerprint Dive into the research topics of 'Online C-benevolent job scheduling on multiple machines'. Together they form a unique fingerprint.

Cite this