Abordagens para resolver o problema integrado de dimensionamento de lotes e scheduling em máquinas paralelas
Data
2019-02-25
Autores
Carvalho, Desiree Maldonado 
Orientadores
Rosset, Maria Cristina Vasconcelos Nascimento
Tipo
Tese de doutorado
Título da Revista
ISSN da Revista
Título de Volume
Resumo
This study approaches the integrated lot sizing and scheduling problem (ILSSP), in which non-identical machines work in parallel with sequence-dependent non-triangular (NT) setup costs and times, setup carr y-over and capacity limitation. The aim of the studied ILSSP, called here ILSSP-NT on parallel machines, is to deter mine a production planning and tasks sequencing which meet the period demands without delay, in such a way that the total costs of production, machine setup and inventor y are minimized. The dearth of literature on the ILSSP-NT on parallel machines and the researchers interest to approach it motivated the study perfor med in this thesis. The aim of this thesis is the development of efficient solution methods to the ILSSP-NT on parallel machines, in particular, the proposal of matheuristics. To this end, it was performed an analysis of the main for mulations designed to the ILSSP-NT found in the literature, adapted to the problem with parallel machines. The pur pose was defining which for mulation could contribute to the best computational performance of solver CPLEX v. 12. 7. 1 limited by a period of time to solve instances from the literature, adapted to the problem with non-triangular setup costs and times. Besides this analysis, in a first moment, we performed a study on the capacitated lot sizing problem (CLSP) on parallel machines where we proposed a math-heuristic based in a Lagrangian heuristic and a method known as kernel search. Such method aimed the solution of the CLSP on parallel machines with SC and inspired the development of one of the methods proposed to the ILSSP-NT on parallel machines. The methods we propose to find solutions to the ILSSP-NT on parallel machines consist, virtually in the hybridization of relax-and-fix and fix-and-optimize methods with path-relinking and kernel search heuristics. Computational experiments attest the good performance of the proposed methods to find solutions to the CLSP, the ILSSP and the ILSSP-NT on parallel machines.
Este estudo aborda um problema integrado de dimensionamento de lotes e sequenciamento (PIDLS), no qual máquinas não idênticas trabalham em paralelo, todas sujeitas a custos e tempos de preparação dependentes do sequenciamento e à limitação de capacidade. Além disso, o PIDLS em questão levará em consideração custos e tempos de preparação que não obedeçam à desigualdade triangular. Para proporcionar melhores sequências de lotes de produção, considerar-se-á também a possibilidade de setup carry-over (SC) entre períodos. Vale ressaltar que essa economia não só pode implicar em um melhor custo econômico, como também tende a infuenciar na redução de uso de recursos para preparação da máquina que têm impactos negativos no ambiente. O objetivo do PIDLS estudado, chamado aqui de PIDLS-NT, é determinar um planejamento de produção e sequenciamento de tarefas que atenda as demandas dos períodos sem atraso, de modo que os custos totais de produção, preparação de máquina e estoque sejam minimizados. Uma década atrás, abordar esses dois problemas de forma sincronizada era um desafo devido ao custo computacional necessário e às limitações dos processadores dos computadores. Porém, com os avanços tecnológicos, aumento do desempenho de processadores, a melhoria da efciência de ferramentas para solução de problemas de otimização combinatória e o avanço nos estudos de programação matemática, popularizou-se uma classe de métodos de solução, as matheurísticas, capazes de tirar vantagens tanto de métodos exatos quanto de heurísticas. Tendo isso em mente, o objetivo da tese se fia no desenvolvimento de métodos efcientes para o PIDLS-NT em questão, em particular, na proposta de matheurísticas. Nesse sentido, realizou-se uma análise das principais formulações para o PIDLS-NT encontradas na literatura, adaptadas para o problema com máquinas paralelas. O objetivo foi defnir qual formulação possuía o melhor desempenho computacional para resolver instâncias da literatura, adaptadas para o problema com tempos e custos de preparação não triangular, quando resolvidas usando o solver CPLEX v.12.7.1 limitado por período de tempo. Os métodos de solução desenvolvidos consistem, basicamente, da hibridização de métodos relax-and-fix e fix-and-optimize, para encontrar soluções iniciais para o PIDLS-NT, com heurísticas de busca local como path-relinking e kernel search para buscar soluções melhores na vizinhança de um conjunto elite de soluções encontrado inicialmente pelo método de solução. Como não existe na literatura métodos de solução para resolver o PIDLS-NT, além de verifcar a efciência dos método em relação ao solver CPLEX, para validar os métodos propostos realizaram-se experimentos comparando os resultados obtidos pelos métodos desenvolvidos, porém, para resolver o PIDLS. Dessa forma, foi possível comparar o desempenho das estratégias propostas em relação a métodos existentes na literatura. Experimentos realizados com um dos conjuntos de instâncias propostos na literatura para resolver o PIDLS mostraram um ótimo desempenho dos métodos para encontrar boas soluções factíveis tanto para o PIDLS quanto para o PIDLS-NT.
Este estudo aborda um problema integrado de dimensionamento de lotes e sequenciamento (PIDLS), no qual máquinas não idênticas trabalham em paralelo, todas sujeitas a custos e tempos de preparação dependentes do sequenciamento e à limitação de capacidade. Além disso, o PIDLS em questão levará em consideração custos e tempos de preparação que não obedeçam à desigualdade triangular. Para proporcionar melhores sequências de lotes de produção, considerar-se-á também a possibilidade de setup carry-over (SC) entre períodos. Vale ressaltar que essa economia não só pode implicar em um melhor custo econômico, como também tende a infuenciar na redução de uso de recursos para preparação da máquina que têm impactos negativos no ambiente. O objetivo do PIDLS estudado, chamado aqui de PIDLS-NT, é determinar um planejamento de produção e sequenciamento de tarefas que atenda as demandas dos períodos sem atraso, de modo que os custos totais de produção, preparação de máquina e estoque sejam minimizados. Uma década atrás, abordar esses dois problemas de forma sincronizada era um desafo devido ao custo computacional necessário e às limitações dos processadores dos computadores. Porém, com os avanços tecnológicos, aumento do desempenho de processadores, a melhoria da efciência de ferramentas para solução de problemas de otimização combinatória e o avanço nos estudos de programação matemática, popularizou-se uma classe de métodos de solução, as matheurísticas, capazes de tirar vantagens tanto de métodos exatos quanto de heurísticas. Tendo isso em mente, o objetivo da tese se fia no desenvolvimento de métodos efcientes para o PIDLS-NT em questão, em particular, na proposta de matheurísticas. Nesse sentido, realizou-se uma análise das principais formulações para o PIDLS-NT encontradas na literatura, adaptadas para o problema com máquinas paralelas. O objetivo foi defnir qual formulação possuía o melhor desempenho computacional para resolver instâncias da literatura, adaptadas para o problema com tempos e custos de preparação não triangular, quando resolvidas usando o solver CPLEX v.12.7.1 limitado por período de tempo. Os métodos de solução desenvolvidos consistem, basicamente, da hibridização de métodos relax-and-fix e fix-and-optimize, para encontrar soluções iniciais para o PIDLS-NT, com heurísticas de busca local como path-relinking e kernel search para buscar soluções melhores na vizinhança de um conjunto elite de soluções encontrado inicialmente pelo método de solução. Como não existe na literatura métodos de solução para resolver o PIDLS-NT, além de verifcar a efciência dos método em relação ao solver CPLEX, para validar os métodos propostos realizaram-se experimentos comparando os resultados obtidos pelos métodos desenvolvidos, porém, para resolver o PIDLS. Dessa forma, foi possível comparar o desempenho das estratégias propostas em relação a métodos existentes na literatura. Experimentos realizados com um dos conjuntos de instâncias propostos na literatura para resolver o PIDLS mostraram um ótimo desempenho dos métodos para encontrar boas soluções factíveis tanto para o PIDLS quanto para o PIDLS-NT.