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
- 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. 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://www.teses.usp.br/teses/disponiveis/18/18156/tde-25062025-095024/. Acesso em: 28 dez. 2025. -
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://www.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 2025 dez. 28 ] Available from: https://www.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 2025 dez. 28 ] Available from: https://www.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
- 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/T.18.2024.tde-25062025-095024 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
