Nous présentons les enjeux du management environnemental et soulignons l’importance d’une politique d’économie d’énergie pour les entreprises. Nous proposons un modèle pour déterminer le bilan énergétique de la fabrication en intégrant les différentes phases productives et non-productives. Nous définissons un double objectif pour la minimisation de la durée de production et de la consommation d’énergie. Nous appliquons ce modèle à l’ordonnancement d’ateliers job-shop flexibles. Pour déterminer la solution optimale nous utilisons deux classes de méthodes : - La première relève des algorithmes génétiques. Nous proposons différents types d’algorithmes pour résoudre ce problème multicritère. Nous proposons par exemple de faire évoluer deux populations pour minimiser respectivement l’énergie consommée et la durée de production et de les croiser pour atteindre l’objectif global. - La seconde relève de la programmation sous contrainte. Nous proposons de rechercher la solution optimale en développant une double arborescence pour évaluer l’énergie consommée et la durée de production. Nous construisons notre algorithme en partant des tâches à réaliser sur les machines ou en partant des machines qui réaliseront les tâches. Nous discutons de la construction du front de Pareto pour l’obtention de la meilleure solution.Nous terminons en comparant les différentes approches et en discutant leur pertinence pour traiter des problèmes de différentes tailles. Nous proposons également plusieurs améliorations et quelques pistes pour de futures recherches. / We present the challenges of environmental management and underline the importance of an energy saving policy for companies. We propose a model to determine the energy balance of manufacturing by integrating the different productive and non-productive phases. We define two purposes for minimizing production time and energy consumption. We apply this model to the scheduling of flexible job-shop workshops. To determine the optimal solution we use two types of methods: - The first is genetic algorithms. We propose different types of algorithms to solve this multi-criteria problem. For example, we propose to develop two populations to minimize the energy consumed and the production time, and to cross them to achieve the overall objective. - The second is constraint programming. We propose to find the optimal solution by developing a double tree to evaluate the energy consumed and the production time. We build our algorithm starting from the tasks to be performed on the machines or from the machines that will perform the tasks. We discuss the construction of the Pareto front to get the best solution.We finish by comparing the different approaches and discussing their relevance to deal with problems of different sizes. We also offer several improvements and some leads for future research.

Scheduling in the context of manufacturing systems has become increasingly impor- tant in order for organizations to achieve success in dynamic and competitive scenarios. Scheduling can be described as allocation of available jobs over resources to meet the performance criteria defined in a domain. Our research work fo cuses on scheduling a given set of three-dimensional cylindrical items, each characterized by width wj , height hj, and depth dj , onto parallel non-identical rectangular heat treatment kilns, such that the capacities of the kilns is optimally used. The problem is strongly NP-hard as it generalizes the (one-dimensional) Bin Packing Problem (1BP), in which a set of n positive values wj has to be partitioned into the minimum number of subsets so that the total value in each subset does not exceed the bin capacity W. The problem has been formulated as a variant of the 3D-BPP by following the MILP approach, and we propose a weight optimization heuristic that produces solutions comparable to that of the LP problem, in addition to reducing the computational complexity. Finally, we also propose a Decomposition Algorithm (DA) and validate the perfor- mance effectiveness of our heuristic. The numerical analyses provides useful insights that influence the shop-floor decision making process.

Le management de la chaîne logistique concerne un large éventail d’activités. Nombreuses ceux qui ont un caractère incertain apportant souvent des conséquences inattendues. Malgré cela, l’incertitude est fréquemment non considérée dans la gestion de la chaîne logistique traditionnelle. En plus de l’incertitude, l’indisponibilité des ressources augmentera la complexité du problème. En prenons en compte les contraintes d’incertitude et de disponibilité nous étudions le management de la chaîne logistique selon différents aspects. Cette thèse représente une tentative de recherche afin d’aborder ce problème d’une façon systématique et complète et nous espérons que notre travail contribuera aux futurs travaux de recherche et sera utile aux gestionnaires de la chaîne logistique. Nous nous concentrons sur trois sources classiques de l’incertitude ; celle de la demande, celle la fabrication et celle liée à la distribution. Pour chaque source d’incertitude, nous analysons ses causes et ses impacts sur les performances de la chaîne logistique. L’incertitude est spécifiée dans des problèmes classiques concrets et des approches sont proposées pour les résoudre. Nous nous sommes également focalisés sur le problème bi-niveau de vendeur de journaux qui représente une chaîne logistique miniature, concerné par une double incertitude. Les méthodes utilisées offrent une bonne démonstration du traitement des variables incertaines dans les problèmes de décision / Supply chain management involves a wide range of activities. Among most of them, uncertainty exists inherently and always brings some consequence not expected. However, uncertainty is not considered much in conventional supply chain management. In the case where availability of resources is not what we expect, complexity of supply chain management increases. Taking constraints of uncertainty and availability into account, we aim to discuss supply chain management from different aspects. This thesis is an attempt of systematic and complete research from this point and we would like to offer some references to researchers and managers in supply chain. We focus on three classic sources of uncertainty: demand, manufacturing and distribution. For each source of uncertainty, we analyze its cause and its impact to the performance of the supply chain. Uncertainty is specified into concrete classic problem and an approach is proposed to solve it. Furthermore, bi-level newsboy problem as a miniature of supply chain, is focused under double uncertain environment. Treating uncertain variables is actually a treatment on operational level. The methods used offer good demonstration in treating uncertain variables in decision problems

Made available in DSpace on 2016-12-23T13:44:55Z (GMT). No. of bitstreams: 1 dissertacao.pdf: 1052399 bytes, checksum: b17ce224ca3822e277c997fd00bd2c67 (MD5) Previous issue date: 2007-03-23 / This work presents an Artificial Immune System (AIS) to deal with problems scheduling. The Artificial Immunologic System developed in this project was based on the structure,architecture and functioning of the Biological or Natural Immune Systems. The use of Genetic Algorithm (GA) became necessary to represent the antibodies and antigens of the AIS. Each individual generated for the GA represented a processed task set library in a set of machines. The evaluation of each individual was given by a fitness function that represents the process of natural selection. The evolution of the individuals, and population as a consequence was obtained by applying the genetic operators of crossover e mutation. The machines and the tasks used for the scheduling represent the problem of Job Shop Scheduling (JSS). Some classic tests of the literature where applied to the problem in order to verify the viability of the AIS on the treatment of task of scheduling problems. Those tests also demonstrated the system s behavior its entire execution, therefore, allowing for a detailed analysis of the system s functionalities sets for certain time period. The representation of the natural immunologic systems through computational algorithms inspires from all over world researchers. The motivation is that the immunologic systems possess parallelism characteristics adaptability and learning, which can be applied in several problems found in many areas, had its portability. / Este trabalho apresenta um Sistema Imune Artificial (SIA) para tratar problemas de escalonamento. O Sistema Imunológico Artificial desenvolvido neste projeto baseia-se na estrutura arquitetura e funcionamento dos Sistemas Imunes Biológicos ou Naturais. O uso de Algoritmo Genético (AG) fez-se necessário para gerar os indivíduos a serem escalonados, representando os antígenos e anticorpos do SIA. Cada indivíduo gerado pelo AG representa um conjunto de tarefas processadas em um conjunto de máquinas. Os indivíduos são avaliados por uma função de aptidão que representa o processo de seleção natural. A evolução dos indivíduos e consequentemente das populações são obtidas aplicando-se os operadores genéticos de crossover e mutação. As tarefas e as máquinas, utilizadas para o escalonamento, representa o problema de Job Shop Scheduling (JSS). Ao problema, foram aplicados alguns testes clássicos da literatura, onde se verificou a viabilidade dos SIA para tratamento de problemas de escalonamento. Ainda com os testes, pode-se observar o comportamento do sistema durante toda a execução, possibilitando assim, uma análise criteriosa das funcionalidades do sistema e dos resultados gerados pela massa de teste, observados durante um período de tempo. A representação dos sistemas imunológicos naturais através de algoritmos computacionais tem inspirado pesquisadores de todo o mundo, a motivação é que os sistemas imunológicos possuem características de paralelismo adaptabilidade e aprendizagem, além da possibilidade de serem aplicados em diversos problemas das mais diversas áreas, devido sua portabilidade.

Combinatorial optimization problems are of high academical as well as practical importance. Many instances of relevant combinatorial optimization problems are, due to their dimensions, intractable for complete methods such as branch and bound. Therefore, approximate algorithms such as metaheuristics received much attention in the past 20 years. Examples of metaheuristics are simulated annealing, tabu search, and evolutionary computation. One of the most recent metaheuristics is ant colony optimization (ACO), which was developed by Prof. M. Dorigo (who is the supervisor of this thesis) and colleagues. This thesis deals with theoretical as well as practical aspects of ant colony optimization.<p><p>* A survey of metaheuristics. Chapter 1 gives an extensive overview on the nowadays most important metaheuristics. This overview points out the importance of two important concepts in metaheuristics: intensification and diversification. <p><p>* The hyper-cube framework. Chapter 2 introduces a new framework for implementing ACO algorithms. This framework brings two main benefits to ACO researchers. First, from the point of view of the theoretician: we prove that Ant System (the first ACO algorithm to be proposed in the literature) in the hyper-cube framework generates solutions whose expected quality monotonically increases with the number of algorithm iterations when applied to unconstrained problems. Second, from the point of view of the experimental researcher, we show through examples that the implementation of ACO algorithms in the hyper-cube framework increases their robustness and makes the handling of the pheromone values easier.<p><p>* Deception. In the first part of Chapter 3 we formally define the notions of first and second order deception in ant colony optimization. Hereby, first order deception corresponds to deception as defined in the field of evolutionary computation and is therefore a bias introduced by the problem (instance) to be solved. Second order deception is an ACO-specific phenomenon. It describes the observation that the quality of the solutions generated by ACO algorithms may decrease over time in certain settings. In the second part of Chapter 3 we propose different ways of avoiding second order deception.<p><p>* ACO for the KCT problem. In Chapter 4 we outline an ACO algorithm for the edge-weighted k-cardinality tree (KCT) problem. This algorithm is implemented in the hyper-cube framework and uses a pheromone model that was determined to be well-working in Chapter 3. Together with the evolutionary computation and the tabu search approaches that we develop in Chapter 4, this ACO algorithm belongs to the current state-of-the-art algorithms for the KCT problem.<p><p>* ACO for the GSS problem. Chapter 5 describes a new ACO algorithm for the group shop scheduling (GSS) problem, which is a general shop scheduling problem that includes among others the well-known job shop scheduling (JSS) and the open shop scheduling (OSS) problems. This ACO algorithm, which is implemented in the hyper-cube framework and which uses a new pheromone model that was experimentally tested in Chapter 3, is currently the best ACO algorithm for the JSS as well as the OSS problem. In particular when applied to OSS problem instances, this algorithm obtains excellent results, improving the best known solution for several OSS benchmark instances. A final contribution of this thesis is the development of a general method for the solution of combinatorial optimization problems which we refer to as Beam-ACO. This method is a hybrid between ACO and a tree search technique known as beam search. We show that Beam-ACO is currently a state-of-the-art method for the application to the existing open shop scheduling (OSS) problem instances.<p><p> / Doctorat en sciences appliquées / info:eu-repo/semantics/nonPublished

We meet with solving of optimization problems every day, when we try to do our tasks in the best way. An Ant Colony Optimization is an algorithm inspired by behavior of ants seeking a source of food. The Ant Colony Optimization is successfuly using on optimization tasks, on which is not possible to use a classical optimization methods. A Genetic Algorithm is inspired by transmision of a genetic information during crossover. The Genetic Algorithm is used for solving optimization tasks like the ACO algorithm. The result of my master's thesis is created simulator for solving choosen optimization tasks by the ACO algorithm and the Genetic Algorithm and a comparison of gained results on implemented tasks.

No description available.

A CONWIP (Constant Work-In-Progress) system is basically a hybrid system with a PUSH-PULL interface at the first machine in the line. This research addresses the most general case of a cyclic CONWIP system by incorporating two additional constraints over earlier studies namely; stochastic processing times and limited intermediate storage. One of the main issues in the design of a CONWIP system is the WIP level 'M', to be maintained. This research proposes an iterative procedure to determine this optimal level. The second main issue is the optimization of the line by determining an appropriate job sequence. This research assumes a 'permutational' scheduling policy and proposes an iterative approach to find the best sequence. The approach utilizes a controlled enumerative approach called the Fast Insertion Heuristic (FIH) coupled with a method to appraise the quality of every enumeration at each iteration. This is done by using a modified version of the Floyd's algorithm, to determine the cycle time (or Flow time) of a partial/full solution. The performance measures considered are the Flow time and the Interdeparture time (inverse of throughput). Finally, both the methods suggested for the two subproblems, are tested through computer implementations to reveal their proficiency. / Master of Science

近年來，印刷電路板(printed circuit board, PCB)產業在台灣蓬勃發展，對台灣經濟表現有相當重要的影響；與此同時，產業內各廠商卻因內外環境變異等因素，而面臨日益激烈的競爭壓力。本研究針對產業前段的生產工廠(PCB manufacturing)從管理面探討問題來源，發現各廠商所導入的管理系統(MRP、ERP、SCM等)均缺乏現場排程(shop floor scheduling)功能，因此造成排程結果不具可行性，連帶導致管理系統的績效也未如預期理想。 　　為解決該產業所面臨的現場排程問題，本研究透過個案訪談方式，對產業特性深入了解，歸類此類問題為排程領域中的流程型工廠排程問題(flow shop scheduling)。 　　在求解過程中，本研究以總延遲時間(total tardiness)最小化為目標，並以禁忌搜尋法(tabu search)作為最佳化過程的演算法。於理論探討後，本研究亦實際建置一套排程系統，並以來自個案工廠的訂單資料實際求解，以評估此系統績效。

[pt] GRASP (Greedy Randomized Adaptive Search Procedure)é uma metaeurística de partidas múltiplas usada para obter soluções para problemas de otimização combinatória. Nesse trabalho. A metaheurística GRASP tem sido usada para obter soluções de qualidade para muitos problemas de otimização combinatória. Nesse trabalho é proposta uma metodologia para análise do comportamento da metaheurística GRASP. Também são propostas estratégias de hibridização com o religamento de caminhos. Essas estratégias foram desenvolvidas para o problema de atribuição de três índices (AP3) e para o problema de escalonamento de tarefas conhecido na literatura como job-shop schedulling problem (JSP) e são analisadas de acordo com a metodologia proposta. A metodologia para análise do comportamento do método GRASP pode ser usada para prever a partir da versão seqüencial do algoritmo, como a qualidade da solução do algoritmo implementado em paralelo irá variar. Os algoritmos GRASPs desenvolvidos para AP3 e para JSP foram paralelizados e os resultados são comparados aos resultados obtidos usando a metodologia proposta. / [en] GRASP (Greedy Randomized Adaptive Search Procedure) is a multi-start metaheuristic for combinatorial optimization problems. GRASP has been used to find quality solutions of several combinatorial optimization problems. In this work we describe a methodology for analysis of GRASP. Hybrid strategies of GRASP with path relinking are also proposed. These strategies are studied for the 3-index assignment problem (AP3) and for the job-shop schedulling problem (JSP) and are analyzed according to the methodology proposed. The methodology for analysis of GRASP is used to predict qualitatively how the quality of the solution varies in a parallel independent GRASP, using the data of the GRASP sequential version as input. The GRASPs for the AP3 and for the JSP are parallelized and the computational results are compared to the results obtained using the methodology proposed.