Programación en una sola máquina con el costo total ponderado del trabajo tardío y el costo de rechazo

Resumen: Estudiamos un problema de programación en una sola máquina con el costo total ponderado del trabajo tardío y el costo total de rechazo. El trabajo tardío de un trabajo es la parte de este trabajo ejecutada después de su fecha de vencimiento, y el costo de rechazo de un trabajo es la tarifa por rechazar su procesamiento. Consideramos un problema de programación de Pareto y dos problemas de programación restringidos. El problema de programación de Pareto tiene como objetivo encontrar todos los valores no dominados del costo total ponderado del trabajo tardío y el costo total de rechazo. Los problemas de programación restringidos están dedicados a minimizar el costo total ponderado del trabajo tardío con el costo total de rechazo no mayor que un umbral dado, y minimizar el costo total de rechazo con el costo total ponderado del trabajo tardío no mayor que un umbral dado, respectivamente. Para el problema de programación de Pareto, demostramos que es NP-duro binario proporcionando un algoritmo de tiempo pseudo-polinómico, y damos un esquema de aproximación de tiempo polinómico totalmente (FPTAS). Para los problemas de programación restringidos, demostramos que no hay FPTAS a menos que lo cual responde a un problema abierto. Además, desarrollamos FPTAS relajados para estos dos problemas de programación restringidos.