Multi-agent Scheduling to Minimize Total Completion Times

被引:0
作者
Chen, Ru-Bing [1 ]
Gao, Yuan [1 ]
Yuan, Jin-Jiang [1 ]
Zhao, Qiu-Lan [2 ]
机构
[1] Zhengzhou Univ, Sch Math & Stat, Zhengzhou 450001, Henan, Peoples R China
[2] Nanjing Univ, Sch Math, Nanjing 210093, Jiangsu, Peoples R China
基金
中国国家自然科学基金;
关键词
Multi-agent scheduling; Single machine; Total completion time; Unary NP-hardness; Polynomial-time algorithm; SINGLE-MACHINE;
D O I
10.1007/s40305-025-00598-9
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
We consider a multi-agent scheduling problem on a single machine with k competing agents. The objective is to minimize the total completion time of first agent, subject to the condition that the total completion time of any other agent is bounded. When k is arbitrary, the exact complexity of this problem is open. We show the unary NP-hardness of this problem and present a polynomial-time algorithm when all the jobs of first agent have deadlines and any other agent has only one job.
引用
收藏
页数:13
相关论文
共 12 条
[1]   Scheduling problems with two competing agents [J].
Agnetis, A ;
Mirchandani, PB ;
Pacciarelli, D ;
Pacifici, A .
OPERATIONS RESEARCH, 2004, 52 (02) :229-242
[2]  
Agnetis A., 2014, Multiagent Scheduling: Models and Algorithms, DOI DOI 10.1007/978-3-642-41880-8
[3]   Multi-agent single machine scheduling [J].
Agnetis, Alessandro ;
Pacciarelli, Dario ;
Pacifici, Andrea .
ANNALS OF OPERATIONS RESEARCH, 2007, 150 (01) :3-15
[4]   A multiple-criterion model for machine scheduling [J].
Baker, KR ;
Smith, JC .
JOURNAL OF SCHEDULING, 2003, 6 (01) :7-16
[5]   Multi-agent scheduling on a single machine with max-form criteria [J].
Cheng, T. C. E. ;
Ng, C. T. ;
Yuan, 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 [J].
Cheng, T. C. E. ;
Ng, C. T. ;
Yuan, J. J. .
THEORETICAL COMPUTER SCIENCE, 2006, 362 (1-3) :273-281
[7]  
Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness
[8]  
Graham R. L., 1979, Discrete Optimisation, P287
[9]   Complexity analyses for multi-agent scheduling problems with a global agent and equal length jobs [J].
Sadi, F. ;
Soukhal, A. .
DISCRETE OPTIMIZATION, 2017, 23 :93-104
[10]  
Smith W.E., 1956, NAV RES LOGIST Q, V3, P59, DOI DOI 10.1002/NAV.3800030106