Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/646
Title: | Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs | Authors: | Cheng, TCE Ng, CTD Yuan, JJ |
Issue Date: | 11-Oct-2006 | Source: | Theoretical computer science, 11 Oct. 2006, v. 362, no. 1-3, p. 273-281 | 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. | Keywords: | Scheduling Multi-agent deterministic sequencing |
Publisher: | Elsevier | Journal: | Theoretical computer science | ISSN: | 0304-3975 | DOI: | 10.1016/j.tcs.2006.07.011 | Rights: | Theoretical Computer Science © 2006 Elsevier B.V. The journal web site is located at http://www.sciencedirect.com. |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
sum-mu(Multi-Agents) final.pdf | Pre-published version | 154.24 kB | Adobe PDF | View/Open |
Page views
252
Last Week
0
0
Last month
Citations as of Oct 13, 2024
Downloads
239
Citations as of Oct 13, 2024
SCOPUSTM
Citations
194
Last Week
0
0
Last month
3
3
Citations as of Oct 17, 2024
WEB OF SCIENCETM
Citations
174
Last Week
0
0
Last month
2
2
Citations as of Oct 17, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.