Scheduling profit deadlines $NP$-completeness

Question

Let $A$ be a set of $n$ tasks, {$a_1,…,a_n$}, each with an associated execution time, $t_i$, profit, $p_i$, and deadline $d_i$. You can only execute one task at a time; if the task does not complete before its associated deadline, then you do not receive its profit. How to get maximum profit? Prove completeness.

I have tried to make reduction to Traveling Salesman Problem. Directed graph has edge with weight $p_i$ between $a_i$, $a_j$ vertexes if $d_i$ < $d_j$, but I missed $t_i$. How to modify this or make another reduction?

Answer 1

The problem, as you state it in the post, is to find the maximum profit. This is not a decision problem and so it can't be NP-complete by definition.

So let's consider a closely related decision problem: let $A$ be a set of tasks, each task $a$ having an associated execution time $t(a)$, profit $p(a)$, and deadline $d(a)$, and let $B$ be a positive integer. Is there a sequence of distinct tasks $a_1, a_2, \ldots, a_n$ in $A$ such that $\sum_{1 \le i\le k}{t(a_i)} \le d(a_k)$ (that is, each task completes by its deadline) and $\sum_{1 \le i \le n} p(a_i) \ge B$ (that is, total profit of the tasks is at least $B$)?

This problem is clearly in NP (it's easy to check in polynomial time that a given schedule meets the conditions) and it can be shown to be NP-hard, by a reduction from SUBSET SUM:

• Suppose we have an instance of SUBSET SUM, in the form of a finite set $A$, a size $s(a) \in Z^+$ for each $a \in A$, and a positive integer $B$, the problem being to determine if there is a subset $A′ \subseteq A$ such that $\sum_{a\in A′}s(a) = B$.

• Then the corresponding sequencing problem has $t(a) = p(a) = s(a)$ and $d(a) = B$.

A standard argument for reducing an optimization problem to the corresponding decision problem shows that your original problem (to find the maximum profit) is in the class FP^NP.

The decision version of your problem is [SS3] SEQUENCING TO MINIMIZE TARDY TASK WEIGHT in Garey & Johnson, Computers and Intractability, where the authors add:

Can be solved in pseudo-polynomial time (time polynomial in $\left|A\right|$, $\sum{t(a)}$, and $\log \sum {p(a)}$) [Lawler & Moore (1969), "A functional equation and its applications to resource allocation and sequencing problems," Management Science 16 pp. 77–84.]