Look-up in Google Scholar
Title: 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
Other Titles: Programación de tareas en un ambiente flow shop con m máquinas para la minimización del desvío absoluto total de una fecha de entrega común
Advisor(s): Birgin Goldberg, Ernesto Julian
OCDE field: https://purl.org/pe-repo/ocde/ford#1.02.01
Issue Date: Oct-2017
Institution: Universidade de São Paulo
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.
DOI identifier: https://doi.org/10.11606/D.45.2018.tde-11122017-123449
Note: Descargue el texto completo en el repositorio institucional de la Universidade de São Paulo: https://doi.org/10.11606/D.45.2018.tde-11122017-123449
Discipline: Ciencias de la Computación
Grade or title grantor: Universidade de São Paulo. Instituto de Matemática e Estatística
Grade or title: Maestro en Ciencias
Juror: Goldberg Birgin, Ernesto Julian; Mesquita, Marco Aurelio de; Muniz de Oliveira, Alexandre Cesar
Register date: 15-Mar-2023

Files in This Item:
File Description SizeFormat 
DelgadoVasqueJC.pdf
  Restricted Access
Disertación (abierta en repositorio de origen)568.59 kBAdobe PDFView/Open Request a copy
Autorizacion.pdf
  Restricted Access
Autorización del registro1.65 MBAdobe PDFView/Open Request a copy


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.