线性网络上分布式任务调度算法

Distributed Job Scheduling in Linear Networks

针对一种已有的分布式计算理论模型 (单位长度的任务由处理器独立产生 ,没有全局控制 ,彼此通信需要花费时间 ) ,研究了在线性网络上的任务有效调度问题 通过考虑算法中任务处理时间和通信时间之间的平衡 ,给出了一个近似比为 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