论文部分内容阅读
We consider the classical online scheduling problem P||Cmax in which jobs are released over list and provide a nearly optimal online algorithm.More precisely,an online algorithm whose competitive ratio is at most(1+α)times that of an optimal online algorithm could be achieved in polynomial time,where m,the number of machines,is a part of the input.It has been known by folklore that an online problem could be viewed as a game between an adversary and the online player.Our approach extensively explores such a structure and builds up a completely new framework to show that,for the online over list scheduling problem,given any ε＞0,there exists a uniform threshold K which is polynomial in m such that if the competitive ratio of an online algorithm is ρ≤2,then there exists a list of at most K jobs to enforce the online algorithm to achieve a competitive ratio of at least ρ-O(ε).Our approach is substantially different from the work on online scheduling with over time,where the number of machines is fixed.Our method could also be extended to several related online over list scheduling models.