The Job Scheduling Problem: Difference between revisions
Line 30: | Line 30: | ||
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. | 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 ℓ | We could assume that all jobs have the same length and different weights. The objective function will be ℓw<sub>1</sub> + 2ℓw<sub>2</sub> + ... nℓw<sub>n</sub> = ℓ(w<sub>1</sub> + 2w<sub>2</sub> + ... nw<sub>n</sub>), 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. | ||
to minimize we will , then that the jobs have the same weight. Then move beyond special case towards the general case. In this specific case, we aggregate the weight and the length into a single score and schedule the jobs | |||
=The Proof= | =The Proof= |
Revision as of 20:28, 20 October 2021
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
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 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 ℓw1 + 2ℓw2 + ... nℓwn = ℓ(w1 + 2w2 + ... nwn), 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.
to minimize we will , then that the jobs have the same weight. Then move beyond special case towards the general case. In this specific case, we aggregate the weight and the length into a single score and schedule the jobs