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

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

doi:10.1016/j.ipl.2009.04.018

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

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

Computer Science

Research output: Contribution to journal › Article › peer-review

86 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 language	English (US)
Pages (from-to)	913-917
Number of pages	5
Journal	Information Processing Letters
Volume	109
Issue number	16
DOIs	https://doi.org/10.1016/j.ipl.2009.04.018
State	Published - 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

Access to Document

10.1016/j.ipl.2009.04.018

Cite this

@article{2cfa71975a7845e98760882d1d872ca8,

title = "Approximation algorithms for multi-agent scheduling to minimize total weighted completion time",

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.",

keywords = "Approximation algorithm, FPTAS, Multi-Objective Shortest-Path problem, Multi-agent scheduling, Total weighted completion time",

author = "Kangbok Lee and Choi, {Byung Cheon} and Leung, {Joseph Y.T.} and Pinedo, {Michael L.}",

note = "Funding Information: E-mail addresses: klee3@stern.nyu.edu (K. Lee), byungcheon.choi@gmail.com (B.-C. Choi), leung@cis.njit.edu (J.Y.-T. Leung), mpinedo@stern.nyu.edu (M.L. Pinedo). 1 Work supported by the Korea Research Foundation Grant 357-D00270. 2 Work supported by the Korea Research Foundation Grant 357-D00289. 3 Work supported in part by the NSF Grant DMI-0556010. 4 Work supported in part by the NSF Grant DMI-0555999.",

year = "2009",

month = jul,

day = "31",

doi = "10.1016/j.ipl.2009.04.018",

language = "English (US)",

volume = "109",

pages = "913--917",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "16",

}

TY - JOUR

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

AU - Lee, Kangbok

AU - Choi, Byung Cheon

AU - Leung, Joseph Y.T.

AU - Pinedo, Michael L.

N1 - Funding Information: E-mail addresses: klee3@stern.nyu.edu (K. Lee), byungcheon.choi@gmail.com (B.-C. Choi), leung@cis.njit.edu (J.Y.-T. Leung), mpinedo@stern.nyu.edu (M.L. Pinedo). 1 Work supported by the Korea Research Foundation Grant 357-D00270. 2 Work supported by the Korea Research Foundation Grant 357-D00289. 3 Work supported in part by the NSF Grant DMI-0556010. 4 Work supported in part by the NSF Grant DMI-0555999.

PY - 2009/7/31

Y1 - 2009/7/31

N2 - 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.

AB - 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.

KW - Approximation algorithm

KW - FPTAS

KW - Multi-Objective Shortest-Path problem

KW - Multi-agent scheduling

KW - Total weighted completion time

UR - http://www.scopus.com/inward/record.url?scp=67649342188&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67649342188&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2009.04.018

DO - 10.1016/j.ipl.2009.04.018

M3 - Article

AN - SCOPUS:67649342188

SN - 0020-0190

VL - 109

SP - 913

EP - 917

JO - Information Processing Letters

JF - Information Processing Letters

IS - 16

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this