Analysis Design Of Algorithm (ADA) | Job Sequencing with timeline Using Greedy Approach

📌Highlights: Hi friends! In this post I am  going to explain about Job Sequencing with timeline problem using Greedy approach. I am try to explain with the help of examples.

Let we discuss about Job sequencing problem. This is a maximisation problem means If we have so many jobs with their respective profit and timeline. We try to arrange jobs in such a way that we will get more profit and here we must careful about timeline because timeline is like a constraint that we must follow the given time line for respective job.

Let we understand by some examples:

Example 1:

Here in this example 5 task / jobs are given. If this task is completed then we get profit each task is associated with some profit but that job must be finished with in given deadlines.

Here the constraint is every job must be complete with in deadline.

Let take simple example to understand , Suppose here 5 person are available in any shop and want to complete their job with some deadline such as 

job j1 must complete with in suppose 2 hours.

same as,

job j2 must complete with in suppose 2 hours.

job j3 must complete with in suppose 1 hour.

job j4 must complete with in suppose 3 hours.

job j5 must complete with in suppose 3 hours.

Now the worker will decide the cost or profit of each job such as, 

Profit of job 1 = 20

Profit of job 2 = 15

Profit of job 2 = 10

Profit of job 2 = 5

Profit of job 2 = 1

Now the worker analyse which job has maximum profit will do first because it is a maximisation problem.

Suppose here we have time slot suppose it in hours. All job must complete with in 0 to 3 time slot.

So that we can see we have only 3 slots are available. So here we select only 3 jobs which give maximum profit.

In this Greedy approach we select the job by maximum profit.

Let we analyse the problem.

Suppose  for Job j1 profit will be 20 and he can wait for 2 time slots. (suppose 2 hours)

Next we which job have maximum profit i.e j2 profit is 15 and time line is 2 so we can also put job j2 in 0 to 2 time slot.

Next we which job have maximum profit i.e j3 profit is 10 and time line is 1 so her e 0 to 1 time slot is not available so we will not select j3 (suppose he can only wait for 1 hour)

Next we which job have maximum profit i.e j4 profit is 5 and time line is 3 so we can also put job j3 in 2 to 3 time slot. (suppose he is waiting for 3 hours)

Now here total profit = 15 + 20 + 5 

                               = 40

For example: Try your self

Example 2:

Answer: 180

Example 2:

Answer : 65

Example 3:

Answer : 110

Example 4:

Answer : 74

📌Friends it is the end this post i hope you understand the Job sequencing problem using greedy approach for more practice try to do all examples. ! ok we will meet in some new post till continue reading....