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.

O problema do sequenciamento da produção diz respeito à alocação das tarefas nas máquinas em um ambiente de fabricação, o qual vem sendo amplamente estudado. O sequenciamento pode variar em tamanho e complexidade dependendo do tipo de ambiente onde ele é aplicado, do número e tipos de restrições tecnológicas e da função objetivo do problema. A utilização de métodos de decisão para a solução de problemas de sequenciamento na indústria depende de modelos que sejam capazes de oferecer soluções para os problemas reais, que geralmente envolvem diversas restrições, os quais devem ser considerados simultaneamente. No presente trabalho o problema de sequenciamento da produção em ambientes flow shop permutacionais, com bloqueio com buffer zero, e com tempos de setup dependente da sequência e da máquina, com o objetivo de minimização do makespan é estudado, sendo este considerado um problema NP-Completo. O problema é pouco explorado na literatura. No presente trabalho é apresentado um procedimento de cálculo para o makespan e três métodos de solução para o problema: quatro limitantes inferiores para o procedimento Branch-and-Bound; quatro modelos MILP, sendo dois deles adaptados; e 28 modelos heurísticos construtivos adaptados para o problema. Os métodos desenvolvidos baseiam-se em propriedades matemáticas do problema que são apresentadas neste trabalho como limitante inferior e limitante superior. Dentre todos os modelos MILP, o modelo adaptado RBZBS1 obteve os melhores resultados para os problemas menores e o modelo desenvolvido TNZBS1 obteve os melhores desvios relativos médios do makespan para os problemas maiores, que não foram resolvidos dentro do limite de tempo computacional estipulado. O limitante inferior para o Branch-and-Bound LBTN2 foi melhor que os demais tanto no tempo computacional e no número de nós explorados como também no número de problemas não resolvidos e no desvio relativo médio do makespan. Foi realizado uma comparação entre o melhor modelo MILP e o melhor limitante inferior para o Branch-and-Bound, sendo que o último obteve melhores resultados para os problemas testados. Entre os métodos heurísticos adaptados, o PF foi o que obteve, de uma forma geral, os melhores resultados em todas as fases. / Production scheduling is defined as a problem of allocating jobs in machines in a production environment and it has been largely studied. The scheduling can vary in difficulty and complexity depending on the environment, the variety and types of technological restraints and the objective function of the problem. The use of decision making methods to solve scheduling problems in the industry needs models that are capable to solve real problems, that usually involve a big variety of restraints that have to be simultaneously studied. At the present work the scheduling problem in a permutational flow shop environment, considering blocking with zero buffer, and sequence and machine dependent setup times, with the objective of minimizing makespan is studied, which is considered a NP-Complete problem and little explored in literature. The work presents a calculation procedure for the makespan and three solution methods for the problem: four lower bounds for the Branch-and-Bound procedure; four MILP models, two of which are adapted; and 28 constructive heuristic methods adapted to the problem. The methods developed are based on mathematical properties of the problem that are presented in this work as a lower bound and an upper bound. Among all the MILP models, the adapted model RBZBS1 was the one to obtain the best results for the smaller problems, and the developed model TNZBS1 obtained the smallest mean relative deviation of the makespan for the bigger problems that were not solved within the specified computational time limit. The lower bound for the Branch-and-Bound LBTN2 obtained smaller computational times and number of explored nodes as well as the number of unsolved problems and the mean relative deviation for the makespan than all other lower bounds. Also, a comparison among the best MILP model and the best lower bound for the Branch-and-Bound was performed, being that the last obtained better results for the tested problems. Among the adapted heuristic methods, the PF heuristic was the one that obtained, in general, the better results in all phases.

Dans cette thèse, nous menons une étude dans le cadre de la théorie de l'information sur deux questions importantes de la communication sans fil : l'amélioration du débit de données dans les réseaux avec interférence grâce à la coopération entre utilisateurs et le renforcement de la sécurité des transmissions à l'aide d'un signal de rétroaction.Dans la première partie de la thèse, nous nous concentrons sur le modèle le plus simple qui intègre à la fois l'interférence et la coopération, le canal à relais et interférence ou IRC (Interference Relay Channel). Notre objectif est de caractériser dans un nombre fixe de bits la région de capacité du IRC gaussien. À cette fin, nous dérivons une nouvelle limite supérieure de la capacité et deux stratégies de transmission. La limite supérieure est notamment obtenue grâce à une extension non triviale que nous proposons, de la classe de canaux semi-déterministe et injective à l'origine dérivée par Telatar et Tse pour le canal à interférence.Dans la seconde partie, nous étudions le canal avec espion et rétroaction généralisée ou WCGF (Wiretap Channel with Generalized Feedback). Notre objectif est de développer une stratégie de transmission générale qui englobe les résultats existants pour les différents modèles de rétroaction trouvés dans la littérature. À cette fin, nous proposons deux stratégies de transmission différentes sur la capacité du WCGF sans mémoire. Nous dérivons d'abord une stratégie qui est basée sur le codage source-canal conjoint. Nous introduisons ensuite une seconde stratégie où le signal de rétroaction est utilisé pour générer une clé secrète qui permet de chiffrer le message partiellement ou totalement. / In this thesis, we conduct an information-theoretic study on two important aspects of wireless communications: the improvement of data throughput in interference-limited networks by means of cooperation between users and the strengthening of the security of transmissions with the help of feedback.In the first part of the thesis, we focus on the simplest model that encompasses interference and cooperation, the Interference Relay Channel (IRC). Our goal is to characterize within a fixed number of bits the capacity region of the Gaussian IRC, independent of any channel conditions. To do so, we derive a novel outer bound and two inner bounds. Specifically, the outer bound is obtained thanks to a nontrivial extension we propose of the injective semideterministic class of channels, originally derived by Telatar and Tse for the Interference Channel (IC).In the second part of the thesis, we investigate the Wiretap Channel with Generalized Feedback (WCGF) and our goal is to provide a general transmission strategy that encompasses the existing results for different feedback models found in the literature. To this end, we propose two different inner bounds on the capacity of the memoryless WCGF. We first derive an inner bound that is based on the use of joint source-channel coding, which introduces time dependencies between the feedback outputs and the channel inputs through different time blocks. We then introduce a second inner bound where the feedback link is used to generate a key that encrypts the message partially or completely.

O problema do sequenciamento da produção diz respeito à alocação das tarefas nas máquinas em um ambiente de fabricação, o qual vem sendo amplamente estudado. O sequenciamento pode variar em tamanho e complexidade dependendo do tipo de ambiente onde ele é aplicado, do número e tipos de restrições tecnológicas e da função objetivo do problema. A utilização de métodos de decisão para a solução de problemas de sequenciamento na indústria depende de modelos que sejam capazes de oferecer soluções para os problemas reais, que geralmente envolvem diversas restrições, os quais devem ser considerados simultaneamente. No presente trabalho o problema de sequenciamento da produção em ambientes flow shop permutacionais, com bloqueio com buffer zero, e com tempos de setup dependente da sequência e da máquina, com o objetivo de minimização do makespan é estudado, sendo este considerado um problema NP-Completo. O problema é pouco explorado na literatura. No presente trabalho é apresentado um procedimento de cálculo para o makespan e três métodos de solução para o problema: quatro limitantes inferiores para o procedimento Branch-and-Bound; quatro modelos MILP, sendo dois deles adaptados; e 28 modelos heurísticos construtivos adaptados para o problema. Os métodos desenvolvidos baseiam-se em propriedades matemáticas do problema que são apresentadas neste trabalho como limitante inferior e limitante superior. Dentre todos os modelos MILP, o modelo adaptado RBZBS1 obteve os melhores resultados para os problemas menores e o modelo desenvolvido TNZBS1 obteve os melhores desvios relativos médios do makespan para os problemas maiores, que não foram resolvidos dentro do limite de tempo computacional estipulado. O limitante inferior para o Branch-and-Bound LBTN2 foi melhor que os demais tanto no tempo computacional e no número de nós explorados como também no número de problemas não resolvidos e no desvio relativo médio do makespan. Foi realizado uma comparação entre o melhor modelo MILP e o melhor limitante inferior para o Branch-and-Bound, sendo que o último obteve melhores resultados para os problemas testados. Entre os métodos heurísticos adaptados, o PF foi o que obteve, de uma forma geral, os melhores resultados em todas as fases. / Production scheduling is defined as a problem of allocating jobs in machines in a production environment and it has been largely studied. The scheduling can vary in difficulty and complexity depending on the environment, the variety and types of technological restraints and the objective function of the problem. The use of decision making methods to solve scheduling problems in the industry needs models that are capable to solve real problems, that usually involve a big variety of restraints that have to be simultaneously studied. At the present work the scheduling problem in a permutational flow shop environment, considering blocking with zero buffer, and sequence and machine dependent setup times, with the objective of minimizing makespan is studied, which is considered a NP-Complete problem and little explored in literature. The work presents a calculation procedure for the makespan and three solution methods for the problem: four lower bounds for the Branch-and-Bound procedure; four MILP models, two of which are adapted; and 28 constructive heuristic methods adapted to the problem. The methods developed are based on mathematical properties of the problem that are presented in this work as a lower bound and an upper bound. Among all the MILP models, the adapted model RBZBS1 was the one to obtain the best results for the smaller problems, and the developed model TNZBS1 obtained the smallest mean relative deviation of the makespan for the bigger problems that were not solved within the specified computational time limit. The lower bound for the Branch-and-Bound LBTN2 obtained smaller computational times and number of explored nodes as well as the number of unsolved problems and the mean relative deviation for the makespan than all other lower bounds. Also, a comparison among the best MILP model and the best lower bound for the Branch-and-Bound was performed, being that the last obtained better results for the tested problems. Among the adapted heuristic methods, the PF heuristic was the one that obtained, in general, the better results in all phases.

This dissertation studies several aspects of the interface between information theory and signal processing. Several new and existing results in information theory are researched from the perspective of signal processing. Similarly, some fundamental results in signal processing and statistics are studied from the information theoretic viewpoint. The first part of this dissertation focuses on illustrating the equivalence between Stein's identity and De Bruijn's identity, and providing two extensions of De Bruijn's identity. First, it is shown that Stein's identity is equivalent to De Bruijn's identity in additive noise channels with specific conditions. Second, for arbitrary but fixed input and noise distributions, and an additive noise channel model, the first derivative of the differential entropy is expressed as a function of the posterior mean, and the second derivative of the differential entropy is expressed in terms of a function of Fisher information. Several applications over a number of fields, such as statistical estimation theory, signal processing and information theory, are presented to support the usefulness of the results developed in Section 2. The second part of this dissertation focuses on three contributions. First, a connection between the result, proposed by Stoica and Babu, and the recent information theoretic results, the worst additive noise lemma and the isoperimetric inequality for entropies, is illustrated. Second, information theoretic and estimation theoretic justifications for the fact that the Gaussian assumption leads to the largest Cramer-Rao lower bound (CRLB) is presented. Third, a slight extension of this result to the more general framework of correlated observations is shown. The third part of this dissertation concentrates on deriving an alternative proof for an extremal entropy inequality (EEI), originally proposed by Liu and Viswanath. Compared with the proofs, presented by Liu and Viswanath, the proposed alternative proof is simpler, more direct, and more information-theoretic. An additional application for the extremal inequality is also provided. Moreover, this section illustrates not only the usefulness of the EEI but also a novel method to approach applications such as the capacity of the vector Gaussian broadcast channel, the lower bound of the achievable rate for distributed source coding with a single quadratic distortion constraint, and the secrecy capacity of the Gaussian wire-tap channel. Finally, a unifying variational and novel approach for proving fundamental information theoretic inequalities is proposed. Fundamental information theory results such as the maximization of differential entropy, minimization of Fisher information (Cramer-Rao inequality), worst additive noise lemma, entropy power inequality (EPI), and EEI are interpreted as functional problems and proved within the framework of calculus of variations. Several extensions and applications of the proposed results are briefly mentioned.

L’industrie forestière est un secteur qui, même s’il est en déclin, se trouve au cœur du débat sur la mondialisation et le développement durable. Pour de nombreux pays tels que le Canada, la Suède et le Chili, les objectifs sont de maintenir un secteur florissant sans nuire à l’environnement et en réalisant le caractère fini des ressources. Il devient important d’être compétitif et d’exploiter de manière efficace les territoires forestiers, de la récolte jusqu’à la fabrication des produits aux usines, en passant par le transport, dont les coûts augmentent rapidement. L’objectif de ce mémoire est de développer un modèle de planification tactique/opérationnelle qui permet d’ordonnancer les activités pour une année de récolte de façon à satisfaire les demandes des usines, sans perdre de vue le transport des quantités récoltées et la gestion des inventaires en usine. L’année se divise en 26 périodes de deux semaines. Nous cherchons à obtenir les horaires et l’affectation des équipes de récolte aux blocs de coupe pour une année. Le modèle mathématique développé est un problème linéaire mixte en nombres entiers dont la structure est basée sur chaque étape de la chaine d’approvisionnement forestière. Nous choisissons de le résoudre par une méthode exacte, le branch-and-bound. Nous avons pu évaluer combien la résolution directe de notre problème de planification était difficile pour les instances avec un grand nombre de périodes. Cependant l’approche des horizons roulants s’est avérée fructueuse. Grâce à elle en une journée, il est possible de planifier les activités de récolte des blocs pour l’année entière (26 périodes). / Forest industry is a sector located at the heart of the debate on globalisation and sustainable development, even if it is in decline. For many countries like Canada, Sweden and Chile, the objectives are to maintain a flourishing sector without damaging the environment and to realize the finite nature of resources. It is important to be competitive and to operate effectively on forest territories, from harvesting to manufacturing products, through transport, in a context where costs increase rapidly. This master’s thesis is developing a tactical operational planning model to organize activities for a year to meet requests for factories, without losing sight of the transport of harvested quantities and inventory management factory. The year is divided into 26 periods of two weeks. We seek harvest teams schedules and assignment to harvest areas (units) for a year. The problem is formulated as a mixed integer programming model, whose structure is based on each stage of the forest supply chain. We choose to solve it by an exact method, branch-and-bound. We were able to assess how the direct resolution of our planning problem was difficult for instances with a large number of periods. However the rolling horizon approach has proved successful. In a day, we obtained the harvest activities planning for 26 periods.

Onward Bound: -- the first 50 years of Outward Bound Australia traces the founding and development of this unique, Australian, non-profit, non-government organisation from its earnest beginnings to its formidable position today where it attracts some 5,000 participants a year to its courses. The project included interviewing hundreds of people and scouring archives and public records to piece together a picture of how and why Outward Bound Australia (OBA) developed -- recording its challenges and achievements along the way. A mediated oral history approach was used among past and present OBA founders, staff and participants, to gather stories about their history. This use of oral history (in a historical book) was a way of cementing the known recorded facts and adding colour to the formal historical outline, while also giving credence to the text through the use of 'real' people's stories.

Le problème de gestion de projet à contraintes de ressources est un des problèmesles plus étudiés dans la littérature. Il consiste à planifier des activités soumises à desrelations de précédence, et nécessitant des ressources renouvelables. L’objectif est deminimiser la durée du projet, soit le makespan. Nous étudions le problème de gestion deprojet à contraintes de ressources. Nous nous sommes intéressées à la résolution exactedu problème. Dans la première partie de la thèse, nous élaborons une série de bornesinférieures basées sur le raisonnement énergétique et des formulations mathématiques.Les résultats montrent que les bornes proposées surpassent ceux de la littérature. Dansla deuxième partie, nous proposons des procédures par séparation et évaluation utilisantles bornes inférieures dévelopées dans la première partie. / Resource Constrained Project Scheduling Problem is one of the most studied schedulingproblems in the literature. It consists in scheduling activities, submitted to precedencerelationship, and requiring renewable resources to be processed. The objective isto minimize the project duration, i.e., the makespan. We study the Resource ConstrainedProject Scheduling Problem. We are interested on the exact resolution of the problem.In the first part of the thesis, we develop a series of lower bounds based on energeticreasoning and mathematical formulations. The computational results show that theproposed lower bounds outperform the ones of the literature. In the second part, wepropose Branch-and-Bound procedures using the lower bounds developed on the firstpart.

En raison de la capacité et de l'amélioration des performances informatiques, les représentations structurelles sont devenues de plus en plus populaires dans le domaine de la reconnaissance de formes (RF). Quand les objets sont structurés à base de graphes, le problme de la comparaison d'objets revient à un problme d'appariement de graphes (Graph Matching). Au cours de la dernière décennie, les chercheurs travaillant dans le domaine de l'appariement de graphes ont porté une attention particulière à la distance d'édition entre graphes (GED), notamment pour sa capacité à traiter différent types de graphes. GED a été ainsi appliquée sur des problématiques spécifiques qui varient de la reconnaissance de molécules à la classi fication d'images. / Due to the inherent genericity of graph-based representations, and thanks to the improvement of computer capacities, structural representations have become more and more popular in the field of Pattern Recognition (PR). In a graph-based representation, vertices and their attributes describe objects (or part of them) while edges represent interrelationships between the objects. Representing objects by graphs turns the problem of object comparison into graph matching (GM) where correspondences between vertices and edges of two graphs have to be found.

Dans ces travaux, nous présentons des méthodes d'optimisation théoriques et numériques pour la conception optimale de circuits magnétiques pour propulseurs à effet Hall. Ces problèmes de conception sont des problèmes inverses très difficiles à résoudre que nous formulons sous forme de problèmes d'optimisation topologique. Les problèmes resultant sont non convexes avec des contraintes aux équations différentielles de Maxwell. Au cours de ces travaux, des approches originales ont été proposées afin de résoudre efficacement ces problèmes d'optimisation topologique. L'approche de densité de matériaux SIMP (Solid Isotropic Material with Penalization) qui est une variante de la méthode d'homogénéisation a été privilégiées. De plus, les travaux de ma thèse ont permis la mise en place de codes d'optimisation dénommé ATOP (Algorithm To Optimize Propulsion) utilisant en parallèle les logiciels de calculs scientifiques Matlab et d'élément finis FEMM (Finite Element Method Magnetics). Dans ATOP, nous utilisant à la fois des algorithmes d'optimisation locale de type descente basés sur une analyse de la sensibilité du problème et des algorithmes d'optimisation globale principalement de type Branch and Bound basés sur l'Arithmétique des Intervals. ATOP permettra d'optimiser à la fois la forme topologique des circuits magnétiques mais aussi le temps et le coût de production de nouvelles génération de propulseurs électriques. / In this work, we present theoretical and numerical optimization method for designing magnetic circuits for Hall effect thrusters. These design problems are very difficult inverse ones that we formulate under the form of topology optimization problems. Then, the obtained problems are non convex subject to Maxwell equations like constraints. Some original approaches have been proposed to solve efficiently these topology optimization problems. These approaches are based on the material density model called SIMP approach (Solid Isotropic Material with Penalization) which is a variante of the homogenization method. The results in my thesis allowed to provide optimization source code named ATOP (Algorithm To Optimize Propulsion) unsung in parallel two scientific computing softwares namely Matlab and FEMM (Finite Element Method Magnetics). In ATOP, we use both local optimization algorithms based on sensitivity analysis of the design problem; and global optimization algorithms mainly of type Branch and Bound based on Interval Arithmetic analysis. ATOP will help to optimize both the topological shape of the magnetic circuits and the time and cost of production (design process) of new generations of electrical thrusters.