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.

A Component Based Heuristic Search Method with AdaptivePerturbations for Hospital Personnel Scheduling

Nurse rostering is a complex scheduling problem that affects hospital personnel on a daily basis all over the world. This paper presents a new component-based approach with adaptive perturbations, for a nurse scheduling problem arising at a major UK hospital. The main idea behind this technique is to decompose a schedule into its components (i.e. the allocated shift pattern of each nurse), and then mimic a natural evolutionary process on these components to iteratively deliver better schedules. The worthiness of all components in the schedule has to be continuously demonstrated in order for them to remain there. This demonstration employs a dynamic evaluation function which evaluates how well each component contributes towards the final objective. Two perturbation steps are then applied: the first perturbation eliminates a number of components that are deemed not worthy to stay in the current schedule; the second perturbation may also throw out, with a low level of probability, some worthy components. The eliminated components are replenished with new ones using a set of constructive heuristics using local optimality criteria. Computational results using 52 data instances demonstrate the applicability of the proposed approach in solving real-world problems.

Dynamic Programming Approaches for Estimating and Applying Large-scale Discrete Choice Models

People go through their life making all kinds of decisions, and some of these decisions affect their demand for transportation, for example, their choices of where to live and where to work, how and when to travel and which route to take. Transport related choices are typically time dependent and characterized by large number of alternatives that can be spatially correlated. This thesis deals with models that can be used to analyze and predict discrete choices in large-scale networks. The proposed models and methods are highly relevant for, but not limited to, transport applications. We model decisions as sequences of choices within the dynamic discrete choice framework, also known as parametric Markov decision processes. Such models are known to be difficult to estimate and to apply to make predictions because dynamic programming problems need to be solved in order to compute choice probabilities. In this thesis we show that it is possible to explore the network structure and the flexibility of dynamic programming so that the dynamic discrete choice modeling approach is not only useful to model time dependent choices, but also makes it easier to model large-scale static choices. The thesis consists of seven articles containing a number of models and methods for estimating, applying and testing large-scale discrete choice models. In the following we group the contributions under three themes: route choice modeling, large-scale multivariate extreme value (MEV) model estimation and nonlinear optimization algorithms. Five articles are related to route choice modeling. We propose different dynamic discrete choice models that allow paths to be correlated based on the MEV and mixed logit models. The resulting route choice models become expensive to estimate and we deal with this challenge by proposing innovative methods that allow to reduce the estimation cost. For example, we propose a decomposition method that not only opens up for possibility of mixing, but also speeds up the estimation for simple logit models, which has implications also for traffic simulation. Moreover, we compare the utility maximization and regret minimization decision rules, and we propose a misspecification test for logit-based route choice models. The second theme is related to the estimation of static discrete choice models with large choice sets. We establish that a class of MEV models can be reformulated as dynamic discrete choice models on the networks of correlation structures. These dynamic models can then be estimated quickly using dynamic programming techniques and an efficient nonlinear optimization algorithm. Finally, the third theme focuses on structured quasi-Newton techniques for estimating discrete choice models by maximum likelihood. We examine and adapt switching methods that can be easily integrated into usual optimization algorithms (line search and trust region) to accelerate the estimation process. The proposed dynamic discrete choice models and estimation methods can be used in various discrete choice applications. In the area of big data analytics, models that can deal with large choice sets and sequential choices are important. Our research can therefore be of interest in various demand analysis applications (predictive analytics) or can be integrated with optimization models (prescriptive analytics). Furthermore, our studies indicate the potential of dynamic programming techniques in this context, even for static models, which opens up a variety of future research directions.

Interrelated product design activities sequencing with efficient tabu search algorithms

This paper proposes and investigates a metaheuristic tabu search algorithm (TSA) that generates optimal or near optimal solutions sequences for the feedback length minimization problem (FLMP) associated to a design structure matrix (DSM). The FLMP is a non-linear combinatorial optimization problem, belonging to the NP-hard class, and therefore finding an exact optimal solution is very hard and time consuming, especially on medium and large problem instances. First, we introduce the subject and provide a review of the related literature and problem definitions. Using the tabu search method (TSM) paradigm, this paper presents a new tabu search algorithm that generates optimal or sub-optimal solutions for the feedback length minimization problem, using two different neighborhoods based on swaps of two activities and shifting an activity to a different position. Furthermore, this paper includes numerical results for analyzing the performance of the proposed TSA and for fixing the proper values of its parameters. Then we compare our results on benchmarked problems with those already published in the literature. We conclude that the proposed tabu search algorithm is very promising because it outperforms the existing methods, and because no other tabu search method for the FLMP is reported in the literature. The proposed tabu search algorithm applied to the process layer of the multidimensional design structure matrices proves to be a key optimization method for an optimal product development.

An adaptive neighborhood search algorithm for optimizing stochastic mining complexes

Les métaheuristiques sont très utilisées dans le domaine de l'optimisation discrète. Elles permettent d’obtenir une solution de bonne qualité en un temps raisonnable, pour des problèmes qui sont de grande taille, complexes, et difficiles à résoudre. Souvent, les métaheuristiques ont beaucoup de paramètres que l’utilisateur doit ajuster manuellement pour un problème donné. L'objectif d'une métaheuristique adaptative est de permettre l'ajustement automatique de certains paramètres par la méthode, en se basant sur l’instance à résoudre. La métaheuristique adaptative, en utilisant les connaissances préalables dans la compréhension du problème, des notions de l'apprentissage machine et des domaines associés, crée une méthode plus générale et automatique pour résoudre des problèmes. L’optimisation globale des complexes miniers vise à établir les mouvements des matériaux dans les mines et les flux de traitement afin de maximiser la valeur économique du système. Souvent, en raison du grand nombre de variables entières dans le modèle, de la présence de contraintes complexes et de contraintes non-linéaires, il devient prohibitif de résoudre ces modèles en utilisant les optimiseurs disponibles dans l’industrie. Par conséquent, les métaheuristiques sont souvent utilisées pour l’optimisation de complexes miniers. Ce mémoire améliore un procédé de recuit simulé développé par Goodfellow & Dimitrakopoulos (2016) pour l’optimisation stochastique des complexes miniers stochastiques. La méthode développée par les auteurs nécessite beaucoup de paramètres pour fonctionner. Un de ceux-ci est de savoir comment la méthode de recuit simulé cherche dans le voisinage local de solutions. Ce mémoire implémente une méthode adaptative de recherche dans le voisinage pour améliorer la qualité d'une solution. Les résultats numériques montrent une augmentation jusqu'à 10% de la valeur de la fonction économique.

Interrelated product design activities sequencing with efficient tabu search algorithms

This paper proposes and investigates a metaheuristic tabu search algorithm (TSA) that generates optimal or near optimal solutions sequences for the feedback length minimization problem (FLMP) associated to a design structure matrix (DSM). The FLMP is a non-linear combinatorial optimization problem, belonging to the NP-hard class, and therefore finding an exact optimal solution is very hard and time consuming, especially on medium and large problem instances. First, we introduce the subject and provide a review of the related literature and problem definitions. Using the tabu search method (TSM) paradigm, this paper presents a new tabu search algorithm that generates optimal or sub-optimal solutions for the feedback length minimization problem, using two different neighborhoods based on swaps of two activities and shifting an activity to a different position. Furthermore, this paper includes numerical results for analyzing the performance of the proposed TSA and for fixing the proper values of its parameters. Then we compare our results on benchmarked problems with those already published in the literature. We conclude that the proposed tabu search algorithm is very promising because it outperforms the existing methods, and because no other tabu search method for the FLMP is reported in the literature. The proposed tabu search algorithm applied to the process layer of the multidimensional design structure matrices proves to be a key optimization method for an optimal product development.

An adaptive neighborhood search algorithm for optimizing stochastic mining complexes

Les métaheuristiques sont très utilisées dans le domaine de l'optimisation discrète. Elles permettent d’obtenir une solution de bonne qualité en un temps raisonnable, pour des problèmes qui sont de grande taille, complexes, et difficiles à résoudre. Souvent, les métaheuristiques ont beaucoup de paramètres que l’utilisateur doit ajuster manuellement pour un problème donné. L'objectif d'une métaheuristique adaptative est de permettre l'ajustement automatique de certains paramètres par la méthode, en se basant sur l’instance à résoudre. La métaheuristique adaptative, en utilisant les connaissances préalables dans la compréhension du problème, des notions de l'apprentissage machine et des domaines associés, crée une méthode plus générale et automatique pour résoudre des problèmes. L’optimisation globale des complexes miniers vise à établir les mouvements des matériaux dans les mines et les flux de traitement afin de maximiser la valeur économique du système. Souvent, en raison du grand nombre de variables entières dans le modèle, de la présence de contraintes complexes et de contraintes non-linéaires, il devient prohibitif de résoudre ces modèles en utilisant les optimiseurs disponibles dans l’industrie. Par conséquent, les métaheuristiques sont souvent utilisées pour l’optimisation de complexes miniers. Ce mémoire améliore un procédé de recuit simulé développé par Goodfellow & Dimitrakopoulos (2016) pour l’optimisation stochastique des complexes miniers stochastiques. La méthode développée par les auteurs nécessite beaucoup de paramètres pour fonctionner. Un de ceux-ci est de savoir comment la méthode de recuit simulé cherche dans le voisinage local de solutions. Ce mémoire implémente une méthode adaptative de recherche dans le voisinage pour améliorer la qualité d'une solution. Les résultats numériques montrent une augmentation jusqu'à 10% de la valeur de la fonction économique.

CALR mutation profile in Irish patients with myeloproliferative neoplasms

Insertion and/or deletion mutations of the CALR gene have recently been demonstrated to be the second most common driver mutations in the myeloproliferative neoplasms (MPNs) of essential thrombocythemia (ET) and primary myelofibrosis (PMF). Given the diagnostic and emerging prognostic significance of these mutations, in addition to the geographical heterogeneity reported, the incidence of CALR mutations was determined in an Irish cohort of patients with MPNs with a view to incorporate this analysis into a prospective screening program. A series of 202 patients with known or suspected ET and PMF were screened for the presence of CALR mutations. CALR mutations were detected in 58 patients. Type 1 and Type 1-like deletion mutations were the most common (n = 40) followed by Type 2 and Type 2-like insertion mutations (n = 17). The CALR mutation profile in Irish ET and PMF patients appears similar to that in other European populations. Establishment of this mutational profile allows the introduction of a rational, molecular diagnostic algorithm in cases of suspected ET and PMF that will improve clinical management.

Homozygous Inactivating Mutation In Nanos3 In Two Sisters With Primary Ovarian Insufficiency.

Despite the increasing understanding of female reproduction, the molecular diagnosis of primary ovarian insufficiency (POI) is seldom obtained. The RNA-binding protein NANOS3 poses as an interesting candidate gene for POI since members of the Nanos family have an evolutionarily conserved function in germ cell development and maintenance by repressing apoptosis. We performed mutational analysis of NANOS3 in a cohort of 85 Brazilian women with familial or isolated POI, presenting with primary or secondary amenorrhea, and in ethnically-matched control women. A homozygous p.Glu120Lys mutation in NANOS3 was identified in two sisters with primary amenorrhea. The substituted amino acid is located within the second C2HC motif in the conserved zinc finger domain of NANOS3 and in silico molecular modelling suggests destabilization of protein-RNA interaction. In vitro analyses of apoptosis through flow cytometry and confocal microscopy show that NANOS3 capacity to prevent apoptosis was impaired by this mutation. The identification of an inactivating missense mutation in NANOS3 suggests a mechanism for POI involving increased primordial germ cells (PGCs) apoptosis during embryonic cell migration and highlights the importance of NANOS proteins in human ovarian biology.

Familial Systemic Mastocytosis With Germline Kit K509i Mutation Is Sensitive To Treatment With Imatinib, Dasatinib And Pkc412.

Mastocytosis are myeloproliferative neoplasms commonly related to gain-of-function mutations involving the tyrosine kinase domain of KIT. We herein report a case of familial systemic mastocytosis with the rare KIT K509I germ line mutation affecting two family members: mother and daughter. In vitro treatment with imatinib, dasatinib and PKC412 reduced cell viability of primary mast cells harboring KIT K509I mutation. However, imatinib was more effective in inducing apoptosis of neoplastic mast cells. Both patients with familial systemic mastocytosis had remarkable hematological and skin improvement after three months of imatinib treatment, suggesting that it may be an effective front line therapy for patients harboring KIT K509I mutation.

Pyrimidine-5'-nucleotidase Campinas, A New Mutation (p.r56g) In The Nt5c3 Gene Associated With Pyrimidine-5'-nucleotidase Type I Deficiency And Influence Of Gilbert's Syndrome On Clinical Expression.

Pyrimidine-5'-nucleotidase type I (P5'NI) deficiency is an autosomal recessive condition that causes nonspherocytic hemolytic anemia, characterized by marked basophilic stippling and pyrimidine nucleotide accumulation in erythrocytes. We herein present two African descendant patients, father and daughter, with P5'N deficiency, both born from first cousins. Investigation of the promoter polymorphism of the uridine diphospho glucuronosyl transferase 1A (UGT1A) gene revealed that the father was homozygous for the allele (TA7) and the daughter heterozygous (TA6/TA7). P5'NI gene (NT5C3) gene sequencing revealed a further change in homozygosity at amino acid position 56 (p.R56G), located in a highly conserved region. Both patients developed gallstones; however the father, who had undergone surgery for the removal of stones, had extremely severe intrahepatic cholestasis and, liver biopsy revealed fibrosis and siderosis grade III, leading us to believe that the homozygosity of the UGT1A polymorphism was responsible for the more severe clinical features in the father. Moreover, our results show how the clinical expression of hemolytic anemia is influenced by epistatic factors and we describe a new mutation in the P5'N gene associated with enzyme deficiency, iron overload, and severe gallstone formation. To our knowledge, this is the first description of P5'N deficiency in South Americans.

Reference Values For High-density Lipoprotein Particle Size And Volume By Dynamic Light Scattering In A Brazilian Population Sample And Their Relationships With Metabolic Parameters.

Current data indicate that the size of high-density lipoprotein (HDL) may be considered an important marker for cardiovascular disease risk. We established reference values of mean HDL size and volume in an asymptomatic representative Brazilian population sample (n=590) and their associations with metabolic parameters by gender. Size and volume were determined in HDL isolated from plasma by polyethyleneglycol precipitation of apoB-containing lipoproteins and measured using the dynamic light scattering (DLS) technique. Although the gender and age distributions agreed with other studies, the mean HDL size reference value was slightly lower than in some other populations. Both HDL size and volume were influenced by gender and varied according to age. HDL size was associated with age and HDL-C (total population); non- white ethnicity and CETP inversely (females); HDL-C and PLTP mass (males). On the other hand, HDL volume was determined only by HDL-C (total population and in both genders) and by PLTP mass (males). The reference values for mean HDL size and volume using the DLS technique were established in an asymptomatic and representative Brazilian population sample, as well as their related metabolic factors. HDL-C was a major determinant of HDL size and volume, which were differently modulated in females and in males.

The G209A mutation in the alpha-synuclein gene in Brazilian families with Parkinson's disease

A missense G209A mutation of the alpha-synuclein gene was recently described in a large Contursi kindred with Parkinson's disease (PD). The objective of this study is to determine if the mutation G209A of the alpha-synuclein gene was present in 10 Brazilian families with PD. PD patients were recruited from movement disorders clinics of Brazil. A family history with two or more affected in relatives was the inclusion criterion for this study. The alpha-synuclein G209A mutation assay was made using polymerase chain reaction and the restriction enzyme Tsp45I. Ten patients from 10 unrelated families were studied. The mean age of PD onset was 42.7 years old. We did not find the G209A mutation in our 10 families with PD. Our results suggest that alpha-synuclein mutation G209A is uncommon in Brazilian PD families.

Phenotypic variability in a family with x-linked adrenoleukodystrophy caused by the p.Trp132Ter mutation

X-linked adrenoleukodystrophy (X-ALD) is an inherited disease with clinical heterogeneity varying from presymptomatic individuals to rapidly progressive cerebral ALD forms. This disease is characterized by increased concentration of very long chain fatty acids (VLCFAs) in plasma and in adrenal, testicular and nervous tissues. Affected individuals can be classified in different clinical settings, according to phenotypic expression and age at onset of initial symptoms. Molecular defects in X-ALD individuals usually result from ABCD1 gene mutations. In the present report we describe clinical data and the ABCD1 gene study in two boys affected with the childhood cerebral form that presented with different symptomatic manifestations at diagnosis. In addition, their maternal grandfather had been diagnosed with Addison's disease indicating phenotypic variation for X-ALD within this family. The mutation p.Trp132Ter was identified in both male patients; additionally, three females, out of eleven family members, were found to be heterozygous after screening for this mutation. In the present report, the molecular analysis was especially important since one of the heterozygous females was in first stages of pregnancy. Therefore, depending on the fetus outcome, if male and p.Trp132Ter carrier, storage of the umbilical cord blood should be recommended as hematopoietic stem cell transplantation could be considered as an option for treatment in the future.

Structural aspects of the p.P222Q homozygous mutation of HSD3B2 gene in a patient with congenital adrenal hyperplasia

Type II 3β-hydroxysteroid dehydrogenase/Δ5-Δ4-isomerase (3β-HSD2), encoded by the HSD3B2 gene, is a key enzyme involved in the biosynthesis of all the classes of steroid hormones. Deleterious mutations in the HSD3B2 gene cause the classical deficiency of 3β-HSD2, which is a rare autosomal recessive disease that leads to congenital adrenal hyperplasia (CAH). CAH is the most frequent cause of ambiguous genitalia and adrenal insufficiency in newborn infants with variable degrees of salt losing. Here we report the molecular and structural analysis of the HSD3B2 gene in a 46,XY child, who was born from consanguineous parents, and presented with ambiguous genitalia and salt losing. The patient carries a homozygous nucleotide c.665C>A change in exon 4 that putatively substitutes the proline at codon 222 for glutamine. Molecular homology modeling of normal and mutant 3β-HSD2 enzymes emphasizes codon 222 as an important residue for the folding pattern of the enzyme and validates a suitable model for analysis of new mutations.