SRI RAMAKRISHNA ENGINEERING
COLLEGE
[Educational Service : SNR Sons Charitable Trust]
[Autonomous Institution, Reaccredited by NAAC with ‘A+’ Grade]
[Approved by AICTE and Permanently Affiliated to Anna University, Chennai]
[ISO 9001:2015 Certified and all Eligible Programmes Accredited by NBA]
VATTAMALAIPALAYAM, N.G.G.O. COLONY POST, COIMBATORE – 641 022.
partment of Artificial Intelligence and Data Scie
epartment
20IT254 – DESIGN AND ANALYSIS OF ALGORITHMS
Unit2- Task Scheduling problem
Presentation By,
[Link] Sankari
AP/AI&DS
Task Scheduling
Problem
24/02/26 2
Task Scheduling Problem
problem of scheduling jobs out of a set of N jobs on a single
processor which maximizes profit as much as possible
Consider N jobs, each taking unit time for execution
Each job is having some profit and deadline associated with it
Profit earned only if the job is completed on or before its
deadline.
Otherwise, we have to pay a profit as a penalty
24/02/26 3
Task Scheduling Problem
Each job has deadline di ≥ 1 and profit pi ≥ 0.
At a time, only one job can be active on the processor.
24/02/26 4
Solution
Job is Feasible - finished on or before its deadline
A feasible solution is a subset of N jobs such that each job can
be completed on or before its deadline
An optimal solution is a solution with maximum profit.
The simple and inefficient solution is to generate all subsets of
the given set of jobs and find the feasible set that maximizes
the profit.
24/02/26 5
24/02/26 6
Time Complexity:
Sorting: O(n log n)
Slot assignment: O(n²) (or O(n log n)
24/02/26 7
Task Scheduling Problem using
Greedy
• Sort the jobs based on decreasing order of profit.
• Iterate through the jobs and perform the following:
• Choose a Slot i if:
• Slot i isn’t previously selected.
• I < deadline
• I is maximum
• If no such slot exists, ignore the job and continue.
24/02/26 8
24/02/26 9
Sort in decreasing order of
profits:
24/02/26 10
24/02/26 11
Job Slot Assigned Solutio Profit
n
- - Φ 0 Not Included
J1 [0,1] J1 20
J2 [0,1], [2,3] J1,J2 20+38 Maximum Profit =
J3 [0,1], [2,3] J1,J2 20+38 38+30+20=88
J4 [0,1], [2,3] J1,J2 20+38
J5 [0,1], [1,2], J1,J5,J2 20+38+
[2,3] 30
24/02/26 12
Example : Shop Scenario
Job J1 J2 J3 J4 J5
Profit 20 15 10 5 1
Deadline 2 2 1 3 3
s
So there can be only 3 slots
Slot 0 1 2 3 0 to 1
1 to 2
2 to 3
24/02/26 13
Example : Shop Scenario
1. J1has maximum profit and has time of
1-2 so is put in slot 1 to 2
J1 J1 has maximum
Slot 0 1 2 3 profit and slot 2 is
free so J1 is placed
2. Next,J2 has maximum profit but
slot 1 to 2 is occupied, so we see previous slot
As previous slot, slot
J2 J1 1 is free J2 is placed
Slot 0 1 2 3 there
24/02/26 14
[Link], we consider job J3 but that particular slot is
already occupied, so J3 cannot be done
[Link], we consider job J4 so it can be placed as it
has slot availability and time
J2 J1 J4 J4 is placed in slot 3
Slot 0 1 2 3
[Link], we have job J5 but there isn’t an available slot
We have {J2,J1,J4}
Possible sequences - {J2,J1,J4} and {J1,J2,J4} as they have same deadlines
Total Profit = 20+15+5 = 40
24/02/26 15
Final Table
Job J1 J2 J3 J4 J5
Profit 20 15 10 5 1
Deadline 2 2 1 3 3
s
Job Slot Solutio Profit
Assigned n
- - 0
J1 [1,2] J1 20 Not Included
J2 [0,1], [1,2] J1,J2 20+15
J3 [0,1], [1,2] J1,J2 20+15 Total Profit = 40
J4 [0,1], [1,2], J1,J2,J4 20+15
[2,3] +5
J5
24/02/26
[0,1], [1,2], J1,J2,J4 20+15 16
/
Time Complexity
1. Find a free slot for this job = O(n)
2. Free slot found = O(n)
Thereby,
O(n2 )
24/02/26 17
Practise Problem
Job J1 J2 J3 J4 J5 J6 J7
Profit 35 30 25 20 15 12 5
Deadline 3 4 4 2 3 1 2
s
Profit = 35+30+25+20
J4 J3 J1 J2 = 110
Slot 0 1 2 3 4
24/02/26 18
Assignment Problem
24/02/26 19
24/02/26 20IT254 - Design and Analysis of Algorithm - 20