Made available in DSpace on 2015-04-11T14:02:44Z (GMT). No. of bitstreams: 1 aurelio.pdf: 7052556 bytes, checksum: 209649285da9d7e9789f5576368e72c7 (MD5) Previous issue date: 2013-03-26 / The quality of software design is directly related to the decisions taken during its execution, because wrong decisions may cause significant damage in a software project. Among the decisions to be performed by a software engineer, an important one would be the selection of technologies to be applied to software projects. Usually, these decisions are made taking into account the experience of the professionals involved in the task. Thus, we limit the exploration of other possibilities that could be most appropriate for such scenario, what could be offered by a scientific approach to support this decision making. This thesis presents a framework for instantiation of software technologies selection techniques by using search-based strategies. For this, the Software Technologies Selection Problem (STSP) was modeled as a combinatorial optimization problem (Minimum Dominanting Set) with the purpose of to attend different and real scenarios of Software Engineering. The proposed framework for the STSP was idealized as a mechanism to support software engineers who are not able to use other generic optimization frameworks in a software project due to tight deadlines and limited resources. It was designed to be integrated with the main meta-heuristic optimization frameworks, such as JMetal and Opt4J, that implement a large number of meta-heuristics. To analyze the feasibility of the proposed modeling and the developed framework, two case studies were conducted in complex and real optimization problems: (i) selection of model-based testing techniques; (ii) selection of requirements elicitation technique for critical embedded systems. The studies were performed using different meta-heuristics and their results indicate their feasibility to support the selection of software technologies. / A qualidade de um projeto de software está diretamente relacionada com as decisões tomadas durante suas diversas fases, pois decisões equivocadas podem causar danos significativos no projeto. Entre as decisões de um engenheiro de software, pode ser citada a escolha de tecnologias a serem aplicadas em um projeto de software. Geralmente estas decisões são tomadas levando-se em conta a experiência dos profissionais envolvidos nas tarefas. Assim, deixa-se de explorar outras soluções mais adequadas para tal cenário, algo que uma abordagem científica de apoio a tal seleção poderia oferecer. O trabalho apresenta um framework para instanciação de técnicas de seleção de tecnologias de software baseado em estratégias de busca. Para isso, o Problema de Seleção de Tecnologias de Software, do inglês Software Technologies Selection Problem (STSP) foi modelado como um problema de otimização combinatória (Conjunto Dominante Mínimo) com o objetivo de atender diferentes cenários reais de Engenharia de Software. O framework proposto para STSP foi idealizado como um mecanismo de apoio aos engenheiros de software que possuiriam dificuldades em usar outros frameworks de otimização genéricos durante um projeto de software, devido a prazos curtos e recursos limitados. Tal framework foi desenvolvido para ser integrado com os principais frameworks de meta-heurística de otimização identificados na literatura técnica, como JMetal e Opt4J, que implementam um grande número de meta-heurísticas. Para analisar a viabilidade da modelagem proposta para o STSP e do framework desenvolvido, foram realizados dois estudos de casos em problemas de otimização do mundo real: (i) seleção de técnicas de teste baseado em modelos; (ii) seleção de técnicas de elicitação de requisitos para sistemas embarcados. Os estudos foram realizados utilizando diferentes meta-heurísticas. Os resultados indicam sua viabilidade de apoio à seleção de tecnologias de software.

Neste trabalho é apresentado o projeto de uma fonte de tensão de referência, um circuito capaz de prover uma tensão invariante com a temperatura, a tensão de alimentação e o processo de fabricação. São apresentadas: as equações de funcionamento, os passos para a elaboração da uma topologia final, o dimensionamento dos parâmetros de projeto com o uso de algoritmos metaheurísticos, o desenho do layout e os resultados e análises finais. O projeto emprega a tecnologia CMOS de 0,35 &#956m com quatro camadas de metal da Austria Micro Systems, em que os VTH0\'s dos transistores NMOS e PMOS, modelo típico, são, respectivamente, 0,5 V e -0,7 V. O circuito de fonte de referência é do tipo bandgap e faz a soma ponderada de correntes proporcionais a temperatura para atingir uma tensão de referência. Obteve-se um circuito típico com 0,5 V de tensão de referência, coeficiente de temperatura de 15 ppm/ºC em intervalo de temperatura de -10 a 90ºC em 1,0 V de tensão de alimentação, regulação de linha de 263 ppm/V em um intervalo de variação de 1,0 V a 2,5 V em 27ºC, 2,7 &#956A de corrente consumida e área de 0,11 mm². A introdução de um bloco de ajuste de coeficiente de temperatura, com ajuste digital, permite que mais que 90% dos circuitos produzidos tenham um coeficiente de temperatura de até 30 ppm/ºC. As medidas realizadas no trabalho são provenientes de simulações elétricas realizadas com o ELDO e modelos BSIM3v3. / In this work is presented a design of a reference voltage source, circuits capable to provide an invariant voltage regardless of the temperature, power supply and fabrication process. It\'s presented: the operation equations, the steps to elaborate a final topology, the project parameter sizing using a metaheuristic algorithm, the drawing of the layout, and the final results and its analysis. The design employs an AMS-CMOS 0.35 &#956m technology with four metal levels, whose NMOS and PMOS VTH0\'s for a typical circuit is 0.5 V and -0.7 V. The reference voltage circuit is bandgap and performs a weighted summation of proportional temperature currents to achieve the voltage reference. A typical circuit was obtained with 0.5 V reference voltage, 15 ppm/ºC temperature coefficient in the temperature range of -10 to 90ºC under 1.0 V power supply, 263 ppm/V line regulation in the range of 1.0 V to 2.5 V under 27ºC, 2.7 &#956A power consumption in a 0.11 mm² area. For a projected circuit its also possible to ensure a temperate coefficient under 30 ppm/ºC, for more than 95% of the produced circuits, employing an adjustment block which ought to be digitally calibrated for each circuit.

Geradores de referência, ou fontes de tensão de referência, são largamente empregados na composição de diversos circuitos eletrônicos, pois são responsáveis por gerar e manter uma tensão constante para o restante do circuito. Como se trata de um circuito analógico e que possui diversas condições a serem atendidas (baixo coeficiente de temperatura, baixa tensão de alimentação, baixa regulação de linha, dentre outras), sua complexidade é alta e isso se reflete no tempo/dificuldade de um projeto. Com a finalidade de aumentar a qualidade do circuito e diminuir o tempo de projeto, foi estudado o projeto de fontes de tensão de referência através da aplicação de metaheurísticas, que são métodos de otimização utilizados em problemas que não possuem solução analítica. As metaheurísticas aplicadas foram: algoritmos genéticos, simulated annealing e pattern search, todos disponíveis em uma toolbox de otimização do Matlab. A fonte projetada, utilizando uma topologia proposta neste trabalho, fornece uma tensão de referência de 0,302 V em 300 K a uma tensão mínima de operação de 1,01 V. O coeficiente de temperatura, no intervalo de -10°C a 90°C, é de 19 ppm/°C a 1,01 V e a regulação de linha, com tensão de alimentação no intervalo de 1,01 V a 2,5 V, é de 81 ppm/V a 300 K. O consumo de potência é de 4,2 \'mü\'W, também em 300 K e a 1,01 V e a área é de 0,061 \'MM POT.2\'. Como resultado, mostrou-se a eficiência da utilização destes métodos no dimensionamento de elementos do circuito escolhido e foi obtida uma fonte de tensão de referência que atende aos critérios estabelecidos e é superior quanto ao critério de regulação de linha, quando comparada a outras fontes da literatura. Neste trabalho, foi utilizada a tecnologia CMOS de 0,35 \'mü\'m da Austria Micro Systems (AMS). / Voltage references are widely employed to compose electronic circuits, since they are responsible for generating and maintaining a constant voltage to the rest of the circuit. As it is an analog circuit and it has several conditions to fulfill (low temperature coefficient, low supply voltage, low line regulation, among others), its complexity is high, which reflects at the time/difficulties of a design. In order to increase the quality of the circuit and to minimize the design time, it was studied voltage references design using metaheuristics, which are optimization methods used in problems with no analytical solution. The applied metaheuristics were: genetic algorithms, simulated annealing and pattern search, they are all available in an optimization toolbox at Matlab. The designed voltage reference, applying a topology proposed in this work, provides a reference voltage of 0.302 V at 300 K at a minimum supply voltage of 1.01 V. The temperature coefficient, from -10°C to 90°C, is 19 ppm/°C at 1.01 V and the line regulation, using a supply voltage from 1.01 V to 2.5 V, is 81 ppm/V at 300 K. The power consumption is 4.2 W also at 300 K and 1.01 V and the area is 0.061 \'MM POT.2\'. As a result, it was shown that those methods are efficient in sizing the devices of the chosen topology and it was obtained a voltage reference that fulfills all established criteria and that is superior at the line regulation criterion, when compared to other voltage reference of the literature. In this work, the 0.35-\'mü\'m CMOS technology provided by Austria Micro Systems (AMS) was used.

[pt] Problemas de Programação de Horários (PPHs) tem sido amplamente estudados, dada a sua importância prática e teórica. A maioria das variações do problema pertence µa classe NP-Difícil. Em geral, trata-se da alocação de recursos materiais e humanos no espaço e no tempo, visando a otimização de um conjunto de objetivos definidos. Na Programação de Horários de Cursos Universitários, por exemplo, o objetivo pode ser a satisfação do corpo docente e o desempenho acadêmico dos alunos. Nos últimos anos, as formulações de PPHs propostas pela International Timetabling Competition (ITC) tem sido bastante utilizadas, sendo notável a predominância de métodos baseados em busca local e metaeurísticas entre as abordagens propostas recentemente. Este trabalho tem como objetivo propor algoritmos para o Problema de Programação de Horários Pós-Matrícula da ITC, focando principalmente em métodos heurísticos baseados em Programação Matemática. Entre os modelos de Programação Linear Inteira Mista que propomos para este problema, destaca-se o modelo baseado na Formulação de Representantes Assimétricos para o Problema de Coloração de Grafos. Abordamos a aplicação da heurística de Local Branching e propomos um esquema de resolução por Geração de Colunas, como forma de viabilizar o tratamento dos modelos propostos, uma vez que a complexidade de tais modelos representa um desafio para os resolvedores de Programação Linear Inteira Mista atualmente disponíveis. / [en] Timetabling Problems have been widely studied, given its practical and theorical relevance. Most of its variations belong to the NP-Hard class of problems. In general, it is about allocation of material and human resources in time and space, aiming to optimize some set of defined objetives. In University Course Timetabling, for example, the objective might be the satisfaction of professors and the academic performance of students. In the last years, the formulations for timetabling problems proposed by the In- ternational Timetabling Competition (ITC) have been widely adopted. The predominance of meta-heuristics and local search-based methods is remark- able among the recently proposed approaches. The objetive of this thesis is to propose algorithms for the Post Enrolment-based Course Timetabling Problem of the ITC, focusing on Mathematical Programming-based heuris- tic methods. Among the Mixed Integer Linear Programming models that we propose for this problem, we highlight the one based on the Asymetric Representatives Formulation for the Graph Coloring Problem. We explore the application of the Local Branching heuristic and we propose a Column Generation solution procedure, as an attempt to handle the proposed models, given that the complexity of such models poses a challenge for currently available Mixed Integer Linear Programming solvers.

Cette thèse porte sur la modélisation et la résolution de différents problèmes intégrés d'ordonnancement et de transport. Ces problèmes demandent, entre autre, une coordination entre des activités/opérations de production, qui se définissent par une date de début et une durée, et des opérations de transport, qui se définissent par une date de début, une date de fin et une quantité transportée. Pour résoudre ces problèmes, plusieurs méthodes d'optimisation de type métaheuristique sont proposées, afin d’obtenir des solutions de bonne qualité dans des temps raisonnables. Trois problèmes intégrés sont traités successivement : 1) un problème d’ordonnancement à une machine avec un problème de transport limité à un seul véhicule ; 2) un problème d’ordonnancement à une machine avec un problème de transport à plusieurs véhicules ; 3) un problème d’ordonnancement de type RCPSP avec une flotte hétérogène de véhicules, permettant le transport des ressources entre les activités. Le premier problème est un problème d'ordonnancement/transport de type PTSP (Production and Transportation Scheduling Problem - PTSP), limité à un seul véhicule, présenté en 2008 par Geismar et al.. Une méthode de résolution de type GRASP×ELS est proposée dans le chapitre 2, les résultats obtenus avec cette méthode sont comparés aux meilleurs résultats de la littérature. Cette méthode est étendue dans le chapitre 3, afin de traiter du problème de PTPSP, avec une flotte homogène de véhicules. La méthode proposée possède un champ d'application plus large que la méthode de Geimar et al., dédiée au PTSP avec un véhicule, mais permet de résoudre efficacement le cas à un véhicule. Le dernier problème traité concerne la résolution d'un RCPSP, dans lequel une flotte de véhicules assure le transport d'une ressource d'une activité à l'autre. L'objectif est d'offrir une approche tirant profit de décisions stratégiques (organiser des échanges – flot – entre des sites), pour déterminer un plan de transport. La difficulté principale consiste à utiliser le flot, pour déterminer les opérations de transport (création de lots), afin de résoudre le problème d'affectation des véhicules, pour finalement ordonnancer les opérations de transport. Sur ce problème, une méthode heuristique de transformation est présentée dans le chapitre 4, ainsi qu’une méthode exacte (basée sur un algorithme de plus court chemin à contraintes de ressources) dans le chapitre 5. / This dissertation focuses on modelling and resolution of integrated scheduling and routing problems. Efficient resolutions of these problems required a proper coordination of activities/production operation, defined by starting and finishing times, and of transport operations, fully defined by starting times, finishing times and quantities of resources transferred.The resolution of this problem is based on several metaheuristics, with the aim to obtain high quality solutions in acceptable computational time. Three problems are iteratively studied considering: 1) a single machine scheduling problem and a transportation problem with a single vehicle; 2) a single machine scheduling problem with a homogeneous fleet of vehicles for the transport; 3) a RCPSP where the flow transferred between activities is transported by a heterogeneous fleet of vehicles.The first problem addressed is the PTSP (Production and Transportation Scheduling Problem - PTSP) where the routing part is devoted to a single vehicle (Geismar et al., 2008). The chapter 2 focuses on a GRASP×ELS method benchmarked with the best published methods. This method is extended to the PTSP with multiple vehicles in the chapter 3, and the method shows its capacity to address a wide range of problem, since the PTSP with a single vehicle is a special case. The second problem deals with the RCPSP, where a heterogeneous fleet of vehicles is devoted to the transportation of resources, between activities. The objective consists in considering a flow (activity exchanges solved at a strategic level), to compute a transportation plan. The main difficulties consists in using the flow to compute transport batches. A heuristic-based approach is introduced in the chapter 4 and an exact method is provided in the chapter 5.

Multi-objective optimization is a growing field of interest for both theoretical and applied research, mostly due to the higher accuracy with which multi-objective problems (MOPs) model real- world scenarios. While single-objective models simplify real-world problems, MOPs can contain several (and often conflicting) objective functions to be optimized at once. This increased accuracy, however, comes at the expense of a higher difficulty that MOPs pose for optimization algorithms in general, and so a significant research effort has been dedicated to the development of approximate and heuristic algorithms. In particular, a number of proposals concerning the adaptation of evolutionary algorithms (EAs) for multi-objective problems can be seen in the literature, evidencing the interest they have received from the research community.This large number of proposals, however, does not mean that the full search power offered by multi- objective EAs (MOEAs) has been properly exploited. For instance, in an attempt to propose significantly novel algorithms, many authors propose a number of algorithmic components at once, but evaluate their proposed algorithms as monolithic blocks. As a result, each time a novel algorithm is proposed, several questions that should be addressed are left unanswered, such as (i) the effectiveness of individual components, (ii) the benefits and drawbacks of their interactions, and (iii) whether a better algorithm could be devised if some of the selected/proposed components were replaced by alternative options available in the literature. This component-wise view of MOEAs becomes even more important when tackling a new application, since one cannot antecipate how they will perform on the target scenario, neither predict how their components may interact. In order to avoid the expensive experimental campaigns that this analysis would require, many practitioners choose algorithms that in the end present suboptimal performance on the application they intend to solve, wasting much of the potential MOEAs have to offer.In this thesis, we take several significant steps towards redefining the existng algorithmic engineering approach to MOEAs. The first step is the proposal of a flexible and representative algorithmic framework that assembles components originally used by many different MOEAs from the literature, providing a way of seeing algorithms as instantiations of a unified template. In addition, the components of this framework can be freely combined to devise novel algorithms, offering the possibility of tailoring MOEAs according to the given application. We empirically demonstrate the efficacy of this component-wise approach by designing effective MOEAs for different target applications, ranging from continuous to combinatorial optimization. In particular, we show that the MOEAs one can tailor from a collection of algorithmic components is able to outperform the algorithms from which those components were originally gathered. More importantly, the improved MOEAs we present have been designed without manual assistance by means of automatic algorithm design. This algorithm engineering approach considers algorithmic components of flexible frameworks as parameters of a tuning problem, and automatically selects the component combinations that lead to better performance on a given application. In fact, this thesis also represents significant advances in this research direction. Primarily, this is the first work in the literature to investigate this approach for problems with any number of objectives, as well as the first to apply it to MOEAs. Secondarily, our efforts have led to a significant number of improvements in the automatic design methodology applied to multi-objective scenarios, as we have refined several aspects of this methodology to be able to produce better quality algorithms.A second significant contribution of this thesis concerns understanding the effectiveness of MOEAs (and in particular of their components) on the application domains we consider. Concerning combina- torial optimization, we have conducted several investigations on the multi-objective permutation flowshop problem (MO-PFSP) with four variants differing as to the number and nature of their objectives. Through thorough experimental campaigns, we have shown that some components are only effective when jointly used. In addition, we have demonstrated that well-known algorithms could easily be improved by replacing some of their components by other existing proposals from the literature. Regarding continuous optimization, we have conducted a thorough and comprehensive performance assessment of MOEAs and their components, a concrete first step towards clearly defining the state-of-the-art for this field. In particular, this assessment also encompasses many-objective optimization problems (MaOPs), a sub-field within multi-objective optimization that has recently stirred the MOEA community given its theoretical and practical demands. In fact, our analysis is instrumental to better understand the application of MOEAs to MaOPs, as we have discussed a number of important insights for this field. Among the most relevant, we highlight the empirical verification of performance metric correlations, and also the interactions between structural problem characteristics and the difficulty increase incurred by the high number of objectives.The last significant contribution from this thesis concerns the previously mentioned automatically generated MOEAs. In an initial feasibility study, we have shown that MOEAs automatically generated from our framework are able to consistently outperform the original MOEAs from where its components were gathered both for the MO-PFSP and for MOPs/MaOPs. The major contribution from this subset, however, regards continuous optimization, as we significantly advance the state-of-the-art for this field. To accomplish this goal, we have extended our framework to encompass approaches that are primarily used for this continuous problems, although the conceptual modeling we use is general enough to be applied to any domain. From this extended framework we have then automatically designed state-of- the-art MOEAs for a wide range of experimental scenarios. Moreover, we have conducted an in-depth analysis to explain their effectiveness, correlating the role of algorithmic components with experimental factors such as the stopping criterion or the performance metric adopted.Finally, we highlight that the contributions of this thesis have been increasingly recognized by the scientific community. In particular, the contributions to the research of MOEAs applied to continuous optimization are remarkable given that this is the primary application domain for MOEAs, having been extensively studied for a couple decades now. As a result, chapters from this work have been accepted for publication in some of the best conferences and journals from our field. / Doctorat en Sciences de l'ingénieur et technologie / info:eu-repo/semantics/nonPublished

Ce travail de doctorat aborde trois thématiques: (i) l’ordonnancement des systèmes de production à cheminements multiples et plus particulièrement le Job-shop soumis à un seuil de consommation énergétique ; (ii) la résolution d’un problème d’ordonnancement et d’affectation dans le contexte d’un système flexible de production sous la forme d’un Job-shop Flexible ; (iii) les méthodes de couplage entre la simulation et l’optimisation dans le cadre des problèmes de Job-shop avec incertitude. Différentes approches de résolutions sont appliquées pour chaque problème : une formalisation mathématique est proposée ainsi que plusieurs métaheuristiques (GRASP×ELS, VNS, MA, NSGA-II hybride et GRASP×ELS itéré) pour le Job-shop avec contrainte énergétique. Une extension du GRASP×ELS, notée GRASP-mELS, est ensuite proposée pour résoudre un problème de Job-shop Flexible ; différents systèmes de voisinages utilisés lors des phases de diversification et d’intensification des solutions sont également présentés. Les résultats montrent que les performances du GRASP-mELS sont comparables à celles de la littérature à la fois en terme de qualité et de temps de calcul. La dernière thématique concerne les méthodes de couplage entre optimisation et simulation avec deux problèmes étudiés : 1) un Job-shop Stochastique et 2) un Job-shop Flexible Réactif. Les méthodes de résolution reposent sur des métaheuristiques et sur le langage de simulation SIMAN intégré dans l’environnement ARENA. Les résultats montrent que les deux approches permettent de mieux prendre en compte les aspects aléatoires liés à la réalité des systèmes de production. / This doctoral work addresses three themes: (i) the scheduling of multi-path production systems and more specifically the Job-shop subjected to a power threshold; (ii) the resolution of a scheduling and assignment problem in the context of a flexible production system modelled as a Flexible Job-shop; (iii) the coupling methods between simulation and optimisation in the context of Job-shop problems with uncertainty. Different resolution approaches are applied for each problem: a mathematical formalisation is proposed as well as several metaheuristics (GRASP×ELS, VNS, MA, hybrid NSGA-II and iterated GRASP×ELS) for the Job-shop with power requirements. An extension of the GRASP×ELS, denoted GRASP-mELS, is then proposed to solve a Flexible Job-shop problem; different neighbourhood systems used during the diversification and intensification phases of solutions are also presented. The results show that the performances of the GRASP-mELS are comparable to the methods presented in the literature both in terms of quality of solutions and computation time. The last topic concerns the coupling methods between optimisation and simulation with two problems: 1) a Stochastic Job-shop and 2) a Reactive Flexible Job-shop. The resolution methods are based on metaheuristics and the SIMAN simulation language integrated in the ARENA environment. The results show that both approaches allow to better take into account the random aspects related to the reality of production systems.

This paper considers a real world waste collection problem in which glass, metal, plastics, or paper is brought to certain waste collection points by the citizens of a certain region. The collection of this waste from the collection points is therefore a node routing problem. The waste is delivered to special sites, so called intermediate facilities (IF), that are typically not identical with the vehicle depot. Since most waste collection points need not be visited every day, a planning period of several days has to be considered. In this context three related planning problems are considered. First, the periodic vehicle routing problem with intermediate facilities (PVRP-IF) is considered and an exact problem formulation is proposed. A set of benchmark instances is developed and an efficient hybrid solution method based on variable neighborhood search and dynamic programming is presented. Second, in a real world application the PVRP-IF is modified by permitting the return of partly loaded vehicles to the depots and by considering capacity limits at the IF. An average improvement of 25% in the routing cost is obtained compared to the current solution. Finally, a different but related problem, the so called multi-depot vehicle routing problem with inter-depot routes (MDVRPI) is considered. In this problem class just a single day is considered and the depots can act as an intermediate facility only at the end of a tour. For this problem several instances and benchmark solutions are available. It is shown that the algorithm outperforms all previously published metaheuristics for this problem class and finds the best solutions for all available benchmark instances.

Cette thèse s’intéresse aux problèmes d’emploi du temps d’universités. Ces problèmes sont rencontrés chaque année par les utilisateurs. Nous proposons des bornes inférieures, des méthodes heuristiques et des modèles de programmation mixte en nombres entiers et de programmation par contraintes. Nous traitons le problème d’emploi du temps d’examens et celui d’affectation des étudiants. Nous proposons de nouvelles méthodes et formulations et les comparons aux approches existantes. Nous proposons, pour le problème d’emploi du temps d’examens, une amélioration d’un modèle mathématique en nombres entiers qui permettra d’obtenir des solutions optimales. Ensuite, des bornes inférieures, une formulation plus compacte des contraintes et un modèle de programmation par contraintes sont proposés. Pour le problème d’emploi du temps d’examens à l’Université de Technologie de Compiègne, nous proposons une approche mémétique. Enfin, nous présentons un modèle mathématique pour le problème d’affectation des étudiants et nous étudions sa performance sur un ensemble d’instances réelles. / This thesis investigates university timetabling problems. These problems occur across universities and are faced each year by the practitioners. We propose new lower bounds, heuristic approaches, mixed integer and constraint programming models to solve them. We address the exam timetabling and the student scheduling problem. We investigate new methods and formulations and compare them to the existing approaches. For exam timetabling, we propose an improvement to an existing mixed integer programming model that makes it possible to obtain optimal solutions. Next, lower bounds, a more compact reformulation for constraints and a constraint programming model are proposed. For the exam timetabling problem at Université de Technologie de Compiègne, we designed a memetic approach. Finally, we present a new formulation for the student scheduling problem and investigate its performance on a set of real-world instances.

Nous élaborons une approche multi-agents pour la résolution des problèmes d’optimisation combinatoire nommée MAOM-COP. Elle combine des métaheuristiques, les systèmes multi-agents et l’apprentissage par renforcement. Les heuristiques manquent d’une vue d’ensemble sur l’évolution de la recherche. Notre objectif consiste à utiliser les systèmes multi-agents pour créer des méthodes de recherche coopératives. Ces méthodes explorent plusieurs métaheuristiques. MAOM-COP est composée de plusieurs agents qui sont l’agent décideur, les agents intensificateurs et les agents diversificateurs (agents croisement et agent perturbation). A l’aide de l’apprentissage, l’agent décideur décide dynamiquement quel agent à activer entre les agents intensificateurs et les agents croisement. Si les agents intensificateurs sont activés, ils appliquent des algorithmes de recherche locale. Durant leurs recherches, ils peuvent s’échanger des informations, comme ils peuvent déclencher l’agent perturbation. Si les agents croisement sont activés, ils exécutent des opérateurs de recombinaison. Nous avons appliqué MAOM-COP sur les problèmes suivants : l’affectation quadratique, la coloration des graphes, la détermination des gagnants et le sac à dos multidimensionnel. MAOM-COP possède des performances compétitives par rapport aux algorithmes de l’état de l’art. / We elaborate a multi-agent based optimization method for combinatorial optimization problems named MAOM-COP. It combines metaheuristics, multiagent systems and reinforcement learning. Although the existing heuristics contain several techniques to escape local optimum, they do not have an entire vision of the evolution of optimization search. Our main objective consists in using the multi-agent system to create intelligent cooperative methods of search. These methods explore several existing metaheuristics. MAOMCOP is composed of the following agents: the decisionmaker agent, the intensification agents and the diversification agents which are composed of the perturbation agent and the crossover agents. Based on learning techniques, the decision-maker agent decides dynamically which agent to activate between intensification agents and crossover agents. If the intensifications agents are activated, they apply local search algorithms. During their searches, they can exchange information, as they can trigger the perturbation agent. If the crossover agents are activated, they perform recombination operations. We applied MAOMCOP to the following problems: quadratic assignment, graph coloring, winner determination and multidimensional knapsack. MAOM-COP shows competitive performances compared with the approaches of the literature