Signed social structure optimization for shift assignment in the nurse scheduling problem. (December 2016) - Farasat, Alireza; Nikolaev, Alexander G.
Abstract: 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. Highlights: We propose a methodological framework to incorporate signed social structure effects into Nurse Scheduling Problem formulations. We motivate the use of network optimization techniques in the area of Nurse Team Formation and provide examples of application of such techniques. We explore quantitatively how social science findings and theories can be used to study and improve the performance of teams of nurses. Mixed Integer Programming and Lin-Kernighan inspired heuristic based on variable depth neighborhood search are used for solving the formulated problem instances.