Maximizando el trabajo total temprano en un taller de flujo de dos máquinas

Resumen El problema de maximizar el trabajo total temprano en un taller de flujo de dos máquinas, en el que n trabajos deben ser programados sujeto a una fecha de vencimiento común d, ha sido estudiado recientemente en la literatura de programación. Se presentó primero un algoritmo de programación dinámica de tiempo O(n²d⁴) para el caso ponderado, y luego para el caso no ponderado se propuso otro algoritmo de programación dinámica con un tiempo de ejecución O(n²d²) y se convirtió en un esquema de aproximación polinómica de tiempo totalmente preciso (FPTAS). Al establecer nuevas propiedades del problema, presentamos un algoritmo de programación dinámica de tiempo O(nd²) y un FPTAS de tiempo para el problema no ponderado. Generalizamos el problema a un entorno distribuido de m talleres de flujo de dos máquinas en paralelo, desarrollamos un algoritmo de programación dinámica de tiempo O(nd³m), un FPTAS de tiempo y tres formulaciones de programación lineal entera (ILP) para ello. Se realizan experimentos computacionales para evaluar los modelos ILP propuestos.