Greedy Technic

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.

Basics

  1. Solution Space :-      It is set of all possible solutions for the given input.
  2. Feasible Solution :- It is set of all possible solutions that will satisfy our condition.
  3. 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.

  1. Single CPU :- It is the only employee of doing all problems of Job Sequencing with   deadlines.
  2. Arrival Time Same :- All jobs will arrive at the same time so we can’t take any job       directly.
  3. 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.
  4. No-Preemption :- We can’t stop in mid, that is if the system starts work then that will complete work without stopping.

 

For Example:-

n=4

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.

Solution:-

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.

Similarly,

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.

Hence,

(J4,J3) Total Profit = 350+250=600 is our Optimal solution.

 

 

For any query please follow blog and send mail on CONTACT page.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s