Programação de tarefas em um ambiente flow shop com m máquinas para a minimização do desvio absoluto total de uma data de entrega comum

Abstract

En este trabajo abordamos el problema de programación de tareas en un ambiente flow shop permutacional con más de dos máquinas. Restringimos el estudio para eI caso en que todas las tareas tienen una fecha de entrega común y restrictiva, y donde el objetivo es minimizar la suma total de los adelantamientos y atrasos de las tareas en relación a tal fecha de entrega. Es asumido también un ambiente estático y determinístico. Habiendo soluciones con el mismo costo, preferimos aquellas que envuelven menos tiempo de espera en el buffer entre cada máquina. Debido a la dificultad de resolver el problema, incluso para instancias pequeñas, presentamos un abordaje heurístico para tal, el cual está basado en búsqueda local y hace uso de un algoritmo lineal para atribuir fechas de conclusión a las tareas en la última máquina. Este algoritmo se basa en algunas propiedades analíticas inherentes a las soluciones óptimas. Además, se desenvolvió una formulación matemática del problema en programación lineal entera mixta (PLEM) que permite validar la eficacia de nuestro abordaje. Examinamos también el desempeño de las heurísticas con pruebas estándar (benchmarks) y comparamos nuestros resultados con otros obtenidos en la literatura.

Neste trabalho abordamos o problema de programação de tarefas em um ambiente flow shop permutacional com mais de duas máquinas. Restringimos o estudo para o caso em que todas as tarefas têm uma data de entrega comum e restritiva, e onde o objetivo é minimizar a soma total dos adiantamentos e atrasos das tarefas em relação a tal data de entrega. É assumido também um ambiente estático e determinístico. Havendo soluções com o mesmo custo, preferimos aquelas que envolvem menos tempo de espera no buffer entre cada máquina. Devido à dificuldade de resolver o problema, mesmo para instâncias pequenas (o problema pertence à classe NP-difícil), apresentamos uma abordagem heurística para lidar com ele, a qual está baseada em busca local e faz uso de um algoritmo linear para atribuir datas de conclusão às tarefas na última máquina. Este algoritmo baseia-se em algumas propriedades analíticas inerentes às soluções ótimas. Além disso, foi desenvolvida uma formulação matemática do problema em programação linear inteira mista (PLIM) que vai permitir validar a eficácia da abordagem. Examinamos também o desempenho das heurísticas com testes padrões (benchmarks) e comparamos nossos resultados com outros obtidos na literatura.