Parallel-machine scheduling: variants, formulations, and a critical analysis of metaheuristic approaches (2024)
- Authors:
- Autor USP: ROLIM, GUSTAVO ALENCAR - EESC
- Unidade: EESC
- Sigla do Departamento: SEP
- DOI: 10.11606/T.18.2024.tde-25062025-095024
- Subjects: PROGRAMAÇÃO DA PRODUÇÃO; PROGRAMAÇÃO HEURÍSTICA
- Keywords: Aprendizado por reforço.; Atrasos e adiantamentos.; Máquinas paralelas.; Tempo total de produção.
- Agências de fomento:
- Language: Inglês
- Abstract: Esta tese se concentra no estudo do problema de programação de máquinas paralelas não relacionadas e suas variantes. Nos últimos anos, esse problema ganhou bastante atenção devido à sua ampla gama de aplicações, desde a manufatura de semicondutores até a execução de programas de computador. Apesar de sua importância prática, muitas de suas variantes são N P - difíceis, o que torna a solução de instâncias de grande porte desafiadora para a maioria das abordagens exatas. Portanto, esta tese persegue dois objetivos principais: primeiro, propor novas variantes do problema de programação de máquinas paralelas não relacionadas e desenvolver soluções heurísticas rápidas e eficientes; e segundo, revisar e avaliar a literatura atual para identificar os componentes algorítmicos que levam a melhores resultados em metaheurísticas. Para alcançar esses objetivos, estruturamos este trabalho em três etapas. Na primeira etapa, investigamos um problema de programação de máquinas paralelas onde as tarefas estão sujeitas a uma janela de tempo comum, com o objetivo de minimizar a soma total das penalidades de adiantamento e atraso ponderadas. Identificamos propriedades estruturais, apresentamos duas formulações matemáticas, desenvolvemos duas heurísticas construtivas e estendemos a metaheurística adaptive large neighborhood search. Na segunda etapa, realizamos uma pesquisa abrangente da literatura atual sobre metaheurísticas para problemas de programação da produção em máquinas paralelas com setups e minimização do makespan. Analisamos estruturas de vizinhança, representações de soluções e demonstramos as vantagens de usar técnicas de aceleração. Além disso, implementamos e avaliamos um conjunto de 12 metaheurísticas heterogêneas em condições experimentais padronizadas. Finalmente, na terceira etapa, estudamos um problema de programação de máquinas paralelas com formação de lotes, famílias de tarefas e setups,com o objetivo de minimizar a soma total dos tempos de conclusão. Introduzimos uma formulação matemática, estabelecemos uma relação de dominância e propusemos tanto uma heurística construtiva quanto um algoritmo de busca local estocástica com várias estruturas de vizinhança. Também exploramos a incorporação do Q-learning, um algoritmo de aprendizado por reforço, para a seleção de estruturas de vizinhança. No geral, não apenas propusemos algoritmos eficazes que superaram as abordagens existentes em várias instâncias, mas também demonstramos que métodos com estruturas de vizinhança diversificadas e poucos parâmetros de controle tendem a entregar resultados melhores
- Imprenta:
- Publisher place: São Carlos
- Date published: 2024
- Data da defesa: 11.11.2024
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
ABNT
ROLIM, Gustavo Alencar. Parallel-machine scheduling: variants, formulations, and a critical analysis of metaheuristic approaches. 2024. Tese (Doutorado) – Universidade de São Paulo, São Carlos, 2024. Disponível em: https://teses.usp.br/teses/disponiveis/18/18156/tde-25062025-095024/. Acesso em: 11 abr. 2026. -
APA
Rolim, G. A. (2024). Parallel-machine scheduling: variants, formulations, and a critical analysis of metaheuristic approaches (Tese (Doutorado). Universidade de São Paulo, São Carlos. Recuperado de https://teses.usp.br/teses/disponiveis/18/18156/tde-25062025-095024/ -
NLM
Rolim GA. Parallel-machine scheduling: variants, formulations, and a critical analysis of metaheuristic approaches [Internet]. 2024 ;[citado 2026 abr. 11 ] Available from: https://teses.usp.br/teses/disponiveis/18/18156/tde-25062025-095024/ -
Vancouver
Rolim GA. Parallel-machine scheduling: variants, formulations, and a critical analysis of metaheuristic approaches [Internet]. 2024 ;[citado 2026 abr. 11 ] Available from: https://teses.usp.br/teses/disponiveis/18/18156/tde-25062025-095024/ - Heuristics and stochastic local search for just-in-time scheduling of parallel machines against common restrictive due windows
- 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
- 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
- Dynamic Programming algorithms and their applications in machine scheduling: a review
- On the integration of reinforcement learning and simulated annealing for the parallel batch scheduling problem with setups
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
