Heuristics and stochastic local search for just-in-time scheduling of parallel machines against common restrictive due windows (2020)
- Authors:
- Autor USP: ROLIM, GUSTAVO ALENCAR - EESC
- Unidade: EESC
- Sigla do Departamento: SEP
- DOI: 10.11606/D.18.2020.tde-16112021-120034
- Subjects: SEQUENCIAÇÃO DA PRODUÇÃO; HEURÍSTICA; JUST IN TIME; ALGORITMOS
- Keywords: Atraso e adiantamento; Busca local estocástica; Janelas de tempo comuns; Máquinas paralelas; Sequenciamento
- Agências de fomento:
- Language: Inglês
- Abstract: 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 desempenhopromissor 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
- Imprenta:
- Publisher place: São Carlos
- Date published: 2020
- Data da defesa: 03.07.2020
- Este periódico é de acesso aberto
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: gold
- Licença: cc-by-nc-sa
-
ABNT
ROLIM, Gustavo Alencar. Heuristics and stochastic local search for just-in-time scheduling of parallel machines against common restrictive due windows. 2020. Dissertação (Mestrado) – Universidade de São Paulo, São Carlos, 2020. Disponível em: https://www.teses.usp.br/teses/disponiveis/18/18156/tde-16112021-120034/. Acesso em: 28 dez. 2025. -
APA
Rolim, G. A. (2020). Heuristics and stochastic local search for just-in-time scheduling of parallel machines against common restrictive due windows (Dissertação (Mestrado). Universidade de São Paulo, São Carlos. Recuperado de https://www.teses.usp.br/teses/disponiveis/18/18156/tde-16112021-120034/ -
NLM
Rolim GA. Heuristics and stochastic local search for just-in-time scheduling of parallel machines against common restrictive due windows [Internet]. 2020 ;[citado 2025 dez. 28 ] Available from: https://www.teses.usp.br/teses/disponiveis/18/18156/tde-16112021-120034/ -
Vancouver
Rolim GA. Heuristics and stochastic local search for just-in-time scheduling of parallel machines against common restrictive due windows [Internet]. 2020 ;[citado 2025 dez. 28 ] Available from: https://www.teses.usp.br/teses/disponiveis/18/18156/tde-16112021-120034/ - Parallel-machine scheduling: variants, formulations, and a critical analysis of metaheuristic approaches
- Designing state-of-the-art metaheuristics: what have we learned from the parallel-machine scheduling problem with setups?
- Formulations and an adaptive large neighborhood search for just-in-time scheduling of unrelated parallel machines with a common due window
- Effective heuristics and an iterated greedy algorithm to schedule identical parallel machines subject to common restrictive due windows
- Structural properties and algorithms for earliness and tardiness scheduling against common due dates and windows: A review
- On the integration of reinforcement learning and simulated annealing for the parallel batch scheduling problem with setups
- Dynamic Programming algorithms and their applications in machine scheduling: a review
Informações sobre o DOI: 10.11606/D.18.2020.tde-16112021-120034 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
