Suppose you have one machine and a set of n jobs a1, a2,.... ,an to process on t

Question

Suppose you have one machine and a set of n jobs a1, a2,.... ,an to process on that machine. Each job aj has processing time tj, a profit pj , and a deadline dj. The machine can process only one job at a time, and a job must run uninterruptedly for tj consecutive time units once it starts execution. If a given job aj is completed by its deadline dj , you receive a prot of pj ; otherwise, if the job aj is completed after its deadline, you receive a profit of 0. Give an algorithm to nd the schedule that obtains the maximum amount of prot, assuming that all processing times are integers between 1 and n. (Hint: You will need to show that scheduling jobs in increasing order of their deadline is the optimal scheduling approach. Also, the running time of your dynamic programming algorithm should be in terms of n and Dmax = Max j and n = 1 {dj} ).

Explanation / Answer

Let d = dn denote the latest deadline. Define table A[i][j] for 0 = i = n and 0 = j = d as: A[i][j] = maximum profit of any feasible using only jobs from {1, …, i} and jobs finishing by time j. We are to find A[n][d]. Let t’ denote the latest possible time to schedule job j given that it must complete by deadline j and deadline di. t’ = min(j, di) – t’. A[i][j] = { 0 if i = 0, A[i-1][j] if i!= 0 and t’ < 0, max (A[i-1][j], A[i-1][t'] + pi). } This runs in time O(nd).

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.