Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/14827
Title: Two-agent scheduling to minimize the total cost
Authors: Nong, QQ
Cheng, TCE 
Ng, CT 
Keywords: Approximation algorithm
Multi-agent
Polynomial time approximation scheme
Scheduling
Issue Date: 2011
Source: European Journal of operational research, 2011, v. 215, no. 1, p. 39-44 How to cite?
Journal: European Journal of Operational Research 
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.
URI: http://hdl.handle.net/10397/14827
ISSN: 0377-2217
DOI: 10.1016/j.ejor.2011.05.041
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

26
Citations as of Mar 24, 2017

WEB OF SCIENCETM
Citations

22
Last Week
0
Last month
0
Citations as of Mar 26, 2017

Page view(s)

32
Last Week
0
Last month
Checked on Mar 26, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.