Signed social structure optimization for shift assignment in the nurse scheduling problem

This paper develops a mathematical framework that relies on modern social network analysis theories for treating the nurse team formation and nurse scheduling (shift assignment) problems, accounting for signed social connections. These problems lie in assigning nurses to teams/shifts such that the constraints regarding both the working regulations and nurses preferences are satisfied. Recent research indicates the dependence of nursing team performance on team social structure; however, so far, the social structure considerations have not been explicitly incorporated into the mathematical formulations of the nurse scheduling problem. The presented framework introduces models that quantitatively exploit such dependence. This paper explores instances of Nurse Team Formation Problem (NTFP) and Nurse Scheduling Problem (NSP) incorporating signed social structure with the measures based on such network structures as edges, full dyads, triplets, k-stars, balanced and unbalanced triangles, etc., in directed, signed networks. The paper presents the integer programming formulations for NTFP and NSP, and a problem-specific heuristic that performs variable-depth neighborhood search to tackle NTFP instances with signed social structures. Computational results for a real-world problem instance with 20 nurses are reported. The insights obtained from the presented framework and future research directions are discussed.