• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Disertación de Maestría
DOI
https://doi.org/10.11606/D.18.2020.tde-16112021-120034
Documento
Autor
Nombre completo
Gustavo Alencar Rolim
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Carlos, 2020
Director
Tribunal
Nagano, Marcelo Seido (Presidente)
Prata, Bruno de Athayde
Tavares Neto, Roberto Fernandes
Título en inglés
Heuristics and stochastic local search for just-in-time scheduling of parallel machines against common restrictive due windows
Palabras clave en inglés
Common due window
Earliness and Tardiness
Heuristics
Parallel machines
Scheduling
Stochastic local search
Resumen en inglés
This study deals with earliness and tardiness scheduling around common due dates and windows. Related problems share a strong practical importance due to the endogenous and exogenous cost structures that occur within just-in-time production systems. Despite of their significance, there are no recent research that holistically address the two main variants of the problems in terms of the common due date (window) approach. We fill this gap by surveying over 200 papers, which cover more than 40 years of scheduling literature and classifying algorithms for problems where the due date (window) is a given constraint as well as the ones where it is a decision variable. New notations and a comprehensive framework that includes a wide range of earliness and tardiness scheduling problems are introduced. Moreover, a total of 26 structural properties and the computational complexity of available algorithms for single, parallel, and flow-shop machine environments are summarized. From the literature review, we selected the just-in-time parallel machine scheduling problem against common restrictive due windows that is known to be NP-hard. Since there is no procedure available for solving instances with more than 40 jobs, we propose a family of heuristics and report promising results for instances with up to 500 jobs in size. Moreover, the best performing heuristic is combined with a stochastic local search (iterated greedy algorithm) to improve the solutions previously found.
Título en portugués
Heurísticas e busca local estocástica para o sequenciamento just-in-time de máquinas paralelas sujeitas a janelas de tempo restritivas comuns
Palabras clave en portugués
Atraso e adiantamento
Busca local estocástica
Heurísticas
Janelas de tempo comuns
Máquinas paralelas
Sequenciamento
Resumen en portugués
Este estudo lida com problemas de sequenciamento com penalidades por atrasos e adiantamentos submetidos a prazos de entrega os quais podem ser representados por um instante ou intervalo de tempo. Problemas relacionados compartilham um forte viés prático, tendo em vista a às naturezas exógenas e endógenas das estruturas de custo que ocorrem em sistemas de produção just-in-time. Apesar da importância desses problemas, não há estudos recentes que abordam as suas duas principais variantes. Cobrimos essa lacuna através de uma revisão de mais de 200 artigos que representam mais de 40 anos de literatura. Também classificamos algoritmos para os casos onde os prazos (janelas) comuns de entrega são um parâmetro previamente estabelecido, assim como aqueles onde os prazos (janelas) são uma variável de decisão. Novas notações são introduzidas e um quadro de classificação que inclui uma vasta diversidade de problemas relacionados a atrasos e adiantamentos são introduzidos. Ademais, um total de 26 propriedades estruturais e a complexidade computacional de algoritmos para os casos de máquinas únicas, paralelas e flow-shop são sumarizadas. A partir da revisão de literatura, selecionamos um problema relativo ao sequenciamento just-in-time de máquinas paralelas submetidas a janelas de entrega restritivas comuns, o qual é conhecido por ser NP-difícil. Pelo fato de não existir procedimentos de resolução para problemas com mais de 40 tarefas, propomos uma família de heurísticas com desempenho promissor e capazes de resolver instâncias com até 500 tarefas. Além disso, a heurística com melhor desempenho é combinada com uma busca local estocástica (Iterated Greedy) que é capaz de melhorar ainda mais as soluções previamente encontradas.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2021-11-29
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2022. Todos los derechos reservados.