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

86 Scopus citations


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
Issue number16
StatePublished - Jul 31 2009

All Science Journal Classification (ASJC) codes

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


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


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