Home »
Operating Systems
Job sequencing (algorithm, time complexity and example) in Operating System
In this article, we will study about the concept of job sequencing with its algorithm, time complexity and example.
Submitted by Shivangi Jain, on June 22, 2018
Job sequencing
Job sequencing is the set of jobs, associated with the job i where deadline di >= 0 and profit pi > 0. For any job i the profit is earned if and only if the job is completed by its deadline. To complete a job, one has to process the job on a machine for one unit of time. Only one machine is available for processing the jobs.
Steps for performing job sequencing with deadline using greedy approach is as follows:
 Sort all the jobs based on the profit in an increasing order.
 Let α be the maximum deadline that will define the size of array.
 Create a solution array S with d slots.
 Initialize the content of array S with zero.

Check for all jobs.
 If scheduling is possible a lot i^{th} slot of array s to job i.
 Otherwise look for location (i1), (i2)...1.
 Schedule the job if possible else reject.
 Return array S as the answer.
 End.
Algorithm for job sequencing
Input: A is the array of jobs with deadline and profit S array will be the output.
1. Begin
2. Sort all the jobs based on profit Pi so
3. P1 > P2 > P3 …………………………….>=Pn
4. d = maximum deadline of job in A
5. Create array S[1,…………………,d]
6. For i=1 to n do
7. Find the largest job x
8. For j=I to 1
9. If ((S[j] = 0) and (x deadline<= d1))
10. Then
11. S[x] = I;
12. Break;
13. End if
14. End for
15. End for
16. End
Time complexity
Job sequencing problems has the time complexity of O(n2).
Example:
Given a set of 9 jobs where each job has a deadline and profit associated to it .Each job takes 1 unit of time to complete and only one job can be scheduled at a time. We earn the profit if and only if the job is completed by its deadline. The task is to find the maximum profit and the number of jobs done.
Jobs Profit Deadline
J1 85 5
J2 25 4
J3 16 3
J4 40 3
J5 55 4
J6 19 5
J7 92 2
J8 80 3
J9 15 7
Step 1:
Step 2:
Step 3:
Step 4:
Step 5:
Step 6:
So, the maximum profit = 40 + 92 + 80 + 55 + 85 + 15 = 367
TOP Interview Coding Problems/Challenges