Abstract | ||
---|---|---|
Two agents, each having his own set of jobs, compete to perform their own jobs on a common processing resource. Each job of the agents has a weight that specifies its importance. The cost of the first agent is the maximum weighted completion time of his jobs while the cost of the second agent is the total weighted completion time of his jobs. We consider the scheduling problem of determining the sequence of the jobs such that the total cost of the two agents is minimized. We provide a 2-approximation algorithm for the problem, show that the case where the number of jobs of the first agent is fixed is NP-hard, and devise a polynomial time approximation scheme for this case. © 2011 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1016/j.ejor.2011.05.041 | European Journal of Operational Research |
Keywords | Field | DocType |
Scheduling,Multi-agent,Approximation algorithm,Polynomial time approximation scheme | Approximation algorithm,Mathematical optimization,Job shop scheduling,Scheduling (computing),Total cost,Polynomial-time approximation scheme,Operations management,Mathematics | Journal |
Volume | Issue | ISSN |
215 | 1 | 0377-2217 |
Citations | PageRank | References |
21 | 0.78 | 11 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Q. Q. Nong | 1 | 47 | 6.24 |
t c edwin cheng | 2 | 21 | 0.78 |
c t daniel ng | 3 | 21 | 0.78 |