一个经典在线调度算法的另一证明

摘要

考虑基于时间滚动的单机在线调度问题.一些独立的工件要被安排在机器上加工,只有等工件到达才能知道其信息,并且工件在加工过程中不允许中断,其目标是最小化总完工时间和.Hoogeven和Vestjens对此经典问题提出了D-SPT算法,并证明了此算法是最好可能的在线算法,我们给出了D-SPT算法的另外一个证明,同时证明了此算法是最好可能的在线算法.%In this paper,we consider a single machine online scheduling problem where jobs arrive over time.Some independent jobs have to be scheduled on the machine,where all the information of jobs is not known in advance and preemption is not allowed.The goal is to minimize the total completion time.According to the D-SPT algorithm proposed by Hoogeven and Vestjens(Optimal online algorithms for single-machine scheduling.Lecture notes in computer science,vol.1084.Berlin:springer;1996.p.404-414),we give an alternative proof for the classic online algorithm,and prove that its competitive ratio reaches the lower bound 2.