三台等级机器上带重排的半在线问题

计算机工程与科学 ›› 2022, Vol. 44 ›› Issue (06): 1126-1132.

三台等级机器上带重排的半在线问题

赵姝,肖满,李伟东

（云南大学数学与统计学院，云南昆明 650500）

收稿日期:2021-10-11 修回日期:2021-12-17 接受日期:2022-06-25 出版日期:2022-06-25 发布日期:2022-06-17
基金资助:
国家自然科学基金（12071417）

Semi-online algorithms for hierarchical scheduling on three machines with reassignment

ZHAO Shu,XIAO Man,LI Wei-dong

(School of Mathematics and Statistics,Yunnan University,Kunming 650500,China)

Received:2021-10-11 Revised:2021-12-17 Accepted:2022-06-25 Online:2022-06-25 Published:2022-06-17

摘要/Abstract

摘要： 研究了3台机上带2种等级的重排问题，当所有工件都被分配之后，在等级约束下，可以重排一台机器上的最后一个工件，目标是最小化最大完工时间。3台机上带2种等级分为2种情形:第1种是有1台机器的等级为1，另2台机器的等级为2;第2种是2台机器的等级为1，另1台机器的等级为2。针对第1种情形给出了一个竞争比下界为3/2，并提出了一个竞争比至多为5/3的在线算法；针对第2种情形给出了一个竞争比下界为3/2，并提出了一个竞争比至多为12/7的在线算法。

关键词: 等级, 重排, 竞争比, 半在线算法

Abstract: This paper studies the rearrangement problem on three machines with two hierarchies. Under the constraints of hierarchy, after all jobs have been assigned, the last job on arbitrary machine can be rearranged, and the objective is to minimize the maximum machine load. There are two cases on three machines with two hierarchies. Case 1: When one machines hierarchy is 1 and the other two machines hierarchy is 2, a low bound of competitive ratio 3/2 is given and an online algorithm with the competitive ratio of at most 5/3 is proposed. Case 2: When one machine's hierarchys hierarchy is 2 and the other two machines hierarchy is 1, a low bound of competitive ratio 3/2 is given and an online algorithm with the competitive ratio of at most 12/7 is proposed.

Key words: hierarchy, reassignment, competitive ratio, semi-online algorithm.

赵姝, 肖满, 李伟东. 三台等级机器上带重排的半在线问题[J]. 计算机工程与科学, 2022, 44(06): 1126-1132.

ZHAO Shu, XIAO Man, LI Wei-dong. Semi-online algorithms for hierarchical scheduling on three machines with reassignment[J]. Computer Engineering & Science, 2022, 44(06): 1126-1132.

参考文献［24］

［1］	Hwang H C,Chang S Y,Lee K.Parallel machine scheduling under a grade of service provision［J］.Computers and Operations Research,2004,31 (12):2055-2061.
［2］	Wu Y,Ji M,Yang Q F.Optimal semi-online scheduling algorithm on two parallel identical machines under a grade of service provision［J］.International Journal of Production Economics,2011,135(1):367-371.
［3］	Zhang A, Jiang Y W,Tan Z Y.Online parallel machines scheduling with two hierarchies［J］.Theoretical Computer Science,2009,410(38):3597-3605.
［4］	Zhang A,Jiang Y W,Fan L D,et al.Optimal online algorithms on two hierarchical machines with tightly-grouped processing times［J］.Journal of Combinatorial Optimization,2015,29(4):781-795.
［5］	Cai S, Liu K.Heuristics for online scheduling on identical parallel machines with two GoS levels［J］.Journal of Systems Science & Complexity,2019,32(4):1180-1193.
［6］	Albers S.On randomized online scheduling［C］∥Proc of the 34th ACM Symposium on Theory of Computing,2002:134-143.
［7］	Rudin J F, John F,Chandrasekaran R.Improved bounds for the online scheduling problem［J］.SIAM Journal on Computing,2003,32(3):717-735.
［8］	Azar Y, Regev O.On-line bin-stretching［J］.Theoretical Computer Science,2001,268(1):17-41.
［9］	Cao Q,Liu Z H.Semi-online scheduling with known maximum job size on two uniform machines［J］.Journal of Combinatorial Optimization,2010,20(4):369-384.
［10］	Kellerer H,Kovov V,Speranza M R,et al.Semi on-line algorithms for the partition problem［J］.Operations Research Letters,1997,21(5):235-242.
［11］	Xiao M, Ding L, Zhao S, et al. Semi-online algorithms for hierarchical scheduling on three parallel machines with a buffer size of 1［C］∥Proc of 38th National Conference of Theoretical Computer Science,2020:47-56.
［12］	Park J,Chang S Y,Lee K.Online and semi-online sched- uling of two machines under a grade of service provision［J］.Operations Research Letters,2006,34(6):692-696.
［13］	Chen X,Ding N,Dósa G,et al.Online hierarchical sched- uling on two machines with known total size of low- hierarchy jobs［J］.International Journal of Computer Mathematics,2015,92(5):873-881.
［14］	Cao Q,Liu Z H,Cheng T C E.Semi-online scheduling with known partial information about job sizes on two identical machines［J］.Theoretical Computer Science,2011,412(29):3731-3737.
［15］	Xiao Man,Ding Lu,Zhang Yi.Semi-online algorithms for hierarchical scheduling on three parallel machines［J］.Computer Engineering & Science,2020,42 (12):2252-2258.(in Chinese)
［16］	Wu Y, Cheng T C E, Ji M.Optimal algorithms for semi- online machine covering on two hierarchical machines［J］.Theoretical Computer Science,2014,531(6):37-46.
［17］	Dósa G,Wang Y X,Han X,et al.Online scheduling with rearrangement on two related machines［J］.Theoretical Computer Science,2011,412 (8-10):642-653.
［18］	Sanders P,Sivadasan N,Skutella M.Online scheduling with bounded migration［J］.Mathematics of Operations Research,2009,34(2):481-498.
［19］	Tan Z Y,Yu S H.Online scheduling with reassignment［J］.Operations Research Letters,2007,36(2):250-254.
［20］	Min X,Liu J,Wang Y Q.Optimal semi-online algorithms for scheduling problems with reassignment on two identical machines［J］.Information Processing Letters,2011,111(9):423-428.
［21］	Wang Y X,Benko A,Chen X,et al.Online scheduling with one rearrangement at the end:Revisited［J］.Information Processing Letters,2012,112(16):641-645.
［22］	Chen X, Xu Z Z,Dósa G,et al.Semi-online hierarchical scheduling problems with buffer or rearrangements ［J］.Information Processing Letters,2013,113(4):127-131.
［23］	Qi X L, Yuan J J. Semi-online hierarchical scheduling for lp-norm load balancing with buffer or rearrangements［J］.A Quarterly Journal of Operations Research，2017，15(3):265-276.
［24］	Min Xiao. Optimal semi-online algorithm for covering pro- blem with reassignment on two identical machines［J］.Journal of Jiaxing University,2012,24 (3):35-37.(in Chinese)
	附中文参考文献：
［15］	肖满, 丁璐,张怡.带两个服务等级的3台机半在线算法［J］.计算机工程与科学,2020,42(12):2252-2258.
［24］	闵啸.两台可重排平行机覆盖问题的最优在线算法［J］.嘉兴学院学报,2012,24(3):35-37.

[1]	王平, 李彬, 张彤, 王佳. 基于可逆神经网络的图像超分辨率重建算法[J]. 计算机工程与科学, 2023, 45(03): 478-488.
[2]	张勇, 张曦, 万云博, 何先耀, 赵钟, 卢宇彤. 非结构有限体积CFD计算的网格重排序优化[J]. 计算机工程与科学, 2022, 44(10): 1721-1729.
[3]	肖满, 丁璐, 张怡. 带两个服务等级的3台机半在线算法[J]. 计算机工程与科学, 2020, 42(12): 2252-2258.
[4]	彭晋韬1，杨章1,2,刘青凯1,2,张倩1. 结合通信重排和消息合并的通信调度方法研究[J]. 计算机工程与科学, 2020, 42(02): 191-196.
[5]	周栋，赵文玉，伍璇，刘建勋. 个性化跨语言信息检索中结果重排序研究[J]. 计算机工程与科学, 2017, 39(10): 1922-1929.
[6]	李军,孙辉. 准序化供货模式下的混装线重排序[J]. J4, 2016, 38(03): 595-602.
[7]	申蔓蔓1，乐晓波1，周恺卿2. 一种新的基于直觉模糊Petri网的模糊推理算法[J]. J4, 2015, 37(02): 354-358.
[8]	王明岳[1,2]. 目标可移动的直线搜索问题的在线算法研究[J]. J4, 2008, 30(12): 60-62.