Algorithm

job sequencing problem with deadlines using greedy method with pseudo code and examples .

1. GREEDY METHOD (Job sequencing with deadlines) Tamanjana Ghosal(1882005) Debleena Biswas(1882031)

2. Contents What is GREEDY METHOD? What is JOB SEQUENCING PROBLEM WITH DEADLINES? Algorithm of the problem Pseudo Code of the problem Example

3. What is GREEDY METHOD? Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. So the problems where choosing locally optimal also leads to global solution are best fit for Greedy.

4. What is JOB SEQUENCING PROBLEM? The problem consists of n jobs each associated with a deadline and profit and our objective is to earn maximum profit. We will earn profit only when job is completed on or before deadline. We assume that each job will take unit time to complete.

5. In this problem we have n jobs each has an associated deadline d1, d2, … dn and profit p1, p2, ... pn . Profit will only be awarded or earned if the job is completed on or before the deadline. We assume that each job takes unit time to complete. The objective is to earn maximum profit when only one job can be scheduled or processed at any given time. Points to remember

6. Greedy Algorithm to solve the problem

7. < The jobs are sorted in decreasing order of profit. The maximum deadline(dmax) is the size of the result sequence or the timeslot array.> for i = 1 to n do Set k = DEADLINE(i) //where DEADLINE(i) denotes deadline of ith job while k >= 1 do if timeslot[k] is EMPTY then timeslot[k] = job(i) break end if set k = k - 1 end while end for Pseudo code NOTE: The time complexity of this method is O(n^2) where n is the number of jobs.

8. Total Profit:(100+60+20)units = 180 units INDEX JOB DEADLINE PROFIT 1 J1 2 60 2 J2 1 100 3 J3 3 20 4 J4 2 40 5 J5 1 20 INDEX JOB DEADLINE PROFIT 1 J2 1 100 2 J1 2 60 3 J4 2 40 4 J3 3 20 5 J5 1 20 TIME SLOT 1 2 3 JOB EMPTY EMPTY EMPTY TIME SLOT 1 2 3 JOB J2 EMPTY EMPTY TIME SLOT 1 2 3 JOB J2 J1 EMPTY TIME SLOT 1 2 3 JOB J2 J1 J3 Example :

9. Thank You !!!