The Job Scheduling Problem

External

• https://www.coursera.org/learn/algorithms-greedy/lecture/ZvZGZ/problem-definition
• https://www.coursera.org/learn/algorithms-greedy/lecture/Jo6gK/a-greedy-algorithm

Internal

• Algorithms
• Job Scheduling
• Fair Scheduling

Overview

The job scheduling problem is a canonical example for the use of a greedy algorithm.

The Problem

Assume there is a one shared resource (a CPU) and there are n jobs that must be processed bu the shared resource. Each job has two known parameters:

• a weight w_j or priority, which qualifies its "importance". The jobs with higher weight deserve to be processed before the jobs with lower weight.
• a length ℓ_j, which codifies the processing time.

The completion time of a job j C_j is defined as:

Cj = Wj + ℓj

where W_j is the wait time, or how much the job j had to wait before being scheduled. The wait time is given by the sum of the lengths for all jobs scheduled before j.

The question we need to resolve algorithmically is in what order we should sequence the job to maximize the objective function defined by the weighted sum of completion times:

    n
min ∑ wjCj
   j=1

The Greedy Algorithm

The process through which to come up with a greedy algorithm first involves looking at a special case of the problem, where is reasonably intuitive what should be the optimal thing to do.

We could assume that all jobs have the same length and different weights. The objective function will be ℓw₁ + 2ℓw₂ + ... nℓw_n = ℓ(w₁ + 2w₂ + ... nw_n) so the obvious way to minimize it would be to scheduled the job with the biggest weight first, followed by the job with the second biggest weight and so on.

Another special case is a sequence in which all jobs have the same weight, but different lengths. The objective function is ℓ₁w + (ℓ₁+ℓ₂)w + ... + (ℓ₁+ℓ₂+...+ℓ_n)w =(nℓ₁+(n-1)ℓ₂ + ... + ℓ_n). To minimize the function, we should schedule the shortest job first, because the execution time will be reflected in the completion time of all subsequent jobs, then the second shortest job and the longest job last.

We then move beyond special case towards the general case. The analysis of the particular cases indicates that we should favor jobs with the biggest weight and jobs with the shortest length. An obvious way to aggregate the weight and a length in a single score that gives an indication on possible priority in scheduling is:

 wj
────
 ℓj

It is obvious that larger the score, the highest priority in scheduling should be.

The weakness of greedy algorithm design, however, is that is really easy to come up with alternative "obvious" scores that might do the wrong thing. It is not obvious that a greedy algorithm that schedules based on the above score is correct - always minimizes the objective function -, as opposite to an algorithm that uses w_j-ℓ_j as score, for example. In this case, the ratio score happens to be the correct way to go, as demonstrated by the correctness proof below.

To summarize:

A valid greedy algorithm to schedule jobs characterized by their weight w and length ℓ in such a way to minimize the objective function defined by the weighted sum of completion times is to compute the weight per length ratio and schedule the jobs with the highest scores first.

Correctness Proof

Proof by exchange argument:

https://www.coursera.org/learn/algorithms-greedy/lecture/Jo6gK/a-greedy-algorithm

https://www.coursera.org/learn/algorithms-greedy/lecture/mrXwO/correctness-proof-part-ii

https://www.coursera.org/learn/algorithms-greedy/lecture/YuoAV/handling-ties-advanced-optional

Playground Implementation

https://github.com/ovidiuf/playground/blob/master/learning/stanford-algorithms-specialization/09-greedy-job-scheduling/src/main/java/playground/stanford/greedy/Main.java