A Component Based Heuristic Search Method with Adaptive Perturbations

Jingpeng Li, Uwe Aickelin, Edmund BurkeMinerva Access (University of Melbourne) 2006

TL;DR

This paper introduces a novel "Component-Based Heuristic Search" (CHAP) method for the complex problem of hospital personnel scheduling, specifically nurse rostering. CHAP decomposes schedules into individual nurse assignments, adaptively perturbs them to escape local optima, and then reconstructs them, demonstrating improved performance over existing methods.

What Problem Does This Paper Address?

Hospital personnel scheduling, particularly nurse rostering, is a notoriously complex problem. It involves assigning nurses to shifts over a period (typically a week) while satisfying a multitude of constraints: minimum staffing levels for different grades, fairness to nurses (considering preferences and historical data), and contractual obligations. Traditional methods often struggle with the sheer size of the search space and the intricate interdependencies of these constraints. Manual scheduling is time-consuming and prone to errors, while many automated approaches get stuck in suboptimal solutions. This paper aims to develop a more effective automated approach to generate high-quality, feasible nurse schedules.

Methods

The core of the proposed method is the "Component-Based Heuristic Search" (CHAP) algorithm. It operates iteratively through four main steps:

  1. Initialization: Generates an initial, often poor, schedule to start the process.
  2. Evaluation: Assesses the "fitness" of each individual nurse's shift assignment (component) within the current schedule. This fitness considers both soft constraints (nurse preferences) and hard constraints (coverage requirements).
  3. Perturbation-I: Adaptively removes "unfit" components (nurse assignments) based on their evaluated fitness. Assignments with higher fitness have a lower chance of being removed.
  4. Perturbation-II: Introduces a small, random chance to remove even "fit" components. This is crucial for escaping local optima and exploring a wider solution space.
  5. Reconstruction: Uses a refined greedy heuristic (specifically, a "Cover" rule and a "Combined" rule) to repair the partially broken schedule by assigning new shift patterns to the unscheduled nurses, aiming to create a complete and feasible schedule.

This iterative process of evaluation, perturbation, and reconstruction allows the algorithm to progressively improve the schedule. The key novelty lies in decomposing the schedule into components, adaptively perturbing these components, and using a constructive heuristic to rebuild the schedule, which differs from traditional local search methods that operate on the entire solution.

Datasets

The paper evaluates its proposed algorithm using 52 real-world data sets provided by a major UK hospital. These datasets represent one week's requirements for wards with up to 30 nurses, 3 grade-bands, and up to 411 different shift patterns. The authors note that these instances vary in difficulty, with some having few feasible solutions and others having multiple optima.

Key Insights and Ideas

  • Decomposition is Key: Breaking down the complex scheduling problem into individual nurse assignments (components) allows for more targeted and adaptive manipulation of the solution.
  • Adaptive Perturbation for Escaping Local Minima: The two-stage perturbation process is crucial. Perturbation-I intelligently removes weak components, while Perturbation-II's random element prevents the algorithm from getting permanently stuck in suboptimal regions.
  • Iterative Improvement with Constructive Repair: The combination of iterative improvement (through perturbation) and a robust constructive heuristic for repair is a powerful strategy for tackling highly constrained problems.
  • Single-Solution Approach Efficiency: Unlike population-based methods, CHAP operates on a single solution, which can be more computationally efficient in terms of memory and processing.

Key Results

The CHAP algorithm was compared against several other approaches, including integer programming (IP), various genetic algorithms (GA-1 to GA-5), an Estimation of Distribution Algorithm (EDA), and a Learning Classifier System (LCS).

  • Performance: CHAP achieved results that were, on average, only 2.7% more expensive than the optimal solution found by IP, but completed within 20 seconds compared to IP's >24 hours.
  • Comparison to Meta-heuristics: CHAP generally outperformed other meta-heuristic approaches. It was slightly better than the best-performing indirect genetic algorithm (GA-5) in terms of feasibility and best results, and significantly better than other GAs, EDA, and LCS.
  • Feasibility: CHAP demonstrated a high rate of finding feasible solutions, with 21 out of 52 instances solved well (100% feasible solutions within 3 cost units of optimal) and 42 instances solved optimally at least once.
  • Importance of Perturbation: Experiments showed that removing the perturbation steps (using only the reconstruction heuristic) led to a significant number of infeasible solutions, highlighting the critical role of the perturbation stages.

Limitations and Future Work

  • Parameter Tuning: The authors acknowledge that some parameter values (e.g., maximum iterations, perturbation rates) were based on experience and intuition, and they cannot definitively prove they are optimal for every instance.
  • Future Work: The paper suggests that CHAP could be combined with other meta-heuristics to further enhance performance. For instance, tabu search could be integrated into the reconstruction step to explore neighboring solutions more aggressively and avoid cycles. Simulated annealing could be used as an acceptance criterion to allow for occasional acceptance of worse solutions, further aiding in escaping local optima.

Summary updated

Abstract

In an attempt to ensure good-quality printouts of our technical reports, from the supplied PDF files, we process to PDF using Acrobat Distiller. We encourage our authors to use outline fonts coupled with embedding of the used subset of all fonts (in either Truetype or Type 1 formats) except for the standard Acrobat typeface families of Times, Helvetica (Arial), Courier and Symbol. In the case of papers prepared using TEX or LATEX we endeavour to use subsetted Type 1 fonts, supplied by Y&Y Inc., for the Computer Modern, Lucida Bright and Mathtime families, rather than the public-domain Computer Modern bitmapped fonts. Note that the Y&Y font subsets are embedded under a site license issued by Y&Y Inc. For further details of site licensing and purchase of these fonts visit
BibTeX
@inproceedings{li2006component,
  author = {Jingpeng Li and Uwe Aickelin and Edmund Burke},
  title = {{A Component Based Heuristic Search Method with Adaptive Perturbations}},
  booktitle = {Minerva Access (University of Melbourne)},
  year = {2006},
}
Figure