Programación de los plazos de beneficios $NP$ -completitud

Question

Sea $A$ sea un conjunto de $n$ tareas, { $a_1,…,a_n$ }, cada una con un tiempo de ejecución asociado, $t_i$ ganancias, $p_i$ y plazo $d_i$ . Sólo puede ejecutar una tarea a la vez; si la tarea no se completa antes de su fecha límite asociada, entonces no recibe su beneficio. ¿Cómo obtener el máximo beneficio? Demuestre que la tarea está completa.

He intentado hacer una reducción al Problema del Vendedor Viajero. El grafo dirigido tiene aristas con peso $p_i$ entre $a_i$ , $a_j$ vértices si $d_i$ < $d_j$ pero me perdí $t_i$ . ¿Cómo modificar esto o hacer otra reducción?

Answer 1

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