Análise de Scheduling através do teste de Wilcoxon

Análise de Scheduling através do teste de Wilcoxon

1. Introdução

1. Metodologia

Utilizou-se o software “Gerador de dados.exe” para a criação de um banco de dados de 5000 documentos no formato .txt em que nele continha a quantidade de máquias, tarefas e uma matriz composta pelos tempos de cada tarefa a serem realizadas em cada máquina dos quais variavam de 1 a 100. A quantidade de máquinas variou entre 6, 12, 18, 24 e 30, e a quatidade de tarefas foi de 10, 20, 30, 40, 50, 60, 70, 80, 90 e 100. A cada combinação entre quantidade de máquinas e de tarefas, resultou em 100 documentos em txt.

Feita a base de dados, foi compilado um algoritmo no Dev-Pascal da versão 1.9.2 para que as funções objetivos, makespan e flowtime, fossem minimizadas em cada método heurístico no sistema de produção clássico, o qual não apresenta restrições quanto a tarefas em espera e fluxo contínuo nas máquinas. Todos as combinações foram realizadas no mesmo algoritmo, e todas as compilações foram realizadas no mesmo sistema.

Os resustados das compilações foram salvas em documentos .txt como Saídas, e estes foram passadas manualmente para o Excel em planilhas: em cada aba do software foi copiada 2 métodos heurísticos da mesma função objetivo, fazendo com que todos os métodos fossem comparadas entre eles.

Para a comparação foi calculado o valor crítico W e para isso é calculado a diferença em módulo entre o valor mínimo da função objetivo de cada método comparado, com essa diferença é ordenado os valores a cada 100 amostras (mesma combinação), em seguida é insirido um sinal negagtivo nessa ordenação caso a função minimizada do segundo método heurístico seja maior do que o primeiro e por fim, a ordenação dessas 100 amostras são somadas, obtendo o valor W procurado.

Ainda neste software, calcula-se o valor crítico W1 (negativo) e W2 (positivo) para probabilidade de 95% através da EQUAÇÃO 1 para todas as combinações de máquinas e tarefas, mas como totas as combinações tem o mesmo número de amostras  e o mesmo α, o valor crítico será igual para todas combinações.

                 para i = 1,2  (EQUAÇÃO 1)[pic 1]

1. Resultados e discuções

Considerando α = 95% para todas as combinações, e sabendo que elas possuem o mesmo número de amostras, todas terão o mesmo valor crítico W1 e W2.

Assim, sendo Z(α) = Z(95%) = 1,645 e sabendo que o número de amostras para cada combinação é igual a 100, temos então W1 na EQUAÇÃO 2 e W2 na EQUAÇÃO 3.

                        (EQUAÇÃO 2)[pic 2]

                        (EQUAÇÃO 3)[pic 3]

Com essas equações, obteve-se o valor de W1 e W2 igual a 956,86 e -956,86 respectivamente, e assim, foi possível gerar os gráficos para cada comparação de cada função objetivo.

Como já citado no trabalho, o W calculado é basedo na subtração da função objetivo de um método com o outro, nos gráficos que serão apresentados, a ordem as subtração será a mesma em relação ao seu título. Ex: se o título do gráfico for (LPT x SPT) então a diferença calculada foi: função objetivo do LPT menos a função objetivo SPT.

Os gráficos serão apresentados primeiramente com as comparações da minimização do makespan, e em seguida do flowtime.

Gráfico 1 - Comparação dos métodos LPT e SPT na minimização do makespan.

[pic 4]

Fonte: Autoria prória

No GRÁFICO 1, observa-se que a maioria dos pontos se encontram dentro dos limites críticos, porém existem 2 pontos abaixo do W1, o que indica que, neste caso, o método LPT é melhor do que o SPT. Como busca-se a minimização, se os pontos forem menores do que W1, indica que LPT é menor do que SPT.

Gráfico 2 - Comparação dos métodos LPT e NEH na minimização do makespan.

[pic 5]

Fonte: Autoria própria

No GRÁFICO 2, pode-se notar que o valor calculado superou o valor crítico positivo, indicando assim que o LPT é maior do que o NEH, ou seja, entre esses dois métodos o NEH é melhor.

 

Gráfico 3 - Comparação dos métodos LPT e Greedy na minimização do makespan.

[pic 6]

Fonte: Autoria própria

Na comparação entre LPT e Greedy, apretantado no GRÁFICO 3, nota-se um valor crítico calculado muito negativo, indicando que o LPT é menor do que o Greedy, assim sendo LPT o melhor nessa comparação.

Gráfico 4 – Comparação dos métodos SPT e NEH na minimização do makespan.

[pic 7]

Fonte: Autoria própria

Analisando o GRÁFICO 4, observa-se que o valor W calculado é extremamente alto e positivo, mostrando que a função objetivo do SPT é bem superior do NEH, assim, conclui-se que o NEH é o melhor resultado neste caso.

Gráfico 5 – Comparação dos métodos SPT e Greedy na minimização do makespan.

[pic 8]

Fonte: Autoria própria

Na comparação entre SPT e Greedy (GRÁFICO 5), é nítido que o W calculado é inferior ao W1, permintindo concluir que a minimização do makespan no método SPT é superior ao Greedy¸ ou seja, nesse caso o Greedy é o melhor método

Gráfico 6 - Comparação dos métodos NEH e Greedy na minimização do makespan.

[pic 9]

Fonte: Autoria própria

No GRÁFICO 6, o valor calculado encontra-se muito abaixo do W1, o que indica que o Greedy possui um valor bem superior ao NEH, assim, o NEH é o melhor método.