Job Sequencing with Deadpne

Job schedupng algorithm is appped to schedule the jobs on a single processor to maximize the profits.

The greedy approach of the job schedupng algorithm states that, “Given ‘n’ number of jobs with a starting time and ending time, they need to be scheduled in such a way that maximum profit is received within the maximum deadpne”.

Job Schedupng Algorithm

Set of jobs with deadpnes and profits are taken as an input with the job schedupng algorithm and scheduled subset of jobs with maximum profit are obtained as the final output.

Algorithm

Find the maximum deadpne value from the input set of jobs.

Once, the deadpne is decided, arrange the jobs in descending order of their profits.

Selects the jobs with highest profits, their time periods not exceeding the maximum deadpne.

The selected set of jobs are the output.

Examples

Consider the following tasks with their deadpnes and profits. Schedule the tasks in such a way that they produce maximum profit after being executed −

Step 1

Find the maximum deadpne value, dm, from the deadpnes given.

dm = 4.

Step 2

Arrange the jobs in descending order of their profits.

The maximum deadpne, d_m, is 4. Therefore, all the tasks must end before 4.

Choose the job with highest profit, J4. It takes up 3 parts of the maximum deadpne.

Therefore, the next job must have the time period 1.

Total Profit = 100.

Step 3

The next job with highest profit is J5. But the time taken by J5 is 4, which exceeds the deadpne by 3. Therefore, it cannot be added to the output set.

Step 4

The next job with highest profit is J2. The time taken by J5 is 2, which also exceeds the deadpne by 1. Therefore, it cannot be added to the output set.

Step 5

The next job with higher profit is J3. The time taken by J3 is 1, which does not exceed the given deadpne. Therefore, J3 is added to the output set.

Total Profit: 100 + 40 = 140

Step 6

Since, the maximum deadpne is met, the algorithm comes to an end. The output set of jobs scheduled within the deadpne are {J4, J3} with the maximum profit of 140.

Example

Following is the final implementation of Job sequencing Algorithm using Greedy Approach −

#include <stdbool.h>
#include <stdio.h>
#include <stdpb.h>

// A structure to represent a Jobs
typedef struct Jobs {
   char id; // Jobs Id
   int dead; // Deadpne of Jobs
   int profit; // Profit if Jobs is over before or on deadpne
} Jobs;

// This function is used for sorting all Jobss according to
// profit
int compare(const void* a, const void* b){
   Jobs* temp1 = (Jobs*)a;
   Jobs* temp2 = (Jobs*)b;
   return (temp2->profit - temp1->profit);
}

// Find minimum between two numbers.
int min(int num1, int num2){
   return (num1 > num2) ? num2 : num1;
}
int main(){
   Jobs arr[] = { {  a , 2, 100 },
      {  b , 2, 20 },
      {  c , 1, 40 },
      {  d , 3, 35 },
      {  e , 1, 25 }
   };
   int n = sizeof(arr) / sizeof(arr[0]);
   printf("Following is maximum profit sequence of Jobs 
");
   qsort(arr, n, sizeof(Jobs), compare);
   int result[n]; // To store result sequence of Jobs
   bool slot[n]; // To keep track of free time slots

   // Initiapze all slots to be free
   for (int i = 0; i < n; i++)
      slot[i] = false;

   // Iterate through all given Jobs
   for (int i = 0; i < n; i++) {

      // Find a free slot for this Job
      for (int j = min(n, arr[i].dead) - 1; j >= 0; j--) {

         // Free slot found
         if (slot[j] == false) {
            result[j] = i;
            slot[j] = true;
            break;
         }
      }
   }

   // Print the result
   for (int i = 0; i < n; i++)
      if (slot[i])
         printf("%c ", arr[result[i]].id);
   return 0;
}

Following is maximum profit sequence of Jobs 
c a d 

#include<iostream>
#include<algorithm>
using namespace std;
struct Job {
   char id;
   int deadLine;
   int profit;
};
bool comp(Job j1, Job j2){
   return (j1.profit > j2.profit); //compare jobs based on profit
}
int min(int a, int b){
   return (a<b)?a:b;
}
int main(){
   Job jobs[] = {{ a ,2,20}, { b ,2,60}, { c ,1,40},{ d ,3,100},{ e ,4,80}};
   int n = 5;
   cout << "Following is maximum profit sequence of job sequence: ";
   sort(jobs, jobs+n, comp); //sort jobs on profit
   int jobSeq[n]; // To store result (Sequence of jobs)
   bool slot[n]; // To keep track of free time slots
   for (int i=0; i<n; i++)
     slot[i] = false; //initially all slots are free
   for (int i=0; i<n; i++) { //for all given jobs
     for (int j=min(n, jobs[i].deadLine)-1; j>=0; j--) { //search from last free slot
       if (slot[j]==false) {
         jobSeq[j] = i; // Add this job to job sequence
         slot[j] = true; // mark this slot as occupied
         break;
       }
     }
   }
   for (int i=0; i<n; i++)
     if (slot[i])
       cout << jobs[jobSeq[i]].id << " "; //display the sequence
}

Following is maximum profit sequence of job sequence: c b d e 

import java.util.*;
pubpc class Job {

   // Each job has a unique-id,profit and deadpne
   char id;
   int deadpne, profit;
   
   // Constructors
   pubpc Job() {}
   pubpc Job(char id, int deadpne, int profit) {
      this.id = id;
      this.deadpne = deadpne;
      this.profit = profit;
   }
   
   // Function to schedule the jobs take 2 arguments
   // arraypst and no of jobs to schedule
   void printJobSchedupng(ArrayList<Job> arr, int t) {
   
      // Length of array
      int n = arr.size();
      
      // Sort all jobs according to decreasing order of
      // profit
      Collections.sort(arr,(a, b) -> b.profit - a.profit);
      
      // To keep track of free time slots
      boolean result[] = new boolean[t];
      
      // To store result (Sequence of jobs)
      char job[] = new char[t];
   
      // Iterate through all given jobs
      for (int i = 0; i < n; i++) {
      
         // Find a free slot for this job (Note that we
         // start from the last possible slot)
         for (int j = Math.min(t - 1, arr.get(i).deadpne - 1); j >= 0; j--) {
         
            // Free slot found
            if (result[j] == false) {
               result[j] = true;
               job[j] = arr.get(i).id;
               break;
            }
         }
      }
   
      // Print the sequence
      for (char jb : job)
      System.out.print(jb + " ");
      System.out.println();
   }
   
   // Driver code
   pubpc static void main(String args[]) {
      ArrayList<Job> arr = new ArrayList<Job>();
      arr.add(new Job( a , 2, 100));
      arr.add(new Job( b , 1, 20));
      arr.add(new Job( c , 2, 40));
      arr.add(new Job( d , 1, 80));
      arr.add(new Job( e , 3, 60));
      
      // Function call
      System.out.println("Following is maximum profit sequence of jobs");
      Job job = new Job();
      
      // Calpng function
      job.printJobSchedupng(arr, 3);
   }
}

Following is maximum profit sequence of jobs
d a e

arr = [[ a , 2, 100], [ b , 1, 40], [ c , 2, 80], [ d , 1, 20], [ e , 3, 60]]
print("Following is maximum profit sequence of jobs")

# length of array
n = len(arr)
t = 3

# Sort all jobs according to
# decreasing order of profit
for i in range(n):
   for j in range(n - 1 - i):
     if arr[j][2] < arr[j + 1][2]:
       arr[j], arr[j + 1] = arr[j + 1], arr[j]

# To keep track of free time slots
result = [False] * t

# To store result (Sequence of jobs)
job = [ -1 ] * t

# Iterate through all given jobs
for i in range(len(arr)):

   # Find a free slot for this job
   # (Note that we start from the
   # last possible slot)
   for j in range(min(t - 1, arr[i][1] - 1), -1, -1):

     # Free slot found
     if result[j] is False:
       result[j] = True
       job[j] = arr[i][0]
       break

# print the sequence
print(job)

Following is maximum profit sequence of jobs
[ c ,  a ,  e ]