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

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

对大多数调度问题来说 ,处理器集往往是事先给定的 ,而且在算法进行过程中 ,它是不变的 .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.