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