The Job Scheduling Problem: Difference between revisions
Jump to navigation
Jump to search
| Line 3: | Line 3: | ||
=Overview= | =Overview= | ||
The job scheduling problem is a canonical example for a [[Algorithms#Greedy_Algorithms|greedy algorithm]]. | The job scheduling problem is a canonical example for the use of a [[Algorithms#Greedy_Algorithms|greedy algorithm]]. | ||
=The Problem= | =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: | 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: | ||
Revision as of 20:03, 20 October 2021
Internal
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 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
=