Heurísticas e busca local estocástica para o sequenciamento just-in-time de máquinas paralelas sujeitas a janelas de tempo restritivas comuns

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.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