Les chercheurs dans le domaine de la conception aérodynamique et de la fabrication des avions ont fait beaucoup d'effort pour améliorer les performances des ailes par des techniques d'optimisation. Le développement de la mécanique des fluides numérique a permis de réduire les dépenses en soufflerie tout en fournissant des résultats convaincants pour simuler des situations compliquées des aéronefs. Dans cette thèse, il a été choisi une partie spéciale et importante de l'avion, à savoir, la structure de l'aile. L'optimisation basée sur la fiabilité est une méthode plus appropriée pour les structures sous incertitudes. Il se bat pour obtenir le meilleur compromis entre le coût et la sécurité tout en tenant compte des incertitudes du système en intégrant des mesures de fiabilité au sein de l'optimisation. Malgré les avantages de l'optimisation de la fiabilité en fonction, son application à un problème d'ingénierie pratique est encore assez difficile. Dans notre travail, l'analyse de l'incertitude dans la simulation numérique est introduite et exprimée par la théorie des probabilités. La simulation de Monte Carlo comme une méthode efficace pour propager les incertitudes dans le modèle d'éléments finis de la structure est ici appliquée pour simuler les situations compliquées qui peuvent se produire. Pour améliorer l'efficacité de la simulation Monte Carlo dans le processus d'échantillonnage, la méthode de l'Hypercube Latin est effectuée. Cependant, l'énorme base de données de l'échantillonnage rend difficile le fait de fournir une évaluation explicite de la fiabilité. L'expansion polynôme du chaos est présentée et discutée. Le modèle de Kriging comme un modèle de substitution joue un rôle important dans l'analyse de la fiabilité. Les méthodes traditionnelles d'optimisation ont des inconvénients à cause du temps de calcul trop long ou de tomber dans un minimum local causant une convergence prématurée. Le recuit simulé est une méthode heuristique basée sur une recherche locale, les Algorithmes Génétiques puisent leur inspiration dans les principes et les mécanismes de la sélection naturelle, qui nous rendent capables d'échapper aux pièges des optimums locaux. Dans l'optimisation de la conception de base de la fiabilité, ces deux méthodes ont été mises en place comme procédure d'optimisation. La boucle de l'analyse de fiabilité est testée sur le modèle de substitution. / Tremendous struggles of researchers in the field of aerodynamic design and aircraft production were made to improve wing airfoil by optimization techniques. The development of computational fluid dynamic (CFD) in computer simulation cuts the expense of aerodynamic experiment while provides convincing results to simulate complicated situation of aircraft. In our work, we chose a special and important part of aircraft, namely, the structure of wing.Reliability based optimization is one of the most appropriate methods for structural design under uncertainties. It struggles to seek for the best compromise between cost and safety while considering system uncertainties by incorporating reliability measures within the optimization. Despite the advantages of reliability based optimization, its application to practical engineering problem is still quite challenging. In our work, uncertainty analysis in numerical simulation is introduced and expressed by probability theory. Monte Carlo simulation as an effective method to propagate the uncertainties in the finite element model of structure is applied to simulate the complicate situations that may occur. To improve efficiency of Monte Carlo simulation in sampling process, Latin Hypercube sampling is performed. However, the huge database of sampling is difficult to provide explicit evaluation of reliability. Polynomial chaos expansion is presented and discussed. Kriging model as a surrogate model play an important role in the reliability analysis.Traditional methods of optimization have disadvantages in unacceptable time-complexity or natural drawbacks of premature convergence because of finding the nearest local optima of low quality. Simulated Annealing is a local search-based heuristic, Genetic Algorithm draws inspiration from the principles and mechanisms of natural selection, that makes us capable of escaping from being trapped into a local optimum. In reliability based design optimization, these two methods were performed as the procedure of optimization. The loop of reliability analysis is running in surrogate model.

Os problemas de corte e empacotamento são muito comuns nas indústrias e na logística. Dado um conjunto de N itens com diferentes pesos e um conjunto de M contentores com capacidade C, o problema de empacotamento unidimensional consiste em determinar o menor número de contentores a serem utilizados para alocar todos os itens respeitando a restrição de capacidade dos contentores. Nesse estudo pretende-se resolver o problema com instâncias benchmark da literatura, por meio de sessenta heurísticas diferentes, que são comparadas a quatro limitantes inferiores propostos na literatura com o intuito de avaliar a qualidade da solução heurística. Quatro limitantes inferiores e dez heurísticas construtivas diferentes foram programados em C++ num mesmo ambiente computacional, permitindo sua comparação tanto em termos de qualidade das soluções, quanto em termos dos tempos de processamento. Uma heurística simples de troca de itens entre contentores chamada Diferença-de-Quadrados foi proposta para melhorar as soluções iniciais do problema. A metaheurística simulated annealing foi acionada para melhorar a solução inicial quando o limitante inferior não foi atingido. Os parâmetros dos simulated annealing foram determinados com os dados das instâncias de forma diferente da utilizada na literatura. As combinações entre as dez soluções iniciais, a heurística Diferença-de-Quadrados e o simulated annealing geraram um conjunto de sessenta heurísticas diferentes. Os resultados mostraram que o algoritmo proposto é eficiente para resolver o problema com tempos de processamento adequados a tomada de decisão. / Cutting and packing problems are very common in industries and logistics. Given a set of N items with different weights and a set of M bins with full capacity C, the one-dimensional bin packing problem consists of determining the smallest number of bins capable to allocate all items respecting the capacity constraint of the bins. that impose that the sum of the weights of the items allocated to the bin is less than or equal to their capacity. In this study we intend to solve the problem with benchmark instances of the literature, by means of sixty different heuristics, which are compared to four lower bounds proposed in the literature in order to evaluate the quality of the heuristic solution. Four lower bounds and ten different constructive heuristics were programmed in C++ in the same computational environment, allowing their comparison both in terms of the quality of the solutions and in terms of processing times. A simple heuristic of item exchange between bins called Difference-of-Squares was proposed to improve the initial solutions of the problem. The simulated annealing metaheuristic was triggered to improve the initial solution when the lower bounds was not reached. The parameters of the simulated annealing were determined with the data of the instances differently from that used in the literature. The combinations of the ten initial solutions, the Difference-of-Squares heuristic and the simulated annealing generated a set of sixty different heuristics. The results showed that the proposed algorithm is efficient to solve the problem with adequate processing times for decision making.

O Job Shop Scheduling Problem é um problema NP-Difícil que chama a atenção de muitos pesquisadores devido seu desafio matemático e sua aplicabilidade em contextos reais. Geralmente, principalmente em cenários próximos aos de fábricas e indústrias, obter um escalonamento ótimo por meio de métodos computacionais exatos implica em um alto desprendimento de tempo. Em contrapartida, devido às exigências de um mercado cada vez mais competitivo, as decisões de onde, como, quando e com o que produzir devem ser tomadas rapidamente. O presente trabalho propõe o desenvolvimento de um método heurístico Beam Search para solucionar o Job Shop Scheduling Problem e o Flexible Job Shop Scheduling Problem. Para isso, inicialmente um algoritmo do tipo list scheduling é definido e então o método Beam Search é construído baseado neste algoritmo. Os métodos propostos foram avaliados em diferentes níveis de complexidade utilizando instâncias da literatura que retratam diferentes cenários de planejamento. Em linhas gerais, as soluções encontradas se mostraram bastante competitivas quando comparadas a outras soluções da literatura. / The Job Shop Scheduling Problem is a NP-Hard problem which draws the attention of researchers due to both its mathematical challenge and its applicability in real contexts. Usually, mainly in industry and factory environments, an optimal schedule got by the use of exact computational methods implies in a long spending time. On the other hand, due to a more and more competitive marketplace, the decisions on where, how, when and with which to produce must be taken quickly. The present work proposes the development of an heuristic Beam Search method to solve both the Job Shop Scheduling Problem and the Flexible Job Shop Scheduling Problem. To that end, at rst a list scheduling algorithm is dened and then the Beam Search method is built based on the list scheduling algorithm. The proposed methods were evaluated over dierent complexity levels using instances from the literature that report dierent planning environments. In general terms, the solutions implemented have been proved very competitive when compared against other solutions in the literature.

Este trabalho apresenta o problema de programação de operações em máquinas no ambiente no-wait flowshop com o critério de minimização da duração total da programação. Aplicações para o problema no-wait flowshop podem ser encontrados em muitas indústrias, por exemplo, em indústrias de processamento de metais, químicos e farmacêuticos. Neste trabalho, são propostos e avaliados novos métodos heurísticos para o problema, e a superioridade do melhor método proposto é comprovada através uma extensa experimentação computacional. / This work deals with the no-wait flowshop scheduling problem with the objective of minimizing total completion time. Applications of no-wait flowshop can be found in many industries, for example, in steel factories, chemical and pharmaceutical. In this work, we propose evaluate new heuristics methods for the problem. Experimental results show that the best proposed heuristic provides better solutions concerning both the solution quality and computational effort.

In IP networks using the OPSF-principle together with the ECMP-principle, thetraffic is routed in all shortest paths. Weights on links are set by an administrator,not knowing how the resulting routing pattern will become. In this final thesis, I givea heuristic solution to the problem of changing a set of desired routing patterns inan ordered way to make them compatible with each other. An implementation of thealgorithm has been made and some testing with provided data for performance is alsopresented.

国立情報学研究所で電子化したコンテンツを使用している。

Este trabalho apresenta o problema de programação de operações em máquinas no ambiente no-wait flowshop com o critério de minimização da duração total da programação. Aplicações para o problema no-wait flowshop podem ser encontrados em muitas indústrias, por exemplo, em indústrias de processamento de metais, químicos e farmacêuticos. Neste trabalho, são propostos e avaliados novos métodos heurísticos para o problema, e a superioridade do melhor método proposto é comprovada através uma extensa experimentação computacional. / This work deals with the no-wait flowshop scheduling problem with the objective of minimizing total completion time. Applications of no-wait flowshop can be found in many industries, for example, in steel factories, chemical and pharmaceutical. In this work, we propose evaluate new heuristics methods for the problem. Experimental results show that the best proposed heuristic provides better solutions concerning both the solution quality and computational effort.

Os problemas de corte e empacotamento são muito comuns nas indústrias e na logística. Dado um conjunto de N itens com diferentes pesos e um conjunto de M contentores com capacidade C, o problema de empacotamento unidimensional consiste em determinar o menor número de contentores a serem utilizados para alocar todos os itens respeitando a restrição de capacidade dos contentores. Nesse estudo pretende-se resolver o problema com instâncias benchmark da literatura, por meio de sessenta heurísticas diferentes, que são comparadas a quatro limitantes inferiores propostos na literatura com o intuito de avaliar a qualidade da solução heurística. Quatro limitantes inferiores e dez heurísticas construtivas diferentes foram programados em C++ num mesmo ambiente computacional, permitindo sua comparação tanto em termos de qualidade das soluções, quanto em termos dos tempos de processamento. Uma heurística simples de troca de itens entre contentores chamada Diferença-de-Quadrados foi proposta para melhorar as soluções iniciais do problema. A metaheurística simulated annealing foi acionada para melhorar a solução inicial quando o limitante inferior não foi atingido. Os parâmetros dos simulated annealing foram determinados com os dados das instâncias de forma diferente da utilizada na literatura. As combinações entre as dez soluções iniciais, a heurística Diferença-de-Quadrados e o simulated annealing geraram um conjunto de sessenta heurísticas diferentes. Os resultados mostraram que o algoritmo proposto é eficiente para resolver o problema com tempos de processamento adequados a tomada de decisão. / Cutting and packing problems are very common in industries and logistics. Given a set of N items with different weights and a set of M bins with full capacity C, the one-dimensional bin packing problem consists of determining the smallest number of bins capable to allocate all items respecting the capacity constraint of the bins. that impose that the sum of the weights of the items allocated to the bin is less than or equal to their capacity. In this study we intend to solve the problem with benchmark instances of the literature, by means of sixty different heuristics, which are compared to four lower bounds proposed in the literature in order to evaluate the quality of the heuristic solution. Four lower bounds and ten different constructive heuristics were programmed in C++ in the same computational environment, allowing their comparison both in terms of the quality of the solutions and in terms of processing times. A simple heuristic of item exchange between bins called Difference-of-Squares was proposed to improve the initial solutions of the problem. The simulated annealing metaheuristic was triggered to improve the initial solution when the lower bounds was not reached. The parameters of the simulated annealing were determined with the data of the instances differently from that used in the literature. The combinations of the ten initial solutions, the Difference-of-Squares heuristic and the simulated annealing generated a set of sixty different heuristics. The results showed that the proposed algorithm is efficient to solve the problem with adequate processing times for decision making.

This thesis aims to find an optimal route taken by workers reading gas-meters. The text consists of three parts: the collection of necessary data, the selection and subsequent modification of the heuristic method and the calculation itself. Two techniques of data collection are applied: purchase from a specialised company and calculation based on geographical coordinates. These techniques are compared in the end. The method of the nearest neighbour is used for calculation, after being modified for this particular case. The calculation itself is done by the program named Gas-meters, which was created for the purpose of this thesis. The route potentially used by the gas company workers is then the result of the thesis. Furthermore, the thesis presents specific corporate savings possibly brought by using the presented program.

The paper describes how logistic influence process in the firm, also there is a comparation with other firms in automobile section. And second part describes a case study of job scheduling in a mechanical-engineering production, the goal is to minimise the overall processing time. The production jobs are processed by machines. This problem is treated as a hybrid five-stage flow-shop. In other words, the job-processing job consists of maximum five tasks, it depends on product, because there is 12 products, each has own production flow. It is a new type of flow-shop in which the first-stage scheduling depends upon the time scheduling of the second stage, and so on. A mathematical model and a heuristic method is formulated, The problem is the NP hardness. The case study is solved with the heuristic method and the solution achieved represents a 10% reduction of the processing time for the given set of jobs.