Nurse Rostering with Genetic Algorithms

In recent years genetic algorithms have emerged as a useful tool for the heuristic solution of complex discrete optimisation problems. In particular there has been considerable interest in their use in tackling problems arising in the areas of scheduling and timetabling. However, the classical genetic algorithm paradigm is not well equipped to handle constraints and successful implementations usually require some sort of modification to enable the search to exploit problem specific knowledge in order to overcome this shortcoming. This paper is concerned with the development of a family of genetic algorithms for the solution of a nurse rostering problem at a major UK hospital. The hospital is made up of wards of up to 30 nurses. Each ward has its own group of nurses whose shifts have to be scheduled on a weekly basis. In addition to fulfilling the minimum demand for staff over three daily shifts, nurses’ wishes and qualifications have to be taken into account. The schedules must also be seen to be fair, in that unpopular shifts have to be spread evenly amongst all nurses, and other restrictions, such as team nursing and special conditions for senior staff, have to be satisfied. The basis of the family of genetic algorithms is a classical genetic algorithm consisting of n-point crossover, single-bit mutation and a rank-based selection. The solution space consists of all schedules in which each nurse works the required number of shifts, but the remaining constraints, both hard and soft, are relaxed and penalised in the fitness function. The talk will start with a detailed description of the problem and the initial implementation and will go on to highlight the shortcomings of such an approach, in terms of the key element of balancing feasibility, i.e. covering the demand and work regulations, and quality, as measured by the nurses’ preferences. A series of experiments involving parameter adaptation, niching, intelligent weights, delta coding, local hill climbing, migration and special selection rules will then be outlined and it will be shown how a series of these enhancements were able to eradicate these difficulties. Results based on several months’ real data will be used to measure the impact of each modification, and to show that the final algorithm is able to compete with a tabu search approach currently employed at the hospital. The talk will conclude with some observations as to the overall quality of this approach to this and similar problems.

An Indirect Genetic Algorithm for a Nurse Scheduling Problem

This paper describes a Genetic Algorithms approach to a manpower-scheduling problem arising at a major UK hospital. Although Genetic Algorithms have been successfully used for similar problems in the past, they always had to overcome the limitations of the classical Genetic Algorithms paradigm in handling the conflict between objectives and constraints. The approach taken here is to use an indirect coding based on permutations of the nurses, and a heuristic decoder that builds schedules from these permutations. Computational experiments based on 52 weeks of live data are used to evaluate three different decoders with varying levels of intelligence, and four well-known crossover operators. Results are further enhanced by introducing a hybrid crossover operator and by making use of simple bounds to reduce the size of the solution space. The results reveal that the proposed algorithm is able to find high quality solutions and is both faster and more flexible than a recently published Tabu Search approach.

Boosting the performance of metaheuristics for the MinLA problem using a more discriminating evaluation function

International audience

Path relinking for the fixed spectrum frequency assignment problem

International audience

Ordonnancement des opérations dans une unité d’extrusion

Les travaux de ce mémoire traitent du problème d’ordonnancement et d’optimisation de la production dans un environnement de plusieurs machines en présence de contraintes sur les ressources matérielles dans une usine d’extrusion plastique. La minimisation de la somme pondérée des retards est le critère économique autour duquel s’articule cette étude car il représente un critère très important pour le respect des délais. Dans ce mémoire, nous proposons une approche exacte via une formulation mathématique capable des donner des solutions optimales et une approche heuristique qui repose sur deux méthodes de construction de solution sérielle et parallèle et un ensemble de méthodes de recherche dans le voisinage (recuit-simulé, recherche avec tabous, GRASP et algorithme génétique) avec cinq variantes de voisinages. Pour être en totale conformité avec la réalité de l’industrie du plastique, nous avons pris en considération certaines caractéristiques très fréquentes telles que les temps de changement d’outils sur les machines lorsqu’un ordre de fabrication succède à un autre sur une machine donnée. La disponibilité des extrudeuses et des matrices d’extrusion représente le goulot d’étranglement dans ce problème d’ordonnancement. Des séries d’expérimentations basées sur des problèmes tests ont été effectuées pour évaluer la qualité de la solution obtenue avec les différents algorithmes proposés. L’analyse des résultats a démontré que les méthodes de construction de solution ne sont pas suffisantes pour assurer de bons résultats et que les méthodes de recherche dans le voisinage donnent des solutions de très bonne qualité. Le choix du voisinage est important pour raffiner la qualité de la solution obtenue. Mots-clés : ordonnancement, optimisation, extrusion, formulation mathématique, heuristique, recuit-simulé, recherche avec tabous, GRASP, algorithme génétique

An algorithm for optimum control of static VAR compensators to meet phase-wise unbalanced reactive power demands

The operation of thyristor-controlled static VAR compensators (SVCs) at various conduction angles can be used advantageously to meet the unablanced reactive power demands in a system. However, such operation introduces harmonic currents into the AC system. This paper presents an algorithm to evaluate an optimum combination of the phase-wise reactive power generations from SVC and balanced reactive power supply from the AC system, based on the defined performance indices, namely, the telephone influence factor (TIF), the total harmonic current factor (IT) and the distortion factor (D). Results of the studies conducted on a typical distribution system are presented and discussed.

Reactive state selectivity in photodimerization through micellar counter-ion effects: photodimerization of acenaphthylenes

Photodimerization of acenaphthylene and 5,6-dichloroacenaphthylene solubilized in sodium dodecylsulphate (SDS), cetyltrimethylammonium chloride (CTAC), dodecyltrimethylammonium chloride (DTAC), cetyltrimethylammonium bromide (CTAB) and Triton X-100 micelles gives a mixture of cis and trans dimers. The magnitude of the cis:trans ratio is sensitive to the type of micelle used. In CTAB micelles the heavy atom effect of the bromide counter-ions leads to an increased triplet-derived trans dimer yield, whereas in micelles with light atom counter-ions (CTAC, DTAC and SDS) the singlet-derived cis dimer predominates.

Effect of oxygen partial pressure on the structural and optical properties of dc reactive magnetron sputtered molybdenum oxide films

Molybdenum oxide films (MoO3) were deposited on glass and crystalline silicon substrates by sputtering of molybdenum target under various oxygen partial pressures in the range 8 × 10−5–8 × 10−4 mbar and at a fixed substrate temperature of 473 K employing dc magnetron sputtering technique. The influence of oxygen partial pressure on the composition stoichiometry, chemical binding configuration, crystallographic structure and electrical and optical properties was systematically studied. X-ray photoelectron spectra of the films formed at 8 × 10−5 mbar showed the presence of Mo6+ and Mo5+ oxidation states of MoO3 and MoO3−x. The films deposited at oxygen partial pressure of 2 × 10−4 mbar showed Mo6+ oxidation state indicating the films were nearly stoichiometric. It was also confirmed by the Fourier transform infrared spectroscopic studies. X-ray diffraction studies revealed that the films formed at oxygen partial pressure of 2 × 10−4 mbar showed the presence of (0 k 0) reflections indicated the layered structure of α-phase MoO3. The electrical conductivity of the films decreased from 3.6 × 10−5 to 1.6 × 10−6 Ω−1 cm−1, the optical band gap of the films increased from 2.93 to 3.26 eV and the refractive index increased from 2.02 to 2.13 with the increase of oxygen partial pressure from 8 × 10−5 to 8 × 10−4 mbar, respectively.

Fabrication and mechanisms of densification of ZrB2-based ultra high temperature ceramics by reactive hot pressing

Dense ZrB2-SiC (25-30 vol%) composites have been produced by reactive hot pressing using stoichiometric Zr, B4C, C and Si powder mixtures with and without Ni addition at 40 MPa, 1600 degrees C for 60 min. Nickel, a common additive to promote densification, is shown not to be essential; the presence of an ultra-fine microstructure containing a transient plastic ZrC phase is suggested to play a key role at low temperatures, while a transient liquid phase may be responsible at temperatures above 1350 degrees C. Hot Pressing of non-stoichiometric mixture of Zr, B4C and Si at 40 MPa, 1600 degrees C for 30 min resulted in ZrB2-ZrCx-SiC (15 vol%) composites of similar to 98% RD.

Optimal reactive power dispatch based on voltage stability criteria in a large power system with AC/DC and FACTs devices

An algorithm for optimal allocation of reactive power in AC/DC system using FACTs devices, with an objective of improving the voltage profile and also voltage stability of the system has been presented. The technique attempts to utilize fully the reactive power sources in the system to improve the voltage stability and profile as well as meeting the reactive power requirements at the AC-DC terminals to facilitate the smooth operation of DC links. The method involves successive solution of steady-state power flows and optimization of reactive power control variables with Unified Power Flow Controller (UPFC) using linear programming technique. The proposed method has been tested on a real life equivalent 96-bus AC and a two terminal DC system under normal and contingency conditions.

Fuzzy-expert approach for voltage-reactive power dispatch

The voltage stability control problem has become an important concern for utilities transmitting power over long distances. This paper presents an approach using fuzzy set theory for reactive power control with the purpose of improving the voltage stability of a power system. To minimize the voltage deviations from pre-desired values of all the load buses, using the sensitivities with respect to reactive power control variables form the basis of the proposed fuzzy logic control (FLC). Control variables considered are switchable VAR compensators, On Load Tap Changing (OLTC) transformers and generator excitations. Voltage deviations and controlling variables are translated into fuzzy set notations to formulate the relation between voltage deviations and controlling ability of controlling devices. The developed fuzzy system is tested on a few simulated practical Indian power systems and some IEEE standard test systems. The performance of the fuzzy system is compared with conventional optimization technique and results obtained are encouraging. Results obtained for a 24 - node equivalent EHV system of part of Indian southern grid and IEEE New England 39-bus system are presented for illustration purposes. The proposed Fuzzy-Expert technique is found suitable for on-line applications in energy control centre as the solution is obtained fast with significant speedups.

Population-based local search for protein folding simulation in the MJ energy model and cubic lattices

We present experimental results on benchmark problems in 3D cubic lattice structures with the Miyazawa-Jernigan energy function for two local search procedures that utilise the pull-move set: (i) population-based local search (PLS) that traverses the energy landscape with greedy steps towards (potential) local minima followed by upward steps up to a certain level of the objective function; (ii) simulated annealing with a logarithmic cooling schedule (LSA). The parameter settings for PLS are derived from short LSA-runs executed in pre-processing and the procedure utilises tabu lists generated for each member of the population. In terms of the total number of energy function evaluations both methods perform equally well, however. PLS has the potential of being parallelised with an expected speed-up in the region of the population size. Furthermore, both methods require a significant smaller number of function evaluations when compared to Monte Carlo simulations with kink-jump moves. (C) 2009 Elsevier Ltd. All rights reserved.

A heuristic method for reactive power planning

An approach for solving reactive power planning problems is presented, which is based on binary search techniques and the use of a special heuristic to obtain a discrete solution. Two versions were developed, one to run on conventional (sequential) computers and the other to run on a distributed memory (hypercube) machine. This latter parallel processing version employs an asynchronous programming model. Once the set of candidate buses has been defined, the program gives the location and size of the reactive sources needed(if any) in keeping with operating and security constraints.