Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is a job scheduling algorithm?
3.
Problem Statement - Job scheduling algorithm
4.
Approach
4.1.
Implementation
4.2.
C++
4.3.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
How do you solve job scheduling problems?
5.2.
What are the 4 major scheduling algorithms?
5.3.
What is job scheduling approach?
6.
Conclusion
Last Updated: Apr 1, 2024
Medium

Job scheduling algorithm

Author Malay Gain
1 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

Job scheduling is a scheduling problem for numerous jobs with given deadlines to maximize profit (See Maximize profit in Job Scheduling). Here, the main objective is to find the sequence of jobs that maximize completion within the deadline. The Job Scheduling Algorithm is a greedy algorithm-based popular problem that has wide implementations in real-world scenarios. Let's get right to the problem then.

Job Scheduling Algorithm

What is a job scheduling algorithm?

A job scheduling algorithm is a method used by operating systems to determine the order in which tasks or processes are executed on a system's CPU. These algorithms aim to optimize resource utilization, minimize waiting times, and enhance system throughput by efficiently managing the execution of tasks. Common scheduling algorithms include First Come, First Served (FCFS), Shortest Job Next (SJN), Round Robin (RR), and Priority Scheduling. Each algorithm has its own set of advantages and disadvantages, making them suitable for different types of systems and workloads.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Problem Statement - Job scheduling algorithm

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.

Implementation

  • C++

C++

// 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.

Check out this problem - Queue Implementation

Frequently Asked Questions

How do you solve job scheduling problems?

Sort all jobs in decreasing profit order.
Iterate on jobs in decreasing profit order.
Do the following for each job: 
Find a time slot i such that it is empty, i< deadline, and i is greatest. Put the job in this slot and mark it as completed.

What are the 4 major scheduling algorithms?

Following are the famous process scheduling algorithms:
1. First-Come, First-Served (FCFS) Scheduling.
2. Shortest-Job-First (SJF) Scheduling.
3. Priority Scheduling.
4. Shortest Remaining Time (SRT)

What is job scheduling approach?

A job scheduling approach refers to the strategy or methodology used to schedule tasks or processes in a computing system. It involves selecting an appropriate scheduling algorithm and adjusting parameters to optimize system performance and resource utilization based on specific requirements and constraints.

Conclusion

This article covered how to implement the job scheduling algorithm using a greedy-based approach. You can also checkout to the Greedy approach based problems for efficient learning of the same.

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 Coding Ninjas Studio and explore various topics like Web Technologies, Programming Fundamentals, Aptitude, DSA, and much more from our CN Library | Free Online Coding Resources.

Also Read - Selection Sort in C

Recommended Readings


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, etc. on Coding Ninjas Studio.

Happy learning!

Previous article
Activity Selection problem and Greedy Algorithm
Next article
Boruvka's Algorithm
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass