Job Scheduling using Greedy Algorithm

Job scheduling is the problem of scheduling jobs out of a set of N jobs on a single processor which maximizes profit as much as possible. Consider N jobs, each taking unit time for execution. Each job is having some profit and deadline associated with it. Profit earned only if the job is completed on or before its deadline. Otherwise, we have to pay a profit as a penalty. Each job has deadline d_i ≥ 1 and profit p_i ≥ 0. At a time, only one job can be active on the processor.

The job is feasible only if it can be finished on or before its deadline. A feasible solution is a subset of N jobs such that each job can be completed on or before its deadline. An optimal solution is a solution with maximum profit. The simple and inefficient solution is to generate all subsets of the given set of jobs and find the feasible set that maximizes the profit. For N jobs, there exist 2^N schedules, so this brute force approach runs in O(2^N) time.

However, the greedy approach produces an optimal result in fairly less time. As each job takes the same amount of time, we can think of the schedule S consisting of a sequence of job slots 1, 2, 3, …, N, where S(t) indicates job scheduled in slot t. Slot t has a span of (t – 1) to t. S(t) = 0 implies no job is scheduled in slot t.

Schedule S is an array of slots S(t), S(t) ∈ {1, 2, 3, …, N} for each t ∈ {1, 2, 3, …, N}

Schedule S is feasible if,

• S(t) = i, then t ≤ d_i (Scheduled job must meet its deadline)
• Each job can be scheduled at max once.

Our goal is to find a feasible schedule S which maximizes the profit of scheduled job. The goal can be achieved as follow: Sort all jobs in decreasing order of profit. Start with the empty schedule, select one job at a time and if it is feasible then schedule it in the latest possible slot.

Algorithm for Job Scheduling

Algorithm for job scheduling is described below:

Algorithm JOB_SCHEDULING( J, D, P )
// Description : Schedule the jobs using the greedy approach which maximizes the profit

// Input : 		 
J: Array of N jobs
D: Array of the deadline for each job
P: Array of profit associated with each job

// Output : Set of scheduled job which gives maximum profit

Sort all jobs in J in decreasing order of profit
S ← Φ	// S is set of scheduled jobs, initially it is empty 
SP ← 0	// Sum is the profit earned 

for i ← 1 to N do
    if Job J[i] is feasible then
        Schedule the job in the latest possible free slot meeting its deadline.
        S ← S ∪ J[i]
        SP ← SP + P[i]
    end
end

Complexity Analysis of Job Scheduling

Simple greedy algorithm spends most of the time looking for the latest slot a job can use.  On average, N jobs search N/2 slots. This would take O(N²) time.

However, with the use of set data structure (find and union), the algorithm runs nearly in O(N) time.

Examples

Problem: Solve the following job scheduling with deadlines problem using the greedy method. Number of jobs N = 4. Profits associated with Jobs : (P₁, P₂, P₃, P₄) = (100, 10, 15, 27). Deadlines associated with jobs (d₁, d₂, d₃, d₄) = (2, 1, 2, 1)

Solution:

Sort all jobs in descending order of profit.

So, P = (100, 27, 15, 10), J = (J₁, J₄, J₃, J₂) and D = (2, 1, 2, 1). We shall select one by one job from the list of sorted jobs, and check if it satisfies the deadline. If so, schedule the job in the latest free slot. If no such slot is found, skip the current job and process the next one. Initially,

Profit of scheduled jobs, SP = 0

Iteration 1:

Deadline for job J₁ is 2. Slot 2 (t = 1 to t = 2) is free, so schedule it in slot 2. Solution set S= {J₁}, and Profit SP = {100}

Iteration 2:

Deadline for job J₄ is 1. Slot 1 (t = 0 to t = 1) is free, so schedule it in slot 1.

Solution set S = {J₁,J₄}, and Profit SP = {100, 27}

Iteration 3:

Job J₃ is not feasible because first two slots are already occupied and if we schedule J₃ any time later t = 2, it cannot be finished before its deadline 2. So job J₃ is discarded,

Solution set S = {J₁,J₄}, and Profit SP = {100, 27}

Iteration 4:

Job J₂ is not feasible because first two slots are already occupied and if we schedule J₂ any time later t = 2, it cannot be finished before its deadline 1. So job J₂ is discarded,

Solution set S = {J₁,J₄}, and Profit SP = {100, 27}

With the greedy approach, we will be able to schedule two jobs {J₁, J₄}, which gives a profit of 100 + 27 = 127 units.

Problem: Solve the following instance of “job scheduling with deadlines” problem : n = 7, profits (p₁, p₂, p₃, p₄, p₅, p₆, p₇) = (3, 5, 20, 18, 1, 6, 30) and deadlines (d₁,  d₂, d₃, d₄, d₅, d₆, d₇) = (1, 3, 4, 3, 2, 1, 2). Schedule the jobs in such a way to get maximum profit.

Solution:

Given that,

Jobs	j1	j2	j3	j4	j5	j6	j7
Profit	3	5	20	18	1	6	30
Deadline	1	3	4	3	2	1	2

Sort all jobs in descending order of profit.

So, P = (30, 20, 18, 6, 5, 3, 1), J = (J₇, J₃, J₄, J₆, J₂, J₁, J₅) and D = (2, 4, 3, 1, 3, 1, 2). We shall select one by one job from the list of sorted jobs J, and check if it satisfies the deadline. If so, schedule the job in the latest free slot. If no such slot is found, skip the current job and process the next one. Initially,

Profit of scheduled jobs, SP = 0

Iteration 1:

Deadline for job J₇ is 2. Slot 2 (t = 1 to t = 2) is free, so schedule it in slot 2. Solution set S = {J₇}, and Profit SP = {30}

Iteration 2:

Deadline for job J₃ is 4. Slot 4 (t = 3 to t = 4) is free, so schedule it in slot 4. Solution set S = {J₇, J₃}, and Profit SP = {30, 20}

Iteration 3:

Deadline for job J₄ is 3. Slot 3 (t = 2 to t = 3) is free, so schedule it in slot 3.

Solution set S = {J₇, J₃, J₄}, and Profit SP = {30, 20, 18}

Iteration 4:

Deadline for job J₆ is 1. Slot 1 (t = 0 to t = 1) is free, so schedule it in slot 1.

Solution set S = {J₇, J₃, J₄, J₆}, and Profit

SP = {30, 20, 18, 6}

First, all four slots are occupied and none of the remaining jobs has deadline lesser than 4. So none of the remaining jobs can be scheduled. Thus, with the greedy approach, we will be able to schedule four jobs {J₇, J₃, J₄, J₆}, which give a profit of (30 + 20 + 18 + 6) = 74 units.

Some Popular Problems Solved by Greddy Algorithm

Greedy algorithms are used to find an optimal or near-optimal solution to many real-life problems. A few of them are listed below :

• Binary Knapsack Problem
• Fractional Knapsack Problem
• Job Scheduling Problem
• Activity Selection Problem
• Huffman Coding
• Optimal Storage on Tapes
• Optimal Merge Pattern
• Prim’s Algorithm
• Kruskal’s Algorithm
• Dijkstra’s Algorithm

---

Additional Reading: Click to read