An algorithm for multi-agent scheduling to minimize the makespan on m parallel machines

被引：13

作者：

Gu, Manzhan ^{[1
]}

Gu, Jinwei ^{[2
]}

Lu, Xiwen ^{[3
]}

机构：

[1] Shanghai Univ Finance & Econ, Sch Math, Inst Sci Computat & Financial Data Anal, Shanghai 200433, Peoples R China

[2] Shanghai Univ Elect Power, Sch Econ & Management, Shanghai 200090, Peoples R China

[3] East China Univ Sci & Technol, Sch Sci, Shanghai 200237, Peoples R China

来源：

JOURNAL OF SCHEDULING | 2018年 / 21卷 / 05期

基金：

中国国家自然科学基金;

关键词：

Scheduling; Multi-agent; LPT; Makespan; 2 COMPETING AGENTS; SINGLE-MACHINE;

D O I：

10.1007/s10951-017-0546-9

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

This paper considers a multi-agent scheduling problem, in which each agent has a set of non-preemptive jobs, and jobs of all agents are to be processed on m identical parallel machines. The objective is to find a schedule to minimize the makespan of each agent. For an agent, the definition of a point is introduced, based on which an approximation algorithm is proposed for the problem. In the obtained schedule, the agent with the ith smallest a point value is the ith completed agent, and the agent's completion time is at most i+ times its minimummakespan. Finally, we show the performance analysis is tight.

引用

页码：483 / 492

页数：10

共 13 条

[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 SCHEDULIN

[3] Multi-agent single machine scheduling [J].

Agnetis, Alessandro ;

Pacciarelli, Dario ;

Pacifici, Andrea .

ANNALS OF OPERATIONS RESEARCH, 2007, 150 (01) :3-15

[4] A Lagrangian approach to single-machine scheduling problems with two competing agents [J].

Agnetis, Alessandro ;

de Pascale, Gianluca ;

Pacciarelli, Dario .

JOURNAL OF SCHEDULING, 2009, 12 (04) :401-415

[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] Bounded parallel-batching scheduling with two competing agents [J].

Fan, B. Q. ;

Cheng, T. C. E. ;

Li, S. S. ;

Feng, Q. .

JOURNAL OF SCHEDULING, 2013, 16 (03) :261-271

[8] Approximation algorithms for multi-agent scheduling to minimize total weighted completion time [J].

Lee, Kangbok ;

Choi, Byung-Cheon ;

Leung, Joseph Y. -T. ;

Pinedo, Michael L. .

INFORMATION PROCESSING LETTERS, 2009, 109 (16) :913-917

[9] Competitive Two-Agent Scheduling and Its Applications [J].

Leung, Joseph Y. -T. ;

Pinedo, Michael ;

Wan, Guohua .

OPERATIONS RESEARCH, 2010, 58 (02) :458-469

[10] Unbounded parallel-batching scheduling with two competitive agents [J].

Li, Shisheng ;

Yuan, Jinjiang .

JOURNAL OF SCHEDULING, 2012, 15 (05) :629-640

← 1 2 →