Mixed coordination mechanisms for scheduling games on hierarchical machines

被引：6

作者：

Chen, Qianqian ^{[1
]}

Tan, Zhiyi ^{[1
]}

机构：

[1] Zhejiang Univ, Dept Math, Hangzhou 310027, Peoples R China

来源：

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH | 2021年 / 28卷 / 01期

基金：

中国国家自然科学基金;

关键词：

scheduling; Nash equilibrium; parallel machines; price of anarchy; PARALLEL MACHINES; ONLINE; BOUNDS; GRADE; TIME;

D O I：

10.1111/itor.12558

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we study scheduling games under mixed coordination mechanisms on hierarchical machines. The two scheduling policies involved areLG-LPTandLG-SPT, whereLG-LPT(resp.,LG-SPT) policy sequences jobs in nondecreasing order of their hierarchies, and jobs of the same hierarchy in nonincreasing (resp., nondecreasing) order of their processing times. We first show the existence of a Nash equilibrium. Then we present the price of anarchy and the price of stability for the games with social costs of minimizing the makespan and maximizing the minimum machine load. All the bounds given in this paper are tight.

引用

页码：419 / 437

页数：19

共 27 条

[1] THE PRICE OF STABILITY FOR NETWORK DESIGN WITH FAIR COST ALLOCATION [J].

Anshelevich, Elliot ;

Dasgupta, Anirban ;

Kleinberg, Jon ;

Tardos, Eva ;

Wexler, Tom ;

Roughgarden, Tim .

SIAM JOURNAL ON COMPUTING, 2008, 38 (04) :1602-1623

[2] A research survey: review of flexible job shop scheduling techniques [J].

Chaudhry, Imran Ali ;

Khan, Abid Ali .

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2016, 23 (03) :551-591

[3] Coordination mechanisms [J].

Christodoulou, George ;

Koutsoupias, Elias ;

Nanavati, Akash .

THEORETICAL COMPUTER SCIENCE, 2009, 410 (36) :3327-3336

[4]

Conway R.W., 1967, THEORY SCHEDULING

[5] THE EXACT LPT-BOUND FOR MAXIMIZING THE MINIMUM COMPLETION-TIME [J].

CSIRIK, J ;

KELLERER, H ;

WOEGINGER, G .

OPERATIONS RESEARCH LETTERS, 1992, 11 (05) :281-287

[6] A flexible job shop cell scheduling with sequence-dependent family setup times and intercellular transportation times using conic scalarization method [J].

Deliktas, Derya ;

Torkul, Orhan ;

Ustun, Ozden .

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2019, 26 (06) :2410-2431

[7] BOUNDS ON MULTIPROCESSING TIMING ANOMALIES [J].

GRAHAM, RL .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1969, 17 (02) :416-&

[8] BOUNDS FOR CERTAIN MULTIPROCESSING ANOMALIES [J].

GRAHAM, RL .

BELL SYSTEM TECHNICAL JOURNAL, 1966, 45 (09) :1563-+

[9] Coordination mechanism for selfish scheduling under a grade of service provision [J].

Guan, Li ;

Li, Jianping .

INFORMATION PROCESSING LETTERS, 2013, 113 (08) :251-254

[10]

He Y, 2003, ASIA PAC J OPER RES, V20, P31

← 1 2 3 →