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!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用