Nurse-staff scheduling is a highly complicated, deterministic problem. The complexity increases when one considers there are constraints related to staff preferences (e.g., requested off days, shift preferences, etc.), that the staff mix should have a proper combination of skills, and that the staffing must adhere to conventional operational policies at the hospital. In this article, we propose the following three-step heuristic algorithm approach to deal with this problem in a flexible manner: 1) random assignment of work-stretch and off-stretch, in turn, 2) satisfying one-day staff-level demands, and 3) satisfying staff-level demands for each shift. Each of the steps is conducted for a one-month planning horizon.
Because the problem is NP-complete, many past solution strategies rely on finding an initial, feasible solution with a simplified/reduced constraint set, and then to improve upon it typically via neighborhood search procedure. As a result, typical strategies generate one final solution. Inherent to traditional strategies, an objective function must be established and, most often, a cost-based objective function is utilized. We do not fix the objective function (oftentimes, costs are not the deciding factor in nurse-staffing when most staffs are full-time) and thus this approach aims at identifying feasible solutions without judging their fitness. The heuristic algorithm presented herein has been developed to provide a population of feasible solutions from a problem set. The approach has been incorporated into a decision-support system that will allow the user to specify a set number of feasible solutions to identify. Based upon the decision-maker’s ranking preference, the feasible solutions are narrowed to a candidate list. This approach has been tested on three difficult, real-world nurse-scheduling problems. All three problems are from the same hospital, but are representative of staffing in three different months. In the case study problems, the number of feasible solutions to identify was set at 100. From this set, the heuristic algorithm, based upon the user’s priority rankings, narrowed the candidate list to the range of 3 to 6 recommendations. The quality of these solutions is superior to those that were actually implemented in the hospital. The search procedure is quick; in the case study problems, the search time was less than 5 seconds.