Resumen

Consideramos los problemas de programación de trabajos deteriorados con fechas de lanzamiento en una sola máquina (máquinas paralelas) y los trabajos pueden rechazarse pagando penalizaciones. El tiempo de procesamiento de un trabajo es una función lineal simple creciente de su hora de inicio. Para un modelo de una sola máquina, el objetivo es minimizar el retraso máximo de los trabajos aceptados más la penalización total de los trabajos rechazados. Demostramos que el problema es NP-difícil en el sentido fuerte y presentamos un esquema de aproximación en tiempo polinomial para resolverlo cuando todos los trabajos tienen fechas de lanzamiento y fechas de vencimiento aceptables. Para el modelo de máquinas paralelas, el objetivo es minimizar el tiempo máximo de entrega de los trabajos aceptados más la penalización total de los trabajos rechazados. Cuando los trabajos tienen fechas de entrega idénticas, primero proponemos un esquema de aproximación en tiempo polinómico para resolverlo. A continuación, presentamos un algoritmo heurístico para el caso en el que todos los trabajos deben ser aceptados y evaluamos su eficacia mediante experimentos computacionales.

• Materias:Matemáticas Análisis Matemático Álgebra Ingeniería Lógica matemática
• Subjects:mathematics Mathematical Analysis Algebra Engineering Mathematical logic
• Palabras claves:trabajos, esquema de aproximación en tiempo polinómico, penalización total, plazo máximo de entrega, fechas de entrega aceptables, fechas de entrega idénticas, modelo de máquina única, objetivo, experimentos computacionales, fechas de vencimiento
• Keywords:jobs, polynomial time approximation scheme, total penalty, maximum delivery completion time, agreeable release dates, identical release dates, single machine model, objective, computational experiments, due dates