Two-agent scheduling to minimize the total cost

被引：46

作者：

Nong, Q. Q. ^{[2
]}

Cheng, T. C. E. ^{[1
]}

Ng, C. T. ^{[1
]}

机构：

[1] Hong Kong Polytech Univ, Dept Logist & Maritime Studies, Kowloon, Hong Kong, Peoples R China

[2] Ocean Univ China, Coll Math Sci, Qingdao 266100, Shandong, Peoples R China

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 2011年 / 215卷 / 01期

基金：

中国国家自然科学基金;

关键词：

Scheduling; Multi-agent; Approximation algorithm; Polynomial time approximation scheme; SINGLE-MACHINE;

D O I：

10.1016/j.ejor.2011.05.041

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

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. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：39 / 44

页数：6

共 12 条

[1] Afrati F., 1999, 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), P32, DOI 10.1109/SFFCS.1999.814574
[2] Scheduling problems with two competing agents
Agnetis, A
Mirchandani, PB
Pacciarelli, D
Pacifici, A
[J]. OPERATIONS RESEARCH, 2004, 52 (02) : 229 - 242
[3] Multi-agent single machine scheduling
Agnetis, Alessandro
Pacciarelli, Dario
Pacifici, Andrea
[J]. ANNALS OF OPERATIONS RESEARCH, 2007, 150 (01) : 3 - 15
[4] A multiple-criterion model for machine scheduling
Baker, KR
Smith, JC
[J]. JOURNAL OF SCHEDULING, 2003, 6 (01) : 7 - 16
[5] Multi-agent scheduling on a single machine with max-form criteria
Cheng, T. C. E.
Ng, C. T.
Yuan, J. J.
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 188 (02) : 603 - 609
[6] Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs
Cheng, T. C. E.
Ng, C. T.
Yuan, J. J.
[J]. THEORETICAL COMPUTER SCIENCE, 2006, 362 (1-3) : 273 - 281
[7] SEQUENCING GAMES
CURIEL, I
PEDERZOLI, G
TIJS, S
[J]. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1989, 40 (03) : 344 - 351
[8] [冯琪 Feng Qi], 2007, [运筹学学报, OR Transactions], V11, P121
[9] Hamers H., 1995, Mathematical Programming, V70, P1
[10] Competitive Two-Agent Scheduling and Its Applications
Leung, Joseph Y. -T.
Pinedo, Michael
Wan, Guohua
[J]. OPERATIONS RESEARCH, 2010, 58 (02) : 458 - 469

← 1 2 →