Minimização do atraso medio na programação de maquinas paralelas : uma aplicação de busca tabu

Orientador: Vinicius Amaral ArmentanoDissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de ComputaçãoResumo: Esta dissertação trata de problema de programar n tarefas em m máquinas paralelas idênticas, com o objetivo de minimizar o atraso médio em relação às datas de entrega. Para resolver o problema, propõe-se uma aplicação de busca tabu e duas estratégias de diversificação. O desempenho das heurísticas foi comparado através de testes computacionais gerados para 900 problemas. Foram realizados testes envolvendo até 10 máquinas e 150 tarefas. Para 540 problemas os resultados são comparados com limitantes inferiores gerados por relaxação lagrangeana. Em mais 65% desses problemas, os resultados dos métodos propostos chegaram a menos de 1% do limitante inferiorAbstract: This thesis deals with the problem of scheduling n jobs on m parallel identical machines with the objective of minimizing the mean tardiness. In order to solve this problem, it is proposed a tabu search approach and two diversification strategies. The performance of the heuristics was measured by computacional tests for 900 problems. The tests were made in instances with up to 10 machines and 150 jobs. For 540 problems, the results are compared with lower bounds given by a lagragian relaxation. In more than 65% of these problems, the results of the proposed method are within 1% of the lower bounds. within 1% of the lower boundsMestradoMestre em Engenharia Elétric