Abstract: Rescheduling problem for rush jobs on single machine was researched. Due to the reason that the original scheduled jobs have release time， a formulate RRLS(rescheduling rush jobs with loads locked on single machine) problem was proposed based on the following measures. That is， the total waiting time was minimized， and the rush jobs was inserted into original schedule， and the maximum waiting time was minimized with loads locked. Then the RRLS problem was proved as a NPhard one. A heuristic algorithm was presented according to the property of the problem， and its time complexity was also given. At last， an example proved the optimality conditions of algorithm.

Key words: rescheduling problem, NPhard, rush jobs, heuristic algorithm, waiting time