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

摘要：

研究了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的在线算法.

关键词：等级、重排、竞争比、半在线算法

所属期刊栏目：44

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金12071417

在线出版日期：2022-06-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：1126-1132