The Job Scheduling Problem

From NovaOrdis Knowledge Base
Jump to navigation Jump to search

Internal

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 n jobs that must be processed bu the shared resource. Each job has two known parameters:

  • a weight wj 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 Cj is defined as:

Cj = Wj + ℓj

where Wj 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

=