• 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
 
 
Master's Dissertation
DOI
https://doi.org/10.11606/D.18.2020.tde-16112021-120034
Document
Author
Full name
Gustavo Alencar Rolim
Institute/School/College
Knowledge Area
Date of Defense
Published
São Carlos, 2020
Supervisor
Title in English
Heuristics and stochastic local search for just-in-time scheduling of parallel machines against common restrictive due windows
Abstract in English
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.
Title in Portuguese
Heurísticas e busca local estocástica para o sequenciamento just-in-time de máquinas paralelas sujeitas a janelas de tempo restritivas comuns
Abstract in Portuguese
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.
 
Publishing Date
2021-11-29
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2022. All rights reserved.