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

来源：

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA | 2025年

基金：

中国国家自然科学基金;

关键词：

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

← 1 2 →