作　　者： ; ; (陈辰）; (许舸）; (张铮）;

机构地区： 国家高性能计算机工程技术研究中心

出　　处： 《计算机研究与发展》 2003年第10期1476-1481,共6页

摘　　要： 针对一种已有的分布式计算理论模型 (单位长度的任务由处理器独立产生 ,没有全局控制 ,彼此通信需要花费时间 ) ,研究了在线性网络上的任务有效调度问题 通过考虑算法中任务处理时间和通信时间之间的平衡 ,给出了一个近似比为 5 88的分布式算法 ,该算法无需全局信息 ,且处理策略简单 对该问题的近似比下界也做了研究 ,证明了该问题不存在近似比小于 1 This paper aims at an existing distributed computing theoretical model, in which processors generate unit jobs independently and there is no global control and the communications of processors should spend time The job scheduling problem in linear networks is studied The balances of job processing and communications of processors are considered and a distributed algorithm is proposed without any global information and complicated operation, which has a performance ratio no more than 5 88 The lower bound is also studied It shows that there is no distributed algorithm whose approximation ratio is less than 1 16

关 键 词： 分布式算法 调度问题 线性网络 近似比 下界

领　　域： [自动化与计算机技术] [自动化与计算机技术]