[pt] Esta dissertação investiga a aplicação de Algoritmos Genéticos e de Co-Evolução Cooperativa na otimização da programação da produção em refinarias de petróleo. Refinarias de petróleo constituem um dos mais importantes exemplos de plantas contínuas multiproduto, isto é, um sistema de processamento contínuo gerador de múltiplos produtos simultâneos. Uma refinaria, em geral, processa um ou mais tipos de petróleo, produzindo uma série de produtos derivados, como o GLP (gás liquefeito de petróleo), a nafta, o querosene e o óleo diesel. Trata- se de um problema complexo de otimização, devido ao número e diversidade de atividades existentes e diferentes objetivos. Além disso, neste problema, algumas atividades dependem de que outras atividades já tenham sido planejadas para que possam então ser planejadas. Um caso típico é o das retiradas de produtos de uma unidade de processo, que dependem de que a carga já tenha sido planejada, assim como em qual campanha a unidade estará naquele instante. Por isso, o uso de modelos revolucionários convencionais, como os baseados em ordem, pode gerar muitas soluções inválidas, que deverão ser posteriormente corrigidas ou descartadas, comprometendo o desempenho e a viabilidade do algoritmo. O objetivo do trabalho foi, então, desenvolver um modelo evolucionário para otimizar a programação da produção (scheduling), segundo objetivos bem definidos, capaz de lidar com as restrições do problema, gerando apenas soluções viáveis. O trabalho consistiu em três etapas principais: um estudo sobre o refino de petróleo e a programação da produção em refinarias; a definição de um modelo usando algoritmos genéticos e co-evolução cooperativa para otimização da programação da produção e a implementação de uma ferramenta para estudo de caso. O estudo sobre o refino e a programação da produção envolveu o levantamento das várias etapas do processamento do petróleo em uma refinaria, desde o seu recebimento, destilação e transformação em diversos produtos acabados, que são então enviados a seus respectivos destinos. Neste estudo, também foi levantada a estrutura de tomada de decisão em uma refinaria e seus vários níveis, diferenciando os objetivos destes níveis e explicitando o papel da programação da produção nesta estrutura. A partir daí, foram estudadas em detalhes todas as atividades que normalmente ocorrem na refinaria e que são definidas na programação, e seus papéis na produção da refinaria. A decisão de quando e com que recursos executar estas atividades é o resultado final da programação e, portanto, a saída principal do algoritmo. A modelagem do algoritmo genético consistiu inicialmente em um estudo de representações utilizadas para problemas de scheduling. O modelo coevolucionário adotado considera a decomposição do problema em duas partes e,portanto, emprega duas populações com responsabilidades diferentes: uma é responsável por indicar quando uma atividade deve ser planejada e a outra é responsável por indicar com quais recursos essa mesma atividade deve ser realizada. A primeira população teve sua representação baseada em um modelo usado para problemas do tipo Dial-A-Ride (Moon et al, 2002), que utiliza um grafo para indicar à função de avaliação a ordem na qual o planejamento deve ser construído. Esta representação foi elaborada desta forma para que fosse levada em conta a existência de restrições de precedência (atividades que devem ser planejadas antes de outras), e assim não fossem geradas soluções inválidas pelo algoritmo. A segunda população, que se responsabiliza pela alocação dos recursos para a execução das atividades, conta com uma representação onde os operadores genéticos podem atuar na ordem de escolha dos recursos que podem realizar cada uma das atividades. Finalmente, des / [en] This work investigates the use of Genetic Algorithms and Cooperative Coevolution in refinery scheduling optimization. Oil refineries are one of the most important examples of multiproduct continuous plants, that is, a continuous processing system that generates a number of products simultaneously. A refinery processes various crude oil types and produces a wide range of products, including LPG (liquefied petroleum gas), gasoline, kerosene and diesel. It is a complex optimization problem, mainly due to the number of different tasks involved and different objective criteria. In addition, some of the tasks have precedence constraints that require other tasks to be scheduled first. For example, in order to schedule a task that transfers one of the yields of a certain crude distillation unit, both the task that feeds the crude oil into the unit and the task that sets the unit`s current operation mode must already be scheduled. Therefore, applying traditional evolutionary models, like the order- based ones, can create many infeasible solutions that will have to be corrected or rejected later on, thereby jeopardizing the algorithm performance and feasibility. The main goal was the development an evolutionary model satisfying well-defined objectives, which would optimize production scheduling and address the various constraints entailed in the problem, thus generating only feasible solutions. This work consisted on three main steps: a survey on crude oil refining and refinery scheduling; the development of a cooperative coevolutionary model to optimize the refinery scheduling and the development of a software tool for case studies. The study about refining and scheduling involved gathering information about the existent processes in a refinery, starting from the arrival of crude oil, its distillation and transformation into several products and, finally, the delivery of these products to their respective destination. The levels of decision making in a refinery were surveyed too, in order to identify the main goals for each one, and how the scheduling level fits into the structure as whole. Then, all the routine scheduling tasks and their roles in a refinery were carefully studied. The decision of when and how to assign those tasks is the final output of the scheduling task, so it must be the main output of the algorithm too. The development of the evolutionary model consisted of a survey on some of the most common evolutionary approaches to scheduling. The adopted coevolutionary model breaks the problem down into two parts, thus using two species with different responsibilities: One is responsible for deciding when a task should be scheduled, while the other is responsible for assigning a resource for this task. The first species representation was based on a model used for the Dial-a- Ride (Moon et al, 2002) kind of problems, and uses a graph to help the fitness evaluation function find the right order in which to schedule the tasks. This representation was devised in such a way that the precedence constraints were satisfied and no infeasible solutions were generated. The representation of the second species, which assigns resources for the tasks, let genetic operators change the selection order when picking a resource for a task. Finally, a software tool was developed to be used for implement this model and for performing a case study. This case study should comprise all the needed characteristics, in order to test the quality of the representation as well as evaluate the results. A simple refinery was designed, containing all equipment types, tasks and constraints found in a real-world refinery. The constraints mentioned are the precedence constraints, handled by the graph used by the first species, plus other operational constraints found in refinery scheduling. It was possible, then, to see the decoding of chromosomes into feasible solutions, always satisfying all the constraints. Several tests