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 
Issue Date: 2011
Source: European journal of operational research, 2011, v. 215, no. 1, p. 39-44
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.
Keywords: Approximation algorithm
Multi-agent
Polynomial time approximation scheme
Scheduling
Publisher: Elsevier
Journal: European journal of operational research 
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

39
Last Week
0
Last month
0
Citations as of Sep 7, 2020

WEB OF SCIENCETM
Citations

36
Last Week
0
Last month
0
Citations as of Sep 25, 2020

Page view(s)

212
Last Week
0
Last month
Citations as of Sep 20, 2020

Google ScholarTM

Check

Altmetric


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