Achieving compromise solutions in nurse rostering by using automatically estimated acceptance thresholds

Elín Björk Böðvarsdóttir*, Pieter Smet, Greet Vanden Berghe, Thomas Jacob Riis Stidsen

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review


Despite the multi-objective nature of the nurse rostering problem (NRP), most NRP formulations employ a single evaluation function that minimizes the weighted sum of constraint violations. When solving the NRP in practice, the focus should be on obtaining compromise solutions: those with appropriate trade-offs between different constraints. Due to the real-world characteristics of the problem, appropriate trade-offs may vary substantially across instances, and quantifying these trade-offs does not necessarily translate well into a single evaluation function. This paper introduces a new multi-objective approach for the NRP that promotes controlled trade-offs and guides the solver towards acceptable compromise solutions. The method consists of two phases. The first phase quantifies the characteristics of acceptable compromise solutions by estimating acceptance thresholds that implicitly incorporate trade-offs. This quantification is performed automatically by drawing upon the instance at hand and identifying appropriate trade-offs. The second phase solves the NRP by employing these acceptance thresholds in a lexicographic goal programming framework. By automatically estimating instance-specific acceptance thresholds, we not only require minimal information from the user but also obtain a realistic prediction for solution quality. A case study shows that the methodology produces rosters with little or no deviations from acceptance thresholds, within only a few minutes. Furthermore, this methodology provides the user with clear reasoning behind the trade-offs made, as opposed to methods employing a single evaluation function.
Original languageEnglish
JournalEuropean Journal of Operational Research
Issue number3
Pages (from-to)980-995
Publication statusPublished - 2021


  • Timetabling
  • Nurse rostering
  • Multi-objective optimization
  • Compromise solutions
  • Lexicographic goal programming


Dive into the research topics of 'Achieving compromise solutions in nurse rostering by using automatically estimated acceptance thresholds'. Together they form a unique fingerprint.

Cite this