两台同类机排序问题SPT算法的最坏情况比

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

运筹学学报 ›› 2022, Vol. 26 ›› Issue (3): 92-108.doi: 10.15960/j.cnki.issn.1007-6093.2022.03.007

两台同类机排序问题SPT算法的最坏情况比

龚铭炀¹, 谈之奕¹^,*(), 严羽洁¹

1. 浙江大学数学科学学院, 浙江杭州 310027

收稿日期:2022-01-31 出版日期:2022-09-15 发布日期:2022-09-07
通讯作者: 谈之奕 E-mail:tanzy@zju.edu.cn

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

Mingyang GONG¹, Zhiyi TAN¹^,*(), Yujie YAN¹

1. School of Mathematical Science, Zhejiang University, Hangzhou 310027, Zhejiang, China

Received:2022-01-31 Online:2022-09-15 Published:2022-09-07
Contact: Zhiyi TAN E-mail:tanzy@zju.edu.cn
About author:TAN Zhiyi, E-mail: tanzy@zju.edu.cn
Supported by:
National Natural Science Foundation of China(12071427)

摘要/Abstract

摘要：

本文研究以工件总完工时间为目标函数的两台同类机排序问题, 给出了SPT算法以两台机器速度比为参数的最坏情况比, 使该算法的常数最坏情况比上界与下界的差距由0.430 5减小到0.014 7。

关键词: 排序, 最坏情况比, 同类机, 混乱代价

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

中图分类号:

龚铭炀, 谈之奕, 严羽洁. 两台同类机排序问题SPT算法的最坏情况比[J]. 运筹学学报, 2022, 26(3): 92-108.

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.

图/表 1

参考文献 16

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. doi: 10.1287/opre.1100.0865
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. doi: 10.1287/opre.21.3.846
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. doi: 10.1145/361011.361064
6	Horowitz E , Sahni S . Exact and approximate algorithms for scheduling nonidentical processors[J]. Journal of the ACM, 1976, 23 (2): 317- 327. doi: 10.1145/321941.321951
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. doi: 10.1016/j.tcs.2008.12.032
9	Koutsoupias E , Papadimitriou C H . Worst-case equilibria[J]. Computer Science Review, 2009, 3, 65- 69. doi: 10.1016/j.cosrev.2009.04.003
10	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
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. doi: 10.1016/j.ejor.2012.02.001
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. doi: 10.1007/s11590-018-1285-3
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.

[1]	成夏炎, 何滢, 赵聪聪, 李荣珩. 两台自私型机器上自私工件排序的PoA紧界[J]. 运筹学学报, 2022, 26(3): 109-119.
[2]	王冬, 李刚刚, 罗文昌. 工件具有任意尺寸的混合分批平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(3): 133-142.
[3]	周萍, 季敏, 蒋义伟. 极大化提前完工总量平行机排序问题的LPT算法[J]. 运筹学学报, 2022, 26(3): 151-156.
[4]	李文杰, 李钰晶, 刘海玲. 工件的释放时间和加工时间具有一致性的单机在线排序问题研究[J]. 运筹学学报, 2022, 26(2): 55-63.
[5]	毕春燕, 万龙, 罗文昌. 工件有到达时间及可拒绝下的同类平行机排序问题的近似算法[J]. 运筹学学报, 2022, 26(2): 73-82.
[6]	王利博, 李文华, 余丹. 单机上带有可变前瞻区间的分批在线排序问题[J]. 运筹学学报, 2022, 26(1): 134-140.
[7]	余山杉, 金苗苗, 罗文昌. 工件延误和可拒绝下的单机重新排序问题的近似方案[J]. 运筹学学报, 2021, 25(2): 104-114.
[8]	姜晓燕, 帅天平. 两台恒速机上的MapReduce排序算法研究[J]. 运筹学学报, 2020, 24(3): 57-66.
[9]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[10]	陈如冰, 原晋江. 工件具有加工位置上限最小化加权总误工量的单机排序问题[J]. 运筹学学报, 2020, 24(2): 131-144.
[11]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[12]	苟燕, 戴秦, 张新功. 具有时间与位置相关的两类平行机排序问题[J]. 运筹学学报, 2019, 23(4): 86-94.
[13]	李刚刚, 鲁习文. 目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法[J]. 运筹学学报, 2019, 23(4): 95-104.
[14]	李文华, 翟威娜, 柴幸, 高超. 具有两个不相容工件族单位工件的有界分批在线排序问题[J]. 运筹学学报, 2019, 23(4): 105-110.
[15]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.

两台同类机排序问题SPT算法的最坏情况比

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 1

参考文献 16

相关文章 15

编辑推荐

Metrics

本文评价