El problema, tal y como lo planteas en el post, es encontrar el máximo beneficio. No se trata de problema de decisión por lo que no puede ser NP-completo por definición.
Así pues, consideremos un problema de decisión estrechamente relacionado: dejemos que $A$ sea un conjunto de tareas, cada tarea $a$ con un tiempo de ejecución asociado $t(a)$ Beneficio $p(a)$ y plazo $d(a)$ y que $B$ sea un número entero positivo. ¿Existe una secuencia de tareas distintas $a_1, a_2, \ldots, a_n$ en $A$ tal que $\sum_{1 \le i\le k}{t(a_i)} \le d(a_k)$ (es decir, cada tarea se completa dentro de su plazo) y $\sum_{1 \le i \le n} p(a_i) \ge B$ (es decir, el beneficio total de las tareas es de al menos $B$ )?
Este problema está claramente en NP (es fácil comprobar en tiempo polinómico que un horario dado cumple las condiciones) y se puede demostrar que es NP-duro, por una reducción de SUBSET SUM :
-
Supongamos que tenemos una instancia de SUBSET SUM, en forma de conjunto finito $A$ un tamaño $s(a) \in Z^+$ para cada $a \in A$ y un número entero positivo $B$ el problema es determinar si hay un subconjunto $A′ \subseteq A$ tal que $\sum_{a\in A′}s(a) = B$ .
-
Entonces el problema de secuenciación correspondiente tiene $t(a) = p(a) = s(a)$ y $d(a) = B$ .
Un argumento estándar para reducir un problema de optimización al correspondiente problema de decisión muestra que su problema original (encontrar el máximo beneficio) está en la clase FP NP .
La versión de decisión de su problema es [SS3] SEQUENCING TO MINIMIZE TARDY TASK WEIGHT en Garey & Johnson, Ordenadores e intratabilidad donde los autores añaden:
Puede resolverse en tiempo pseudopolinómico (tiempo polinómico en $\left|A\right|$ , $\sum{t(a)}$ y $\log \sum {p(a)}$ ) [Lawler & Moore (1969), "A functional equation and its applications to resource allocation and sequencing problems," Ciencias de la gestión 16 pp. 77-84.]
