Combinatorial algorithms for minimizing the weighted sum of completion times on a single machine

James M. Davis, Rajiv Gandhi, Vijay H. Kothari

Research output: Contribution to journalArticlepeer-review

Abstract

We study the problem of minimizing the weighted sum of completion times of jobs with release dates on a single machine with the aim of shedding new light on "the simplest (linear program) relaxation" (Queyranne and Schulz, 1994 [17]). Specifically, we analyze a 3-competitive online algorithm (Megow and Schulz, 2004 [16]), using dual fitting. In the offline setting, we develop a primal-dual algorithm with approximation guarantee 1+2. The latter implies that the cost of the optimal schedule is within a factor of 1+2 of the cost of the optimal LP solution.

Original languageEnglish (US)
Pages (from-to)121-125
Number of pages5
JournalOperations Research Letters
Volume41
Issue number2
DOIs
StatePublished - Mar 2013

Keywords

  • Algorithms
  • Approximation
  • Dual fitting
  • Online
  • Primal-dual
  • Scheduling

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Combinatorial algorithms for minimizing the weighted sum of completion times on a single machine'. Together they form a unique fingerprint.

Cite this