Source-linked AI summary
Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem
Uwe Aickelin, Kathryn Dowsland
TL;DR
The paper addresses the difficulty of applying classical genetic algorithms to nurse rostering with conflicting objectives and constraints. It exploits the problem’s structure through co-operating sub-populations and adds incentives, disincentives, and repair-oriented mutation. On hospital data, these features improved an unsuccessful canonical GA into a practical solution, although the enhancements are problem-specific and require considerable development effort.
Problem
Classical genetic algorithms struggle with the conflicting objectives and constraints in scheduling, motivating problem-specific mechanisms for a nurse-rostering problem at a UK hospital.
Method
The approach uses grade-based co-operating sub-populations together with incentives, disincentives, and an intelligent mutation operator guided by balanced and unbalanced solution structure.
Results
All problems yielded at least one feasible solution after combining incentives, disincentives, and repair, with solution times reduced to 14.9 seconds per run.
Takeaways & Limitations
Exploiting constraint structure and recognizing solution attributes can make a GA practical for this nurse-scheduling problem.
Takeaways & Limitations
The enhancements cannot be copied directly to different problems because they depend on problem-specific information, and their development effort is considerable.
Abstract
from arXiv · showhide
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
1. Introduction
The paper develops a nurse-scheduling GA that exploits constraint structure and problem-specific knowledge to address conflicting objectives, constraints, and disruptive genetic operators. Co-operating sub-populations, incentives, disincentives, and intelligent mutation transform a canonical GA into a practical approach on hospital data.
- Canonical GA: Constraint handling combines adaptive penalty weights with problem-specific modeling, but the canonical GA remains unable to handle the constraints effectively.The dynamic penalty weight depends on the number of violations until feasibility is found and then remains at a small value.
- Problem setting: The nurse rostering problem must satisfy contracts, grade-specific shift demand, and fairness through preferences and historical workload information.Schedules cover wards of up to 30 nurses, with nurses normally assigned either days or nights in a week.
- Problem setting: The difficult second stage assigns each nurse to days or nights after separate knapsack and network-flow stages establish feasibility and allocate day shifts.The paper focuses on this highly constrained allocation stage because the other stages can be solved quickly with standard algorithms.
- Canonical GA: The canonical GA represents a weekly schedule as one shift-pattern index per nurse, allowing standard crossover to combine nurse assignments from two parents.This encoding preserves feasible pattern choices but does not by itself resolve the problem’s constraints.
- Canonical GA: The canonical GA found acceptable solutions in only 21 of 52 problems, with two optimal terminations across 1040 runs and seven problems failing in all runs.These results provide the baseline for evaluating problem-specific enhancements.
- Co-evolution: A hierarchy of co-operating sub-populations combines low-cost feasible building blocks, making all but one instance feasible at least once with a mean solution time of 17.33 seconds.The sub-population-specific demand calculation was adopted because initial experiments showed it performed better than a global calculation.
- Local guidance: Balanced solutions receive incentives while unbalanced solutions receive disincentives, and a hill-climbing mutation repairs promising solutions or improves preferences.The combined strategy counters crossover disruption and guides search toward solutions likely to become feasible.
- Local guidance: With incentives, disincentives, and repair together, every problem produced at least one feasible solution, most were near-optimal, and runtime fell to 14.9 seconds per run.The incentive alone had limited impact, the disincentive mainly improved feasibility, and the best results required all three features.