并行任务调度的近似算法  

Approximation Algorithm for Parallel Job Scheduling

作　　者：黄金贵[1] 陈建二[2] 陈松乔[2] 

机构地区：[1]湖南师范大学计算机系,长沙410081 [2]中南大学信息工程学院计算机理论与软件研究所,长沙410083

出　　处：《计算机工程与应用》2003年第30期6-8,15,共4页Computer Engineering and Applications

基　　金：国家自然科学基金(编号:90104028);国家杰出青年自然科学基金(编号:6992801);长江学者奖励计划基金资助

摘　　要：并行任务调度不论是从理论上还是应用上近年来都倍受关注。但是目前出现的大量算法很难应用于实际,基于此,论文探讨了典型的调度问题P3｜fix｜Cmax,这类问题是强NP-难的。论文在Goemans的研究基础上,给出了一个很简单的线性算法,构造出调度性能为9/8的半规则调度,改进了Goemans的7/6的结果。Parallel task scheduling problem has become increasingly interesting,for both theoretical study and practical applications.Theoretical study of the problem has made signification progress recently,which,however,seems not yet to imply practical algorithms.This paper offers new observations and introduces new techniques for the parallel task scheduling problem P3｜fix｜Cmax.A very simple linear time algorithm with9/8-approximation ratio for constructing semi-normal scheduling is developed.

关 键 词：并行任务调度 近似算法 NP—难问题 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]