中文

Operations Research Transactions >

2022 , Vol. 26 >Issue 3: 92 - 108

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.03.007

On the worst-case ratio of algorithm SPT for two uniform machines scheduling with minisum criteria

Expand
  • 1. School of Mathematical Science, Zhejiang University, Hangzhou 310027, Zhejiang, China
TAN Zhiyi, E-mail: tanzy@zju.edu.cn

Received date: 2022-01-31

  Online published: 2022-09-07

Supported by

National Natural Science Foundation of China(12071427)

Fold

Abstract

This paper studies the scheduling problem on two uniform machines with objective of minimizing the total completion time. The parametric worst-case ratio of the algorithm SPT is investigated. The gap between the overall upper bound and lower bound decreases from 0.430 5 to 0.014 7.

Key words： scheduling; worst-case ratio; uniform machines; price of anarchyc

Cite this article

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 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.03.007

References

1 Graham R , Lawler E , Lenstra J , et al. Optimization and approximation in deterministic sequencing and scheduling: A survey[J]. Annals of Discrete Mathematics, 1979, 5, 287- 326.
2 Bertsimas D , Farias V F , Trichakis N . The price of fairness[J]. Operations Research, 2011, 59 (1): 17- 31.
3 Garey M R , Johnson D S . Computers and Intractability: A Guide to the Theory of NP-Completeness[M]. New York: Freeman, 1978.
4 Horn W A . Minimizing average flow time with parallel machines[J]. Operations Research, 1973, 21 (3): 846- 847.
5 Bruno J , Coffman Jr E G , Sethi R . Scheduling independent tasks to reduce mean finishing time[J]. Communications of the ACM, 1974, 17 (7): 382- 387.
6 Horowitz E , Sahni S . Exact and approximate algorithms for scheduling nonidentical processors[J]. Journal of the ACM, 1976, 23 (2): 317- 327.
7 Conway R W , Maxwell W L , Miller LW . Theory of Scheduling[M]. Boston: Addison-Wesley, 1967.
8 Immorlica N , Li L , Mirrokni V S , et al. Coordination mechanisms for selfish scheduling[J]. Theoretical Computer Science, 2009, 410, 1589- 1598.
9 Koutsoupias E , Papadimitriou C H . Worst-case equilibria[J]. Computer Science Review, 2009, 3, 65- 69.
10 Hoeksma R , Uetz M . The price of anarchy for utilitarian scheduling games on related machines[J]. Discrete Optimization, 2019, 31, 29- 39.
11 Lee K , Leung J Y T , Pinedo M L . Coordination mechanisms for parallel machine scheduling[J]. European Journal of Operational Research, 2012, 220 (2): 305- 313.
12 Zhang L , Zhang Y , Du D , et al. Improved price of anarchy for machine scheduling games with coordination mechanisms[J]. Optimization Letters, 2019, 13 (4): 949- 959.
13 Hoeksma R. Price of anarchy for machine scheduling games with sum of completion times objective[D]. Enschede: University of Twente, 2010.
14 Yan Y J. Scheduling problems with utilitarian objective and related problems[D]. Hangzhou: Zhejiang University, 2017.
15 Epstein L , Noga J , Seiden S , et al. Randomized on-line scheduling on two uniform machines[J]. Journal of Scheduling, 2001, 4, 71- 92.
16 Mireault P , Orlin J B , Vohra R V . A parametric worst case analysis of the LPT heuristic for two uniform machines[J]. Operations Research, 1997, 45 (1): 116- 125.
Options
Outlines

/

〈 〉