Memetic and neuro-memetic scheduling of tasks

Orientador: Akebo YamakamiTese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de ComputaçãoResumo: Este trabalho apresenta uma nova abordagem de resolução, por algoritmo memético e pela coevolução de algoritmo memético com redes neurais, para o problema de escalonamento de tarefas em máquinas paralelas idênticas e para o problema de job shop com parâmetros precisos. Para os problemas de escalonamento com parâmetros com incertezas, onde os parâmetros não são precisamente conhecidos, toma-se dificil classificar um determinado escalonamento ótimo. A noção de ótimo também torna-se imprecisa e o grau de otimalidade de um dado escalonamento ("o quanto um escalonamento é ótimo") pode ser caracterizada por um número fuzzy. Foi aplicado também o conceito de otimalidade possível para medir a possibilidade de um determinado escalonamento ser ótimo. O algoritmo memético foi aplicado para encontrar soluções para o problema, a rede neural foi aplicada para encontrar a função de fitness das soluções encontradas pelo algoritmo memético, e o conceito de possibilidade foi aplicado para avaliar as melhores soluções. Foram utilizadas as redes neurais backpropagation e com aprendizado por reforço para encontrar o valor da função de fitness. As simulações mostraram que as redes neurais apresentaram uma boa performance na coevolução com o algoritmo memético e na resolução dos problemas, e mostraram que o conceito de possibilidade teve uma boa perfomance na avaliação da otimalidade das soluçõesAbstract: This work presents a new approach for the resolution of the problem of identical parallel machine scheduling and job shop scheduling with precise parameters, with memetic algorithm and memetic algorithm coevolving with neural networks. For problems with parameters with uncertainties, where the parameters of the problem are not precisely known, it is difficult to say in prior which schedule will be optimal. The notion of optimal also becomes imprecise and the degree of optimality of a given schedule ("how much a schedule is optimal") can be characterized by a fuzzy number. We was used also the concepts of possibility to measure the possibility of a given schedule be optimal. Memetic algorithm has been used to find the solutions of the problem, the neural network has been used to find the fitness function of these solutions, and the concept of possibility has been used to evaluate the best solutions. We was used neural networks with backpropagation and reinforcement learning to find the fitness function. Simulations showed that the neural networks presents a good performance in the coevolution of the memetic algorithm and in the resolution of the problems, and showed that the concept of possibility present a good performance in the evaluation of solutions optimalityDoutoradoTelecomunicações e TelemáticaDoutor em Engenharia Elétric