任意处理时间的多处理机任务调度近似算法

doi:10.3778/j.issn.1002-8331.2008.33.002

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (33): 7-9.DOI: 10.3778/j.issn.1002-8331.2008.33.002

任意处理时间的多处理机任务调度近似算法

黄金贵

湖南师范大学计算机教学部，长沙 410083

收稿日期:2008-07-28 修回日期:2008-08-21 出版日期:2008-11-21 发布日期:2008-11-21
通讯作者: 黄金贵

Approximation algorithm on multi-processor job scheduling

HUANG Jin-gui

Department of Computer Teaching，Hunan Normal University，Changsha 410083，China

Received:2008-07-28 Revised:2008-08-21 Online:2008-11-21 Published:2008-11-21
Contact: HUANG Jin-gui

摘要/Abstract

摘要： 研究多处理机任务调度模型P_mfixC_max，即在m个处理机系统中调度n个多处理机任务，每个任务指派到所需一组处理机上不可剥夺地执行。该问题应用广泛但早已证明为NP难问题，而且也不存在常数近似算法。在E.Bampis等人提出的Split-Round技术基础上，提出了该问题的一个改进的多项式时间近似算法，并从理论上证明了该算法在最坏情况下的近似比为2(2m)^-2，优于E.Bampis等人给出的3m^-2的结果。

关键词: 多处理机任务调度, 近似算法, NP难问题

Abstract: This paper studies the problem of scheduling a set of n independent multiprocessor jobs with prespecified processor allocation on a set of identical processors in order to minimize the makespan.The problem P_mfixC_max is proved to be NP-hard and cannot be approximated within a constant factor unless P=NP.Recently，E.Bampis et al. have given a 3m^-2-approximation algorithm for this problem by using the split-round technique.This paper proposes a 2(2m^)-2-approximation algorithm for this problem based on the improvement of the split-round algorithm.

Key words: multiprocessor job scheduling, approximation algorithm, NP-hard problem

黄金贵. 任意处理时间的多处理机任务调度近似算法[J]. 计算机工程与应用, 2008, 44(33): 7-9.

HUANG Jin-gui. Approximation algorithm on multi-processor job scheduling[J]. Computer Engineering and Applications, 2008, 44(33): 7-9.

[1]	曾维新1，赵翔1，2，冯滔1，唐九阳1，2. 面向领域的命名实体消歧方法改进研究[J]. 计算机工程与应用, 2018, 54(17): 126-134.
[2]	蒋小娟1，张安1，陈永1，陈光亭2. 内部节点受限的最小生成树问题算法研究[J]. 计算机工程与应用, 2017, 53(10): 35-37.
[3]	聂文艳1，王仲根2. 应用ACA算法快速分析导体目标电磁散射特性[J]. 计算机工程与应用, 2015, 51(4): 232-234.
[4]	王继强. 集合覆盖问题的模型与算法[J]. 计算机工程与应用, 2013, 49(17): 15-17.
[5]	纪鹏宇1，谢红1，赵蕴龙2. 一种中继节点上的网络-信道编码联合设计方案[J]. 计算机工程与应用, 2012, 48(34): 102-106.
[6]	王继强. 基于TSP的图的路包装问题的算法研究[J]. 计算机工程与应用, 2011, 47(21): 220-222.
[7]	何晓琼，陈冲，李荣珩. 工厂地址集中的k-种产品选址问题的近似算法[J]. 计算机工程与应用, 2010, 46(8): 238-241.
[8]	高文宇. 有向图连通支配集求解算法[J]. 计算机工程与应用, 2010, 46(21): 9-13.
[9]	黄金贵. 具有优先链约束的网格作业多资源调度问题[J]. 计算机工程与应用, 2009, 45(6): 48-51.
[10]	黄金贵. 应用团划分方法改进多处理机任务近似调度[J]. 计算机工程与应用, 2009, 45(4): 4-8.
[11]	许金星，吴素萍. 旅行售货员问题的图论近似算法[J]. 计算机工程与应用, 2009, 45(32): 51-52.
[12]	易斌¹,李荣珩². 一类多产品选址算法的若干进展[J]. 计算机工程与应用, 2009, 45(17): 221-224.
[13]	沈庆涛,张振宇. 高效的求解TSP问题的近似算法[J]. 计算机工程与应用, 2008, 44(35): 46-49.
[14]	黄金贵. 单位处理时间的多处理机任务调度近似算法[J]. 计算机工程与应用, 2008, 44(32): 26-28.
[15]	李勇,蒋建国,夏娜. 一种求解单任务Agent联盟生成的近似算法[J]. 计算机工程与应用, 2008, 44(2): 29-31.

任意处理时间的多处理机任务调度近似算法

Approximation algorithm on multi-processor job scheduling

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics