In this paper, we consider online scheduling problem of maximizing the number of jobs completed on time on a single machine in the preemption-restart model, in which jobs with common deadline can be preempted in the process of it and restarted in a later time, but the
preempted jobs have to be processed from scratch. For the problem of single machine, we give a lower bound of 2, which indicates that SRPT (shortest remaining processing time) algorithm is the best possible online algorithm.

online scheduling, preemption-restart, lower bound.