Approximation Algorithms for Multi-agent Scheduling to Minimize Total Weighted Completion Time
SCIE
SCOPUS
- Title
- Approximation Algorithms for Multi-agent Scheduling to Minimize Total Weighted Completion Time
- Authors
- Lee, K; Choi, BC; Leung, JYT; Pinedo, ML
- Date Issued
- 2009-07-31
- Publisher
- ELSEVIER SCIENCE BV
- 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. (C) 2009 Elsevier B.V. All rights reserved.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/36388
- DOI
- 10.1016/J.IPL.2009.04.018
- ISSN
- 0020-0190
- Article Type
- Article
- Citation
- INFORMATION PROCESSING LETTERS, vol. 109, no. 16, page. 913 - 917, 2009-07-31
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.