This paper presents a general methodology for online scheduling of parallel jobs onto multi-processor servers in a soft real-time environment, where the final utility of each job decreases with the job completion time. A solution approach is presented where each server uses Reinforcement Learning for tuning its own value function, which predicts the average future utility per time step obtained from completed jobs based on the dynamically observed state information. The server then selects jobs from its job queue, possibly preempting some currently running jobs and
“squeezing” some jobs into fewer CPUs than they ideally require to maximize the value of the resulting server state. The experimental results demonstrate the feasibility and benefits of the proposed approach.