Question: Solve the following Job Sequencing with deadlines problem. N = 7 Profits (P1, P2, P3, P4, P5, P6, P7) = {3, 5, 20, 18, 1, 6, 30} Deadlines (D1, D2, D3, D4, D5, D6, D7) = {1, 3, 4, 3, 2, 1, 2}
2

Mumbai University > Computer Engineering > AOA > SEM - 4

Year: May 16

Marks: 10 M

 modified 2.3 years ago  • written 2.3 years ago by Sagar Narkar • 1.5k
2

Step: 1

We will arrange the profits Pi in descending order, along with corresponding deadlines.

Step: 2

Create an array J [] which stores the jobs. Initially j [] will be

Step: 3

Add ith Job in array J [ ] at index denoted by its deadlines Di

First Job is P7, its deadline is 2.

Hence insert P7 in the array J [] at 2nd index.

Step: 4

Next Job is P3. Insert it in array J [] at index 4.

Step: 5

Next Job is P4. It has a deadline 3. Therefore insert it at index 3.

Step: 6

Next Job is P6, it has deadline 1. Hence Place P6 at index 1.

Step: 7

Next Job is P2, it had deadline 3. But as 3 is already occupied and there is no empty slot at index < J [3]. Just discard job P2. Similarly Job P1 and P5 will get discarded.

Step: 8

Thus the optimal sequence which we will obtain will be 6-7-4-3. The maximum profit will be 74.