1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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 FPNP.

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.]

$\endgroup$
2
  • 1
    $\begingroup$ the inequality $\sum_{1 \le i\le k}{t(a_i)} \le d(k)$ doesn't actually make sense. You probably meant to say $\sum_{1 \le i\le k}{t(a_i)} \le d(a_k)$ for every $k$. $\endgroup$
    – xdavidliu
    May 2, 2021 at 4:34
  • $\begingroup$ @xdavidliu Thanks for spotting the typo $\endgroup$ May 2, 2021 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.