两台自私型机器上自私工件排序的PoA紧界

doi:10.15960/j.cnki.issn.1007-6093.2022.03.008

Operations Research Transactions ›› 2022, Vol. 26 ›› Issue (3): 109-119.doi: 10.15960/j.cnki.issn.1007-6093.2022.03.008

Previous Articles Next Articles

Tight Price of Anarchy for selfish task scheduling on two selfish machines

Xiayan CHENG¹, Yin HE², Congcong ZHAO², Rongheng LI²^,*()

1. Hunan First Normal University, Changsha 410205, Hunan, China
2. Key Laboratory of High Performance Computing and Stochastic Information Processing, Department of Mathematics, Hunan Normal University, Changsha 410081, Hunan, China

Received:2022-01-28 Online:2022-09-15 Published:2022-09-07
Contact: Rongheng LI E-mail:lirongheng@hunnu.edu.cn
About author:LI Rongheng, E-mail: lirongheng@hunnu.edu.cn
Supported by:
National Natural Science Foundation of China(11471110);Scientific Research Foundation Grant of Education Department of Hunan(16A126)

Abstract

Abstract:

In this paper, we study selfish task scheduling on two selfish machines with respect to Dual Equilibrium, called Dual Equilibrium Schedule. For any job list $L$, we show that the Price of Anarchy of Dual Equilibrium Schedule is $\frac{8}{7}$. If the job sizes are constrained in $[1, r](r\ge1)$, this research states that the tight PoA(Price of Anarchy) of Dual Equilibrium Schedule is a piecewise linear function of $r$.

Key words: selfish machines, scheduling, tight bound, Nash equilibrium

CLC Number:

O223

Xiayan CHENG, Yin HE, Congcong ZHAO, Rongheng LI. Tight Price of Anarchy for selfish task scheduling on two selfish machines[J]. Operations Research Transactions, 2022, 26(3): 109-119.

Figures/Tables 1

References 12

1	Nisan N , Ronen A . Algorithmic mechanism design[J]. Games and Economic Behavior, 2001, 35, 166- 196. doi: 10.1006/game.1999.0790
2	Koutsoupias E, Papadimitriou C. Wrost-case equlibria[C]//Proceeding of the 16th International Symposium on Theoretical Aspects of Computer Science. Berlin Heidelberg: Springer-Verlag, 1999: 404-413.
3	Caragiannis I , Flammini M , Kaklamanis C , et al. Tight Bounds for Selfish and Greedy Load Balancing[J]. Algorithmica, 2011, 61 (3): 606- 637. doi: 10.1007/s00453-010-9427-8
4	Czumaj A , Krysta P , Vöcking B . Selfish traffic allocation for server farms[J]. SIAM Journal on Computing, 2010, 39 (5): 1957- 1987. doi: 10.1137/070693862
5	Chen B , Gürel S . Efficiency analysis of load balancing games with and without activation costs[J]. Journal of Scheduling, 2012, 15 (2): 157- 164. doi: 10.1007/s10951-011-0247-8
6	Xie F , Xu Z , Zhang Y , et al. Scheduling games on uniform machines with activation cost[J]. Theoretical Computer Science, 2015, 580, 28- 35. doi: 10.1016/j.tcs.2015.02.023
7	Hoeksma R , Uetz M . The price of anarchy for utilitarian scheduling games on related machines[J]. Discrete Optimization, 2019, 31, 29- 39. doi: 10.1016/j.disopt.2018.08.001
8	Xie F , Zhang Y , Bai Q , et al. Inefficiency analysis of the scheduling game on limited identical machines with activation costs[J]. Information Processing Letters, 2016, 116 (4): 316- 320. doi: 10.1016/j.ipl.2015.10.006
9	Berenbrink P , Friedetzky T , Goldberg L A , et al. Distributed selfish load balancing[J]. SIAM Journal on Computing, 2007, 37 (4): 1163- 1181. doi: 10.1137/060660345
10	Angel E , Bampis E , Pascual F , et al. On truthfulness and approximation for scheduling selfish tasks[J]. Journal of Scheduling, 2009, 12 (5): 437- 445. doi: 10.1007/s10951-009-0118-8
11	Chen X , Hu X , Ma W , et al. Reducing price of anarchy of selfish task allocation with more selfishness[J]. Theoretical Computer Science, 2013, 507 (7): 17- 33.
12	Cheng X , Li R , Zhou Y . Tighter price of anarchy for selfish task allocation on selfish machines[J]. Journal of Combinatorial Optimization, 2020, doi: 10.1007/s10878-020-00556-6

[1]	Dong WANG, Ganggang LI, Wenchang LUO. Approximation algorithm for mixed batch scheduling on identical machines for jobs with arbitrary sizes [J]. Operations Research Transactions, 2022, 26(3): 133-142.
[2]	Ping ZHOU, Min JI, Yiwei JIANG. LPT heuristic for parallel-machine scheduling of maximizing total early work [J]. Operations Research Transactions, 2022, 26(3): 151-156.
[3]	Mingyang GONG, Zhiyi TAN, Yujie YAN. On the worst-case ratio of algorithm SPT for two uniform machines scheduling with minisum criteria [J]. Operations Research Transactions, 2022, 26(3): 92-108.
[4]	Wenjie LI, Yujing LI, Hailing LIU. Research on the single-machine online schedule in which the jobs' release times and processing times are agreeable [J]. Operations Research Transactions, 2022, 26(2): 55-63.
[5]	Chunyan BI, Long WAN, Wenchang LUO. Approximation algorithm for uniform parallel machine scheduling with release dates and job rejection [J]. Operations Research Transactions, 2022, 26(2): 73-82.
[6]	Yinling WANG, Xin HAN, Xinxin SHAO. Online single machine scheduling problem with transportation [J]. Operations Research Transactions, 2022, 26(1): 125-133.
[7]	Libo WANG, Wenhua LI, Dan YU. Online scheduling on single batch machine with variable lookahead interval [J]. Operations Research Transactions, 2022, 26(1): 134-140.
[8]	Chen XU, Yinfeng XU, Feifeng ZHENG. Multitasking scheduling considering part jobs uninterrupted assignment [J]. Operations Research Transactions, 2021, 25(4): 91-100.
[9]	CHEN Feng. Research and application of operations research on intelligent scheduling decision support system for automotive outbound logistics [J]. Operations Research Transactions, 2021, 25(3): 37-73.
[10]	Shanshan YU, Miaomiao JIN, Wenchang LUO. Approximation scheme for rescheduling on a single machine with job delay and rejection [J]. Operations Research Transactions, 2021, 25(2): 104-114.
[11]	Yindong SHEN, Zhuang QIAN, Yuanyuan LI. A survey on driver scheduling in public transportation [J]. Operations Research Transactions, 2021, 25(1): 1-16.
[12]	HUANG Jidan, ZHENG Feifeng, XU Yingfeng, LIU Ming. Parallel machine scheduling with deteriorating installation times in the MapReduce system [J]. Operations Research Transactions, 2020, 24(4): 93-106.
[13]	ZHANG Yuzhong, LI Shuguang. Scheduling with tree-hierarchical processing set restrictions [J]. Operations Research Transactions, 2020, 24(4): 107-112.
[14]	JIANG Xiaoyan, SHUAI Tianping. Online MapReduce scheduling on two uniform machines [J]. Operations Research Transactions, 2020, 24(3): 57-66.
[15]	LU Shuxiang, Lü Changhong, QIN Tao. An algorithm based on makespan lower bound for quay crane schedule problem in container terminals [J]. Operations Research Transactions, 2020, 24(3): 67-76.

Tight Price of Anarchy for selfish task scheduling on two selfish machines

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 1

References 12

Related Articles 15

Recommended Articles

Metrics

Comments