# Job sequencing with deadlines | Greedy method

## Greedy method Application Job sequencing with deadlines

Sequencing jobs on a single processor with deadline constraints is called Job sequencing with deadlines.
We give you a set of jobs.

• Each job has a defined deadline and a certain benefit/profit is associated with it.
• We get Profit For a job only when the particular job is completed within the deadline
• A single processor is available to handle all jobs.
• The processor takes a unit of time to complete a job.

The Problem is stated as follows:
There are n jobs let us say S={1, 2, …, n} and each job i has a deadline di >= 0 and a profit pi >= 0. We need one unit of time to process each job and we can do at most one job each time. We can earn the profit pi if job i is completed by its deadline but only one machine is available for processing. A feasible solution is a subset of jobs J, such that each job in the subset is completed by its deadline gaining a profit pi. An optimal solution is a feasible solution that maximizes total profit

Example: n=4, (p1, p2, p3, p4)=(100,10,15,27), (d1, d2, d3, d4)=(2,1,2,1)

Different feasible solution with the sequencing of jobs and total profit are given below:

 Feasible Solution processing sequence value 1. (1, 2) 2, 1 110 2. (1, 3) 1, 3 or 3, 1 115 3. (1, 4) 4, 1 127 (optimal solution) 4. (2, 3) 2, 3 25 5. (3, 4) 4, 3 42

This is a trial and error method

Greedy approach is to sort pi into non-increasing order. After sorting p1 >= p2 >=…>= pi. Add the next job i to the solution set J if i can be completed by its deadline and that maximizes the total profit. Total Profit = 100 + 27 = 127. So this is an optimal solution.

An algorithm for solving Job sequencing with deadlines problem is given below:

``````Algorithm JS(d, n)
// The jobs are ordered such that p>=p>= ... >=p[n].
// J[i] is the ith job in the optimal solution, 1<=i<=k.
{
d := J := 0; // Initialize. J := 1; // Include job 1.
k := 1;
for (i:=2 to n) do
{
// r is the position for i and check feasibility of insertion. r := k;
while ((d[J[r]] > d[i]) and (d[J[r]] != r)) do r:=r-1;
if ((d[J[r]] <= d[i]) and (d[i] > r)) then
{
// Insert i into J[].
for ( q:=k to (r+1) step -1) do
{
J[q+1] := J[q];
}
J[r+1] := i; k:=K+1;
}
}
return (k);
}``````

Example 2

a1              4                              20
b1              1                              10
c1              1                              40
d1              1                             30

Output: Below sequence of jobs have maximum  profit
c1, a1

Example 3

a1                            2                                100
b1                             1                                 19
c1                             2                                 27
d1                             1                                 25
e1                             3                                15
Output: Below sequence of jobs have maximum  profit
c1, a1, e1

Time complexity of Job Sequencing algorithm is O(n2)

### This Post Has 2 Comments

1. M.Aruna

M.

1. ghgh

M for what