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.

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

A Bayesian optimization algorithm for the nurse scheduling problem

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.

BOA for nurse scheduling

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.

Scheduling the repair of aircraft components - a case study

In aircraft components maintenance shops, components are distributed amongst repair groups and their respective technicians based on the type of repair, on the technicians skills and workload, and on the customer required dates. This distribution planning is typically done in an empirical manner based on the group leader’s past experience. Such a procedure does not provide any performance guarantees, leading frequently to undesirable delays on the delivery of the aircraft components. Among others, a fundamental challenge faced by the group leaders is to decide how to distribute the components that arrive without customer required dates. This paper addresses the problems of prioritizing the randomly arriving of aircraft components (with or without pre-assigned customer required dates) and of optimally distributing them amongst the technicians of the repair groups. We proposed a formula for prioritizing the list of repairs, pointing out the importance of selecting good estimators for the interarrival times between repair requests, the turn-around-times and the man hours for repair. In addition, a model for the assignment and scheduling problem is designed and a preliminary algorithm along with a numerical illustration is presented.

Neuronal ceroid-lipofuscinosis, a type of amaurotic family idiocy: clinical and pathological study of four cases

Neuronal ceroid-lipofuscinosis (NCL) is a recent term, proposed for acurate designation of the late-onset types of Amaurotic Family Idiocy (AFI). Histopathology shows ubiquitous intraneuronal accumulation of lipopigments, being the most important factor for characterization of the entity at present time. Biochemical changes and pathogenesis are obscure. NCL is in contrast to the infantile type of AFI (Tay-Sachs disease), in which intraneuronal accumulation of gangliosides (sphingolipids) is due to the well known deficiency of a lysosomal enzyme. The authors report on four cases of NCL, two brothers of the late infantile (Jansky-Bielschowsky) type and a brother and a sister of the juvenile (Spielmeyer-Sjögren) type. One autopsy and three cortical biopsies revealed moderate to severe distention of the neurons by lipopigment, with nerve cell loss, gliosis and cerebral atrophy. Lipopigment was also increased in liver, heart and spleen. The patients were the first in Brazilian literature in whom the storage material was identified as lipopigment by histochemical methods. A brief summary of the clinical features of NCL is presented, and relevant problems are discussed, concerning interpretation of the nature of the storage material, and significance of the disease for gerontological research.

Anti-oxidative and anti-ulcerogenic activity of Ipomoea imperati

Ipomoea imperati (Vahl) Griseb., Convolvulaceae, is used in traditional medicine for the treatment of inflammation, swelling and wounds, as well as to treat pains and stomach problems. This work evaluates the anti-oxidative activity by ESR (Electron Spin Resonance spectroscopy) and the preventive and curative actions of I. imperati in gastric ulcer animal model. Ipomoea imperati (200 mg/kg, p.o.) prevented the formation of gastric lesions in 78% (p<0.05) when compared with the negative control tween 80. Lanzoprazole, prevented in 85% the gastric lesions formation induced by ethanol (p<0.05). Therefore, the oral administration of I. imperati one hour before the ulcerogenic agent prevented the ulcer formation, conserving the citoprotection characteristics of the gastric mucosa and assuring the integrity of gastric glands and gastric fossets. The healing activity of I. imperati (200 mg/kg, p.o.) evaluated in chronic ulcer experiments induced by the acetic acid, was 72% (p<0.05). The positive control, ranitidine, healed 78% of the gastric lesions (p<0.05). The histological analysis confirmed the recovery of the mucosal layer and the muscle mucosal layer harmed by the acetic acid. Experiments in vitro with DPPH (2.2-diphenyl-1-picrylhydrazyl) of anti-oxidative activity demonstrated that I. imperati presents an IC50 of 0.73±0.01 mg/mL.

Surface dental enamel lead levels and antisocial behavior in Brazilian adolescents

Lead poisoning has been reportedly linked to a high risk of learning disabilities, aggression and criminal offenses. To study the association between lead exposure and antisocial/delinquent behavior, a cross-sectional study was conducted with 173 Brazilian youths aged 14\201318 and their parents (n = 93), living in impoverished neighborhoods of Bauru-SP, with high criminality indices. Self-Reported Delinquency (SRD) and Child Behavior Checklist (CBCL) questionnaires were used to evaluate delinquent/antisocial behavior. Body lead burdens were evaluated in surface dental enamel acid microbiopsies. The dental enamel lead levels (DELL) were quantified by graphite furnace atomic absorption spectrometry (GFAAS) and phosphorus content was measured using inductively coupled plasma optical emission spectrometry (ICP-OES). Logistic regression was used to identify associations between DELL and each scale defined by CBCL and SRD scores. Odd ratios adjusted for familial and social covariates, considering a group of youths exposed to high lead levels (\2265 75 percentile), indicated that high DELL is associated with increased risk of exceeding the clinical score for somatic complaints, social problems, rule-breaking behavior and externalizing problems (CI 95 per cent). High DELL was not found to be associated with elevated SRD scores. In conclusion, our data support the hypothesis that high-level lead exposure can trigger antisocial behavior, which calls for public policies to prevent lead poisoning

The bubbles or the boiling pot?: an ecosystemic approach to culture, environment and quality of life

For the diagnosis and prognosis of the problems of quality of life, a multidisciplinary ecosystemic approach encompasses four dimensions of being-in-the-world, as donors and recipients: intimate, interactive, social and biophysical. Social, cultural and environmental vulnerabilities are understood and dealt with, in different circumstances of space and time, as the conjugated effect of all dimensions of being-in-the-world, as they induce the events (deficits and assets), cope with consequences (desired or undesired) and contribute for change. Instead of fragmented and reduced representations of reality, diagnosis and prognosis of cultural, educational, environmental and health problems considers the connections (assets) and ruptures (deficits) between the different dimensions, providing a planning model to develop and evaluate research, teaching programmes, public policies and field projects. The methodology is participatory, experiential and reflexive; heuristic-hermeneutic processes unveil cultural and epistemic paradigms that orient subject-object relationships; giving people the opportunity to reflect on their own realities, engage in new experiences and find new ways to live better in a better world. The proposal is a creative model for thought and practice, providing many opportunities for discussion, debate and development of holistic projects integrating different scientific domains (social sciences, psychology, education, philosophy, etc.)

Dopamine-beta hydroxylase polymorphism and cocaine addiction

Cocaine addiction involves a number of medical, psychological and social problems. Understanding the genetic aetiology of this disorder will be essential for design of effective treatments. Dopamine-beta hydroxylase (DbH) catalyzes the conversion of dopamine to norepinephrine and could, therefore, have an influence on both cocaine action and the basal sensitivity of neurotransmitter systems to cocaine. Recently, the - 1021C> T polymorphism have been found to strongly correlated with individual variation in plasma DbH activity. To test the influence of this polymorphism on the susceptibility of cocaine addiction, we decided to genotype it in a sample of 689 cocaine addicts and 832 healthy individuals. Genotypic and allelic analyses did not show any evidence of association with cocaine addiction, even after correcting for the effect of population stratification and other possible confounders. Our results do not support a major role of the - 1021C> T polymorphism or the gene itself in the development of cocaine addiction but further examination of other variants within this gene will be necessary to completely rule out an effect.

Mutational analysis of genes p14ARF, p15INK4b, p16INK4a, and PTEN in human nervous system tumors

The cancer is one of the most common and severe problems in clinical medicine, and nervous system tumors represent about 2% of the types of cancer. The central role of the nervous system in the maintenance of vital activities and the functional consequences of the loss of neurons can explain how severe brain cancers are. The cell cycle is a highly complex process, with a wide number of regulatory proteins involved, and such proteins can suffer alterations that transform normal cells into malignant ones. The INK4 family members (CDK inhibitors) are the cell cycle regulators that block the progression of the cycle through the R point, causing an arrest in G1 stage. The p14ARF (alternative reading frame) gene is a tumor suppressor that inhibits p53 degradation during the progression of the cell cycle. The PTEN gene is related to the induction of growth suppression through cell cycle arrest, to apoptosis and to the inhibition of cell adhesion and migration. The purpose of the present study was to assess the mutational state of the genes p14ARF, p15INK4b, p16INK4a, and PTEN in 64 human nervous system tumor samples. Homozygous deletions were found in exon 2 of the p15INK4b gene and exon 3 of the p16INK4a gene in two schwannomas. Three samples showed a guanine deletion (63 codon) which led to a loss of heterozygosity in the p15 gene, and no alterations could be seen in the PTEN gene. Although the group of patients was heterogeneous, our results are in accordance with other different studies that indicate that homozygous deletion and loss of heterozygosity in the INK4 family members are frequently observed in nervous system tumors.