计算机工程与科学

作者：赵姝, 肖满, 李伟东

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

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

基金：国家自然科学基金（12071417）

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

来源：2022年第6期

《计算机工程与科学》期刊编辑部

查看计算机工程与科学杂志2022年第6期