DAA- Job Sequencing With Deadlines

Job Sequencing With Deadlines

Here is the process of Job sequencing in brief.

• Firstly, you are given a set of jobs.
• Each job has a set of defined deadlines and some profit associated with it.
• A job is profited only if that job is completed within the given deadline.
• Another point to note is that only one processor will be available for processing all the jobs.
• The processor will take one unit of time in order to complete a job.

The problem states-

Approach to Solution

• A feasible solution is a subset of jobs such that each job of the subset is completed within the given deadline.
• The value of a feasible solution is said to be the sum of the profit of all the jobs contained in that subset.
• An optimal solution to the problem would be a feasible solution that gives the maximum profit.

Greedy Algorithm Approach- 

We adopt the greedy algorithm inorder to determine the selection of the next job to get an optimal solution.

Below is the greedy algorithm that is always supposed to give an optimal solution to the job sequencing problem.

Step-01:

• Sorting of all the given jobs in the decreasing order of their profit.

Step-02: 

• Checking the value of the maximum deadline.
• Drawing a Gantt chart such that the maximum time on the Gantt chart is the value of the maximum deadline.

Step-03: 

• Picking up the jobs one after the other.
• Adding the jobs on the Gantt chart in such a way that they are as far as possible from 0. This ensures that the job gets completed before the given deadline.

Algorithm for Job Sequencing with Deadline:

Algorithm: Job-Sequencing-With-Deadline (Dead, Job, n, k) 

Dead(0) := Job(0) := 0 
k := 1 
Job(1) := 1   // means first job is selected 
for i = 2 … n do 
   r := k 
   while Dead(Job(r)) > Dead(i) and Dead(Job(r)) ≠ r do 
      r := r – 1 
   if Dead(Job(r)) ≤ Dead(i) and Dead(i) > r then 
      for l = k … r + 1 by -1 do 
         Job(l + 1) := Job(l) 
         Job(r + 1) := i 
         k := k + 1 

PROBLEM BASED ON JOB SEQUENCING WITH DEADLINES-

Problem- 

We are given the jobs, their deadlines and associated profits as shown-

Answer the following questions-

1. Write the optimal schedule that provides us the maximum profit.
2. Can we complete all the jobs in the optimal schedule?
3. What is the maximum earned profit?

Solution:

Step-01:

Firstly, we need to sort all the given jobs in decreasing order of their profit as follows.

Step-02:

For each step, we calculate the value of the maximum deadline.

Here, the value of the maximum deadline is 5.

So, we draw a Gantt chart as follows and assign it with a maximum time on the Gantt chart with 5 units as shown below.

Now,

• We will be considering each job one by one in the same order as they appear in the Step-01.
• We are then supposed to place the jobs on the Gantt chart as far as possible from 0.

Step-03: 

• We now consider job4.
• Since the deadline for job4 is 2, we will be placing it in the first empty cell before deadline 2 as follows.

Step-04:

• Now, we go with job1.
• Since the deadline for job1 is 5, we will be placing it in the first empty cell before deadline 5 as shown below.

Step-05:

• We now consider job3.
• Since the deadline for job3 is 3, we will be placing it in the first empty cell before deadline 3 as shown in the following figure.

Step-06:

• Next, we go with job2.
• Since the deadline for job2 is 3, we will be placing it in the first empty cell before deadline 3.
• Since the second cell and third cell are already filled, so we place job2 in the first cell as shown below.

Step-07:

• Now, we consider job5.
• Since the deadline for job5 is 4, we will be placing it in the first empty cell before deadline 4 as shown in the following figure.

Now,

• We can observe that the only job left is job6 whose deadline is 2.
• Since all the slots before deadline 2 are already occupied, job6 cannot be completed.

Now, the questions given above can be answered as follows:

Part-01: 

The optimal schedule is-

Job2, Job4, Job3, Job5, Job1

In order to obtain the maximum profit this is the required order in which the jobs must be completed.

Part-02: 

• As we can observe, all jobs are not completed on the optimal schedule.
• This is because job6 was not completed within the given deadline.

Part-03: 

Maximum earned profit = Sum of the profit of all the jobs from the optimal schedule

= Profit of job2 + Profit of job4 + Profit of job3 + Profit of job5 + Profit of job1

= 181 + 301 + 191 + 121 + 201

= 995 units

Analysis of the algorithm:

In the job sequencing with deadlines algorithm, we make use of two loops, one loop within another. Hence, the complexity of this algorithm would be O(n2).