Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem

There is considerable interest in the use of genetic algorithms to solve problems arising in the areas of scheduling and timetabling. However, the classical genetic algorithm paradigm is not well equipped to handle the conflict between objectives and constraints that typically occurs in such problems. In order to overcome this, successful implementations frequently make use of problem specific knowledge. This paper is concerned with the development of a GA for a nurse rostering problem at a major UK hospital. The structure of the constraints is used as the basis for a co-evolutionary strategy using co-operating sub-populations. Problem specific knowledge is also used to define a system of incentives and disincentives, and a complementary mutation operator. Empirical results based on 52 weeks of live data show how these features are able to improve an unsuccessful canonical GA to the point where it is able to provide a practical solution to the problem.

'The application of Bayesian Optimization and Classifier Systems in Nurse Scheduling'

Abstract. Two ideas taken from Bayesian optimization and classifier systems are presented for personnel scheduling based on choosing a suitable scheduling rule from a set for each person's assignment. Unlike our previous work of using genetic algorithms whose learning is implicit, the learning in both approaches is explicit, i.e. we are able to identify building blocks directly. To achieve this target, the Bayesian optimization algorithm builds a Bayesian network of the joint probability distribution of the rules used to construct solutions, while the adapted classifier system assigns each rule a strength value that is constantly updated according to its usefulness in the current situation. Computational results from 52 real data instances of nurse scheduling demonstrate the success of both approaches. It is also suggested that the learning mechanism in the proposed approaches might be suitable for other scheduling problems.

The power struggle between Mcmurphy and nurse Ratched in Ken Kesey's: ''One flew over the cuckoo's nest'' [recurso electr?nico]

This monograph is a literary analysis of the novel One Flew over the Cuckoo's Nest, by Ken Kesey published in 1962, that explores the power struggle between its two main characters: Randle Patrick McMurphy and Nurse Ratched. This struggle involves their ways of exerting power, their roles inside the ward, their distinct personalities, their actions, and even their ideas about life, especially what constitutes sanity and insanity. The analysis is based on techniques from New Criticism and the Psychological Critical Approach

'Bayesian Optimisation for Nurse Scheduling'

A Bayesian optimisation algorithm for a nurse scheduling problem is presented, which involves choosing a suitable scheduling rule from a set for each nurse's assignment. When a human scheduler works, he normally builds a schedule systematically following a set of rules. After much practice, the scheduler gradually masters the knowledge of which solution parts go well with others. He can identify good parts and is aware of the solution quality even if the scheduling process is not yet completed, thus having the ability to finish a schedule by using flexible, rather than fixed, rules. In this paper, we design a more human-like scheduling algorithm, by using a Bayesian optimisation algorithm to implement explicit learning from past solutions. A nurse scheduling problem from a UK hospital is used for testing. Unlike our previous work that used Genetic Algorithms to implement implicit learning [1], the learning in the proposed algorithm is explicit, i.e. we identify and mix building blocks directly. The Bayesian optimisation 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, new rule strings have been obtained. Sets of rule strings are generated in this way, some of which will replace previous strings based on fitness. 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. For clarity, consider the following toy example of scheduling five nurses with two rules (1: random allocation, 2: allocate nurse to low-cost shifts). In the beginning of the search, the probabilities of choosing rule 1 or 2 for each nurse is equal, i.e. 50%. After a few iterations, due to the selection pressure and reinforcement learning, we experience two solution pathways: Because pure low-cost or random allocation produces low quality solutions, either rule 1 is used for the first 2-3 nurses and rule 2 on remainder or vice versa. In essence, Bayesian network learns 'use rule 2 after 2-3x using rule 1' or vice versa. It should be noted that for our and most other scheduling problems, the structure of the network model is known and all variables are fully observed. In this case, the goal of learning is to find the rule values that maximize the likelihood of the training data. Thus, learning can amount to 'counting' in the case of multinomial distributions. For our problem, we use our rules: Random, Cheapest Cost, Best Cover and Balance of Cost and Cover. In more detail, the steps of our Bayesian optimisation algorithm for nurse scheduling are: 1. Set t = 0, and generate an initial population P(0) at random; 2. Use roulette-wheel selection to choose a set of promising rule strings S(t) from P(t); 3. Compute conditional probabilities of each node according to this set of promising solutions; 4. Assign each nurse using roulette-wheel selection based on the rules' conditional probabilities. A set of new rule strings O(t) will be generated in this way; 5. Create a new population P(t+1) by replacing some rule strings from P(t) with O(t), and set t = t+1; 6. If the termination conditions are not met (we use 2000 generations), go to step 2. Computational results from 52 real data instances demonstrate the success of this approach. They also suggest that the learning mechanism in the proposed approach might be suitable for other scheduling problems. Another direction for further research is to see if there is a good constructing sequence for individual data instances, given a fixed nurse scheduling order. If so, the good patterns could be recognized and then extracted as new domain knowledge. Thus, by using this extracted knowledge, we can assign specific rules to the corresponding nurses beforehand, and only schedule the remaining nurses with all available rules, making it possible to reduce the solution space. Acknowledgements The work was funded by the UK Government's major funding agency, Engineering and Physical Sciences Research Council (EPSRC), under grand GR/R92899/01. References [1] Aickelin U, "An Indirect Genetic Algorithm for Set Covering Problems", Journal of the Operational Research Society, 53(10): 1118-1126,

'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.

An Estimation of Distribution Algorithm with Intelligent Local Search for Rule-based Nurse Rostering

This paper proposes a new memetic evolutionary algorithm to achieve explicit learning in rule-based nurse rostering, which involves applying a set of heuristic rules for each nurse's assignment. The main framework of the algorithm is an estimation of distribution algorithm, in which an ant-miner methodology improves the individual solutions produced in each generation. Unlike our previous work (where learning is implicit), the learning in the memetic estimation of distribution algorithm is explicit, i.e. we are able to identify building blocks directly. The overall approach learns by building a probabilistic model, i.e. an estimation of the probability distribution of individual nurse-rule pairs that are used to construct schedules. The local search processor (i.e. the ant-miner) reinforces nurse-rule pairs that receive higher rewards. A challenging real world nurse rostering problem is used as the test problem. Computational results show that the proposed approach outperforms most existing approaches. It is suggested that the learning methodologies suggested in this paper may be applied to other scheduling problems where schedules are built systematically according to specific rules.

An Estimation of Distribution Algorithm for Nurse Scheduling

Schedules can be built in a similar way to a human scheduler by using a set of rules that involve domain knowledge. This paper presents an Estimation of Distribution Algorithm (EDA) for the nurse scheduling problem, which involves choosing a suitable scheduling rule from a set for the assignment of each nurse. Unlike previous work that used Genetic Algorithms (GAs) to implement implicit learning, the learning in the proposed algorithm is explicit, i.e. we identify and mix building blocks directly. The EDA 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.

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.

Building Better Nurse Scheduling Algorithms

The aim of this research is twofold: Firstly, to model and solve a complex nurse scheduling problem with an integer programming formulation and evolutionary algorithms. Secondly, to detail a novel statistical method of comparing and hence building better scheduling algorithms by identifying successful algorithm modifications. The comparison method captures the results of algorithms in a single figure that can then be compared using traditional statistical techniques. Thus, the proposed method of comparing algorithms is an objective procedure designed to assist in the process of improving an algorithm. This is achieved even when some results are non-numeric or missing due to infeasibility. The final algorithm outperforms all previous evolutionary algorithms, which relied on human expertise for modification.

'Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem'

There is considerable interest in the use of genetic algorithms to solve problems arising in the areas of scheduling and timetabling. However, the classical genetic algorithm paradigm is not well equipped to handle the conflict between objectives and constraints that typically occurs in such problems. In order to overcome this, successful implementations frequently make use of problem specific knowledge. This paper is concerned with the development of a GA for a nurse rostering problem at a major UK hospital. The structure of the constraints is used as the basis for a co-evolutionary strategy using co-operating sub-populations. Problem specific knowledge is also used to define a system of incentives and disincentives, and a complementary mutation operator. Empirical results based on 52 weeks of live data show how these features are able to improve an unsuccessful canonical GA to the point where it is able to provide a practical solution to the problem.

Women's perceptions of Nurse-Midwives' caring behaviours during perinatal loss in Lilongwe, Malawi: An Exploratory study

Objective The Objective for this study was to explore women’s perceptions of and satisfaction with nursing care they received following stillbirth and neonatal death in villages around a community hospital in Lilongwe. Methods This qualitative, exploratory study through a mixture of purposive and snowball sampling, recruited 20 women who had lost a child through stillbirth or neonatal death in the past 2 years. Data were collected through semi-structured interviews in the privacy of the homes of the women. All interviews were tape-recorded and transcribed verbatim and were analyzed using thematic analysis. Results Almost half of the respondents expressed satisfaction with the way nurses cared for them after experiencing perinatal loss, although some felt unable to comment on the quality of care received. However, several bereaved women were dissatisfied with how nurses handled their loss. They noted nurses not providing attention or explanations and some even attributed the death of their child to nurses’ neglect. Conclusions Interventions are needed which foster awareness where nurses become more sensitive to the mothers’ emotional needs in an equally sensitive health care system. There is also need for more research into care provided following perinatal deaths in resource-poor settings to increase the evidence-base for informed and improved care for women who have experienced child loss.

‘Failure to maintain’: care rationing and the clinical and financial burden of nurse sensitive hospital-acquired complications in complex older patients

Background: The ageing population, with concomitant increase in chronic conditions, is increasing the presence of older people with complex needs in hospital. People with dementia are one of these complex populations and are particularly vulnerable to complications in hospital. Registered nurses can offer simultaneous assessment and intervention to prevent or mitigate hospital-acquired complications through their skilled brokerage between patient needs and hospital functions. A range of patient outcome measures that are sensitive to nursing care has been tested in nursing work environments across the world. However, none of these measures have focused on hospitalised older patients. Method: This thesis explores nursing-sensitive complications for older patients with and without dementia using an internationally recognised, risk-adjusted patient outcome approach. Specifically explored are: the differences between rates of complications; the costs of complications; and cost comparisons of patient complexity. A retrospective cohort study of an Australian state’s 2006–07 public hospital discharge data was utilised to identify patient episodes for people over age 50 (N=222,440) where dementia was identified as a primary or secondary diagnosis (N=44,422). Extra costs for patient episodes were estimated based on length of stay (LOS) above the average for each patient’s Diagnosis Related Group (DRG) (N=157,178) and were modelled using linear regression analysis to establish the strongest patient complexity predictors of cost. Results: Hospitalised patients with a primary or secondary diagnosis of dementia had higher rates of complications than did their same-age peers. The highest rates and relative risk for people with dementia were found in four key complications: urinary tract infections; pressure injuries; pneumonia, and delirium. While 21.9% of dementia patients (9,751/44,488, p<0.0001) suffered a complication, only 8.8% of non-dementia patients did so (33,501/381,788, p<0.0001), giving dementia patients a 2.5 relative risk of acquiring a complication (p<0.0001). These four key complications in patients over 50 both with and without dementia were associated with an eightfold increase in length of stay (813%, or 3.6 days/0.4 days) and double the increased estimated mean episode cost (199%, or A$16,403/ A$8,240). These four complications were associated with 24.7% of the estimated cost of additional days spent in hospital in 2006–07 in NSW (A$226million/A$914million). Dementia patients accounted for 22.0% of these costs (A$49million/A$226million) even though they were only 10.4% of the population (44,488/426,276 episodes). Hospital-acquired complications, particularly for people with a comorbidity of dementia, cost more than other kinds of inpatient complexity but admission severity was a better predictor of excess cost. Discussion: Four key complications occur more often in older patients with dementia and the high rate of these complications makes them expensive. These complications are potentially preventable. However, the care that can prevent them (such as mobility, hydration, nutrition and communication) is known to be rationed or left unfinished by nurses. Older hospitalised people who have complex needs, such as those with dementia, are more likely to experience care rationing as their care tends to take longer, be less predictable and less curative in nature. This thesis offers the theoretical proposition that evidence-based nursing practices are rationed for complex older patients and that this rationed care contributes to functional and cognitive decline during hospitalisation. This, in turn, contributes to the high rates of complications observed. Thus four key complications can be seen as a ‘Failure to Maintain’ complex older people in hospital. ‘Failure to Maintain’ is the inadequate delivery of essential functional and cognitive care for a complex older person in hospital resulting in a complication, and is recommended as a useful indicator for hospital quality. Conclusions: When examining extra length of stay in hospital, complications and comorbid dementia are costly. Complications are potentially preventable, and dementia care in hospitals can be improved. Hospitals and governments looking to decrease costs can engage in risk-reduction strategies for common nurse sensitive complications such as healthy nursing work environments that minimise nurses’ rationing of functional and cognitive care. The conceptualisation of complex older patients as ‘business as usual’ rather than a ‘burden’ is likely necessary for sustainable health care services of the future. The use of the ‘Failure to Maintain’ indicators at institution and state levels may aid in embedding this approach for complex older patients into health organisations. Ongoing investigation is warranted into the relationships between the largest health services expense (hospitals), the largest hospital population (complex older patients), and the largest hospital expense (nurses). The ‘Failure to Maintain’ quality indicator makes a useful and substantive contribution to further clinical, administrative and research developments.

Predictors of Patient Activation Among Underserved Patients in a Nurse-managed Health Center: A Pilot Study

The concept of patient activation has gained traction as the term referring to patients who understand their role in the care process and have “the knowledge, skills and confidence” necessary to manage their illness over time (Hibbard & Mahoney, 2010). Improving health outcomes for vulnerable and underserved populations who bear a disproportionate burden of health disparities presents unique challenges for nurse practitioners who provide primary care in nurse-managed health centers. Evidence that activation improves patient self-management is prompting the search for theory-based self-management support interventions to activate patients for self-management, improve health outcomes, and sustain long-term gains. Yet, no previous studies investigated the relationship between Self-determination Theory (SDT; Deci & Ryan, 2000) and activation. The major purpose of this study, guided by the Triple Aim (Berwick, Nolan, & Whittington, 2008) and nested in the Chronic Care Model (Wagner et al., 2001), was to examine the degree to which two constructs– Autonomy Support and Autonomous Motivation– independently predicted Patient Activation, controlling for covariates. For this study, 130 nurse-managed health center patients completed an on-line 38-item survey onsite. The two independent measures were the 6-item Modified Health Care Climate Questionnaire (mHCCQ; Williams, McGregor, King, Nelson, & Glasgow, 2005; Cronbach’s alpha =0.89) and the 8-item adapted Treatment Self-Regulation Questionnaire (TSRQ; Williams, Freedman, & Deci, 1998; Cronbach’s alpha = 0.80). The Patient Activation Measure (PAM-13; Hibbard, Mahoney, Stock, & Tusler, 2005; Cronbach’s alpha = 0.89) was the dependent measure. Autonomy Support was the only significant predictor, explaining 19.1% of the variance in patient activation. Five of six autonomy support survey items regressed on activation were significant, illustrating autonomy supportive communication styles contributing to activation. These results suggest theory-based patient, provider, and system level interventions to enhance self-management in primary care and educational and professional development curricula. Future investigations should examine additional sources of autonomy support and different measurements of autonomous motivation to improve the predictive power of the model. Longitudinal analyses should be conducted to further understand the relationship between autonomy support and autonomous motivation with patient activation, based on the premise that patient activation will sustain behavior change.