Job scheduling algorithm

Operating System Scheduling Algorithms

Operating system scheduling algorithms are crucial components of an OS that determine how processes are managed and executed on a computer system's CPU. These algorithms aim to maximize CPU utilization, throughput, fairness, and responsiveness while minimizing overhead and latency.

Business Processes

Business processes encompass various activities and workflows within an organization, and efficient scheduling of these processes can significantly impact productivity and performance. Here are some key aspects related to business processes:

Task Prioritization

In a business context, task prioritization involves identifying and categorizing tasks based on their importance, urgency, and impact on organizational goals. Scheduling algorithms help in prioritizing tasks by allocating CPU time accordingly, ensuring critical processes are completed in a timely manner.

Resource Allocation

Resource allocation is essential for optimizing the utilization of available resources such as CPU, memory, and disk space. Scheduling algorithms play a vital role in allocating resources efficiently to business processes, ensuring equitable distribution and preventing resource contention.

Time Management

Effective time management is crucial for meeting deadlines and achieving business objectives. Scheduling algorithms help in managing time effectively by scheduling processes based on deadlines, dependencies, and resource availability, thereby enhancing productivity and minimizing delays.

Multi-tasking

In a multitasking environment, multiple processes compete for CPU time simultaneously. Scheduling algorithms determine the order in which processes are executed, allowing the system to switch between tasks seamlessly. This enables businesses to efficiently handle concurrent activities and improve overall system responsiveness.

Workload Balancing

Workload balancing involves distributing processing tasks evenly across system resources to prevent bottlenecks and maximize throughput. Scheduling algorithms facilitate workload balancing by dynamically adjusting process priorities and resource allocations based on system load and demand, ensuring optimal performance across all business processes.

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

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 in C++

• 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]<<" ";
}
}

You can also try this code with Online C++ Compiler

Run Code

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

Multilevel Feedback Queue

The multilevel feedback queue is a scheduling algorithm that manages processes by assigning them to different priority levels and adjusting their priority dynamically based on their behavior and resource requirements. In this algorithm, processes are placed into multiple queues, each with its own priority level. The scheduler selects processes for execution from the highest priority queue that contains ready processes. If a process uses too much CPU time or exhibits a high level of I/O activity, its priority may be lowered, allowing other processes to receive more attention. Conversely, processes that are I/O-bound or have been waiting for a long time may have their priority increased to ensure timely execution.

Greedy Algorithm

A greedy algorithm is a problem-solving approach that makes locally optimal choices at each step with the hope of finding a globally optimal solution. In greedy algorithms, decisions are made based solely on the current state of the problem without considering future consequences. This approach works well for problems where making the best choice at each step leads to an optimal overall solution. However, greedy algorithms may not always produce the most optimal solution for all problem instances, as they do not consider the entire solution space.

Job Scheduling with ActiveBatch

ActiveBatch is a job scheduling and workload automation software solution designed to streamline and optimize business processes by automating repetitive tasks and workflows. It provides a centralized platform for managing and scheduling jobs across various systems, applications, and environments. With ActiveBatch, users can create complex job workflows, define dependencies, set priorities, and monitor job execution in real-time.

ActiveBatch offers features such as:

• Visual Workflow Design: Users can easily create and customize job workflows using a drag-and-drop interface, allowing for quick and intuitive workflow design.
• Dependency Management: ActiveBatch allows users to define dependencies between jobs, ensuring that tasks are executed in the correct order based on their dependencies.
• Resource Optimization: The software optimizes resource utilization by scheduling jobs based on available resources, priorities, and service level agreements (SLAs), maximizing efficiency and minimizing idle time.
• Monitoring and Reporting: ActiveBatch provides comprehensive monitoring and reporting capabilities, allowing users to track job execution, identify bottlenecks, and generate detailed reports for analysis and auditing purposes.

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.

What is the best scheduling algorithm?

The best scheduling algorithm depends on the specific requirements and characteristics of the system. Popular choices include Shortest Job Next (SJN), Round Robin, and Multilevel Feedback Queue.

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

• Kadane's Algorithm
• Weighted Job Scheduling
• Maximum Profit in Job Scheduling
• FCFS Scheduling
• Data Structure
• Design and Analysis of Algorithms
• Introduction to Operating System
• Process Control Block in OS
• scheduling algorithms in operating system

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!