三台机并行工件排序问题的改进的下界

计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (10): 26-29.

三台机并行工件排序问题的改进的下界

余国松，徐刚

南昌大学数学系，南昌 330031

出版日期:2015-05-15 发布日期:2015-05-15

Improved lower bound for online scheduling of parallel jobs on three machines

YU Guosong, XU Gang

Department of Mathematics, Nanchang University, Nanchang 330031, China

Online:2015-05-15 Published:2015-05-15

摘要/Abstract

摘要： 与经典的排序问题不同的是，并行工件排序指的是在加工某些工件时，需要多个机器同时并行工作。竞争比是评价在线算法好坏的一个重要指标，而竞争比的下界则是算法设计的一个重要参考。利用反证法，通过构造一个特殊的反例，分析了由此产生的全部9种可能的情形，建立了它们对应的9种线性规划模型，借助计算软件证明了前8种情形是不可能的，然后详细分析了第9种情形也是不可能的，从而给出了三台机并行工件排序问题的竞争比的一个改进的下界2.07。这个结果优于已知的最好的下界1.999。

关键词: 排序, 并行工件, 在线算法, 竞争比

Abstract: The online scheduling of parallel jobs on parallel machines is considered in this paper. Contrary to classical parallel machine scheduling problems, jobs may require processing on several machines in parallel. The standard metric for worst-case performance is the competitive ratio. By constructing certain adversary sequence, all the nine kinds of cases are analyzed. It is shown that 2.07 is a new lower bound on the competitive ratio of any online algorithm, which is better than the previous lower bound of 1.999.

Key words: scheduling, parallel job, online algorithm, competitive ratio

余国松，徐刚. 三台机并行工件排序问题的改进的下界[J]. 计算机工程与应用, 2015, 51(10): 26-29.

YU Guosong, XU Gang. Improved lower bound for online scheduling of parallel jobs on three machines[J]. Computer Engineering and Applications, 2015, 51(10): 26-29.

[1]	杨玮，吴莹莹，王婷. 子母式穿梭车仓储系统配置优化问题研究[J]. 计算机工程与应用, 2021, 57(4): 258-265.
[2]	李倩，蒋丽，梁昌勇. 基于模糊时间窗的多目标冷链配送优化[J]. 计算机工程与应用, 2021, 57(23): 255-262.
[3]	马震太，张晓梅，孙功星. BESIII实验软件事例级并行化研究[J]. 计算机工程与应用, 2021, 57(20): 253-262.
[4]	郭佳丽，王秋萍，王晓峰. 融合学习策略和邻域搜索的飞蛾火焰算法[J]. 计算机工程与应用, 2021, 57(12): 170-179.
[5]	肖成龙，聂紫阳，王珊珊. 基于ParetoHeu和实例化失败统计的关联启发式方法[J]. 计算机工程与应用, 2020, 56(5): 57-64.
[6]	姜金川，王冲. 基于学习自动机和用户兴趣的PageRank算法研究[J]. 计算机工程与应用, 2020, 56(3): 80-85.
[7]	张松慧，熊汉江. 融合神经网络和泊松分解的兴趣点推荐算法[J]. 计算机工程与应用, 2020, 56(21): 176-186.
[8]	段浴，曹龙汉，张治中，高尚蕾. 5G终端模拟器中信令分析技术的研究与实现[J]. 计算机工程与应用, 2020, 56(15): 106-112.
[9]	丁棋梁，石泽智，李建华. 基于分组贝叶斯排序的药物-靶标关系预测[J]. 计算机工程与应用, 2020, 56(15): 185-190.
[10]	郭皓月，樊重俊. 考虑决策者权重和核心评级的模糊排序方法[J]. 计算机工程与应用, 2020, 56(10): 163-170.
[11]	任慧. 考虑运输中断的可靠三级供应链网络设计[J]. 计算机工程与应用, 2019, 55(6): 265-270.
[12]	董骏峰，王祥，梁昌勇. 基于个体邻域的改进NSGA-II算法[J]. 计算机工程与应用, 2019, 55(5): 166-174.
[13]	田泽金，黄锐露，吕跃进. 区间粗糙数互补判断矩阵的两种一致性[J]. 计算机工程与应用, 2019, 55(24): 235-240.
[14]	严太山，文怡婷，李文彬，杨勃. 出租车合乘多目标优化方法研究[J]. 计算机工程与应用, 2019, 55(20): 222-226.
[15]	连天友，余勤. 改进KNN算法对人体身份的识别[J]. 计算机工程与应用, 2019, 55(11): 142-146.