%0 Journal Article
%T 工件从大到小到达的带处理器费用的半在线调度算法
%A 蔡圣义
%A 何勇
%J 自动化学报
%P 917-921
%D 2003
%X ？对大多数调度问题来说,处理器集往往是事先给定的,而且在算法进行过程中,它是不变的.Imreh和Noga第一次提出了在调度中考虑处理器有费用的模型.他们研究了所谓的ListModel问题,给出了竞争比为1.618的在线算法,同时证明了任意在线算法的竞争比至少是4/3.该文研究ListModel问题的一个半在线情形,即假设工件是从大到小到达的,给出一个竞争比为3/2的半在线算法.同时证明对该问题的这一半在线情形,任意半在线算法的竞争比至少是4/3.
%K 半在线
%K 算法
%K 竞争比
%K 调度
%K 处理器费用
%U http://www.aas.net.cn/CN/abstract/abstract16430.shtml