L'entreprise "Cyres-group" cherche à améliorer le temps de réponse de ses grappes Hadoop et la manière dont les ressources sont exploitées dans son centre de données. Les idées sous-jacentes à la réduction du temps de réponse sont de faire en sorte que (i) les travaux soumis se terminent au plus tôt et que (ii) le temps d'attente de chaque utilisateur du système soit réduit. Nous identifions deux axes d'amélioration : 1. nous décidons d'intervenir pour optimiser l'ordonnancement des travaux sur une plateforme Hadoop. Nous considérons le problème d'ordonnancement d'un ensemble de travaux du type MapReduce sur une plateforme homogène. 2. Nous décidons d'évaluer et proposer des outils capables (i) de fournir plus de flexibilité lors de la gestion des ressources dans le centre de données et (ii) d'assurer l'intégration d'Hadoop dans des infrastructures Cloud avec le minimum de perte de performance. Dans une première étude, nous effectuons une revue de la littérature. À la fin de cette étape, nous remarquons que les modèles mathématiques proposés dans la littérature pour le problème d'ordonnancement ne modélisent pas toutes les caractéristiques d'une plateforme Hadoop. Nous proposons à ce niveau un modèle plus réaliste qui prend en compte les aspects les plus importants tels que la gestion des ressources, la précédence entre les travaux, la gestion du transfert des données et la gestion du réseau. Nous considérons une première modélisation simpliste et nous considérons la minimisation de la date de fin du dernier travail (Cmax) comme critère à optimiser. Nous calculons une borne inférieure à l'aide de la résolution du modèle mathématique avec le solveur CPLEX. Nous proposons une heuristique (LocFirst) et nous l'évaluons. Ensuite, nous faisons évoluer notre modèle et nous considérons, comme fonction objective, la somme des deux critères identifiés depuis la première étape : la minimisation de la somme pondérée des dates de fin des travaux ( ∑ wjCj) et la minimisation du (Cmax). Nous cherchons à minimiser la moyenne pondérée des deux critères, nous calculons une borne inférieure et nous proposons deux heuristiques de résolution. / "Cyres-Group" is working to improve the response time of his clusters Hadoop and optimize how the resources are exploited in its data center. That is, the goals are to finish work as soon as possible and reduce the latency of each user of the system. Firstly, we decide to work on the scheduling problem in the Hadoop system. We consider the problem as the problem of scheduling a set of jobs on a homogeneous platform. Secondly, we decide to propose tools, which are able to provide more flexibility during the resources management in the data center and ensure the integration of Hadoop in Cloud infrastructures without unacceptable loss of performance. Next, the second level focuses on the review of literature. We conclude that, existing works use simple mathematical models that do not reflect the real problem. They ignore the main characteristics of Hadoop software. Hence, we propose a new model ; we take into account the most important aspects like resources management and the relations of precedence among tasks and the data management and transfer. Thus, we model the problem. We begin with a simplistic model and we consider the minimisation of the Cmax as the objective function. We solve the model with mathematical solver CPLEX and we compute a lower bound. We propose the heuristic "LocFirst" that aims to minimize the Cmax. In the third level, we consider a more realistic modelling of the scheduling problem. We aim to minimize the weighted sum of the following objectives : the weighted flow time ( ∑ wjCj) and the makespan (Cmax). We compute a lower bound and we propose two heuristics to resolve the problem.

Dans cette thèse, nous nous intéressons au problème de chargement des laveurs dans un service de stérilisation de dispositifs médicaux réutilisables (DMR). Ce problème de chargement des laveurs a été considéré comme un problème d'ordonnancement par batch. Nous présentons, dans un premier temps, des études offline pour lesquelles nous avons développé des algorithmes, exacts et approchés, ainsi que des modèles PLNE pour certains cas particuliers et pour des cas généraux. Nous présentons ensuite des études semi-online et online pour lesquelles nous avons développé des heuristiques. Nous avons également conçu des modèles de simulation afin de tester l'impact de nos heuristiques sur l'ensemble du service de stérilisation. Nous proposons, en dernier lieu, l'implémentation d'une approche de type bin packing pour le cas d'un service de stérilisation externe afin de minimiser le nombre de cycles de lavage lancés. / In this dissertation, we are interested in the problem of loading of washing resources in hospital sterilization services of reusable medical devices (RMD). Through our studies, we modeled the problem of loading of washing resources as a batch scheduling problem. We began our research with offline studies for whom exact algorithms are proposed for some special cases and then heuristics, approximation algorithms and linear models are proposed for general cases. Afterwards, we continued our research with semi-online and online studies for whom heuristics are developed. We inserted these heuristics also in simulation models in order to test their efficiency on the whole sterilization service. We finished our studies with a final work aiming at minimizing the number of washing cycles for an external sterilization service where we adopted a bin packing approach.

En raison de problèmes opérationnels et d’autres événements inattendus, un grand nombre d’incidents se produisent quotidiennement dans les systèmes de transport ferroviaire. Certains d’entre eux ont un impact local, mais quelques fois, essentiellement dans les réseaux ferroviaires plus saturés, des petits incidents peuvent se propager à travers tout le réseau et perturber de manière significative les horaires des trains. Dans cette thèse doctorale, nous présentons le problème de réordonnancement de plan de circulation ferroviaire en cas d’incident comme la problématique de créer un plan de circulation provisoire de manière à minimiser les effets de la propagation des incidents. Ce travail est issu du projet MAGES (Module d’Aide à la Gestion des Sillons) qui développe des systèmes de régulation pour le trafic ferroviaire. Nous présentons deux modèles différents qui permettent de trouver des solutions à ce problème : Programmation Linéaire en Nombres Entiers (PLNE) et Programmation Par Contraintes (PPC). Du fait de la nature fortement combinatoire du problème et de la nécessité de répondre rapidement aux incidents, il ne paraît pas raisonnable d’envisager une résolution exacte. Les méthodes correctives proposées consistent donc à explorer un voisinage restreint des solutions : right-shift rescheduling; une méthode basée sur des coupes de proximité; une méthode d’analyse statistique de la propagation des incidents (SAPI) et un méthode basée sur la PPC. Additionnellement, certaines de ces méthodes ont été adaptées sous forme d’algorithmes itératifs avec l’objectif d’améliorer progressivement la solution quand le temps d’exécution le permet. SAPI est une des principales contributions de cette thèse. SAPI intègre les concepts de right-shift rescheduling avec les coupes de proximité. Du fait de la taille des réseaux en jeu et du nombre de circulations, les phénomènes complexes de propagation d’un incident font qu’il est très difficile de connaitre de manière précise les événements qui seront affectés. Toutefois, il est tout de même envisageable d’évaluer la probabilité qu’un événement soit affecté. Pour calculer cette probabilité, un modèle de régression logistique est utilisé avec des variables explicatives dérivées du réseau et des circulations. Diverses variantes de ces méthodes sont évaluées et comparées en utilisant deux réseaux ferroviaires localisés en France et au Chili. À partir des résultats obtenus, il est possible de conclure que SAPI est meilleure que les autres méthodes en terme de vitesse de convergence vers l’optimum pour les instances de petite taille et moyenne alors qu’une méthode coopérative PNLE/PPC est capable de trouver des solutions pour les instances de plus grande taille. La difficulté de comparer SAPI avec d’autres méthodes présentées dans la littérature nous a encouragés à appliquer la méthode à un autre problème. Ainsi, cette méthodologie a été également adaptée au problème de réordonnancement de passagers, vols et appareils (avions) en cas de perturbations, problème originalement proposé dans le contexte du Challenge ROADEF 2009. Les résultats montrent que SAPI est efficace pour résoudre ce problème avec des solutions au-dessus de la moyenne des équipes finalistes en obtenant la troisième place du challenge / For operational and unpredictable reasons, many small incidents occur day after day in rail transportation systems. Most of them have a local impact; but, in some cases, minimal disruptions can spread out through the whole network and affect significantly the train schedules. In this Thesis, we present the Railway Rescheduling Problem (RRP) as the problem of finding a new schedule of trains after one or several incidents by minimizing some measure of the effect, e.g., the total delay. This Thesis has been developed in the context of the MAGES project that builds mathematical models and algorithms for optimizing railway operations. Two complementary formulations are proposed to model this problem: Mixed-Integer Programming (MIP) and Constraint Programming (CP). Because of the impossibility of solving real-world instances by using standard solvers, we propose several solutions methods: right-shift rescheduling; a MIP-based local search method; Statistical Analysis of Propagation of Incidents (SAPI); and a CP-based approach. Some methods are presented in different versions by extending them to iterative approaches. Among them; SAPI is one of the major contributions of this Thesis. It integrates the concepts of right-shift rescheduling and the MIP-based local search method by fixing integer variables and adding linear inequalities (cuts). SAPI assumes that the effects of disruptions can be propagated to other upcoming events. Nevertheless, this propagation is not uniform to all events and could be forecasted by a statistical analysis. Different versions of the methods are compared in two different networks located in France and Chile. From the results, it is possible to conclude that SAPI finds good solutions faster than the other methods, while a cooperative CP/MIP approach that takes advantage of both formulations seems to be appropriate for large instances. Because of the difficulty to compare SAPI to other methods presented in the literature due to lack of public benchmarks, we applied it to another problem where public instances are available. Hence, the methodology was adapted and applied to the problem of rescheduling passengers, flights, and aircraft under disrupted operations in the context of the ROADEF challenge 2009. SAPI took the third position on this competition, showing that the method seems to be effective solving such type of problems efficiently

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

This dissertation studies in depth the structure of the Discrete Ordered Median Problem (DOMP), to define new formulations and resolution algorithms. Furthermore we analyze an interesting extension for DOMP, namely MDOMP (Monotone Discrete Ordered Median Problem). This thesis is structured in three main parts.First, a widely theoretical and computational study is reported. It presents several new formulations for the Discrete Ordered Median Problem (DOMP) based on its similarity with some scheduling problems. Some of the new formulations present a considerably smaller number of constraints to define the problem with respect to some previously known formulations. Furthermore, the lower bounds provided by their linear relaxations improve the ones obtained with previous formulations in the literature even when strengthening is not applied. We also present a polyhedral study of the assignment polytope of our tightest formulation showing its proximity to the convex hull of the integer solutions of the problem. Several resolution approaches, among which we mention a branch and cut algorithm, are compared. Extensive computational results on two families of instances, namely randomly generated and from Beasley's OR-library, show the power of our methods for solving DOMP. One of the achievements of the new formulation consists in its tighter LP-bound. Secondly, DOMP is addressed with a new set partitioning formulation using an exponential number of variables. This chapter develops a new formulation in which each variable corresponds to a set of demand points allocated to the same facility with the information of the sorting position of their corresponding distances. We use a column generation approach to solve the continuous relaxation of this model. Then, we apply a branch-cut-and-price algorithm to solve to optimality small to moderate size of DOMP in competitive computational time.To finish, the third contribution of this dissertation is to analyze and compare formulations for the monotone discrete ordered median problem. These formulations combine different ways to represent ordered weighted averages of elements by using linear programs together with the p-median polytope. This approach gives rise to two efficient formulations for DOMP under a hypothesis of monotonicity in the lambda vectors. These formulations are theoretically compared and also compared with some other formulations valid for the case of general lambda vector. In addition, it is also developed another new formulation, for the general case, that exploits the efficiency of the rationale of monotonicity. This representation allows to solve very efficiently some DOMP instances where the monotonicity is only slightly lost. Detailed computational tests on all these formulations is reported in the dissertation. They show that specialized formulations allow to solve to optimality instances with sizes that are far beyond the limits of those that can solve in the general case. / Cette dissertation étudie en profondeur la structure du "Discrete Ordered Median Problem" (DOMP), afin de proposer de nouvelles formulations et de nouveaux algorithmes de résolution. De plus, une extension intéressante du DOMP nommée MDOMP ("Monotone Discrete Ordered Median Problem") a été étudiée.Cette thèse a été structurée en trois grandes parties.La première partie présente une étude riche aux niveaux théorique et expérimentale. Elle développe plusieurs formulations pour le DOMP qui sont basées sur des problèmes d'ordonnancement largement étudiés dans la littérature. Plusieurs d'entres elles nécessitent un nombre réduit de contraintes pour définir le problème en ce qui concerne certaines formulations connues antérieurement. Les bornes inférieures, qui sont obtenues par la résolution de la relaxation linéaire, donnent de meilleurs résultats que les formulations précédentes et ceci même avec tout processus de renforcement désactivé. S'ensuit une étude du polyhèdre de notre formulation la plus forte qui montre sa proximité entre l'enveloppe convexe des solutions entières de notre problème. Un algorithme de branch and cut et d'autres méthodes de résolution sont ensuite comparés. Les expérimentations qui montrent la puissance de nos méthodes s'appuient sur deux grandes familles d'instances. Les premières sont générées aléatoirement et les secondes proviennent de Beasley's OR-library. Ces expérimentations mettent en valeur la qualité de la borne obtenue par notre formulation.La seconde partie propose une formulation "set partitioning" avec un nombre exponentiel de variables. Dans ce chapitre, la formulation comporte des variables associées à un ensemble de demandes affectées à la même facilité selon l'ordre établi sur leurs distances correspondantes. Nous avons alors développé un algorithme de génération de colonnes pour la résolution de la relaxation continue de notre modèle mathématique. Cet algorithme est ensuite déployé au sein d'un Branch-and-Cut-and-Price afin de résoudre des instances de petites et moyennes tailles avec des temps compétitifs.La troisième partie présente l'analyse et la comparaison des différentes formulations du problème DOMP Monotone. Ces formulations combinent plusieurs manières de formuler l'ordre des éléments selon les moyennes pondérées en utilisant plusieurs programmes linéaires du polytope du p-median. Cette approche donne lieu à deux formulations performantes du DOMP sous l'hypothèse de monotonie des vecteurs lambda. Ces formulations sont comparées de manière théorique puis comparées à d'autres formulations valides pour le cas général du vecteur lambda. Une autre formulation est également proposée, elle exploite l'efficacité du caractère rationnel de la monotonie. Cette dernière permet de résoudre efficacement quelques instances où la monotonie a légèrement disparue. Ces formulations ont fait l'objet de plusieurs expérimentations dècrites dans ce manuscrit de thèse. Elles montrent que les formulations spécifiques permettent de résoudre des instances plus importantes que pour le cas général. / Este trabajo estudia en profundidad la estructura del problema disctreto de la mediana ordenada (DOMP, por su acrónimo en inglés) con el objetivo de definir nuevas formulaciones y algoritmos de resolución. Además, analizamos una interesante extensión del DOMP conocida como el problema monótono discreto de la mediana ordenada (MDOMP, de su acrónimo en inglés).Esta tesis se compone de tres grandes bloques.En primer lugar, se desarrolla un detallado estudio teórico y computacional. Se presentan varias formulaciones nuevas para el problema discreto de la mediana ordenada (DOMP) basadas en su similaridad con algunos problemas de secuenciación. Algunas de estas formulaciones requieren de un cosiderable menor número de restricciones para definir el problema respecto a algunas de las formulaciones previamente conocidas. Además, las cotas inferiores proporcionadas por las relajaciones lineales mejoran a las obtenidas con formulaciones previas de la literatura incluso sin reforzar la nueva formulación. También presentamos un estudio poliédrico del politopo de asignación de nuestra formulación más compacta mostrando su proximidad con la envolvente convexa de las soluciones enteras del problema. Se comparan algunos procedimientos de resolución, entre los que destacamos un algoritmo de ramificación y corte. Amplios resultados computacionales sobre dos familias de instancias -aleatoriamente generadas y utilizando la Beasley's OR-library- muestran la potencia de nuestros métodos para resolver el DOMP.En el segundo bloque, el problema discreto de la mediana ordenada es abordado con una formulación de particiones de conjuntos empleando un número exponencial de variables. Este capítulo desarrolla una nueva formulación en la que cada variable corresponde a un conjunto de puntos de demanda asignados al mismo servidor con la información de la posición obtenida de ordenar las distancias correspondientes. Utilizamos generación de columnas para resolver la relajación continua del modelo. Después, empleamos un algoritmo de ramificación, acotación y "pricing" para resolver a optimalidad tamaños moderados del DOMP en un tiempo computacional competitivo.Por último, el tercer bloque de este trabajo se dedica a analizar y comparar formulaciones para el problema monótono discreto de la mediana ordenada. Estas formulaciones combinan diferentes maneras de representar medidas de pesos ordenados de elementos utilizando programación lineal junto con el politopo de la $p$-mediana. Este enfoque da lugar a dos formulaciones eficientes para el DOMP bajo la hipótesis de monotonía en su vector $lambda$. Se comparan teóricamente las formulaciones entre sí y frente a algunas de las formulaciones válidas para el caso general. Adicionalmente, se desarrolla otra formulación válida para el caso general que explota la eficiencia de las ideas de la monotonicidad. Esta representación permite resolver eficientemente algunos ejemplos donde la monotonía se pierde ligeramente. Finalmente, llevamos a cabo un detallado estudio computacional, en el que se aprecia que las formulaciones ad hoc permiten resolver a optimalidad ejemplos cuyo tamaño supera los límites marcados en al caso general. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Benchmarking is a technique used by Decision Making Units (DMUs) to enable continuous quality improvement. Benchmarking includes almost any activity that compares a DMU's performance with some standard. Benchmarking offers the possibility of optimizing the DMU's processes, services, outcomes and products through those comparisons. Quite often, benchmarking is understood to be an act of imitating or copying but in reality benchmarking proves to be a concept that helps in innovation rather than imitation. Though benchmarking is not new, it has become popular both as an analytical research instrument and a practical decision-support tool. To some, benchmarking is not a choice; it is a necessity. Indeed, the penalty for neglecting proper benchmarking is loss of competitive edge, which is the key to survival and profitability.Usually, benchmarking involves four distinct phases. Phase I: determine the set of comparison partners. There are three types of benchmarking procedure: internal benchmarking (i.e. the benchmark is chosen within the same organization), functional benchmarking (i.e. the benchmark is chosen regardless of which industry they are) and competitive benchmarking (i.e a competitor is used as the benchmark). Phase II: collect the data. Much information is already in the public domain (financial reports, newspaper reports, analysts' reports) but it is unlikely to provide all the information required for a successful benchmarking exercise. Phase III: analyze the collected information which results in the creation of a model and an identification of performance gaps. The model will have huge influence on the results. It is crucial to motivate all assumptions made in that phase. The model could be specific to the benchmarking exercise. Phase IV: the action phase. Analyzing the reasons for the performance differentials and use the findings to redefine goals, redesign processes, and change expectations regarding the evaluated DMU's own functions and activities.Amongst the models chosen in Phase III, Data Envelopment Analysis (DEA) has received more and more attention in the benchmarking literature. The goal of such analysis is to evaluate the efficiency of a DMU by comparing its input-output performance to that of other DMUs operating in a similar technological environment. The increasing attention for DEA could be explained by two main reasons. On the one hand, DEA does not resort to any unverifiable parametric/functional specifications of the production technology but rather lets the data speak for themselves by reconstructing the production possibilities using the observed inputs and outputs and imposing some technology axioms (such as monotonicity, convexity, returns-to-scale). Consequently, DEA is nonparametric in nature. On the other hand, deviation from efficiency, which is measured as the distance to the reconstructed production possibilities, is very easily computed. Indeed, the computation of the efficiency measures merely requires solving simple linear programming problems.Recently, Cherchye et al (2008, 2013) argued that standard DEA models provide a black-box treatment of efficiency production behavior since they ignore the links between inputs and outputs, i.e. they implicitly assume that all the inputs produce all the outputs simultaneously. This assumption is not plausible in several applications (e.g. employees that are allocated to different productions processes, specific capital which is used to produce only one type of goods). These authors suggested a multi-output nonparametric efficiency measurement technique, based on a cost minimization condition, which uses available information on the allocation of inputs to outputs. The new methodology characterizes each output by its own production technology while accounting for interdependencies between the different output-specific technologies giving rise to scope economies. This methodology provides a more realistic modelling of the production process and has a bigger ability to detect inefficient behavior (i.e. has more discriminatory power) than standard DEA techniques.In this thesis, we extend the method suggested by Cherchye et al (2008, 2013) in several directions. Firstly, we incorporate bad outputs (in contrast to good outputs). This extension deals in a natural way with several limitations of existing DEA approaches to treat undesirable outputs. As demonstrated with our application to the electricity sector. Next, we extend the methodology to allow for output-specific returns-to-scale assumptions. This allows for a more flexible model that does not force the practitioners to choose the same returns-to-scale assumption for all the outputs (as it is the case for the standard DEA model). This simultaneous choice could be difficult to defend in several settings but it is surely the case when undesirable outputs are present in the production process, as demonstrated in our application. Next, we extend the methodology for multi-output producers by considering a dynamic context. We suggest a new productivity index which takes the form of a Malmquist Productivity Index. Finally, we also generalize the method of Cherchye et al (2008, 2013), based on a cost minimization condition, to a profit maximization condition. This establishes a novel DEA toolkit for profit efficiency assessments in situations with multiple inputs and multiple outputs. We apply this new model to the case of electricity plants. / Doctorat en Sciences économiques et de gestion / info:eu-repo/semantics/nonPublished

The interdisciplinary field of systems biology has evolved rapidly over the last few years. Different disciplines have contributed to the development of both its experimental and theoretical branches.Although computational biology has been an increasing activity in computer science for more than a two decades, it has been only in the past few years that optimization models have been increasingly developed and analyzed by researchers whose primary background is Operations Research(OR). This dissertation aims at contributing to the field of computational biology by applying mathematical programming to certain problems in molecular biology.Specifically, we address three problems in the domain of Genome Wide Association Studies}:(i) the Pure Parsimony Haplotyping Under uncertatind Data Problem that consists in finding the minimum number of haplotypes necessary to explain a given set of genotypes containing possible reading errors; (ii) the Parsimonious Loss Of Heterozygosity Problem that consists of partitioning suspected polymorphisms from a set of individuals into a minimum number of deletion areas; (iii) and the Multiple Individuals Polymorphic Alu Insertion Recognition Problem that consists of finding the set of locations in the genome where ALU sequences are inserted in some individual(s).All three problems are NP-hard combinatorial optimization problems. Therefore, we analyse their combinatorial structure and we propose an exact approach to solution for each of them. The proposed models are efficient, accurate, compact, polynomial-sized and usable in all those cases for which the parsimony criterion is well suited for estimation. / Option Informatique du Doctorat en Sciences / 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.

Les réseaux de capteurs sans fil suscitent une attention croissante depuis quelques années, tant les applications sont nombreuses, incluant notamment le suivi de véhicules ou la surveillance de champs de bataille. Un ensemble de capteurs disséminé aléatoirement a pour but de surveiller des cibles se déplaçant dans une région donnée. Chaque capteur a une durée de vie limitée et deux états : actif ou inactif. Un capteur actif peut surveiller des cibles dans son rayon de portée, au prix d'une consommation d'énergie. Dans cette thèse, les problèmes étudiés consistent à déterminer un ordonnancement optimal d'activités de surveillance, afin de couvrir toutes les cibles à tout instant de la mission. Nous abordons en premier lieu un problème d'ordonnancement robuste. Une cible dont on connaît la trajectoire spatiale avec précision est sujette à incertitude temporelle. Cette situation est rencontrée lorsqu'un avion vole dans un couloir aérien, qu'un train circule sur une voie ferrée, ou que de tout autre véhicule suit un itinéraire pré-déterminé. L'objectif est de calculer un ordonnancement d'activités capable de résister au plus grand écart par rapport aux dates prévisionnelles de passage de la cible. Ce premier problème est résolu à l'aide d'un algorithme exact pseudo-polynomial, reposant sur une dichotomie. En second lieu, nous étudions le problème visant à préserver la capacité de surveillance du réseau de capteurs dans un contexte multi-missions. Les cibles sont maintenant sujettes à une incertitude spatiale, c'est-à-dire susceptibles de se trouver à une distance inférieure à un seuil delta de leur position prévisionnelle. Ce second problème est résolu à l’aide d’un algorithme exact basé sur la génération de colonnes, et accéléré par une métaheuristique. Les méthodes de résolution proposées ont en commun une étape préliminaire, appelée discrétisation, qui conduit à reformuler les problèmes originaux comme des problèmes d'ordonnancement d'activités de surveillance. L'espace de surveillance est découpé en faces, ensembles de points couverts par un même sous-ensemble de capteurs. Le calcul des durées de séjour des cibles dans chaque face permet de découper la durée de la mission en fenêtres de temps, et d'envisager le problème de couverture de cibles mobiles comme une séquence de problèmes de couverture de cibles immobiles. Les algorithmes proposés pour aborder ces problèmes sont testés sur de nombreuses instances, et leurs résultats sont analysés. De nombreuses perspectives ouvertes par ces travaux sont également présentées. / Wireless sensor networks have received a particular attention during the last years, involving many applications, such as vehicle tracking or battlefield monitoring. A set of sensors is randomly dispatched in a region in order to monitor moving targets. Each sensor has a limited battery lifetime and two states: active or inactive. An active sensor is able to monitor targets inside its sensing radius, which consumes energy. In this thesis, the studied problems consist in deciding an optimal schedule of sensing activities, in order to cover all the targets at any instant of the mission. First, we study a robust scheduling problem. A target such that the spatial trajectory is exactly known is subject to temporal uncertainties. This context is met for a plane flying in an airline route, a train running on a railway, or any vehicle following a predetermined path. The objective is to compute a schedule of activities able to resist to the largest uncertainties This first problem is solved using an exact pseudo-polynomial algorithm, relying on a dichotomy. Second, we study a problem aiming at preserving enough sensor network capacity in order to perform further missions. For this problem, the targets are subject to spatial uncertainties, i.e. their actual position may be at a distance delta of their expected position. This second problem is solved using an exact algorithm based on column generation, accelerated by a metaheuristic. All the proposed methods have a common phase, called discretization, that leads to reformulate the original problems as activity scheduling problems. The monitored area is split into faces, that are defined as sets of points covered by the same set of sensors. Computing the stay duration of targets inside each face leads to split the mission duration into time windows, so the moving target tracking problem can be seen as a sequence of static target tracking problems. The proposed algorithms are tested on many instances, and the analysis of the results is provided. Numerous open perspectives of this work are also given.