1 Write an algorithm for job scheduling using greedy approach with suitable example.

Q.

Algorithm:

JobSceduling(d[1…n],p[1…n],N)

{

            S={1}

            for(i=2 to N)

            {

                        if(all jobs in s union i(s U {i}) Schedule by a deadline)

                        {

                                    S=S U {i}

                                    return s;

                        }

            }

}

Example:-

Problem: n jobs, S={1, 2, …, n}, each job i has a deadline di  and a profit pi . We need one unit of time to process each job and we can do at most one job each time. We can earn the profit pi if job i is completed by its deadline.

Jobs	J 1	J 2	J 3	J 4	J 5
Profit	20	15	10	5	1
Deadline	2	1	1	3	3

Deadline 1:   {j2,j3}

                        {15,10}

Deadline 2:   {j1}

                         {20}

Deadline 3:   { j4, j5}

                        {5,1}

The optimal solution = {1, 2, 4}.

The total profit = 20 + 15 + 5 = 40