O sequenciamento e a programação da produção trazem grandes benefícios financeiros às empresas se realizados de forma adequada. Atualmente, soluções generalizadas apresentam resultados aceitáveis, porém têm como consequência benefícios inferiores quando comparados a estudos específicos. O ramo da otimização de resultados possui dois tipos de soluções: as exatas para problemas de menores dimensões e não exatas, ou heurísticas, para problemas de médias e grandes dimensões. Este trabalho apresenta algoritmos exatos do tipo Branch & Bound e Modelos de Programação Linear Inteira Mista para solucionar quatro variações de problemas de scheduling: Fm|block|∑Cjm, Fm|block|∑Tj, Fm|block, Sijk|∑Cjm e Fm|block, Sijk|∑Tj. As abordagens utilizadas são inéditas na literatura e apresentaram resultados animadores para a maioria dos cenários. O limitante para o tempo total de fluxo obteve resposta ótima em 100% dos casos para problemas de até 20 tarefas e 4 máquinas em menos de uma hora. Para o tempo total de atraso, o limitante se mostrou mais eficiente quando os valores das due dates apresentam alta taxa de dispersão. Para os casos com setup, foram elaboradas três variações de limitantes para cada problema. O limitante com setup que apresentou o melhor desempenho foi o que obteve a melhor relação entre o seu valor numérico e seu custo computacional. Os modelos MILP solucionaram 100% dos problemas sem setup para até 20 tarefas e 4 máquinas e para os casos com setup, foram solucionados problemas de até 14 tarefas e 4 máquinas no tempo limite de uma hora. Os testes computacionais mostram a eficiência na redução do número de nós e, consequentemente, no tempo de execução. Portanto, o estudo realizado indica que, para problemas de pequeno porte e médio, os métodos em questão possuem grande potencial para aplicações práticas. / Job Sequence and Programming give benefits both financial and organizational to any company when performed properly. Nowadays, there is still a gap between theory and practice due to solutions that are short in specification. The analyzed problems differ in type and dimension thus modifying its complexity. The results optimization field is divided into two types of solution: the exact solution for minor problems and the non-exact solution for greater dimension problems. The present paper presents exact algorithms to solve the problems Fm|block|∑Cjm, Fm|block|∑Tj, Fm|block, Sijk|∑Cjm by the Branch & Bounds and Mixed Integer Linear Program models. The approaches are new and presented good results for most cases. Bounds for the no-setup total flow time scenario solved 100% of the 20 jobs and 4 machines cases. High dispersion range due dates contributed for the effectiveness of the no-setup total tardiness bound\'s effectiveness. Three different approaches were developed for the setup cases. The best approach aimed to optimize the value/effort factor for the B&B. The Mixed Integer Linear Program models solved 100% of the no-setup cases for 20 jobs and 4 machines. The MILPs setup cases solved optimally 14 jobs and 4 machines cases. Computational tests were executed and analyzed and they highlighted the node count reduction and, consequently, the execution time. The present study points out that the exact methods can be applied to small and medium scheduling problems in practice.

Exploitation of waste heat could achieve economic and environmental benefits, while at the same time increase energy efficiency in process sites. Diverse commercialised technologies exist to recover useful energy from waste heat. In addition, there are multiple on-site and offsite end-uses of recovered energy. The challenge is to find the optimal mix of technologies and end-uses of recovered energy taking into account the quantity and quality of waste heat sources, interactions with interconnected systems and constraints on capital investment. Explicit models for waste heat recovery technologies that are easily embedded within appropriate process synthesis frameworks are proposed in this work. A novel screening tool is also proposed to guide selection of technology options. The screening tool considers the deviation of the actual performance from the ideal performance of technologies, where the actual performance takes into account irreversibilities due to finite temperature heat transfer. Results from applying the screening tool show that better temperature matching between heat sources and technologies reduces the energy quality degradation during the conversion process. A ranking criterion is also proposed to evaluate end-uses of recovered energy. Applying the ranking criterion shows the use to which energy recovered from waste heat is put determines the economics and potential to reduce CO2 emissions when waste heat recovery is integrated in process sites. This thesis also proposes a novel methodological framework based on graphical and optimization techniques to integrate waste heat recovery into existing process sites. The graphical techniques are shown to provide useful insights into the features of a good solution and assess the potential in industrial waste heat prior to detailed design. The optimization model allows systematic selection and combination of waste heat source streams, selection of technology options, technology working fluids, and exploitation of interactions with interconnected systems. The optimization problem is formulated as a Mixed Integer Linear Program, solved using the branch-and-bound algorithm. The objective is to maximize the economic potential considering capital investment, maintenance costs and operating costs of the selected waste heat recovery technologies. The methodology is applied to industrial case studies. Results indicate that combining waste heat recovery options yield additional increases in efficiency, reductions in CO2 emissions and costs. The case study also demonstrates that significant benefits from waste heat utilization can be achieved when interactions with interconnected systems are considered simultaneously. The thesis shows that the methodology has potential to identify, screen, select and combine waste heat recovery options for process sites. Results suggest that recovery of waste heat can improve the energy security of process sites and global energy security through the conservation of fuel and reduction in CO2 emissions and costs. The methodological framework can inform integration of waste heat recovery in the process industries and formulation of public policies on industrial waste heat utilization.

O sequenciamento e a programação da produção trazem grandes benefícios financeiros às empresas se realizados de forma adequada. Atualmente, soluções generalizadas apresentam resultados aceitáveis, porém têm como consequência benefícios inferiores quando comparados a estudos específicos. O ramo da otimização de resultados possui dois tipos de soluções: as exatas para problemas de menores dimensões e não exatas, ou heurísticas, para problemas de médias e grandes dimensões. Este trabalho apresenta algoritmos exatos do tipo Branch & Bound e Modelos de Programação Linear Inteira Mista para solucionar quatro variações de problemas de scheduling: Fm|block|∑Cjm, Fm|block|∑Tj, Fm|block, Sijk|∑Cjm e Fm|block, Sijk|∑Tj. As abordagens utilizadas são inéditas na literatura e apresentaram resultados animadores para a maioria dos cenários. O limitante para o tempo total de fluxo obteve resposta ótima em 100% dos casos para problemas de até 20 tarefas e 4 máquinas em menos de uma hora. Para o tempo total de atraso, o limitante se mostrou mais eficiente quando os valores das due dates apresentam alta taxa de dispersão. Para os casos com setup, foram elaboradas três variações de limitantes para cada problema. O limitante com setup que apresentou o melhor desempenho foi o que obteve a melhor relação entre o seu valor numérico e seu custo computacional. Os modelos MILP solucionaram 100% dos problemas sem setup para até 20 tarefas e 4 máquinas e para os casos com setup, foram solucionados problemas de até 14 tarefas e 4 máquinas no tempo limite de uma hora. Os testes computacionais mostram a eficiência na redução do número de nós e, consequentemente, no tempo de execução. Portanto, o estudo realizado indica que, para problemas de pequeno porte e médio, os métodos em questão possuem grande potencial para aplicações práticas. / Job Sequence and Programming give benefits both financial and organizational to any company when performed properly. Nowadays, there is still a gap between theory and practice due to solutions that are short in specification. The analyzed problems differ in type and dimension thus modifying its complexity. The results optimization field is divided into two types of solution: the exact solution for minor problems and the non-exact solution for greater dimension problems. The present paper presents exact algorithms to solve the problems Fm|block|∑Cjm, Fm|block|∑Tj, Fm|block, Sijk|∑Cjm by the Branch & Bounds and Mixed Integer Linear Program models. The approaches are new and presented good results for most cases. Bounds for the no-setup total flow time scenario solved 100% of the 20 jobs and 4 machines cases. High dispersion range due dates contributed for the effectiveness of the no-setup total tardiness bound\'s effectiveness. Three different approaches were developed for the setup cases. The best approach aimed to optimize the value/effort factor for the B&B. The Mixed Integer Linear Program models solved 100% of the no-setup cases for 20 jobs and 4 machines. The MILPs setup cases solved optimally 14 jobs and 4 machines cases. Computational tests were executed and analyzed and they highlighted the node count reduction and, consequently, the execution time. The present study points out that the exact methods can be applied to small and medium scheduling problems in practice.

Cette thèse se situe à l’intersection de deux domaines de recherche scientifique la Reconnaissance d’Objets Structurels (ROS) et la Recherche Opérationnelle (RO). Le premier consiste à rendre la machine plus intelligente et à reconnaître les objets, en particulier ceux basés sur les graphes. Alors que le second se focalise sur la résolution de problèmes d’optimisation combinatoire difficiles. L’idée principale de cette thèse est de combiner les connaissances de ces deux domaines. Parmi les problèmes difficiles existants en ROS, le problème de la distance d’édition entre graphes (DEG) a été sélectionné comme le cœur de ce travail. Les contributions portent sur la conception de méthodes adoptées du domaine RO pour la résolution du problème de DEG. Explicitement, des nouveaux modèles linéaires en nombre entiers et des matheuristiques ont été développé à cet effet et de très bons résultats ont été obtenus par rapport à des approches existantes. / This thesis is focused on Graph Matching (GM) problems and in particular the Graph Edit Distance (GED) problems. There is a growing interest in these problems due to their numerous applications in different research domains, e.g. biology, chemistry, computer vision, etc. However, these problems are known to be complex and hard to solve, as the GED is a NP-hard problem. The main objectives sought in this thesis, are to develop methods for solving GED problems to optimality and/or heuristically. Operations Research (OR) field offers a wide range of exact and heuristic algorithms that have accomplished very good results when solving optimization problems. So, basically all the contributions presented in thesis are methods inspired from OR field. The exact methods are designed based on deep analysis and understanding of the problem, and are presented as Mixed Integer Linear Program (MILP) formulations. The proposed heuristic approaches are adapted versions of existing MILP-based heuristics (also known as matheuristics), by considering problem-dependent information to improve their performances and accuracy.