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
Publisher: Elsevier
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
EISSN: 1872-6860
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

29
Last Week
0
Last month
0
Citations as of Aug 17, 2017

WEB OF SCIENCETM
Citations

26
Last Week
0
Last month
0
Citations as of Aug 12, 2017

Page view(s)

110
Last Week
1
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



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