The no-wait flow shop scheduling problem with sequence-dependent setup times: a comprehensive review and an application of the ALNS algorithm (2021)
- Authors:
- Autor USP: REIS, VIVIANE SOUZA VILÉLA JUNQUEIRA DOS - EESC
- Unidade: EESC
- Sigla do Departamento: SEP
- DOI: 10.11606/D.18.2021.tde-17082023-144657
- Subjects: SCHEDULING; SEQUENCIAÇÃO DA PRODUÇÃO; HEURÍSTICA; PROGRAMAÇÃO DA PRODUÇÃO
- Agências de fomento:
- Language: Inglês
- Abstract: Uma das decisões mais importantes em empresas de manufatura é como sequenciar operações nas máquinas disponíveis. Em várias industrias, a natureza do trabalho impõe certas restrições ao sequenciamento de tarefas. Em um ambiente no-wait flow shop, uma vez que uma tarefa é iniciada na primeira máquina, ela deve continuar sendo processada nas próximas máquinas sem esperas. Assim como o problema de sequenciamento de flow shop, a variação no-wait também traz grande dificuldade de ser otimizada dentro de um tempo razoável, por isso várias heurísticas foram propostas para esse problema. Este trabalho tem como objetivo classificar os algoritmos de solução propostos para resolver o problema de sequenciamento no-wait flow shop com tempos de setup dependentes da sequência e algumas variantes. Mostramos como combinar uma heurística para gerar uma boa solução inicial, procedimentos de busca local, inserção e troca de posições de tarefas e técnicas desenvolvidas originalmente para resolver problemas de transporte estão entre as técnicas mais populares e eficientes para o problema em questão. Também é proposto um novo método de solução baseado no algoritmo Adaptive Large Neighbourhood Search (ALNS) da ciência dos transportes. A utilização deste algoritmo visa minimizar o tempo total de fluxo (TFT) como medida de desempenho. Por se tratar de um problema de alta complexidade, para atingir alta qualidade de solução em um tempo razoável, um método de aceleração também foi adaptado e aplicadoem procedimentos de busca local com operações de swap. Os resultados do novo método foram comparados aos melhores resultados da literatura para instâncias bem conhecidas, validando assim a qualidade do método
- Imprenta:
- Publisher place: São Carlos
- Date published: 2021
- Data da defesa: 10.11.2021
- Este periódico é de acesso aberto
- Este artigo NÃO é de acesso aberto
-
ABNT
REIS, Viviane Souza Viléla Junqueira dos. The no-wait flow shop scheduling problem with sequence-dependent setup times: a comprehensive review and an application of the ALNS algorithm. 2021. Dissertação (Mestrado) – Universidade de São Paulo, São Carlos, 2021. Disponível em: https://www.teses.usp.br/teses/disponiveis/18/18156/tde-17082023-144657/. Acesso em: 26 jan. 2026. -
APA
Reis, V. S. V. J. dos. (2021). The no-wait flow shop scheduling problem with sequence-dependent setup times: a comprehensive review and an application of the ALNS algorithm (Dissertação (Mestrado). Universidade de São Paulo, São Carlos. Recuperado de https://www.teses.usp.br/teses/disponiveis/18/18156/tde-17082023-144657/ -
NLM
Reis VSVJ dos. The no-wait flow shop scheduling problem with sequence-dependent setup times: a comprehensive review and an application of the ALNS algorithm [Internet]. 2021 ;[citado 2026 jan. 26 ] Available from: https://www.teses.usp.br/teses/disponiveis/18/18156/tde-17082023-144657/ -
Vancouver
Reis VSVJ dos. The no-wait flow shop scheduling problem with sequence-dependent setup times: a comprehensive review and an application of the ALNS algorithm [Internet]. 2021 ;[citado 2026 jan. 26 ] Available from: https://www.teses.usp.br/teses/disponiveis/18/18156/tde-17082023-144657/
Informações sobre o DOI: 10.11606/D.18.2021.tde-17082023-144657 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
