In this paper, we consider the scheduling problem of maximizing the number of early jobs on midentical parallel machines in the online version of preemption-restart model which means that jobs may be preempted, but preempting results in all the work done on this job so far being lost.

For the problem that  and all the jobs have common deadline, we give a lower bound of  and we show algorithm SRPT has an upper bound of 2. For the problem that  we give a lower bound of  and we show algorithm SRPT has an upper bound of 2.

on-line scheduling, preemption-restart, lower bound, identical parallel machines.