In this paper, we consider the scheduling problem of maximizing the number of jobs with common deadline completed on time on m identical 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. Thus, if the job is restarted at some later moment in time, then it has to be done from scratch.

For the problem that m ≥ 2, we give a lower bound of 4/3 and show that the algorithm SRPT has an upper bound of 2.

online scheduling, preemption-restart, lower bound, identical parallel machines.