• 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
 
 
Dissertação de Mestrado
DOI
https://doi.org/10.11606/D.18.2020.tde-16112021-120034
Documento
Autor
Nome completo
Gustavo Alencar Rolim
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Carlos, 2020
Orientador
Banca examinadora
Nagano, Marcelo Seido (Presidente)
Prata, Bruno de Athayde
Tavares Neto, Roberto Fernandes
Título em inglês
Heuristics and stochastic local search for just-in-time scheduling of parallel machines against common restrictive due windows
Palavras-chave em inglês
Common due window
Earliness and Tardiness
Heuristics
Parallel machines
Scheduling
Stochastic local search
Resumo em 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 em 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
Palavras-chave em português
Atraso e adiantamento
Busca local estocástica
Heurísticas
Janelas de tempo comuns
Máquinas paralelas
Sequenciamento
Resumo em 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.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2021-11-29
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2022. Todos os direitos reservados.