Continuous Quality Assurance and Optimisation in Cloud-Based Virtual Enterprises

Part 18: Optimization in Collaborative Networks

An evolutionary squeaky wheel optimisation approach to personnel scheduling

The quest for robust heuristics that are able to solve more than one problem is ongoing. In this paper, we present, discuss and analyse a technique called Evolutionary Squeaky Wheel Optimisation and apply it to two different personnel scheduling problems. Evolutionary Squeaky Wheel Optimisation improves the original Squeaky Wheel Optimisation’s effectiveness and execution speed by incorporating two additional steps (Selection and Mutation) for added evolution. In the Evolutionary Squeaky Wheel Optimisation, a cycle of Analysis-Selection-Mutation-Prioritization-Construction continues until stopping conditions are reached. The aim of the Analysis step is to identify below average solution components by calculating a fitness value for all components. The Selection step then chooses amongst these underperformers and discards some probabilistically based on fitness. The Mutation step further discards a few components at random. Solutions can become incomplete and thus repairs may be required. The repair is carried out by using the Prioritization step to first produce priorities that determine an order by which the following Construction step then schedules the remaining components. Therefore, improvements in the Evolutionary Squeaky Wheel Optimisation is achieved by selective solution disruption mixed with iterative improvement and constructive repair. Strong experimental results are reported on two different domains of personnel scheduling: bus and rail driver scheduling and hospital nurse scheduling.

Étude de la médiane de permutations sous la distance de Kendall-Tau

La distance de Kendall-τ compte le nombre de paires en désaccord entre deux permuta- tions. La distance d’une permutation à un ensemble est simplement la somme des dis- tances entre cette permutation et les permutations de l’ensemble. À partir d’un ensemble donné de permutations, notre but est de trouver la permutation, appelée médiane, qui minimise cette distance à l’ensemble. Le problème de la médiane de permutations sous la distance de Kendall-τ, trouve son application en bio-informatique, en science politique, en télécommunication et en optimisation. Ce problème d’apparence simple est prouvé difficile à résoudre. Dans ce mémoire, nous présentons plusieurs approches pour résoudre le problème, pour trouver une bonne solution approximative, pour le séparer en classes caractéristiques, pour mieux com- prendre sa compléxité, pour réduire l’espace de recheche et pour accélérer les calculs. Nous présentons aussi, vers la fin du mémoire, une généralisation de ce problème et nous l’étudions avec ces mêmes approches. La majorité du travail de ce mémoire se situe dans les trois articles qui le composent et est complémenté par deux chapitres servant à les lier.

FOCUS : frailty management optimisation through EIPAHA commitments and utilisation of stakeholders’ input – an innovative European project in elderly care

The goal of FOCUS, which stands for Frailty Management Optimization through EIPAHA Commitments and Utilization of Stakeholders’ Input, is to reduce the burden of frailty in Europe. The partners are working on advancing knowledge of frailty detection, assessment, and management, including biological, clinical, cognitive and psychosocial markers, in order to change the paradigm of frailty care from acute intervention to prevention. FOCUS partners are working on ways to integrate the best available evidence from frailty-related screening tools, epidemiological and interventional studies into the care of frail people and their quality of life. Frail citizens in Italy, Poland and the UK and their caregivers are being called to express their views and their experiences with treatments and interventions aimed at improving quality of life. The FOCUS Consortium is developing pathways to leverage the knowledge available and to put it in the service of frail citizens. In order to reach out to the broadest audience possible, the FOCUS Platform for Knowledge Exchange and the platform for Scaling Up are being developed with the collaboration of stakeholders. The FOCUS project is a development of the work being done by the European Innovation Partnership on Active and Healthy Ageing (EIPAHA), which aims to increase the average healthy lifespan in Europe by 2020 while fostering sustainability of health/social care systems and innovation in Europe. The knowledge and tools developed by the FOCUS project, with input from stakeholders, will be deployed to all EIPAHA participants dealing with frail older citizens to support activities and optimize performance.

Étude de la médiane de permutations sous la distance de Kendall-Tau

La distance de Kendall-τ compte le nombre de paires en désaccord entre deux permuta- tions. La distance d’une permutation à un ensemble est simplement la somme des dis- tances entre cette permutation et les permutations de l’ensemble. À partir d’un ensemble donné de permutations, notre but est de trouver la permutation, appelée médiane, qui minimise cette distance à l’ensemble. Le problème de la médiane de permutations sous la distance de Kendall-τ, trouve son application en bio-informatique, en science politique, en télécommunication et en optimisation. Ce problème d’apparence simple est prouvé difficile à résoudre. Dans ce mémoire, nous présentons plusieurs approches pour résoudre le problème, pour trouver une bonne solution approximative, pour le séparer en classes caractéristiques, pour mieux com- prendre sa compléxité, pour réduire l’espace de recheche et pour accélérer les calculs. Nous présentons aussi, vers la fin du mémoire, une généralisation de ce problème et nous l’étudions avec ces mêmes approches. La majorité du travail de ce mémoire se situe dans les trois articles qui le composent et est complémenté par deux chapitres servant à les lier.

Theory and optimisation of 1.3 and 1.55 μm (Al)InGaAs metamorphic quantum well lasers

The use of InGaAs metamorphic buffer layers (MBLs) to facilitate the growth of lattice-mismatched heterostructures constitutes an attractive approach to developing long-wavelength semiconductor lasers on GaAs substrates, since they offer the improved carrier and optical confinement associated with GaAs-based materials. We present a theoretical study of GaAs-based 1.3 and 1.55 μm (Al)InGaAs quantum well (QW) lasers grown on InGaAs MBLs. We demonstrate that optimised 1.3 μm metamorphic devices offer low threshold current densities and high differential gain, which compare favourably with InP-based devices. Overall, our analysis highlights and quantifies the potential of metamorphic QWs for the development of GaAs-based long-wavelength semiconductor lasers, and also provides guidelines for the design of optimised devices.

Amélioration de la représentation des processus stochastiques pour l'optimisation appliquée à la gestion des systèmes hydriques

Dans un contexte de pression toujours plus grande sur les ressources naturelles, une gestion rationnelle des ressources hydriques s'impose. La principale difficulté de leur gestion provient du caractère aléatoire des apports en eau dans le système. Le sujet de cette recherche consiste à développer des méthodes d'optimisation stochastique capable de bien représenter les processus aléatoires. Le cas de Kemano, située en Colombie-Britannique (Canada), illustre les travaux de recherche. L'importante accumulation de neige sur les bassins versants engendre une hydrologie complexe, rendant la gestion du système délicate. La programmation dynamique stochastique est la méthode la plus utilisée pour déterminer la politique de gestion des réservoirs. Mais, son étude fait ressortir que cette méthode ne peut gérer que des modèles simplifiés des processus stochastiques, ne rendant pas compte des complexes corrélations spatio-temporelles des apports hydriques. Ainsi, la politique obtenue peut être de mauvaise qualité. Cette méthode est comparée avec la recherche directe de politique qui n'utilise pas de modèles pour représenter les processus stochastiques, mais évalue la politique sur des scénarios d'apports. Ainsi la recherche directe de politique se révèle globalement plus performante en prenant bien en considération la complexité des apports, mais est limitée par la forme prédéterminée de la politique. De plus, l'optimisation des paramètres en utilisant un algorithme évolutionnaire s'avère lente. La conception d'un algorithme de descente par gradient, combinée à une architecture "acteur-critique" appropriée, permet de réduire notablement le temps d'optimisation. Combinée à une fonction plus complexe employée pour la paramétrisation de la politique de gestion, la méthode permet d'obtenir une politique de qualité significativement supérieure à celle obtenue avec la programmation dynamique stochastique. Les travaux effectués dans le cadre de cette thèse ouvrent la voie à une application opérationnelle de la méthode de recherche directe de politique. L'évaluation en simulation devrait être appréciée des opérateurs en permettant une bonne représentation du système et des apports.

Retrofit de systèmes de revalorisation de chaleur industrielle à basse température par optimisation exergo-économique

Ce projet porte, dans un souci d’efficacité énergétique, sur la récupération d’énergie des rejets thermiques à basse température. Une analyse d’optimisation des technologies dans le but d’obtenir un système de revalorisation de chaleur rentable fait objet de cette recherche. Le but sera de soutirer la chaleur des rejets thermiques et de la réappliquer à un procédé industriel. Réduire la consommation énergétique d’une usine entre habituellement en conflit avec l’investissement requis pour les équipements de revalorisation de chaleur. Ce projet de maitrise porte sur l’application d’optimisations multiobjectives par algorithme génétique (GA) pour faciliter le design en retrofit des systèmes de revalorisation de chaleur industrielle. L’originalité de cette approche consiste à l’emploi du «fast non-dominant sorting genetic algorithm» ou NSGA-II dans le but de trouver les solutions optimales entre la valeur capitale et les pertes exergétiques des réseaux d’échangeurs de chaleur et de pompes à chaleur. Identifier les solutions optimales entre le coût et l’efficacité exergétique peut ensuite aider dans le processus de sélection d’un design approprié en considérant les coûts énergétiques. Afin de tester cette approche, une étude de cas est proposée pour la récupération de chaleur dans une usine de pâte et papier. Ceci inclut l’intégration d’échangeur de chaleur Shell&tube, d’échangeur à contact direct et de pompe à chaleur au réseau thermique existant. Pour l’étude de cas, le projet en collaboration avec Cascades est constitué de deux étapes, soit de ciblage et d’optimisation de solutions de retrofit du réseau d’échangeur de chaleur de l’usine de tissus Cascades à Kinsley Falls. L’étape de ciblage, basée sur la méthode d’analyse du pincement, permet d’identifier et de sélectionner les modifications de topologie du réseau d’échangeurs existant en y ajoutant de nouveaux équipements. Les scénarios résultants passent ensuite à l’étape d’optimisation où les modèles mathématiques pour chaque nouvel équipement sont optimisés afin de produire une courbe d’échange optimal entre le critère économique et exergétique. Pourquoi doubler l’analyse économique d’un critère d’exergie? D’abord, parce que les modèles économiques sont par définition de nature imprécise. Coupler les résultats des modèles économiques avec un critère exergétique permet d’identifier des solutions de retrofit plus efficaces sans trop s’éloigner d’un optimum économique. Ensuite, le rendement exergétique permet d’identifier les designs utilisant l’énergie de haute qualité, telle que l’électricité ou la vapeur, de façon plus efficace lorsque des sources d’énergie de basse qualité, telles que les effluents thermiques, sont disponibles. Ainsi en choisissant un design qui détruit moins d’exergie, il demandera un coût énergétique moindre. Les résultats de l’étude de cas publiés dans l’article montrent une possibilité de réduction des coûts en demande de vapeur de 89% tout en réduisant la destruction d’exergie de 82%. Dans certains cas de retrofit, la solution la plus justifiable économiquement est également très proche de la solution à destruction d’exergie minimale. L’analyse du réseau d’échangeurs et l’amélioration de son rendement exergétique permettront de justifier l’intégration de ces systèmes dans l’usine. Les diverses options pourront ensuite être considérées par Cascades pour leurs faisabilités technologiques et économiques sachant qu’elles ont été optimisées.

Optimisation thermodynamique d’un procédé solaire utilisant un système de réfrigération à éjecto-compression pour la production du froid

L’objectif essentiel de cette thèse est de développer un système industriel de réfrigération ou de climatisation qui permet la conversion du potentiel de l’énergie solaire en production du froid. Ce système de réfrigération est basé sur la technologie de l’éjecto-compression qui propose la compression thermique comme alternative économique à la compression mécanique coûteuse. Le sous-système de réfrigération utilise un appareil statique fiable appelé éjecteur actionné seulement par la chaleur utile qui provient de l’énergie solaire. Il est combiné à une boucle solaire composée entre autres de capteurs solaires cylindro-paraboliques à concentration. Cette combinaison a pour objectif d’atteindre des efficacités énergétiques et exergétiques globales importantes. Le stockage thermique n’est pas considéré dans ce travail de thèse mais sera intégré au système dans des perspectives futures. En première étape, un nouveau modèle numérique et thermodynamique d’un éjecteur monophasique a été développé. Ce modèle de design applique les conditions d’entrée des fluides (pression, température et vitesse) et leur débit. Il suppose que le mélange se fait à pression constante et que l’écoulement est subsonique à l’entrée du diffuseur. Il utilise un fluide réel (R141b) et la pression de sortie est imposée. D’autre part, il intègre deux innovations importantes : il utilise l'efficacité polytropique constante (plutôt que des efficacités isentropiques constantes utilisées souvent dans la littérature) et n’impose pas une valeur fixe de l'efficacité du mélange, mais la détermine à partir des conditions d'écoulement calculées. L’efficacité polytropique constante est utilisée afin de quantifier les irréversibilités au cours des procédés d’accélérations et de décélération comme dans les turbomachines. La validation du modèle numérique de design a été effectuée à l’aide d’une étude expérimentale présente dans la littérature. La seconde étape a pour but de proposer un modèle numérique basé sur des données expérimentales de la littérature et compatible à TRNSYS et un autre modèle numérique EES destinés respectivement au capteur solaire cylindro-parabolique et au sous-système de réfrigération à éjecteur. En définitive et après avoir développé les modèles numériques et thermodynamiques, une autre étude a proposé un modèle pour le système de réfrigération solaire à éjecteur intégrant ceux de ses composantes. Plusieurs études paramétriques ont été entreprises afin d’évaluer les effets de certains paramètres (surchauffe du réfrigérant, débit calorifique du caloporteur et rayonnement solaire) sur sa performance. La méthodologie proposée est basée sur les lois de la thermodynamique classique et sur les relations de la thermodynamique aux dimensions finies. De nouvelles analyses exergétiques basées sur le concept de l’exergie de transit ont permis l'évaluation de deux indicateurs thermodynamiquement importants : l’exergie produite et l’exergie consommée dont le rapport exprime l’efficacité exergétique intrinsèque. Les résultats obtenus à partir des études appliquées à l’éjecteur et au système global montrent que le calcul traditionnel de l’efficacité exergétique selon Grassmann n’est désormais pas un critère pertinent pour l'évaluation de la performance thermodynamique des éjecteurs pour les systèmes de réfrigération.

Optimisation de l’extraction de lumière de scintillation dans les matrices de détecteurs pixellisés pour des applications en tomographie d’émission par positrons (TEP) et en tomodensitométrie (TDM)

Résumé : Les performances de détecteurs à scintillation, composés d’un cristal scintillateur couplé à un photodétecteur, dépendent de façon critique de l’efficacité de la collecte et de l’extraction des photons de scintillation du cristal vers le capteur. Dans les systèmes d’imagerie hautement pixellisés (e.g. TEP, TDM), les scintillateurs doivent être arrangés en matrices compactes avec des facteurs de forme défavorables pour le transport des photons, au détriment des performances du détecteur. Le but du projet est d’optimiser les performances de ces détecteurs pixels par l'identification des sources de pertes de lumière liées aux caractéristiques spectrales, spatiales et angulaires des photons de scintillation incidents sur les faces des scintillateurs. De telles informations acquises par simulation Monte Carlo permettent une pondération adéquate pour l'évaluation de gains atteignables par des méthodes de structuration du scintillateur visant à une extraction de lumière améliorée vers le photodétecteur. Un plan factoriel a permis d'évaluer la magnitude de paramètres affectant la collecte de lumière, notamment l'absorption des matériaux adhésifs assurant l'intégrité matricielle des cristaux ainsi que la performance optique de réflecteurs, tous deux ayant un impact considérable sur le rendement lumineux. D'ailleurs, un réflecteur abondamment utilisé en raison de ses performances optiques exceptionnelles a été caractérisé dans des conditions davantage réalistes par rapport à une immersion dans l'air, où sa réflectivité est toujours rapportée. Une importante perte de réflectivité lorsqu'il est inséré au sein de matrices de scintillateurs a été mise en évidence par simulations puis confirmée expérimentalement. Ceci explique donc les hauts taux de diaphonie observés en plus d'ouvrir la voie à des méthodes d'assemblage en matrices limitant ou tirant profit, selon les applications, de cette transparence insoupçonnée.

Development and optimisation of protocols for surface cleaning of cultural heritage metals

The conservation and valorisation of cultural heritage is of fundamental importance for our society, since it is witness to the legacies of human societies. In the case of metallic artefacts, because corrosion is a never-ending problem, the correct strategies for their cleaning and preservation must be chosen. Thus, the aim of this project was the development of protocols for cleaning archaeological copper artefacts by laser and plasma cleaning, since they allow the treatment of artefacts in a controlled and selective manner. Additionally, electrochemical characterisation of the artificial patinas was performed in order to obtain information on the protective properties of the corrosion layers. Reference copper samples with different artificial corrosion layers were used to evaluate the tested parameters. Laser cleaning tests resulted in partial removal of the corrosion products, but the lasermaterial interactions resulted in melting of the desired corrosion layers. The main obstacle for this process is that the materials that must be preserved show lower ablation thresholds than the undesired layers, which makes the proper elimination of dangerous corrosion products very difficult without damaging the artefacts. Different protocols should be developed for different patinas, and real artefacts should be characterised previous to any treatment to determine the best course of action. Low pressure hydrogen plasma cleaning treatments were performed on two kinds of patinas. In both cases the corrosion layers were partially removed. The total removal of the undesired corrosion products can probably be achieved by increasing the treatment time or applied power, or increasing the hydrogen pressure. Since the process is non-invasive and does not modify the bulk material, modifying the cleaning parameters is easy. EIS measurements show that, for the artificial patinas, the impedance increases while the patina is growing on the surface and then drops, probably due to diffusion reactions and a slow dissolution of copper. It appears from these results that the dissolution of copper is heavily influenced by diffusion phenomena and the corrosion product film porosity. Both techniques show good results for cleaning, as long as the proper parameters are used. These depend on the nature of the artefact and the corrosion layers that are found on its surface.

Exact Combinatorial Optimization with Graph Convolutional Neural Networks

Combinatorial optimization problems are typically tackled by the branch-and-bound paradigm. We propose to learn a variable selection policy for branch-and-bound in mixed-integer linear programming, by imitation learning on a diversified variant of the strong branching expert rule. We encode states as bipartite graphs and parameterize the policy as a graph convolutional neural network. Experiments on a series of synthetic problems demonstrate that our approach produces policies that can improve upon expert-designed branching rules on large problems, and generalize to instances significantly larger than seen during training.

Formulations and Metaheuristics for combinatorial optimization problems

Combinatorial optimization problems have been strongly addressed throughout history. Their study involves highly applied problems that must be solved in reasonable times. This doctoral Thesis addresses three Operations Research problems: the first deals with the Traveling Salesman Problem with Pickups and Delivery with Handling cost, which was approached with two metaheuristics based on Iterated Local Search; the results show that the proposed methods are faster and obtain good results respect to the metaheuristics from the literature. The second problem corresponds to the Quadratic Multiple Knapsack Problem, and polynomial formulations and relaxations are presented for new instances of the problem; in addition, a metaheuristic and a matheuristic are proposed that are competitive with state of the art algorithms. Finally, an Open-Pit Mining problem is approached. This problem is solved with a parallel genetic algorithm that allows excavations using truncated cones. Each of these problems was computationally tested with difficult instances from the literature, obtaining good quality results in reasonable computational times, and making significant contributions to the state of the art techniques of Operations Research.

High performance and energy-efficient instruction cache design and optimisation for ultra-low-power multi-core clusters

High Energy efficiency and high performance are the key regiments for Internet of Things (IoT) end-nodes. Exploiting cluster of multiple programmable processors has recently emerged as a suitable solution to address this challenge. However, one of the main bottlenecks for multi-core architectures is the instruction cache. While private caches fall into data replication and wasting area, fully shared caches lack scalability and form a bottleneck for the operating frequency. Hence we propose a hybrid solution where a larger shared cache (L1.5) is shared by multiple cores connected through a low-latency interconnect to small private caches (L1). However, it is still limited by large capacity miss with a small L1. Thus, we propose a sequential prefetch from L1 to L1.5 to improve the performance with little area overhead. Moreover, to cut the critical path for better timing, we optimized the core instruction fetch stage with non-blocking transfer by adopting a 4 x 32-bit ring buffer FIFO and adding a pipeline for the conditional branch. We present a detailed comparison of different instruction cache architectures' performance and energy efficiency recently proposed for Parallel Ultra-Low-Power clusters. On average, when executing a set of real-life IoT applications, our two-level cache improves the performance by up to 20% and loses 7% energy efficiency with respect to the private cache. Compared to a shared cache system, it improves performance by up to 17% and keeps the same energy efficiency. In the end, up to 20% timing (maximum frequency) improvement and software control enable the two-level instruction cache with prefetch adapt to various battery-powered usage cases to balance high performance and energy efficiency.