The no-wait flow shop scheduling problem with sequence-dependent setup times: a comprehensive review and an application of the ALNS algorithm
One of the most important decisions in any manufacturing company is how to schedule the operations on the available machines. In several industries, the nature of the job imposes certain constraints to operations scheduling. In a no-wait flow shop, once a job starts on the first machine, it has to c...
| Author: | |
|---|---|
| Format: | Master's thesis |
| Status: | Published version |
| Publication date: | 2021 |
| Country: | Brasil |
| Institution: | USP |
| Repository: | Biblioteca Digital de Teses e Dissertações da USP |
| Language: | English |
| OAI Identifier: | oai:teses.usp.br:tde-17082023-144657 |
| Online Access: | https://www.teses.usp.br/teses/disponiveis/18/18156/tde-17082023-144657/ |
| Access Level: | Open access |
| Keyword: | ALNS flow shop scheduling no-wait setup |
| _version_ | 1878760376742445056 |
|---|---|
| author | Reis, Viviane Souza Viléla Junqueira dos |
| author_browse | Reis, Viviane Souza Viléla Junqueira dos |
| author_facet | Reis, Viviane Souza Viléla Junqueira dos |
| author_role | author |
| collection | Biblioteca Digital de Teses e Dissertações da USP |
| description | One of the most important decisions in any manufacturing company is how to schedule the operations on the available machines. In several industries, the nature of the job imposes certain constraints to operations scheduling. In a no-wait flow shop, once a job starts on the first machine, it has to continue being processed on the next ones, without any interruptions. As an extension of the flow shop scheduling, the no-wait version is also very difficult to be solved to optimality within a reasonable time, and many heuristics have been proposed for this problem. This work aims to classify existing solution algorithms proposed to solve the no-wait flow shop scheduling problem with setup times and some of its variants. We show how combining a heuristic to generate a good initial solution, local search procedures, insertion and swapping of job positions and techniques developed originally to solve transportation problems are among the popular and efficient techniques for the problem at hand. We also propose a new solution method based on the well-known Adaptive Large Neighborhood Search (ALNS) algorithm from transportation science. The use of this algorithm aims to minimize the total flow time as a performance measure. As this is a problem with high complexity, to achieve high solution quality in a reasonable time, an acceleration method was also adapted and applied into local search procedures with swapping operations. The results of the new method were compared to the best results in the literature for widespread instances, validating the quality of the method. |
| eu_rights_str_mv | openAccess |
| format | masterThesis |
| id | BR_95aef9c8a8d08f3d45cb3f4ff5cb2eb3 |
| institution | USP |
| instname_str | Universidade de São Paulo (USP) |
| language | eng |
| network_acronym_str | BR |
| network_name_str | Brasil |
| oai_identifier_str | oai:teses.usp.br:tde-17082023-144657 |
| publishDate | 2021 |
| publishDateSort | 2021 |
| publisher | Biblioteca Digitais de Teses e Dissertações da USP |
| publisherStr | Biblioteca Digitais de Teses e Dissertações da USP |
| reponame_str | Biblioteca Digital de Teses e Dissertações da USP |
| spelling | The no-wait flow shop scheduling problem with sequence-dependent setup times: a comprehensive review and an application of the ALNS algorithm O problema de sequenciamento no-wait flow shop com tempos de setup dependentes da sequência: uma revisão abrangente e uma aplicação do algoritmo ALNS Reis, Viviane Souza Viléla Junqueira dos ALNS flow shop scheduling no-wait setup One of the most important decisions in any manufacturing company is how to schedule the operations on the available machines. In several industries, the nature of the job imposes certain constraints to operations scheduling. In a no-wait flow shop, once a job starts on the first machine, it has to continue being processed on the next ones, without any interruptions. As an extension of the flow shop scheduling, the no-wait version is also very difficult to be solved to optimality within a reasonable time, and many heuristics have been proposed for this problem. This work aims to classify existing solution algorithms proposed to solve the no-wait flow shop scheduling problem with setup times and some of its variants. We show how combining a heuristic to generate a good initial solution, local search procedures, insertion and swapping of job positions and techniques developed originally to solve transportation problems are among the popular and efficient techniques for the problem at hand. We also propose a new solution method based on the well-known Adaptive Large Neighborhood Search (ALNS) algorithm from transportation science. The use of this algorithm aims to minimize the total flow time as a performance measure. As this is a problem with high complexity, to achieve high solution quality in a reasonable time, an acceleration method was also adapted and applied into local search procedures with swapping operations. The results of the new method were compared to the best results in the literature for widespread instances, validating the quality of the method. 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 aplicado em 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. Biblioteca Digitais de Teses e Dissertações da USP https://www.teses.usp.br/teses/disponiveis/18/18156/tde-17082023-144657/ |
| spellingShingle | The no-wait flow shop scheduling problem with sequence-dependent setup times: a comprehensive review and an application of the ALNS algorithm Reis, Viviane Souza Viléla Junqueira dos ALNS flow shop scheduling no-wait setup |
| status_str | publishedVersion |
| title | The no-wait flow shop scheduling problem with sequence-dependent setup times: a comprehensive review and an application of the ALNS algorithm |
| title_full | The no-wait flow shop scheduling problem with sequence-dependent setup times: a comprehensive review and an application of the ALNS algorithm |
| title_fullStr | The no-wait flow shop scheduling problem with sequence-dependent setup times: a comprehensive review and an application of the ALNS algorithm |
| title_full_unstemmed | The no-wait flow shop scheduling problem with sequence-dependent setup times: a comprehensive review and an application of the ALNS algorithm |
| title_short | The no-wait flow shop scheduling problem with sequence-dependent setup times: a comprehensive review and an application of the ALNS algorithm |
| title_sort | The no-wait flow shop scheduling problem with sequence-dependent setup times: a comprehensive review and an application of the ALNS algorithm |
| topic | ALNS flow shop scheduling no-wait setup |
| topic_facet | ALNS flow shop scheduling no-wait setup |
| url | https://www.teses.usp.br/teses/disponiveis/18/18156/tde-17082023-144657/ |