'A Bayesian Optimisation Algorithm for the Nurse Scheduling Problem'

Abstract- A Bayesian optimization algorithm for the nurse scheduling problem is presented, which involves choosing a suitable scheduling rule from a set for each nurse's assignment. Unlike our previous work that used GAs to implement implicit learning, the learning in the proposed algorithm is explicit, i.e. eventually, we will be able to identify and mix building blocks directly. The Bayesian optimization algorithm is applied to implement such explicit learning by building a Bayesian network of the joint distribution of solutions. The conditional probability of each variable in the network is computed according to an initial set of promising solutions. Subsequently, each new instance for each variable is generated by using the corresponding conditional probabilities, until all variables have been generated, i.e. in our case, a new rule string has been obtained. Another set of rule strings will be generated in this way, some of which will replace previous strings based on fitness selection. If stopping conditions are not met, the conditional probabilities for all nodes in the Bayesian network are updated again using the current set of promising rule strings. Computational results from 52 real data instances demonstrate the success of this approach. It is also suggested that the learning mechanism in the proposed approach might be suitable for other scheduling problems.

Optimisation de l'extraction, en réacteur "batch", de biomasse énergétique à l'aide d'émulsions ultrasoniques de solvants verts

L’industrie des biocarburants de deuxième génération utilise, entre autre, la biomasse lignocellulosique issue de résidus forestiers et agricoles et celle issue de cultures énergétiques. Le sorgho sucré [Sorghum bicolor (L.) Moench] fait partie de ces cultures énergétiques. L’intérêt croissant de l’industrie agroalimentaire et des biocarburants pour cette plante est dû à sa haute teneur en sucres (jusqu’à 60% en masse sèche). En plus de se développer rapidement (en 5-6 mois), le sorgho sucré a l’avantage de pouvoir croître sur des sols pauvres en nutriments et dans des conditions de faibles apports en eau, ce qui en fait une matière première intéressante pour l’industrie, notamment pour la production de bioéthanol. Le concept de bioraffinerie alliant la production de biocarburants à celle de bioénergies ou de bioproduits est de plus en plus étudié afin de valoriser la production des biocarburants. Dans le contexte d’une bioraffinerie exploitant la biomasse lignocellulosique, il est nécessaire de s’intéresser aux différents métabolites extractibles en plus des macromolécules permettant la fabrication de biocarburants et de biocommodités. Ceux-ci pouvant avoir une haute valeur ajoutée et intéresser l’industrie pharmaceutique ou cosmétique par exemple. Les techniques classiques pour extraire ces métabolites sont notamment l’extraction au Soxhlet et par macération ou percolation, qui sont longues et coûteuses en énergie. Ce projet s’intéresse donc à une méthode d’extraction des métabolites primaires et secondaires du sorgho sucré, moins coûteuse et plus courte, permettant de valoriser économiquement l’exploitation industrielle du de cette culture énergétique. Ce travail au sein de la CRIEC-B a porté spécifiquement sur l’utilisation d’une émulsion ultrasonique eau/carbonate de diméthyle permettant de diminuer les temps d’opération (passant à moins d’une heure au lieu de plusieurs heures) et les quantités de solvants mis en jeu dans le procédé d’extraction. Cette émulsion extractive permet ainsi de solubiliser à la fois les métabolites hydrophiles et ceux hydrophobes. De plus, l’impact environnemental est limité par l’utilisation de solvants respectueux de l’environnement (80 % d’eau et 20 % de carbonate de diméthyle). L’utilisation de deux systèmes d’extraction a été étudiée. L’un consiste en la recirculation de l’émulsion, en continu, au travers du lit de biomasse; le deuxième permet la mise en contact de la biomasse et des solvants avec la sonde à ultrasons, créant l’émulsion et favorisant la sonolyse de la biomasse. Ainsi, en réacteur « batch » avec recirculation de l’émulsion eau/DMC, à 370 mL.min[indice supérieur -1], au sein du lit de biomasse, l’extraction est de 37,91 % en 5 minutes, ce qui est supérieur à la méthode ASTM D1105-96 (34,01 % en 11h). De plus, en réacteur « batch – piston », où la biomasse est en contact direct avec les ultrasons et l’émulsion eau/DMC, les meilleurs rendements sont de 35,39 % en 17,5 minutes, avec 15 psig de pression et 70 % d’amplitude des ultrasons. Des tests effectués sur des particules de sorgho grossières ont donné des résultats similaires avec 30,23 % d’extraits en réacteur « batch » avec recirculation de l’émulsion (5 min, 370 mL.min[indice supérieur -1]) et 34,66 % avec le réacteur « batch-piston » (30 psig, 30 minutes, 95 % d’amplitude).

Optimisation tools for flip-chip design

Abstract not available

Optimisation of digitally coded test vectors for mixed-signal components

International audience

Cascade hydropower capacity increase profitability analysis with optimisation modelling

The electricity market and climate are both undergoing a change. The changes impact hydropower and provoke an interest for hydropower capacity increases. In this thesis a new methodology was developed utilising short-term hydropower optimisation and planning software for better capacity increase profitability analysis accuracy. In the methodology income increases are calculated in month long periods while varying average discharge and electricity price volatility. The monthly incomes are used for constructing year scenarios, and from different types of year scenarios a long-term profitability analysis can be made. Average price development is included utilising a multiplier. The method was applied on Oulujoki hydropower plants. It was found that the capacity additions that were analysed for Oulujoki were not profitable. However, the methodology was found versatile and useful. The result showed that short periods of peaking prices play major role in the profitability of capacity increases. Adding more discharge capacity to hydropower plants that initially bypassed water more often showed the best improvements both in income and power generation profile flexibility.

Improved Squeaky Wheel Optimisation for Driver Scheduling

This paper presents a technique called Improved Squeaky Wheel Optimisation (ISWO) for driver scheduling problems. It improves the original Squeaky Wheel Optimisation’s (SWO) effectiveness and execution speed by incorporating two additional steps of Selection and Mutation which implement evolution within a single solution. In the ISWO, a cycle of Analysis-Selection-Mutation-Prioritization-Construction continues until stopping conditions are reached. The Analysis step first computes the fitness of a current solution to identify troublesome components. The Selection step then discards these troublesome components probabilistically by using the fitness measure, and the Mutation step follows to further discard a small number of components at random. After the above steps, an input solution becomes partial and thus the resulting partial solution needs to be repaired. 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, the optimisation in the ISWO is achieved by solution disruption, iterative improvement and an iterative constructive repair process performed. Encouraging experimental results are reported.

Bayesian Optimisation Algorithm for Nurse Scheduling, Scalable Optimization via Probabilistic Modeling

Our research has shown that schedules can be built mimicking a human scheduler by using a set of rules that involve domain knowledge. This chapter presents a Bayesian Optimization Algorithm (BOA) for the nurse scheduling problem that chooses such suitable scheduling rules from a set for each nurse’s assignment. Based on the idea of using probabilistic models, the BOA builds a Bayesian network for the set of promising solutions and samples these networks to generate new candidate solutions. Computational results from 52 real data instances demonstrate the success of this approach. It is also suggested that the learning mechanism in the proposed algorithm may be suitable for other scheduling problems.

Noise Reduction Technique for a Simulation Optimisation Study

This paper reports on an attempt to apply Genetic Algorithms to the problem of optimising a complex system, through discrete event simulation (Simulation Optimisation), with a view to reducing the noise associated with such a procedure. We are applying this proposed solution approach to our application test bed, a Crossdocking distribution centre, because it provides a good representative of the random and unpredictable behaviour of complex systems i.e. automated machine random failure and the variability of manual order picker skill. It is known that there is noise in the output of discrete event simulation modelling. However, our interest focuses on the effect of noise on the evaluation of the fitness of candidate solutions within the search space, and the development of techniques to handle this noise. The unique quality of our proposed solution approach is we intend to embed a noise reduction technique in our Genetic Algorithm based optimisation procedure, in order for it to be robust enough to handle noise, efficiently estimate suitable fitness function, and produce good quality solutions with minimal computational effort.

Valeur pronostique de CD73 et des lymphocytes T CD8 et optimisation de la vaccination de type GVAX dans le cancer de la prostate

CD73 est un ecto-enzyme qui a été associé à la suppression de l'immunité anti-tumorale. Ses valeurs pronostiques et thérapeutiques ont été mises de l'avant dans plusieurs types de cancer. La première hypothèse du projet est que l'expression de CD73 dans la tumeur prédit le pronostic des patients atteints du cancer de la prostate. L'expression de CD73 a été étudiée par immunofluorescence dans des échantillons de tumeur. Puis, des analyses univariées et multivariées ont été conduites pour déterminer si l'expression de CD73 permet de prédire la récidive biochimique des patients. Nous avons déterminé que CD73 prédit indépendamment le pronostic des patients atteints du cancer de la prostate. De plus, nous avons déterminé que son expression dans le tissu normal adjacent ou dans la tumeur prédit différemment la survenue de la récidive biochimique. La deuxième hypothèse est que l'inhibition de CD73 permet d'améliorer l'efficacité d'un vaccin thérapeutique contre le cancer de la prostate. L'effet d'un vaccin de type GVAX a été étudié dans des souris CD73KO ou en combinaison avec un anticorps ciblant CD73. Nous avons observé que l'efficacité du vaccin était augmentée dans les souris où CD73 était absent. Cependant, la combinaison avec l'anti-CD73 n'a pas permis d'améliorer l'efficacité.

A III-V channel field effect transistor for non-classical CMOS: process optimisation for improved gate stack function

This thesis describes a collection of studies into the electrical response of a III-V MOS stack comprising metal/GaGdO/GaAs layers as a function of fabrication process variables and the findings of those studies. As a result of this work, areas of improvement in the gate process module of a III-V heterostructure MOSFET were identified. Compared to traditional bulk silicon MOSFET design, one featuring a III-V channel heterostructure with a high-dielectric-constant oxide as the gate insulator provides numerous benefits, for example: the insulator can be made thicker for the same capacitance, the operating voltage can be made lower for the same current output, and improved output characteristics can be achieved without reducing the channel length further. It is known that transistors composed of III-V materials are most susceptible to damage induced by radiation and plasma processing. These devices utilise sub-10 nm gate dielectric films, which are prone to contamination, degradation and damage. Therefore, throughout the course of this work, process damage and contamination issues, as well as various techniques to mitigate or prevent those have been investigated through comparative studies of III-V MOS capacitors and transistors comprising various forms of metal gates, various thicknesses of GaGdO dielectric, and a number of GaAs-based semiconductor layer structures. Transistors which were fabricated before this work commenced, showed problems with threshold voltage control. Specifically, MOSFETs designed for normally-off (VTH > 0) operation exhibited below-zero threshold voltages. With the results obtained during this work, it was possible to gain an understanding of why the transistor threshold voltage shifts as the gate length decreases and of what pulls the threshold voltage downwards preventing normally-off device operation. Two main culprits for the negative VTH shift were found. The first was radiation damage induced by the gate metal deposition process, which can be prevented by slowing down the deposition rate. The second was the layer of gold added on top of platinum in the gate metal stack which reduces the effective work function of the whole gate due to its electronegativity properties. Since the device was designed for a platinum-only gate, this could explain the below zero VTH. This could be prevented either by using a platinum-only gate, or by matching the layer structure design and the actual gate metal used for the future devices. Post-metallisation thermal anneal was shown to mitigate both these effects. However, if post-metallisation annealing is used, care should be taken to ensure it is performed before the ohmic contacts are formed as the thermal treatment was shown to degrade the source/drain contacts. In addition, the programme of studies this thesis describes, also found that if the gate contact is deposited before the source/drain contacts, it causes a shift in threshold voltage towards negative values as the gate length decreases, because the ohmic contact anneal process affects the properties of the underlying material differently depending on whether it is covered with the gate metal or not. In terms of surface contamination; this work found that it causes device-to-device parameter variation, and a plasma clean is therefore essential. This work also demonstrated that the parasitic capacitances in the system, namely the contact periphery dependent gate-ohmic capacitance, plays a significant role in the total gate capacitance. This is true to such an extent that reducing the distance between the gate and the source/drain ohmic contacts in the device would help with shifting the threshold voltages closely towards the designed values. The findings made available by the collection of experiments performed for this work have two major applications. Firstly, these findings provide useful data in the study of the possible phenomena taking place inside the metal/GaGdO/GaAs layers and interfaces as the result of chemical processes applied to it. In addition, these findings allow recommendations as to how to best approach fabrication of devices utilising these layers.

'A Bayesian Optimisation Algorithm for the Nurse Scheduling Problem'

Abstract- A Bayesian optimization algorithm for the nurse scheduling problem is presented, which involves choosing a suitable scheduling rule from a set for each nurse's assignment. Unlike our previous work that used GAs to implement implicit learning, the learning in the proposed algorithm is explicit, i.e. eventually, we will be able to identify and mix building blocks directly. The Bayesian optimization algorithm is applied to implement such explicit learning by building a Bayesian network of the joint distribution of solutions. The conditional probability of each variable in the network is computed according to an initial set of promising solutions. Subsequently, each new instance for each variable is generated by using the corresponding conditional probabilities, until all variables have been generated, i.e. in our case, a new rule string has been obtained. Another set of rule strings will be generated in this way, some of which will replace previous strings based on fitness selection. If stopping conditions are not met, the conditional probabilities for all nodes in the Bayesian network are updated again using the current set of promising rule strings. Computational results from 52 real data instances demonstrate the success of this approach. It is also suggested that the learning mechanism in the proposed approach might be suitable for other scheduling problems.

Optimisation of a crossdocking distribution centre simulation model

This paper reports on continuing research into the modelling of an order picking process within a Crossdocking distribution centre using Simulation Optimisation. The aim of this project is to optimise a discrete event simulation model and to understand factors that affect finding its optimal performance. Our initial investigation revealed that the precision of the selected simulation output performance measure and the number of replications required for the evaluation of the optimisation objective function through simulation influences the ability of the optimisation technique. We experimented with Common Random Numbers, in order to improve the precision of our simulation output performance measure, and intended to use the number of replications utilised for this purpose as the initial number of replications for the optimisation of our Crossdocking distribution centre simulation model. Our results demonstrate that we can improve the precision of our selected simulation output performance measure value using Common Random Numbers at various levels of replications. Furthermore, after optimising our Crossdocking distribution centre simulation model, we are able to achieve optimal performance using fewer simulations runs for the simulation model which uses Common Random Numbers as compared to the simulation model which does not use Common Random Numbers.

Climbing Combinatorial Fitness Landscapes

International audience