One embodiment of the present invention provides a system that assigns jobs to a system containing a number of central processing units (CPUs). During operation, the system captures a current state of the system, which describes available resources on the system, characteristics of jobs currently being processed, and characteristics of jobs waiting to be assigned. The system then uses the current system state to estimate a long-term benefit to the system of not preempting any jobs currently being processed. If the benefit from preempting one or more jobs exceeds the benefit from not preempting any jobs, the system preempts one or more jobs currently being processed on the system with a new job.