The Job Scheduling Problem

Internal

• Algorithms

Overview

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

The Problem

Assume there is a one shared resource (a CPU) and there are 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

The question we need to resolve algorithmically is in what order we should sequence the job to maximize

=