Les Réseaux de Chaleur (RdC) connaissent un nouvel essor en France qui s’explique par leur capacité à valoriser, à un prix raisonnable, des énergies bas carbone dans les domaines du chauffage et de l’eau chaude sanitaire aujourd’hui fortement émetteurs de CO2. L’amélioration du contrôle de ces systèmes complexes est un enjeu clé pour accroître leur compétitivité et favoriser leur développement. Cette thèse s’intéresse à la gestion par commande optimale des RdC. Pour cette application, nous avons développé et évalué un algorithme qui, à partir d’une prévision de la demande, optimise l’utilisation des différents moyens de production ainsi que la température de départ et la pression différentielle. Par rapport aux systèmes existants, les originalités de notre solution sont de tirer pleinement partie des capacités de stockage thermique dans le réseau et de déterminer le meilleur compromis entre coûts liés au pompage et pertes thermiques. Cette thèse débute par un travail de modélisation dynamique réalisé à l’échelle composant. En nous appuyant sur une démarche de validation expérimentale, nous avons systématiquement recherché le meilleur compromis entre précision et efficacité numérique (Chapitre 1). Le cas d’étude, décrit dans le Chapitre 2, est un RdC virtuel à l’échelle d’un quartier, représentatif du cas Grenoble. Pour le développement du système de gestion avancée, nous présentons ensuite une version linéarisée du modèle de réseau de distribution que nous intégrons à un optimiseur en suivant le formalisme de la programmation linéaire mixte. L’algorithme de gestion proposé est ensuite décrit (Chapitre 3). Il associe un modèle dynamique non-linéaire et l’optimiseur précité. L’objet du quatrième chapitre est l’évaluation des performances de notre algorithme par la simulation et la comparaison à des méthodes de contrôle existantes. Enfin, un dernier chapitre étudie la robustesse de l’algorithme en condition de commande réelle, c’est-à-dire en tenant compte de différentes sources d’incertitude. / District Heating (DH) are currently fast-growing in France. This situation is explained by their ability to exploit and disseminate massively, at a reasonable price, energy sources with low CO2 contents in the sectors of space heating and domestic hot water production, nowadays strongly emitters of greenhouse gases. Improving the control of these complex energy systems is a key issue for increasing their competitiveness and promote their development.This thesis focuses on the optimal control of DH systems. For this application, we have developed and tested an algorithm that optimizes, given a load prediction, the use of the production means, the supply temperature and the differential pressure. Compared to existing methods, the original features of the developed solution are to fully exploit the thermal storage capacity of the network and to determine the best compromise between costs for pumping and heat losses.This thesis begins with a work on dynamic modeling carried out at the component scale. Based on an experimental validation approach, we systematically sought the best compromise between accuracy and computational efficiency (Chapter 1). The case study, described in Chapter 2, is a virtual DH at the district scale, representing the Grenoble case. For the development of the advanced control system, we then present a linearized version of the distribution network model that we integrate into an optimizer relying on Mixed Linear Programming. The proposed control algorithm is described in Chapter 3. It combines a nonlinear dynamic model and the aforementioned optimizer. The topic of the fourth chapter is the evaluation of the performance of our algorithm by simulation and comparison with existing methods of control. A final chapter examines the robustness of the algorithm in real control conditions considering various sources of uncertainty.

[pt] Problemas de geração de grades horárias visam agendar eventos a fim de satisfazer demandas, ao mesmo tempo que satisfazem restrições adicionais. Uma solução é boa se todas as grades horárias resultantes são aceitáveis para todas as pessoas e recursos envolvidos. Para a geração de grades horárias escolares, um número conhecido de aulas, envolvendo estudantes, professores e salas de aula, deve ser agendado ao longo da semana, enquanto limitações operacionais, institucionais, pedagógicas e pessoais devem ser satisfeitas. A alta dificuldade do problema tem levado muitos pesquisadores a trabalhar em abordagens de resolução para o mesmo desde o início dos anos 60. Encontrar uma solução aplicável em um cenário do mundo real implica em satisfazer vários requisitos de qualidade e em não ignorar questões políticas, o que torna o problema clássico muito mais intrincado. Este trabalho descreve uma abordagem baseada em programação inteira mista (MIP) desenvolvida para resolver um problema real de geração de grades horárias escolares e discute ideias e desafios encarados durante a fase de implantação da solução em algumas escolas brasileiras. Em contraste com outros trabalhos na área, o compartilhamento de professores entre diferentes unidades de uma escola é considerado. Experimentos computacionais foram realizados para cenários cujo número de unidades varia de 2 a 15, o número de professores de 35 a 471, e o número de turmas de 16 a 295. Diferentes estratégias foram combinadas, visando a convergência da procura por boas soluções. Por fim, os resultados são avaliados e as melhores abordagens são destacadas. / [en] Timetabling problems look to schedule meetings in order to satisfy a set of demands, while respecting additional constraints. In a good solution the resulting timetables are acceptable to all people and resources involved. In school timetabling, a given number of lectures, involving students, teachers and classrooms, need to be scheduled over the week, while having to satisfy operational, institutional, pedagogical and personal restrictions. The difficulty of the problem has driven many researchers to work on solving approaches for it since the early 1960 s. Finding an actual solution to a real world scenario implies satisfying many quality requirements and not ignoring the political issues, which turns the classical problem much more intricate. This work describes an approach based on mixed integer programming (MIP) developed for solving a real-world school timetabling problem and discusses ideas and issues faced during solution deployment phase for some Brazilian schools. In contrast to other works on school timetabling, teaching staff sharing between distinct school units are considered. Computational experiments were performed for scenarios whose number of school units varies from 2 to 15, number of teachers varies from 35 to 471 and number of classes varies from 16 to 295. Different strategies were combined aiming at converging to good solutions. Finally, results are evaluated and the best approaches are highlighted.

In industrial applications, the thermal energy is obtained in specific equipment, such as boilers or heaters, and distributed to local usage through some transport fluid, mostly water vapor. Most industries uses multiple boilers to supply its steam demand, having tied operational costs. In this dissertation, was developed a mathematical optimization model in a language of algebraic modeling using GAMS® software. The aim is develop a computational systemic tool to support operational decisions of the steam generation. Generally, manufacturers do not operate simultaneously all of its steam generators. The choice of equipment to be used is a function of industrial process demand of steam. Regarding the use of such equipment, is not considered structured aid tools. The decisions were embased in the experience of those who were involved in operational activities. The model allows to identify specific situations to startup and shutdown, as well as the load on each boiler. In addition, the model provides estimates of steam production costs. Adjustments and evaluation of the applicability of the model occurred through a study case in a factory of the polyvinyl chloride production company, called Braskem S/A. The actual data provided by the company were compared to the results generated by the model, being evaluated their effectiveness. The results proved the model successful applicability, providing a direction, considering the generation of steam in the one year horizon. The application efficiency of the tool as a basis for the operation of steam generation was proved for long planning horizons and can be applied to shorter periods, such as weeks or months. / Em aplicações industriais, a energia térmica é obtida em equipamentos específicos, tais como caldeiras ou aquecedores, e distribuída aos locais de utilização através de um fluido de transporte, em sua maioria o vapor de água. A maior parte das indústrias utiliza várias caldeiras para suprir a demanda de vapor, havendo custos operacionais atrelados. Neste trabalho foi desenvolvido um modelo matemático de otimização em uma linguagem de modelagem algébrica, utilizando o software GAMS®. O intuito foi desenvolver uma ferramenta computacional sistêmica para apoiar as decisões operacionais de geração de vapor. De um modo geral, as indústrias não operam todos os geradores de vapor simultaneamente. A escolha do equipamento a ser utilizado, dentre os existentes na planta, é função da demanda de vapor dos processos industriais. No que diz respeito à utilização desses equipamentos, não se considera ferramentas de auxílio estruturadas, ficando as decisões embasadas na experiência dos envolvidos nas atividades operacionais. O modelo permitirá identificar situações específicas para acionamento e desligamento, bem como a carga em cada uma das caldeiras. Além disso, o modelo fornece estimativas dos custos de produção de vapor. Os ajustes e a avaliação da aplicabilidade do modelo ocorreram por meio de um estudo de caso realizado na unidade de produção de Policloreto de Viníla da empresa BRASKEM S/A. Os dados reais fornecidos pela empresa foram comparados aos resultados gerados pelo modelo, sendo avaliada sua eficácia. Os resultados obtidos comprovaram o sucesso na aplicabilidade do modelo, sendo obtido um direcionamento, considerando a geração de vapor no horizonte de um ano. A eficiência de aplicação da ferramenta como embasamento para a operação de geração de vapor foi comprovada para horizontes de planejamento longos, podendo ser aplicado a períodos mais curtos, como meses ou semanas.

Este trabalho apresenta um modelo linearizado para ser utilizado em problemas de planejamento da expansão de sistemas de distribuição de energia elétrica (SDEE) com geração distribuída (GD), em um horizonte de curto prazo. O ponto de operação em regime permanente é calculado através de um modelo linearizado da rede, sendo as cargas e geradores representados por injeções constantes de corrente, o que torna possível calcular as correntes nos ramos e as tensões nas barras através de expressões lineares. As alternativas de expansão consideradas são: (i) alocação de bancos de capacitores; (ii) alocação de reguladores de tensão; e (iii) recondutoramento. Ainda, o modelo considera a possibilidade de seleção do tap dos transformadores de distribuição como alternativa para a redução das violações de tensão. A flexibilidade do modelo permite obter soluções considerando a contribuição das GDs no controle de tensão e potência reativa sem a necessidade de especificar uma tensão para a barra da subestação. O modelo de otimização proposto para a solução destes problemas utiliza uma função objetivo linear, além de restrições lineares e variáveis contínuas e binárias. Dessa forma, o modelo de otimização pode ser representado como um problema de programação linear inteira mista (PLIM) A função objetivo considera a minimização dos custos de investimento (aquisição, instalação e remoção de equipamentos e aquisição de condutores) e dos custos de operação, que correspondem aos custos anuais de manutenção somados aos custos das perdas de energia e das violações dos limites de tensão. A variação da carga é representada através de curvas de duração, sendo que os custos das perdas e das violações são ponderados pela duração de cada nível de carregamento. Utilizando uma abordagem de PLIM, sabe-se que existem condições suficientes que garantem a otimalidade de uma dada solução factível, além de permitir que a solução seja obtida através de métodos de otimização clássica. O modelo proposto foi implementado na linguagem de programação OPL e resolvido utilizando o solver comercial CPLEX. O modelo foi validado através da comparação dos resultados obtidos para cinco sistemas de distribuição com os resultados obtidos utilizando um fluxo de carga convencional. Os casos analisados e os resultados obtidos demonstram a precisão do modelo proposto e seu potencial de aplicação. / This work presents a linearized model to be used in short-term expansion planning problems of power distribution systems (PDS) with distributed generation (DG). The steady state operation point is calculated through a linearized model of the network, being the loads and generators modeled as constant current injections, which makes it possible to calculate the branch currents and bus voltages through linear expressions. The alternatives considered for expansion are: (i) capacitor banks placement; (ii) voltage regulators placement; and (iii) reconductoring. Furthermore, the model considers the possibility of adjusting the taps of the distribution transformers as an alternative to reduce voltage violations. The flexibility of the model enables solutions that includes the contribution of DGs in the control of voltage and reactive power without the need to specify the substation voltage. The optimization model proposed to solve these problems uses a linear objective function, along with linear constraints, binary and continuous variables. Thus, the optimization model can be represented as a mixed integer linear programming problem (MILP) The objective function considers the minimization of the investment costs (acquisition, installation and removal of equipment and acquisition of conductors) and the operation costs, which corresponds to the annual maintenance cost plus the costs related to energy losses and violation of voltage limits. The load variation is represented by discrete load duration curves and the costs of losses and voltage violations are weighted by the duration of each load level. Using a MILP approach, it is known that there are sufficient conditions that guarantee the optimality of a given feasible solution, besides allowing the solution to be obtained by classical optimization methods. The proposed model was written in the programming language OPL and solved by the commercial solver CPLEX. The model was validated through the comparison of the results obtained for five distribution systems with the results obtained through conventional load flow. The analyzed cases and the obtained results show the accuracy of the proposed model and its potential for application.

Le travail de thèse présenté dans ce mémoire porte sur des méthodes d'optimisation pour la conception conjointe des nomenclatures d'une famille de produits et de sa chaîne logistique. Dans les milieux industriels comme dans les services, le contexte commercial très concurrentiel oblige les entreprises à diversifier leurs offres pour mieux répondre aux demandes de leurs clients. La gestion de cette diversité est alors une problématique centrale : comment proposer une large variété de produits pour satisfaire les besoins des clients tout en maîtrisant les coûts de production, d'inventaire et de logistique ? Les réponses à ce problème relèvent des disciplines habituellement séparées : la conception des produits, la production et la logistique. Si une majorité des approches existantes traitent ces problématiques de façon séquentielle, l'interdisciplinarité apparaît cependant comme un élément essentiel dans la gestion de la diversité. L'objectif de cette thèse est de chercher comment améliorer les interactions entre la conception de familles de produits et l'optimisation des réseaux logistiques en proposant une étape de conception intermédiaire et en développant des outils mathématiques, avec un intérêt particulier porté aux problématiques de développement durable. / This PhD thesis addresses the problem of joint bills-of-materials and supply chain design for a product family. In industry as well as in services, the highly competitive business environment obliges companies to diversify their offers to meet the demands of their customers. Then, managing diversity is a central issue: how to offer a wide variety of products to meet customer needs while controlling costs of production, inventory and logistics? Answers to theses problems are usually in separate disciplines: product design, production and logistics. If most of existing approaches tackle these problems sequentially, interdisciplinarity, however, appears as a key aspect of diversity management. The objective of this thesis is to investigate how to improve the interaction between product families design and supply chain optimization and to develop mathematical tools, with a focus on sustainable development.

Resumo: Neste trabalho, otimiza-se o funcionamento de uma fábrica desidratadora de forragens localizada na Espanha. Esta possui processos seqüenciados, secagem, produção de fardos de feno e produção de grãos, que para serem realizados consomem quantidades distintas de energia. Estabelecem-se então, os períodos de produção para cada processo, juntamente com a quantidade em toneladas a serem produzidas, sabendo que na Espanha a energia elétrica possui vinte e quatro preços, um para cada hora do dia. É proposto um modelo para a função objetivo, utilizando dados históricos de produção (Ton), consumo (kWh) e tempo (h), que retratará o funcionamento da empresa. Este modelo é obtido por meio de regressão linear múltipla e é implementado utilizando o software Lingo. Os resultados dessa implementação fornecerão as horas totais diárias que cada processo deverá ser realizado, juntamente com a quantidade de toneladas de pacotes de feno e grãos, e o custo diário da energia elétrica para realizar a produção. / Abstract: In this work, optimize of the functioning of a plant that dehydrates fodder plants located in Spain. This possess sequenced processes, drying, production of hay packs and production of grains, which to be carried through consumes distinct amounts of energy. Then, the periods of production for each process are established, together with the amount in tons to be produced, knowing that in Spain the electric energy possess twenty and four prices, one for each hour of the day. It is considered a model for the objective function, by using given historical data of production (Ton), consumption (kWh) and time (h), that the functioning of the company will portray. This model is gotten by means of multiple linear regression and is implemented using software Lingo. The results of this implementation will supply the daily total hours that each process will have to be carried through, with the amount of tons of packages of hay and grains , and the daily cost of the electric energy to carry through the production. / Orientador: Francisco Villarreal Alvarado / Coorientador: Antonio Padilha Feltrin / Banca: Evaristo Bianchini Sobrinho / Banca: José Carlos de Melo Vieira Júnior / Mestre

Made available in DSpace on 2014-06-11T19:22:35Z (GMT). No. of bitstreams: 0 Previous issue date: 2007-03-22Bitstream added on 2014-06-13T18:08:34Z : No. of bitstreams: 1 silva_mv_me_ilha.pdf: 743779 bytes, checksum: 5aad49dd95d63ada483f753bee811fd7 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho, otimiza-se o funcionamento de uma fábrica desidratadora de forragens localizada na Espanha. Esta possui processos seqüenciados, secagem, produção de fardos de feno e produção de grãos, que para serem realizados consomem quantidades distintas de energia. Estabelecem-se então, os períodos de produção para cada processo, juntamente com a quantidade em toneladas a serem produzidas, sabendo que na Espanha a energia elétrica possui vinte e quatro preços, um para cada hora do dia. É proposto um modelo para a função objetivo, utilizando dados históricos de produção (Ton), consumo (kWh) e tempo (h), que retratará o funcionamento da empresa. Este modelo é obtido por meio de regressão linear múltipla e é implementado utilizando o software Lingo. Os resultados dessa implementação fornecerão as horas totais diárias que cada processo deverá ser realizado, juntamente com a quantidade de toneladas de pacotes de feno e grãos, e o custo diário da energia elétrica para realizar a produção. / In this work, optimize of the functioning of a plant that dehydrates fodder plants located in Spain. This possess sequenced processes, drying, production of hay packs and production of grains, which to be carried through consumes distinct amounts of energy. Then, the periods of production for each process are established, together with the amount in tons to be produced, knowing that in Spain the electric energy possess twenty and four prices, one for each hour of the day. It is considered a model for the objective function, by using given historical data of production (Ton), consumption (kWh) and time (h), that the functioning of the company will portray. This model is gotten by means of multiple linear regression and is implemented using software Lingo. The results of this implementation will supply the daily total hours that each process will have to be carried through, with the amount of tons of packages of hay and grains , and the daily cost of the electric energy to carry through the production.

Este trabalho apresenta um modelo linearizado para ser utilizado em problemas de planejamento da expansão de sistemas de distribuição de energia elétrica (SDEE) com geração distribuída (GD), em um horizonte de curto prazo. O ponto de operação em regime permanente é calculado através de um modelo linearizado da rede, sendo as cargas e geradores representados por injeções constantes de corrente, o que torna possível calcular as correntes nos ramos e as tensões nas barras através de expressões lineares. As alternativas de expansão consideradas são: (i) alocação de bancos de capacitores; (ii) alocação de reguladores de tensão; e (iii) recondutoramento. Ainda, o modelo considera a possibilidade de seleção do tap dos transformadores de distribuição como alternativa para a redução das violações de tensão. A flexibilidade do modelo permite obter soluções considerando a contribuição das GDs no controle de tensão e potência reativa sem a necessidade de especificar uma tensão para a barra da subestação. O modelo de otimização proposto para a solução destes problemas utiliza uma função objetivo linear, além de restrições lineares e variáveis contínuas e binárias. Dessa forma, o modelo de otimização pode ser representado como um problema de programação linear inteira mista (PLIM) A função objetivo considera a minimização dos custos de investimento (aquisição, instalação e remoção de equipamentos e aquisição de condutores) e dos custos de operação, que correspondem aos custos anuais de manutenção somados aos custos das perdas de energia e das violações dos limites de tensão. A variação da carga é representada através de curvas de duração, sendo que os custos das perdas e das violações são ponderados pela duração de cada nível de carregamento. Utilizando uma abordagem de PLIM, sabe-se que existem condições suficientes que garantem a otimalidade de uma dada solução factível, além de permitir que a solução seja obtida através de métodos de otimização clássica. O modelo proposto foi implementado na linguagem de programação OPL e resolvido utilizando o solver comercial CPLEX. O modelo foi validado através da comparação dos resultados obtidos para cinco sistemas de distribuição com os resultados obtidos utilizando um fluxo de carga convencional. Os casos analisados e os resultados obtidos demonstram a precisão do modelo proposto e seu potencial de aplicação. / This work presents a linearized model to be used in short-term expansion planning problems of power distribution systems (PDS) with distributed generation (DG). The steady state operation point is calculated through a linearized model of the network, being the loads and generators modeled as constant current injections, which makes it possible to calculate the branch currents and bus voltages through linear expressions. The alternatives considered for expansion are: (i) capacitor banks placement; (ii) voltage regulators placement; and (iii) reconductoring. Furthermore, the model considers the possibility of adjusting the taps of the distribution transformers as an alternative to reduce voltage violations. The flexibility of the model enables solutions that includes the contribution of DGs in the control of voltage and reactive power without the need to specify the substation voltage. The optimization model proposed to solve these problems uses a linear objective function, along with linear constraints, binary and continuous variables. Thus, the optimization model can be represented as a mixed integer linear programming problem (MILP) The objective function considers the minimization of the investment costs (acquisition, installation and removal of equipment and acquisition of conductors) and the operation costs, which corresponds to the annual maintenance cost plus the costs related to energy losses and violation of voltage limits. The load variation is represented by discrete load duration curves and the costs of losses and voltage violations are weighted by the duration of each load level. Using a MILP approach, it is known that there are sufficient conditions that guarantee the optimality of a given feasible solution, besides allowing the solution to be obtained by classical optimization methods. The proposed model was written in the programming language OPL and solved by the commercial solver CPLEX. The model was validated through the comparison of the results obtained for five distribution systems with the results obtained through conventional load flow. The analyzed cases and the obtained results show the accuracy of the proposed model and its potential for application.

Submitted by Raildo Barros Rodrigues (raildo.barros@gmail.com) on 2018-09-24T15:10:31Z No. of bitstreams: 1 Dissertação_Grade_Horária_Raildo_Marins_Aneirson.pdf: 2926580 bytes, checksum: 6799724ac48abd21caecd50cf5156480 (MD5) / Rejected by Pamella Benevides Gonçalves null (pamella@feg.unesp.br), reason: Solicitamos que realize correções na submissão seguindo as orientações abaixo Verificar formatação com a equipe da biblioteca. Agradecemos a compreensão. on 2018-09-24T18:49:58Z (GMT) / Submitted by Raildo Barros Rodrigues (raildo.barros@gmail.com) on 2018-09-25T16:48:30Z No. of bitstreams: 2 Dissertação_Grade_Horária_Raildo_Marins_Aneirson.pdf: 2926580 bytes, checksum: 6799724ac48abd21caecd50cf5156480 (MD5) Dissertação_Grade_Horária_Raildo_Marins_Aneirson.pdf: 2944631 bytes, checksum: d0f33c161c9cb711a7b75cd2666f0470 (MD5) / Approved for entry into archive by Pamella Benevides Gonçalves null (pamella@feg.unesp.br) on 2018-09-25T18:15:24Z (GMT) No. of bitstreams: 1 rodrigues_rb_me_guara.pdf: 2944631 bytes, checksum: d0f33c161c9cb711a7b75cd2666f0470 (MD5) / Made available in DSpace on 2018-09-25T18:15:24Z (GMT). No. of bitstreams: 1 rodrigues_rb_me_guara.pdf: 2944631 bytes, checksum: d0f33c161c9cb711a7b75cd2666f0470 (MD5) Previous issue date: 2018-09-20 / Outra / Esta dissertação trata da construção de um modelo matemático para a elaboração do quadro de horários dos cursos de graduação do CBV/IFRR. A programação de horários é um problema de otimização combinatória estudado há anos pela Pesquisa Operacional e, em termos de complexidade computacional, é tido como NP-Completo, sendo assim, é um problema que exige grande capacidade de processamento. A elaboração do quadro de horários em qualquer instituição de ensino é complexa e demanda tempo para os responsáveis por essa atividade, pois as necessidades dos professores e alunos devem ser atendidas e devem-se evitar conflitos nos horários dos professores. A instituição estudada nesta dissertação assim como outras instituições, possui particularidades institucionais, dessa forma, uma formulação geral do problema acaba não lhe sendo útil. O CBV/IFRR realiza a elaboração dos horários de forma manual, por meio de planilha eletrônica e realização de reuniões entre os gestores, o que torna difícil encontrar uma solução factível. Sendo assim, foi necessária a realização de pesquisa científica para encontrar métodos que poderiam ser aplicados ao problema. Assim, este trabalho teve como objetivo desenvolver um modelo de Programação Matemática que permitisse a elaboração dos horários para cursos de graduação do CBV/IFRR. Utilizou-se entrevistas com as Coordenações de Cursos para obtenção das informações acerca do problema tratado, tais como restrições e prioridades a serem atendidas com a programação de aulas para professores. Estas informações serviram de base para a construção do modelo conceitual, que foi utilizado para elaboração do modelo matemático final, que foi implementado na linguagem de alto nível GAMS® e resolvido pelo solver CPLEX®. Os testes do modelo foram realizados otimizando uma instância com dados reais da instituição estudada. Os resultados obtidos da otimização foram satisfatórios, pois foi possível encontrar uma solução ótima para a instância em tempo computacional adequado, com todas as restrições, impostas pelas características peculiares do problema tratado, sendo respeitadas e as prioridades estabelecidas pelas Coordenações de Cursos atendidas. / This dissertation deals with the construction of a mathematical model for the elaboration of the timetable of the undergraduate courses of the CBV/IFRR. Time scheduling is a combinatorial optimization problem that has been studied for years by Operational Research and, in terms of computational complexity, is considered as NP-Complete, so it is a problem that requires large processing capacity. The elaboration of the timetable in any educational institution is complex and takes time for those responsible for this activity, because the needs of teachers and students must be met and avoid conflicts in the schedules of teachers. The institution studied in this dissertation as well as other institutions, has institutional features, so a general formulation of the problem ends up being of no use to it. The CBV/IFRR performs the elaboration of the schedules manually, through a spreadsheet and holding meetings between managers, which makes it difficult to find a feasible solution. Thus, it was necessary to carry out scientific research to find methods that could be applied to the problem. Thus, this work had the objective of developing a Mathematical Programming model that allowed the elaboration of the schedules for the undergraduate courses of the CBV/IFRR. We used interviews with the Course Coordinators to obtain information about the problem, such as constraints and priorities to be met with the programming of classes for teachers. This information was the basis for the construction of the conceptual model, which was used to elaborate the final mathematical model, which was implemented in the GAMS® high-level language and solved by the CPLEX® solver. The tests of the model were performed optimizing an instance with real data of the studied institution. The results obtained from the optimization were satisfactory, since it was possible to find an optimal solution for the instance in adequate computational time, with all the restrictions imposed by the peculiar characteristics of the problem, being respected and the priorities established by the Coordination of Courses attended.

A presente pesquisa considera o problema de programação de uma frota de embarcações de lançamentos de dutos, conhecidas como Pipe Layer Support Vessel (PLSVs), as quais fazem parte da frota de apoio marítimo de uma operação offshore. As embarcações do tipo PLSVs são responsáveis pelas tarefas de lançamento de dutos submarinos, que escoam a produção dos poços de petróleo, e pela interligação destes dutos à infraestrutura submarina. A programação da frota deve atender uma demanda de serviço conhecida, em um horizonte de médio prazo, respeitando restrições operacionais, visando minimizar o atraso ponderado total das tarefas ou evitar que existam atrasos. Foi desenvolvido um método para estimar o valor da solução ótima do problema, baseado na técnica de relaxação Lagrangiana, e um conjunto de heurísticas para gerar soluções viáveis para o problema. / This research considers the problem of scheduling a fleet of specialized vessels used for launching pipes and connecting them to the subsea infrastructure, in an offshore oil production environment. The Pipe Layer Support Vessels (PLSV) must be scheduled such that the demand is fully attended within the planning horizon, observing other operational constraints, with the purpose of minimizing the total weighted tardiness. The solution method is based on constructive and local search heuristics. Bounds on the optimal solution were derived by a Lagrangean relaxation algorithm.