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.

Hexagonal patterns in finite domains

In many mathematical models for pattern formation, a regular hexagonal pattern is stable in an infinite region. However, laboratory and numerical experiments are carried out in finite domains, and this imposes certain constraints on the possible patterns. In finite rectangular domains, it is shown that a regular hexagonal pattern cannot occur if the aspect ratio is rational. In practice, it is found experimentally that in a rectangular region, patterns of irregular hexagons are often observed. This work analyses the geometry and dynamics of irregular hexagonal patterns. These patterns occur in two different symmetry types, either with a reflection symmetry, involving two wavenumbers, or without symmetry, involving three different wavenumbers. The relevant amplitude equations are studied to investigate the detailed bifurcation structure in each case. It is shown that hexagonal patterns can bifurcate subcritically either from the trivial solution or from a pattern of rolls. Numerical simulations of a model partial differential equation are also presented to illustrate the behaviour.