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

对大多数调度问题来说 ,处理器集往往是事先给定的 ,而且在算法进行过程中 ,它是不变的 .Imreh和Noga第一次提出了在调度中考虑处理器有费用的模型 .他们研究了所谓的ListModel问题 ,给出了竞争比为 1.6 18的在线算法 ,同时证明了任意在线算法的竞争比至少是4 / 3.该文研究ListModel问题的一个半在线情形 ,即假设工件是从大到小到达的 ,给出一个竞争比为 3/ 2的半在线算法 .同时证明对该问题的这一半在线情形 ,任意半在线算法的竞争比至少是 4 / 3.