Approximation algorithms for multi-agent scheduling to minimize total weighted completion time

Kangbok Lee, Byung Cheon Choi, Joseph Y.T. Leung, Michael L. Pinedo

Research output: Contribution to journalArticlepeer-review

77 Scopus citations

Abstract

We consider a multi-agent scheduling problem on a single machine in which each agent is responsible for his own set of jobs and wishes to minimize the total weighted completion time of his own set of jobs. It is known that the unweighted problem with two agents is NP-hard in the ordinary sense. For this case, we can reduce our problem to a Multi-Objective Shortest-Path (MOSP) problem and this reduction leads to several results including Fully Polynomial Time Approximation Schemes (FPTAS). We also provide an efficient approximation algorithm with a reasonably good worst-case ratio.

Original languageEnglish (US)
Pages (from-to)913-917
Number of pages5
JournalInformation Processing Letters
Volume109
Issue number16
DOIs
StatePublished - Jul 31 2009

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Approximation algorithm
  • FPTAS
  • Multi-Objective Shortest-Path problem
  • Multi-agent scheduling
  • Total weighted completion time

Fingerprint

Dive into the research topics of 'Approximation algorithms for multi-agent scheduling to minimize total weighted completion time'. Together they form a unique fingerprint.

Cite this