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

    Fingerprint

Keywords

  • Approximation algorithm
  • C-benevolent jobs
  • Online scheduling

ASJC Scopus subject areas

  • Control and Optimization

Cite this