Contribuições a solução de problemas de escalonamento pela aplicação conjunta de computação evolutica e otimização com restrições

AUTOR(ES)
DATA DE PUBLICAÇÃO

2000

RESUMO

This dissertation presents contributions to the solution of two assignment problems: generation of a complete set of rounds in tournaments, and definition of timetables in educational establishments (allocation of didactic charge). They represent practical problems of high interest, being characterized by feasibility aspects and a combinatorial explosion of solution candidates. In this case, the direct actuation of an expert and the use of conventional search tools guide to unsatisfactory results. The proposed solution strategy is based on the joint application of evolutionary computation, local search and restriction-based optimization. Although other evolutionary approaches have already been proposed in the literature, the one considered here innovates, since it suggests a compact genetic codification in conjunction with an algorithm to expand the code, using repairing and local search routines. When compared with the solutions already implemented to deal with real-world assignment problems, the ones obtained from the solution strategy proposed in this work presented a better performance and the required amount of computational resource to produce the solution was reasonable. The joint application of evolutionary computation, local search and restriction-based optimization may be extended to deal with other assignment problems, assuming the existence of a compact genetic codification and the availability of an algorithm for restriction-based optimization.

ASSUNTO(S)

inteligencia artificial algoritmos geneticos otimização combinatoria

ACESSO AO ARTIGO

Documentos Relacionados