Experiencing barriers under stay

Até o momento, os resultados sugerem que para o problema aqui tratado, versões mais elaboradas de algoritmos genéticos apresentam uma melhor performance em termos de qualidade de solução em relação a uma heurística construtiva sofisticada. Uma outra questão que merece investigação é se esta superioridade é mantida em relação a outros algoritmos de busca, ou seja, algoritmos que, ao contrário da heurística de CHINNECK et al. (2003), permitem a melhoria das soluções iniciais.

Neste sentido, foi elaborado um algoritmo do tipo multiple starts, o qual consiste de iterativamente, gerar uma solução inicial seguida por um procedimento de busca. O procedimento de busca consiste em analisar todas as possíveis trocas de tarefas entre processadores e inserções de uma tarefa em um processador distinto (vizinhança) a cada iteração, e selecionar a troca ou inserção que resulta na maior diminuição do atraso. As soluções iniciais utilizadas pelo multiple starts são as 6 soluções geradas pelo algoritmo de CHINNECK et al. (2003) e perturbações do mesmo, e soluções geradas aleatoriamente. Para uma comparação mais justa, o critério de parada do algoritmo

multiple starts corresponde ao tempo utilizado pelo algoritmo inteligente 9 para

encontrar a melhor solução. O resultado do algoritmo é o melhor ótimo local encontrado em todas as execuções.

A TABELA 4.7 apresenta os resultados do algoritmo inteligente 8, do algoritmo inteligente 9 (com aplicação de busca local a cada 50 gerações sem melhoria), do algoritmo multiple starts, e da heurística de CHINNECK et al. (2003) para os 117 diagramas. Assim como na TABELA 4.6, os valores de Atraso∆ e ∆#proc

representam o desempenho relativo dos três primeiros algoritmos ao da heurística de CHINNECK et al. (2003) A TABELA 4.8 apresenta os resultados da heurística de CHINNECK et al. (2003) e do algoritmo inteligente 8, divididos em grupos de acordo com o número de tarefas, a TABELA 4.9 apresenta os resultados da heurística de CHINNECK et al. (2003) e do algoritmo inteligente 9, divididos em grupos de acordo com o número de tarefas, a TABELA 4.10 apresenta os resultados do algoritmo multiple

starts e do algoritmo inteligente 8, divididos em grupos de acordo com o número de

starts e do algoritmo inteligente 9, também divididos em grupos de acordo com o

número de tarefas. Nas TABELAS 4.10 e 4.11 as colunas Atraso∆ e ∆#proc indicam respectivamente a diferença entre os atrasos médios e número médio de processadores obtidos com o algoritmo inteligente 8 (TABELA 4.10) e inteligente 9 (TABELA 4.11) com o algoritmo multiple starts.

TABELA 4.7 - Resultados computacionais gerais– 117 diagramas (5 a 176 tarefas). Algoritmo Atraso #proc ∆Atraso ∆# proc T(seg) E G P

Inteligente 8 24,91 27,95 -1,62 -1,82 33,84 29 88 0 Inteligente 9 23,79 28,09 -2,71 -1,68 97,21 15 102 0

Multiple Starts 24,88 29,50 -1,62 -0,27 7,16 40 77 0

Chinneck et al. 26,50 29,77 - - 1,56 - - -

TABELA 4.8 - Resultados computacionais para 5 grupos de diagramas – algoritmo INTELIGENTE 8 e Chinneck et al.

Grupo #tarefas # problemas Chinneck et al. Atraso/#proc Algoritmo Inteligente 8 Atraso/#proc Atraso ∆ ∆# proc T (seg) E G P 1 15,9 23 6,96/6,57 6,17/6,17 -0,83 -0,39 2,52 11 12 0 2 32,4 24 13,38/14,17 12,04/13,17 -1,33 -1,00 10,01 5 19 0 3 69,3 26 27,88/31,04 25,38/28,81 -2,50 -2,23 30,21 2 24 0 4 89,3 26 34,08/39,65 32,12/37,31 -1,96 -2,35 53,83 5 21 0 5 143,6 18 56,06/64,11 54,89/60,72 -1,17 -3,39 82,02 7 11 0

TABELA 4.9 - Resultados computacionais para 5 grupos de diagramas – algoritmo INTELIGENTE 9 e Chinneck et al.

Grupo #tarefas # problemas Chinneck et al. Atraso/#proc Algoritmo Inteligente 9 Atraso/#proc Atraso ∆ ∆# proc T (seg) E G P 1 15,9 23 6,96/6,57 6,13/6,17 -0,87 -0,39 3,59 10 13 0 2 32,4 24 13,38/14,17 11,79/13,04 -1,58 -1,13 11,54 3 21 0 3 69,3 26 27,88/31,04 24,46/28,81 -3,42 -2,23 71,07 0 26 0 4 89,3 26 34,08/39,65 30,92/37,35 -3,15 -2,31 122,15 0 26 0 5 143,6 18 56,06/64,11 51,00/61,78 -5,06 -2,33 332,77 0 18 0

TABELA 4.10 - Resultados computacionais para os 5 grupos de diagramas – algoritmo INTELIGENTE 8 e mutliple starts.

Grupo #tarefas # problemas Multiple Starts Atraso/#proc Algoritmo Inteligente 8 Atraso/#proc Atraso ∆ ∆# proc E G P 1 15,9 23 6,48/6,13 6,17/6,17 -0,31 0,04 16 6 1 2 32,4 24 12,88/13,96 12,04/13,17 -0,84 -0,79 8 16 0 3 69,3 26 26,04/30,85 25,38/28,81 -0,65 -2,04 5 16 5 4 89,3 26 32,19/39,58 32,12/37,31 -0,07 -2,27 10 7 9 5 143,6 18 52,17/63,56 54,89/60,72 +2,72 -2,84 2 0 16

TABELA 4.11 - Resultados computacionais para os 5 grupos de diagramas – algoritmo INTELIGENTE 9 e mutliple starts.

Grupo #tarefas # problemas Multiple Starts Atraso/#proc Algoritmo Inteligente 9 Atraso/#proc Atraso ∆ ∆# proc E G P 1 15,9 23 6,48/6,13 6,13/6,17 -0,35 0,04 17 6 0 2 32,4 24 12,88/13,96 11,79/13,04 -1,08 -0,92 4 20 0 3 69,3 26 26,04/30,85 24,46/28,81 -1,58 -2,04 5 21 0 4 89,3 26 32,19/39,58 30,92/37,35 -1,27 -2,23 5 20 1 5 143,6 18 52,17/63,56 51,00/61,78 -1,17 -1,78 4 13 1

Como já observado nas baterias de experimentos anteriores, os algoritmos 8 e 9 obtiveram ganhos expressivos em relação aos resultados de CHINNECK et al.(TABELA 4.7). O algoritmo inteligente 9 superou os resultados do algoritmo inteligente 8 em relação à qualidade das soluções, porém requerendo maior custo computacional. Com relação ao algoritmo inteligente 9, para os grupos com menor número de tarefas (grupos 1 e 2 - TABELA 4.9) a diferença em relação ao atraso é pequena, porém conforme aumenta o número de tarefas, a diferença de atraso médio também aumenta. O algoritmo inteligente 9 apresenta uma diferença de atraso de até 9 ciclos para o diagrama de 176 tarefas, e em média obtém uma diferença de 5,06 ciclos para o grupo 5 que contém diagramas com mais de 100 tarefas.

Na TABELA 4.7, observa-se que o algoritmo multiple starts produz, em média, soluções de qualidade superior às obtidas pela heurística de CHINNECK et al. (2003). Os tempos médios de execução até o melhor ótimo local de multiple starts foram bastante reduzidos, apresentando uma pequena variação - 5 a 20 segundos - entre os grupos de tarefas.

O algoritmo inteligente 8 obteve um desempenho considerado competitivo em relação ao algoritmo multiple starts. Apesar de apresentar atrasos

menores em 38,5% do total de diagramas (contra 26,5% de exemplos com atrasos maiores), o algoritmo 8 não conseguiu superar as soluções de multiple starts em nenhum dos diagramas do grupo 5 (veja TABELA 4.10). De fato, em 89% dos diagramas deste grupo, o algoritmo 8 foi superado por multiple starts. Concluiu-se, portanto, que o desempenho do algoritmo 8 em relação a multiple starts diminui com o aumento do número de tarefas.

Por outro lado, observa-se na TABELA 4.11 que o algoritmo inteligente 9 obteve soluções com atraso igual (35 diagramas) ou inferior (80 diagramas) às obtidas por multiple starts. Os 2 diagramas em que o algoritmo inteligente 9 obteve soluções de pior qualidade que as apresentadas pelo algoritmo multiple starts pertencem aos grupos 4 e 5, os quais contêm mais de 78 tarefas. Como as soluções iniciais geradas pelo algoritmo de CHINNECK et al. (2003) são utilizadas pelos dois algoritmos e o tempo de execução é o mesmo para ambos, esses resultados sugerem que o algoritmo multiple

starts obtém boas soluções rapidamente, porém possibilidades de melhorias adicionais

são também rapidamente esgotadas. De fato, os melhores ótimos locais foram obtidos a partir das soluções de CHINNECK et al. (as primeiras as serem utilizadas), e a aplicação de buscas locais nas demais soluções – geradas aleatoriamente – se revelaram infrutíferas.

O algoritmo inteligente 9, por outro lado, mostrou-se capaz de obter melhorias significativas em estágios avançados da busca a partir de uma população mista. Pode-se dizer que uma das razões de seu melhor desempenho seja o resultado da combinação de decisões aleatórias que conferem diversidade à população e de boas decisões determinísticas que intensificam a busca em regiões atraentes. Entretanto, o maior custo computacional requerido pode não ser desprezível.