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: [email protected] (K. Lee), [email protected] (B.-C. Choi), [email protected] (J.Y.-T. Leung), [email protected] (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 -