Heurísticas para o problema de programação no-wait flowshop

Este trabalho aborda o problema de programação no-wait flowshop. Dois objetivos são considerados: (1) minimizar o makespan sujeito à restrição de que o tempo médio de fluxo é menor ou igual a um dado valor; e (2) minimizar o tempo total de fluxo sujeito à restrição de que o makespan é menor ou igual a um dado valor. Dado que esses problemas são considerados intratáveis (NP-Hard), diversos métodos heurísticos têm sido propostos. Para cada um dos dois objetivos, é proposta uma adaptação da meta-heurística de Ruiz e Stützle (2007), Iterated Greedy with Local Search (GL), com cinco versões L (1, 5, 10, 15 e 20). As cinco versões de GL adaptadas para o objetivo 1 são comparadas com a heurística HH1, proposta por Aydilek e Allahverdi (2012). E as cinco versões de GL adaptadas para o objetivo 2 são comparadas com a heurística PA20, proposta por Allanhverdi e Aydilek (2013). As heurísticas são avaliadas em problemas gerados aleatoriamente, com diferentes números de tarefas e máquinas, e nas mesmas condições iniciais. Todos os resultados são verificados estatisticamente. Os experimentos computacionais relativos ao objetivo 1 mostram que o erro relativo médio geral de G20 é menor do que o de HH1, enquanto o tempo de CPU de G20 é significativamente menor que o de HH1. Portanto, o algoritmo G20 é superior a heurística HH1. Da mesma forma, os experimentos computacionais relacionados ao objetivo 2 mostram que os erros relativos médios gerais de G10, G15 e G20 são menores do que o de PA20. Portanto, os algoritmos G10, G15 e G20 superam a performance da heurística PA20.

Título em Inglês

Heuristics for the no-wait flowshop scheduling problem

Palavras-chave em Inglês

Mean completion time
Total completion time

Resumo em Inglês

This work addresses the no-wait flowshop scheduling problem. Two objectives are considered: (1) minimizing makespan subject to the constraint that mean completion time is less than or equal to a given value; and (2) minimizing the total completion time subject to the constraint that the makespan is less than or equal to a given value. Since these problems are considered intractable (NP-Hard), several heuristic methods have been proposed. For each of the two objectives, it is proposed an adaptation of Ruiz and Stützle’ metaheuristic (2007), Iterated Greedy with Local Search (GL), with five versions L (1, 5, 10, 15 and 20). The five versions of GL adapted for objective 1 are compared with the HH1 heuristic proposed by Aydilek and Allahverdi (2012). And the five versions of GL adapted for objective 2 are compared with the PA20 heuristic proposed by Allanhverdi and Aydilek (2013). The heuristics are evaluated on randomly generated problems, with different numbers of jobs and machines, and under the same initial conditions. All results are statistically verified. Computational experiments related to objective 1 show that the overall average relative error of G20 is smaller than that of HH1, while the CPU time of G20 is significantly smaller than that of HH1. Therefore, the G20 algorithm is superior to the HH1 heuristic. In the same way, computational experiments related to objective 2 show that the overall average relative errors of G10, G15 and G20 are smaller than that of PA20. Therefore, the G10, G15 and G20 heuristics outperform the PA20 heuristic.

Arquivos

AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome(s) do(s) autor(es) do trabalho.

Almeida_Fernando_Siqueira_de_tcc.pdf (1.01 Mbytes)

Data de Publicação

2019-04-02

Número de visitas

514

Número de downloads

226