Job scheduling algorithm

Malay Gain
Last Updated: Jun 29, 2022

Introduction

Job scheduling is a scheduling problem of jobs with given deadlines to maximize profit. Here, the main objective is to find the sequence of jobs that maximize completion within the deadline. It is a greedy algorithm-based popular problem that has wide implementations in real-world scenarios.

Problem statement

You are given a set of n jobs where each has a deadline and profit associated with it. Each job takes one unit of time to complete, and only one job can be scheduled at a time. We earn the profit associated with the job if and only if the job is completed by its deadline. Find the job scheduling of the given jobs that ensure maximum profit.

Input

Job id

1

2

3

4

5

deadline

2

1

2

1

3

profit

100

19

27

25

15

 

Output

Order of job ids : 3, 1, 5

 

Explanation

First, select the job with the highest profit(100) i.e., job 1 with deadline=2.

Job 3 has 2nd highest profit= 27 with deadline= 2;

So, we can schedule jobs 1 and 3 for the first two time slots. No other job can be assigned these time slots.

Next, we need to find a job having the deadline >2 i.e job 5; as there is no other job with higher profit we will allot the 3rd time slot to job 5.

So, the order of job ids after scheduling is 3, 1, 5 or 1, 3, 5. This ordering ensures the maximum profit.

Note: Please try to solve the problem first and then see the below solution approach.

Approach

Here we will take a greedy approach to implement the job scheduling problem. We will follow the following steps to schedule the job in the desired ways.

  • First, sort the jobs in the decreasing order of their profits.
  • Then find the highest deadline among all deadlines.
  • Next, we need to assign time slots to individual job ids.
  • First, check if the maximum possible time slot for the job, i.e., its deadline, is assigned to another job or not. If it is not filled yet, assign the slot to the current job id. 
  • Otherwise, search for any empty time slot less than the deadline of the current job. If such a slot is found, assign it to the current job id and move to the next job id.

Code

// C++ implementation of the job scheduling algorithm

#include <bits/stdc++.h>
using namespace std;

struct Job 
{ 
    int id; // Job Id 
    int dead; // Deadline of job 
    int profit; // Profit if job is over before or on deadline 
};

bool compare(Job a, Job b)
{
    return a.profit>b.profit;
}

//function to find the final schedule of the jobs for gaining maximum profit
    vector<int> JobScheduling(Job arr[], int n) 
    { 
        //sorting  the jobs in the decreasing order of their profits
        
         sort(arr,arr+n,compare);
        int maxline=0,j=0;
        
        // finding the max deadline
        for(int i=0;i<n;i++)
        {
            if(arr[i].dead>maxline)
            {
                maxline=arr[i].dead;
            }
        }
        int i=0;
        int a[maxline];
        memset(a,-1,sizeof(a));
        
        //finding time slot for the jobs 
        while(j!=maxline && i<n )
        {
         //if slot is not filled, fill the slot with current job id
            if(a[arr[i].dead-1]==-1)
            {
                a[arr[i].dead-1]=arr[i].id;
                 j++;
            }
            
            //otherwise search for any empty time slot less than the deadline of the current job
            else{
                for(int k=arr[i].dead-1;k>=0;k--)
                {
                 // if such slot found, fill it with current job id and move to next job id
                    if(a[k]==-1)
                    {
                        a[k]=arr[i].id;
                        j++;
                        break;
                    }
                }
            }
            i++;
        }
        
        
      
        vector<int> schedule;
        for(i=0;i<maxline;i++)
        {
            if(a[i]==-1)
            {
                continue;
            }
            else{
                schedule.push_back(a[i]);
            }
        }
        
    
        return schedule;
    } 
    
    
    //driver code
    
int main()
{
Job arr[] = { {1, 2, 100}, {2, 1, 19}, {3, 2, 27},{4, 1, 25}, {5, 3, 15}};
vector<int> schedule=JobScheduling( arr, 5);

cout<<"order of scheduled jobs for maximum profit: ";
for(int i=0;i<schedule.size();i++)
{
cout<<schedule[i]<<" ";
}
}

 

Output

order of scheduled jobs for maximum profit: 3 1 5

 

Complexity Analysis

The time complexity for the above job scheduling algorithm is O(n2) in the worst case.

Here space complexity is O(n) as extra space is used in the above implementation.

 

Frequently Asked Questions

What is the greedy algorithm?

Greedy is one algorithmic paradigm that follows the approach of making the locally optimal choice at each stage, leading to the globally optimum solution. A greedy algorithm always takes the best immediate or local solution while reaching the final solution. 

What is the priority queue?

It is a special type of queue where elements are ordered based on their priority and pop out early if priority is higher than other elements.

Application of job scheduling algorithm.

In the field of networking for optimal routing in railway networks as well as airline networks job scheduling algorithms are widely used.

Conclusion

This article covered how to implement the job scheduling algorithm using a greedy-based approach.

If you want to learn more about the greedy algorithm and want to practice some questions to get a good grasp on such problems, then you can visit our CodeStudio and explore various topics like Web Technologies, Programming Fundamentals, Aptitude, DSA, and much more from our CN Library | Free Online Coding Resources.

Happy learning!

Was this article helpful ?
0 upvotes