Constatei que o algoritmo de Graham com variante (aquele que ordena as tarefas antes) é tão bom que na verdade é difícil encontrar uma combinação de tarefas tal que uma busca exaustiva consiga um resultado melhor. Nos meus testes, quase sempre o Graham com variante consegue o melhor resultado possível.
Depois de vários testes, achei essa combinação:
3 11 4 14 7 12 10 15 8 12 14 10 14
Ou seja:
3 máquinas
11 tarefas, com durações 4, 14, 7 etc.
Para esta combinação, na minha implementação os tempos dos melhores escalonamentos obtidos foram:
Graham simples: 43
Graham variante: 43
busca exaustiva: 40
Outra combinação interessante:
5 11 4 14 7 12 10 15 8 12 14 10 14
5 máquinas
11 tarefas iguais ao caso anterior
Para este problema eu obtive:
Graham simples: 29
Graham variante: 26
busca exaustiva: 25
Vale lembrar que implementar o Graham com variante não é necessário e não faz parte do enunciado, e que o enunciado determina que o limitante inicial da busca exaustiva seja o resultado do Graham simples.
Esses resultados apenas mostram que se for usado o Graham com variante para definir o limitante inicial, na maioria dos casos que eu testei a busca exaustiva não consegue um resultado melhor.
Achei bacana que o Prof. Reverbel se deu ao trabalho de contar sobre a variante do Graham no enunciado, mesmo não cobrando sua implementação, porque na prática esta opção do Graham com variante é provavelmente a melhor solução para este problema em termos de custo x benefício, já que ela é tão eficaz quando a busca exaustiva exceto em casos raros, e quando não é, o desvio máximo de 33% é razoável.
Fórum