+5 votes
595 views

We are given 9 tasks $T_1, T_2, \dots, T_9$. The execution of each task requires one unit of time. We can execute one task at a time. Each task $T_i$ has a profit $P_i$ and a deadline $d_i$. Profit $P_i$ is earned if the task is completed before the end of the $d_i^{th}$ unit of time.

Task $T_1$ $T_2$ $T_3$ $T_4$ $T_5$ $T_6$ $T_7$ $T_8$ $T_9$
Profit 15 20 30 18 18 10 23 16 25
Deadline 7 2 5 3 4 5 2 7 3

Are all tasks completed in the schedule that gives maximum profit?

1. All tasks are completed

2. $T_1$ and $T_6$ are left out

3. $T_1$ and $T_8$ are left out

4. $T_4$ and $T_6$ are left out

asked | 595 views

Question has been splitted. Please check the below URL for the B part http://gateoverflow.in/82514/gate2005-84b

Please refer the below URL for video lecture on this topic(Task Scheduling Problem).

## 2 Answers

+8 votes
Best answer

The most important statement in question is

each task requires one unit of time

This shows that we can greedily choose the better task and that should give us the optimal solution. The best task would be the one with maximum profit. Thus we can sort the tasks based on deadline and then profit as follows:

Task T7 T2 T9 T4 T5 T3 T6 T8 T1
Deadline 2 2 3 3 4 5 5 7 7

0 ----T7 ----- 1----T2-----2-----T9-----3-----T5-----4-----T3-----5-----T8-----6-----T1------7

T4 and T6 left out

D is answer.

answered by Veteran (31k points)
edited
Can you explain why T4 and T6 are left out

Since we have to be greedy about profit, so first we have to choose a task with max profit considering its deadline.

 Time 1 2 3 4 5 6 7 Order Of Task T7 T2 T9 T5 T3 T8 T1 Profit 23 20 25 18 30 16 15 deadline 2 2 3 4 5 7 7

TOTAL MAXIMUM PROFIT = (23 + 20 + 25 + 18 + 30 + 16 + 15) = 147.

@vijay can you provide some reference material to understand this ?
+2 votes

Step -1 Sort the tasks in decreasing order of profit and if any conflict arises between two or more tasks,resolve them by sorting them on basis of having greater deadline first(Because we have more time to complete the task with greater deadline and same profit).

Step 2- Since Maximum deadline given is 7, so we consider we have 7 time slots ranging from 0-7 where a task Ti having deadline say 2 can be filled in slots either 0-1 or 1-2 and not beyond 2 because this task has deadline of 2 time units, so this task has to be completed by atmost time T=2.

Now according to question, since Each task completes in Unit time, so a single tasks takes only one slot as shown.

Now Take the first task in the list i.e. T3 which has a deadline of 5, so it can be completed in maximum 5 time units, so place it in slot 4-5 which is the maximum deadline by which this task can be completed.

Task T9 with deadline 3 is similarly placed in  slot 2-3.

Task T7 with deadline 2 is placed in slot 1-.2.

Now for task T2 having deadline 2 can be placed in either 0-1 or 1-2(Occupied by T7). So T2 will occupy slot 0-1.

Task T5 with deadline 4 is placed in slot 3-4.

Now comes task T4 which has deadline 3 can be put in slots 0-1 or 1-2 or 2-3 and not beyond that.Unfortunately, all such slots are occupied so T4 will be left out.

Task T8 with deadline 7 goes in slot 6-7.

Task T1 with deadline 7 can be placed in  slot 5-6.

Now all time slots are full.

So, Task T6 will be left out.

So, option (d) is the answer.

answered by Active (1.1k points)
edited
Best Explanation. Thanks
Answer:

+3 votes
2 answers
1
+2 votes
2 answers
2
+2 votes
1 answer
3