Abstract
We consider the feasibility model of multi-agent scheduling on a single machine, where each agent's objective function is to minimize the total weighted number of tardy jobs. We show that the problem is strongly NP-complete in general. When the number of agents is fixed, we first show that the problem can be solved in pseudo-polynomial time for integral weights, and can be solved in polynomial time for unit weights; then we present a fully polynomial-time approximation scheme for the problem.
Original language | English |
---|---|
Pages (from-to) | 273-281 |
Number of pages | 9 |
Journal | Theoretical Computer Science |
Volume | 362 |
Issue number | 1-3 |
DOIs | |
Publication status | Published - 11 Oct 2006 |
Keywords
- Multi-agent deterministic sequencing
- Scheduling
ASJC Scopus subject areas
- Computational Theory and Mathematics