34-4 Scheduling with profits and deadlines

Suppose that we have one machine and a set of $n$ tasks $a_1, a_2, \dots, a_n$, each of which requires time on the machine. Each task $a_j$ requires $t_j$ time units on the machine (its processing time), yields a profit of $p_j$, and has a deadline $d_j$. The machine can process only one task at a time, and task $a_j$ must run without interruption for $t_j$ consecutive time units. If we complete task $a_j$ by its deadline $d_j$, we receive a profit $p_j$, 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 $\text{NP-complete}$.

c. Give a polynomial-time algorithm for the decision problem, assuming that all processing times are integers from $1$ to $n$. ($\textit{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$.

(Omit!)