Casos solubles en tiempo polinomial para el problema 1|ri ∈ {r 1 , r2}, qi ∈ {q 1 , q2}|Cmax y la reducción al problema ´ SUBSET SUM

Estudiamos un problema de calendarización para una sola máquina con dos tiempos de liberación permitidos y dos tiempos de entrega permitidos. Este es un caso especial del problema general de calendarización NP-duro en sentido estricto con una sola máquina, en donde se cuenta con un número arbitrario de tiempos de liberación y un número arbitrario de tiempos de entrega, con el objetivo de minimizar el máximo tiempo de completes total. Nuestro problema resulta ser más transparente y accesible que la versión general, por lo que podemos realizar un análisis y obtener algunas propiedades de manera simple y que sean eficientes para solucionarlo.