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 new jobs waiting to be assigned. The system then uses the system state to estimate a long-term benefit to the system of not oversubscribing the system. If the benefit from oversubscribing the system with a new job exceeds the benefit from not oversubscribing the system, the system oversubscribes the system with the new job.