工件从大到小到达的带处理器费用的半在线调度算法  

Quasi-Online Algorithm for Scheduling Non-Increasing Processing-Time Jobs with Processor Cost

作　　者：蔡圣义[1] 何勇[1] 

机构地区：[1]浙江大学数学系

出　　处：《自动化学报》2003年第6期917-921,共5页Acta Automatica Sinica

基　　金：国家"973"重点基础研究专项经费 (G19980 30 4 0 1);国家自然科学基金 (10 2 71110 );高校优秀青年教师教学科研奖励计划资助项目;温州师范学院课题经费 (2 0 0 1Z0 6 )~~

摘　　要：对大多数调度问题来说 ,处理器集往往是事先给定的 ,而且在算法进行过程中 ,它是不变的 .Imreh和Noga第一次提出了在调度中考虑处理器有费用的模型 .他们研究了所谓的ListModel问题 ,给出了竞争比为 1.6 18的在线算法 ,同时证明了任意在线算法的竞争比至少是4 / 3.该文研究ListModel问题的一个半在线情形 ,即假设工件是从大到小到达的 ,给出一个竞争比为 3/ 2的半在线算法 .同时证明对该问题的这一半在线情形 ,任意半在线算法的竞争比至少是 4 / 3.For most scheduling problems the set of processors is fixed initially and remains unchanged for the duration of the problem. Imreh and Noga recently proposed adding the concept of processor cost to the scheduling problem and considered the so-called List Model problem. An online algorithm of a competitive ratio 1.618 was given with a lower bound of 4/3. In this paper, we investigate a quasi-online version of the List Model by supposing that jobs arrive in the non-increasing order of their processing times. We present a quasi-online algorithm with the competitive ratio being 3/2 and the lower bound 4/3.

关 键 词：半在线调度算法 处理器 ListModel问题 目标函数值 

分 类 号：TP11[自动化与计算机技术—控制理论与控制工程]