Buscar en Google Scholar
Título: 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
Otros títulos: 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
Asesor(es): Birgin Goldberg, Ernesto Julian
Campo OCDE: https://purl.org/pe-repo/ocde/ford#1.02.01
Fecha de publicación: oct-2017
Institución: Universidade de São Paulo
Resumen: 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.
Identificador DOI: https://doi.org/10.11606/D.45.2018.tde-11122017-123449
Nota: 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
Disciplina académico-profesional: Ciencias de la Computación
Institución que otorga el grado o título: Universidade de São Paulo. Instituto de Matemática e Estatística
Grado o título: Maestro en Ciencias
Jurado: Goldberg Birgin, Ernesto Julian; Mesquita, Marco Aurelio de; Muniz de Oliveira, Alexandre Cesar
Fecha de registro: 15-mar-2023

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
DelgadoVasqueJC.pdf
  Acceso restringido
Disertación (abierta en repositorio de origen)568.59 kBAdobe PDFVisualizar/Abrir  Solicita una copia
Autorizacion.pdf
  Acceso restringido
Autorización del registro1.65 MBAdobe PDFVisualizar/Abrir  Solicita una copia


IMPORTANTE
La información contenida en este registro es de entera responsabilidad de la universidad, institución o escuela de educación superior que administra el repositorio académico digital donde se encuentra el trabajo de investigación y/o proyecto, los cuales son conducentes a optar títulos profesionales y grados académicos. SUNEDU no se hace responsable por los contenidos accesibles a través del Registro Nacional de Trabajos de Investigación – RENATI.