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

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.