Let me introduce greedy technique basics first, Most of the greedy techniques have (n) no. of inputs and output is subset of that (n) inputs. which satisfies our conditions and give feasible and optimal solutions.
- Solution Space :- It is set of all possible solutions for the given input.
- Feasible Solution :- It is set of all possible solutions that will satisfy our condition.
- Optimal Solution :- It is Best solution among all feasible solutions or we can say that it optimizes our solution further.
Job Sequencing With Deadlines
Job sequencing is a part of greedy technique in algorithm and design, there are mainly four points which we have to remember to solve any kind of problem in Job sequencing with deadlines.
- Single CPU :- It is the only employee of doing all problems of Job Sequencing with deadlines.
- Arrival Time Same :- All jobs will arrive at the same time so we can’t take any job directly.
- 1 Unit Running Time for Each Job :- Each job will run a single running time we can also see this as the for each job time of completion is 1 unit.
- No-Preemption :- We can’t stop in mid, that is if the system starts work then that will complete work without stopping.
Jobs Profits Deadlines
J1 200 2
J2 300 1
J3 250 2
J4 350 1
We have to find the optimal solution for this Job scheduling problem.
As deadlines are given as 2,1,2 and 1 means we have to choose only best two which will give us the optimal solution.
For this let check all possible sets of feasible solutions
1. First (0) Means No work at all.
It’s also a feasible solution but not optimal.
Total Cost = Profit
2. (J1) Total Cost 200
3. (J2) Total Cost 300
4. (J3) Total Cost 250
5. (J5) Total Cost 350
This Four Single set of solutions are also possible feasible solutions but they are not optimal.
Now, check with two jobs
let take deadlines as months for easiness
6. (J1, J2) is not possible because J1 can complete job in either first month or second but for J2 deadline is 1 month only so, J2 can not complete after anyone it has to complete first.
(J2,J1) is Possible as J2 Will Complete job in first month and after it J1 can do job as J1 can do job either first or in second. As J2 has 2 months deadline.Total Cost =300+200=500.
7. (J1, J3) Total Cost = 200+250= 450.As both J1 and j3 has two months deadlines so from both they can do task from themselves on any sequence.
8. (J3, J1) Total Cost = 250+200=450. Same as above.
9.( J4, J1) Total Cost = 350+200=550. Same reason as for solution 6. (As Dead line of J4 is 1 month so J4 has to do work in first month and after it J1 can do)
10. (J4,J3) Total Cost = 350+250=600 .
11. (J2,J3) Total Cost = 300+250=550.
Now, all feasible solutions that can be possible is written above among them 10th feasible solution is most Optimal as total cost or total profit is 600 which is greatest among them.
(J4,J3) Total Profit = 350+250=600 is our Optimal solution.
For any query please follow blog and send mail on CONTACT page.