# 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^{2}) 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 _{1}, P_{2}, P_{3}, P_{4}) = (100, 10, 15, 27). Deadlines associated with jobs (d_{1}, d_{2}, d_{3}, d_{4}) = (2, 1, 2, 1)**

**Solution:**

Sort all jobs in descending order of profit.

So, P = (100, 27, 15, 10), J = (J_{1}, J_{4}, J_{3}, J_{2}) 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_{1} is 2. Slot 2 (t = 1 to t = 2) is free, so schedule it in slot 2. Solution set S= {J_{1}}, and Profit SP = {100}

**Iteration 2:**

Deadline for job J_{4} is 1. Slot 1 (t = 0 to t = 1) is free, so schedule it in slot 1.

Solution set S = {J_{1},J_{4}}, and Profit SP = {100, 27}

**Iteration 3:**

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

Solution set S = {J_{1},J_{4}}, and Profit SP = {100, 27}

**Iteration 4:**

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

Solution set S = {J_{1},J_{4}}, and Profit SP = {100, 27}

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

**Problem: Solve the following instance of “job scheduling with deadlines” problem : n = 7, profits (p _{1}, p_{2}, p_{3}, p_{4}, p_{5}, p_{6}, p_{7}) = (3, 5, 20, 18, 1, 6, 30) and deadlines (d_{1}, d_{2}, d_{3}, d_{4}, d_{5}, d_{6}, d_{7}) = (1, 3, 4, 3, 2, 1, 2). Schedule the jobs in such a way to get maximum profit.**

**Solution:**

Given that,

Jobs | j_{1} | j_{2} | j_{3} | j_{4} | j_{5} | j_{6} | j_{7} |

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_{7}, J_{3}, J_{4}, J_{6}, J_{2}, J_{1}, J_{5}) 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_{7} is 2. Slot 2 (t = 1 to t = 2) is free, so schedule it in slot 2. Solution set S = {J_{7}}, and Profit SP = {30}

**Iteration 2:**

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

**Iteration 3:**

Deadline for job J_{4} is 3. Slot 3 (t = 2 to t = 3) is free, so schedule it in slot 3.

Solution set S = {J_{7}, J_{3}, J_{4}}, and Profit SP = {30, 20, 18}

**Iteration 4:**

Deadline for job J_{6} is 1. Slot 1 (t = 0 to t = 1) is free, so schedule it in slot 1.

Solution set S = {J_{7}, J_{3}, J_{4}, J_{6}}, 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_{7}, J_{3}, J_{4}, J_{6}}, 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