Scheduling with profits and deadlines Suppose that we have

Chapter 34, Problem 34-4

(choose chapter or problem)

Scheduling with profits and deadlines Suppose that we have one machine and a set of n tasks a1; a2;:::;an, each of which requires time on the machine. Each task aj requires tj time units on the machine (its processing time), yields a profit of pj , and has a deadline dj . The machine can process only one task at a time, and task aj must run without interruption for tj consecutive time units. If we complete task aj by its deadline dj , we receive a profit pj , but if we complete it after its deadline, we receive no profit. As an optimization problem, we are given the processing times, profits, and deadlines for a set of n tasks, and we wish to find a schedule that completes all the tasks and returns the greatest amount of profit. The processing times, profits, and deadlines are all nonnegative numbers. a. State this problem as a decision problem. b. Show that the decision problem is NP-complete. c. Give a polynomial-time algorithm for the decision problem, assuming that all processing times are integers from 1 to n. (Hint: Use dynamic programming.) d. Give a polynomial-time algorithm for the optimization problem, assuming that all processing times are integers from 1 to n.