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

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. Assume that all the job have the same length, then thaT the jobs have the same weight.