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