Job Scheduling Problem
Definition
• Given an array of jobs where every job has a deadline and associated profit
if the job is finished before the deadline. It is also given that every job takes a
single unit of time, so the minimum possible deadline for any job is 1. How
to maximize total profit if only one job can be scheduled at a time.
Greedy Approach for Job Scheduling Problem
• Sort all jobs in decreasing order of profit.
• Iterate on jobs in decreasing order of profit.For each job , do the following :
• For each job find an empty time slot from deadline to 0. If found empty
slot put the job in the slot and mark this slot filled.
Example
• Let us consider a set of given jobs as shown in the following tables.we have
to find a sequence of jobs,which will be completed within their deadlines and
will give maximum profit.Each job is associated with deadline and profit.
Job J1 J2 J3 J4 J5
Deadline 2 1 3 2 1
Profit 60 100 20 40 20
Solution
• To solve this problem, the given jobs are sorted according to their profit in a
descending order. Hence, after sorting, the jobs are ordered as shown in the
following table.
Job J2 J1 J4 J3 J5
Deadline 1 2 2 3 1
Profit 100 60 40 20 20
Solution
• From this set of jobs, first we select J2, as it can be completed within its
deadline and contributes maximum profit.
• Next, J1 is selected as it gives more profit compared to J4.
• In the next clock,J4 cannot be selected as its deadline is over, hence J3 is
selected as it executes within its deadline.
• The job J5 is discarded as it cannot be executed within its deadline.
Solution
• Thus, the solution is the sequence of jobs (J2, J1, J3) which are being
executed within their deadline and gives maximum profit.
• Total profit of this sequence is 100 + 60 + 20 = 180.
Program
• #include <stdio.h>
• #define MAX 100
• typedef struct Job {
• char id[5];
• int deadline;
• int profit;
• } Job;
• void jobSequencingWithDeadline(Job jobs[], int n);
• int minValue(int x, int y) {
• if(x < y) return x;
• return y;
• }
Program
• int main(void) {
• int i, j;
• //jobs with deadline and profit
• Job jobs[5] = {
• {"j1", 2, 60},
• {"j2", 1, 100},
• {"j3", 3, 20},
• {"j4", 2, 40},
• {"j5", 1, 20},
• };
• Job temp;
• //number of jobs
• int n = 5;
Program
• for(i = 1; i < n; i++) {
• for(j = 0; j < n - i; j++) {
• if(jobs[j+1].profit > jobs[j].profit) {
• temp = jobs[j+1];
• jobs[j+1] = jobs[j];
• jobs[j] = temp;
• }
• }
• }
• printf("%10s %10s %10s\n", "Job", "Deadline", "Profit");
• for(i = 0; i < n; i++) {
• printf("%10s %10i %10i\n", jobs[i].id, jobs[i].deadline, jobs[i].profit);
• }
• jobSequencingWithDeadline(jobs, n);
• return 0;
• }
Program
void jobSequencingWithDeadline(Job jobs[], int n) {
int i, j, k, maxprofit;
int timeslot[MAX];
int filledTimeSlot = 0;
int dmax = 0;
for(i = 0; i < n; i++) {
if(jobs[i].deadline > dmax) {
dmax = jobs[i].deadline;
}
}
//free time slots initially set to -1 [-1 denotes EMPTY]
for(i = 1; i <= dmax; i++) {
timeslot[i] = -1;
}
printf("dmax: %d\n", dmax);
Program
for(i = 1; i <= n; i++) {
k = minValue(dmax, jobs[i - 1].deadline);
while(k >= 1) {
if(timeslot[k] == -1) {
timeslot[k] = i-1;
filledTimeSlot++;
break;
}
k--;
}
//if all time slots are filled then stop
if(filledTimeSlot == dmax) {
break;
}
}
Program
//required jobs
printf("\nRequired Jobs: ");
for(i = 1; i <= dmax; i++) {
printf("%s", jobs[timeslot[i]].id);
if(i < dmax) {
printf(" --> ");
}
}
//required profit
maxprofit = 0;
for(i = 1; i <= dmax; i++) {
maxprofit += jobs[timeslot[i]].profit;
}
printf("\nMax Profit: %d\n", maxprofit);
}
Time Complexity
• The time complexity of this problem is O(n^2).
Thank You
• Mahyavanshi Rohan
• Katara Aryan
