Coding_wolrd
Job Sequencing with deadline
If there are n jobs i.e j1,j2, j3,......jn & those jobs are assosiated with deadline d1,d2,d3 ... dn
having some profit p1,p2,p3 ... pn
Then object is to achieve max profit when only one job is scheduling at any given time.
Job Sequencing With Deadlines :-
The sequencing of jobs on a single processor with deadline constraints is called as Job Sequencing with Deadlines.
How can the total profit be maximized if only one job can be completed at a time?
Here :-
- You are given a set of jobs.
- Only one processor is available for processing all the jobs.
- The profit of a job is given only when that job is completed within its deadline.
- Each job has a defined deadline and some profit associated with it.
- Processor takes one unit of time to complete a job.
Approach to Solution:-
- Value of the feasible solution would be the sum of profit of all the jobs contained in the subset.
- A feasible solution would be a subset of jobs where each job of the subset gets completed within its deadline.
- An optimal solution of the problem would be a feasible solution which gives the maximum profit.
Greedy Algorithms:-
- Greedy Algorithm is adopted to determine how the next job is selected for an optimal solution.
- The greedy algorithm described below always gives an optimal solution to the job sequencing problem.
Step of solving problem :-
Step- 01.
- Sort all the given jobs in decreasing order of their profit.
Step- 02.
- Check the value of maximum deadline.
- Draw a Gantt chart where maximum time on Gantt chart is the value of maximum deadline.
Step- 03.
- Pick up the jobs one by one.
- Put the job on Gantt chart as far as possible from 0 ensuring that the job gets completed before its deadline.
PRACTICE PROBLEM BASED ON JOB SEQUENCING WITH DEADLINES:-
Problem-
Given the jobs, their deadlines and associated profits as shown-
| jobs | Deadline | Profit |
|---|---|---|
| j1 | 20 | 2 |
| j2 | 15 | 2 |
| j3 | 10 | 1 |
| j4 | 5 | 3 |
| j5 | 1 | 3 |
soluation:- maximum deadline = 3.
| jobs | Slot | select job | profit |
|---|---|---|---|
| j1 | [1,2] | j1 | 20 |
| j2 | [0,1] [1,2] | j1, j2 | 20+15 |
| j4 | [0,1][1,2][2,3] | j1 , j2 ,j4 | 20+15+5 |
| Total | 40 |
Answer:- maximum profit = 40.
How to write algorithm :-
- Arrange all jobs in descending order of profit
- for each job (m) do Linear search
- finding particular slot in order of size (n)
- where : n = maximum deadline
- m = total job
Note:-
1.It is uniprocesser i.e if select one job they have to complet the given job . No preemption allowed
2. every job take 1 unit Time
Implement coding
-
tab1
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;// Data structure to store job details. Each job has an identifier,
// a deadline, and profit associated with it.class Job
{
public int taskID, deadline, profit;
public Job(int taskID, int deadline, int profit)
{
this.taskID = taskID;
this.deadline = deadline;
this.profit = profit;
}
}class Main
{
// Function to schedule jobs to maximize profit
public static void scheduleJobs(Listjobs, int T)
{
// stores the maximum profit that can be earned by scheduling jobs
int profit = 0;
// array to store used and unused slots info
int[] slot = new int[T];
Arrays.fill(slot, -1);
// arrange the jobs in decreasing order of their profits
Collections.sort(jobs, (a, b) -> b.profit - a.profit);
// consider each job in decreasing order of their profits
for (Job job: jobs)
{
// search for the next free slot and map the task to that slot
for (int j = job.deadline - 1; j >= 0; j--)
{
if (j < T && slot[j] == -1)
{
slot[j] = job.taskID;
profit += job.profit;
break;
}
}
}// print the scheduled jobs
System.out.println("The scheduled jobs are " + Arrays.stream(slot).filter(val -> val != -1).boxed() .collect(Collectors.toList()));
// print total profit that can be earned
System.out.println("The total profit earned is " + profit);
} public static void main(String[] args)
{
// List of given jobs. Each job has an identifier, a deadline, and
// profit associated with it
Listjobs = Arrays.asList(
new Job(1, 9, 15), new Job(2, 2, 2),
new Job(3, 5, 18), new Job(4, 7, 1),
new Job(5, 4, 25), new Job(6, 2, 20),
new Job(7, 5, 8), new Job(8, 7, 10),
new Job(9, 4, 12), new Job(10, 3, 5)
); // stores the maximum deadline that can be associated with a job
final int T = 15;
// schedule jobs and calculate the maximum profit
scheduleJobs(jobs, T);
}
} -
# A class to store job details. Each job has an identifier,
# a deadline, and profit associated with it.class Job:
def __init__(self, taskID, deadline, profit):
self.taskID = taskID
self.deadline = deadline
self.profit = profit# Function to schedule jobs to maximize profit
def scheduleJobs(jobs, T):# stores the maximum profit that can be earned by scheduling jobs
profit = 0# list to store used and unused slots info
slot = [-1] * T
# arrange the jobs in decreasing order of their profits
jobs.sort(key=lambda x: x.profit, reverse=True)
# consider each job in decreasing order of their profits
for job in jobs:# search for the next free slot and map the task to that slot
for j in reversed(range(job.deadline)):if j < T and slot[j] == -1:
slot[j] = job.taskID
profit += job.profit
break# print the scheduled jobs
print("The scheduled jobs are", list(filter(lambda x: x != -1, slot)))
# print total profit that can be earned
print("The total profit earned is", profit)if __name__ == '__main__':
# List of given jobs. Each job has an identifier, a deadline, and
# profit associated with itjobs = [
Job(1, 9, 15), Job(2, 2, 2),
Job(3, 5, 18), Job(4, 7, 1),
Job(5, 4, 25), Job(6, 2, 20),
Job(7, 5, 8), Job(8, 7, 10),
Job(9, 4, 12), Job(10, 3, 5)
]
# stores the maximum deadline that can be associated with a job
T = 15# schedule jobs and calculate the maximum profit
scheduleJobs(jobs, T)
Greedy Method
No comments:
Post a Comment