Integer programming for optimized nurse scheduling: A model for efficient workforce allocation in healthcare systems

 Corresponding author: Okoro C.N Copyright © 2025 Author(s) retain the copyright of this article. This article is published under the terms of the Creative Commons Attribution License 4.0. Integer programming for optimized nurse scheduling: A model for efficient workforce allocation in healthcare systems Okoro, C.N. *, Oti C. G. and Mmahi, E.C. Department of Industrial Mathematics and Applied Statistics, Ebonyi State University, Abakaliki Nigeria. World Journal of Advanced Research and Reviews, 2025, 27(01), 1430-1439 Publication history: Received on 03 May 2025; revised on 08 July 2025; accepted on 11 July 2025 Article DOI: https://doi.org/10.30574/wjarr.2025.27.1.2464 Abstract Effective nurse scheduling is essential for optimizing healthcare workforce management. This study presents an integer programming model that ensures optimal shift allocation while balancing operational efficiency, legal constraints, and staff preferences. By minimizing scheduling inefficiencies and improving workload distribution, the model enhances both cost-effectiveness and nurse satisfaction. The result of implementation at mile four hospital Abakaliki, Nigeria produces optimal allocation of nurses for days off and also optimal number of nurse requirement for each ward or unit. Results demonstrate superior performance over traditional scheduling methods by minimizing 0.09% of the hospital’s total nursing staff cost. This framework offers a scalable solution for improving workforce allocation in healthcare systems. Keywords: Nurse Scheduling; Integer Programming; Workforce Optimization; Healthcare Operations 1. Introduction A mathematical programming approach has been shown to effectively minimize nursing shortages and satisfy staffing constraints (Warner and Prawda, 1972). Abdalkareem et al. (2021) provided a comprehensive survey of healthcare scheduling problems, highlighting key areas such as nurse scheduling, patient admissions, and operating room planning, and analyzing 190 articles across various optimization approaches. Efficient nurse scheduling is fundamental to the smooth operation of healthcare facilities, directly impacting patient care, hospital efficiency, and staff well-being. Given the critical role that nurses play in patient management, ensuring adequate staffing levels while balancing nurse workload, regulatory requirements, and institutional constraints remains a complex challenge. The Nurse Scheduling Problem (NSP) is a well-documented issue in healthcare operations, requiring hospitals to develop shift allocations that minimize inefficiencies, prevent staff burnout, and optimize resource utilization. An effective scheduling system ensures uninterrupted patient care, adherence to labor laws, and fair workload distribution among nurses. Traditionally, hospitals have relied on manual scheduling methods, which are often time-consuming, error-prone, and inflexible. These traditional approaches struggle to accommodate fluctuating patient demands, staff preferences, and legal constraints, leading to understaffing or overstaffing, increased overtime costs, and nurse dissatisfaction. Studies have shown that poor scheduling contributes to low job satisfaction and high turnover rates, which in turn affect the quality of healthcare delivery (Cheang et al., 2003; Burke et al., 2004). Additionally, ineffective scheduling can result in higher operational costs, as hospitals often rely on expensive temporary staffing solutions to fill gaps in coverage (Smith World Journal of Advanced Research and Reviews, 2025, 27(01), 1430-1439 1431 and Wiggins, 1997). These challenges necessitate the adoption of more systematic and data-driven approaches to workforce scheduling. In response to these inefficiencies, Integer Programming (IP) has emerged as a powerful optimization tool for solving complex scheduling problems, including NSP. Unlike heuristic or manual methods, IP ensures mathematically optimal solutions by systematically assigning nurses to shifts while satisfying multiple constraints. This approach enhances fairness, efficiency, and cost-effectiveness, ensuring compliance with institutional policies and labor laws. Prior research has demonstrated that IP-based scheduling models improve nurse allocation, enhance workforce efficiency, and reduce scheduling conflicts in hospital settings (Alfares, 2002; El-Quliti and Al-Darrab, 2009). By leveraging mathematical optimization, hospitals can achieve a balance between workforce demands and staff well-being, leading to improved patient care outcomes. This study applies an Integer Programming model to optimize nurse scheduling at Mile Four Hospital, Abakaliki, which operates 21 wards with a total of 64 full-time nurses. Given that each nurse is required to work five days per week with two consecutive days off, scheduling becomes a highly constrained problem that requires careful optimization. The study aims to develop a structured, data-driven model that efficiently assigns nurses to shifts while ensuring compliance with hospital policies and staffing requirements. The key objectives of this research are to: Develop an optimized nurse scheduling model that ensures proper shift coverage while adhering to staffing requirements. Minimize inefficiencies such as understaffing, excessive overtime, and workload imbalances. Enhance nurse satisfaction by promoting fair workload distribution. Ensure regulatory compliance, particularly in terms of maximum working hours and mandated rest periods. By applying Integer Programming, this research contributes to the field of healthcare operations management, offering a scalable and decision-support framework for hospital administrators seeking to improve workforce planning. The findings will not only benefit Mile Four Hospital but can also serve as a benchmark for optimizing nurse scheduling in other healthcare institutions. Through this study, hospitals can achieve a balance between cost-effectiveness, staff wellbeing, and patient care quality, reinforcing the significance of mathematical optimization in modern healthcare management. 2. Methodology 2.1. Problem Formulation The Nurse Scheduling Problem (NSP) is a highly constrained combinatorial optimization problem, where the goal is to create an efficient roster that assigns nurses to shifts while satisfying multiple constraints. The primary challenge in nurse scheduling is balancing hospital staffing requirements, employee preferences, legal regulations, and operational efficiency. To address this, the problem is formulated as an Integer Programming (IP) model, which ensures mathematically optimal solutions while adhering to defined constraints. The scheduling problem involves allocating shifts to nurses while ensuring adequate shift coverage (meeting daily nurse demand per ward), fair workload distribution (avoiding nurse burnout and excessive overtime), regulatory compliance (adhering to labor laws and hospital policies). days-off scheduling constraints (ensuring every nurse gets two consecutive days off per week). This study focuses on days-off scheduling, where the decision variables represent the assignment of nurses to specific off-day patterns. The IP model minimizes scheduling inefficiencies while satisfying all hospital constraints. 2.2. Mathematical Model The NSP is formulated as an Integer Linear Programming (ILP) model, which ensures that the number of nurses assigned to each shift is an integer value. The key components of the model are: 2.3. Decision Variables Let Xi=Number of nurses assigned to a specific days-off pattern (i=1,2, 7) • X1: Saturday-Sunday off • X2: Sunday-Monday off • X3: Monday-Tuesday off World Journal of Advanced Research and Reviews, 2025, 27(01), 1430-1439 1432 • X4: Tuesday-Wednesday off • X5: Wednesday-Thursday off • X6: Thursday-Friday off • X7: Friday-Saturday off 2.4. Objective Function The goal is to minimize the total number of days-off allocations while ensuring that each ward meets its daily staffing requirements. Min Z=X1+X2+X3+X4+X5+X6+X7 2.5. Constraints Each day must meet a minimum staffing requirement bj (nurses needed per shift per ward). The model ensures that enough nurses are scheduled on duty each day: • X1+X2+X3+X4+X5 ≥ b1 (Saturday) • X2+X3+X4+X5+X6≥b2 (Sunday) • X3+X4+X5+X6+X7≥b3 (Monday) • X1+X4+X5+X6+X7≥b4 (Tuesday) • X1+X2+X5+X6+X7≥b5 (Wednesday) • X1+X2+X3+X6+X7≥b6 (Thursday) • X1+X2+X3+X4+X7≥b7 (Friday) Additionally, the number of assigned nurses must be non-negative integers Xi≥0, XS is an integer for all i. 2.6. Solution Approach (Branch and Bound Algorithm) 2.6.1. Step 1: Solve the Linear Relaxation (LP Relaxation) • Ignore integer constraints and solve the linear programming (LP) version of the problem using the Simplex Method. • The solution obtained will have fractional values for some variables, which are not feasible since nurses cannot be assigned in fractional numbers. • If the LP solution is already an integer, it is the optimal solution. Otherwise, proceed to branching 2.6.2. Step 2: Branching (Divide the Problem into Sub problems) • Identify the first non-integer variable in the LP solution. • Create two new sub problems (branches) by forcing the noninteger variable to take integer values. • These two constraints create two new LP problems, each with a smaller feasible region. 2.6.3. Step 3: Bounding (Eliminating Non-Optimal Solutions) • Solve both sub problems using the LP relaxation. • If a branch leads to an infeasible solution (i.e., violates nurse staffing constraints), it is pruned (discarded). • If a branch gives an integer solution, record it as a candidate optimal solution. • If the objective function value of a new integer solution is worse than an already known feasible solution, discard it 2.6.4. Step 4: Node exploration • Select the next non-integer variable and repeat the branching and bounding process. • If a branch leads to a better feasible integer solution, update the best-known solution. • Stop when all branches have either been explored or pruned. • The best feasible integer solution found is the optimal nurse schedule. World Journal of Advanced Research and Reviews, 2025, 27(01), 1430-1439 1433 2.7. Data Collection and Representation This study is based on real hospital data collected from Mile Four Hospital, Abakaliki, Ebonyi State, Nigeria. The hospital has 21 yards and 64 full-time nurses, each required to work five days per week with two consecutive days off. 2.7.1. Ward-wise Staffing Data The table below presents the total nurse availability and the daily staffing requirement per ward Table 1 Nurses distribution per ward Ward/Unit Total Nurses Available Daily Requirement Postnatal (1) and (2) 9 4 Postnatal (3) 6 2 Nursery 6 4 Labour Ward 12 6 Antenatal Clinic (ANC) 6 6 Anesthesia Unit (ART) 2 2 Multiple Drug Resistant (MDR) 2 2 Outpatient Dept. (OPD) 3 2 Children's Ward 8 4 Operating Theatre 2 1 Admin/Counseling Unit 2 2 Tuberculosis Ward 1 1 2.8. Constraint Representation for Each Ward For each ward/unit, we formulate separate constraints using their daily staffing requirements. 2.8.1. Formulation for Postnatal (1) and (2) Ward This ward requires 4 nurses per day thus, the constraints specific to this ward will be: • X1+X2+X3+X4+X5≥4 (Saturday) • X2+X3+X4+X5+X6≥4 (Sunday) • X3+X4+X5+X6+X7≥4 (Monday) • X1+X4+X5+X6+X7≥4 (Tuesday) • X1+X2+X5+X6+X7≥4 (Wednesday) • X1+X2+X3+X6+X7≥4 (Thursday) • X1+X2+X3+X4+X7≥4 (Friday) Similar constraints apply for all other wards, adjusting bj for each day's specific staffing needs. The above is represented in the following matrix form World Journal of Advanced Research and Reviews, 2025, 27(01), 1430-1439 1434 Figure 1 Integer linear programming model for nurses distribution per ward Similarly, integer programming formulation for F2 representing Anesthesia unit, Counseling unit and Multiple drugresistant units with a daily requirement of 2 nurses, F3 representing Labor ward and Antenatal clinic with a daily requirement of 6 nurses, and F4 representing Operating theatre and Tuberculosis ward with daily requirement of 1 nurse were formulated with values of bj’s on the right-hand side of the constraints as 2, 6 and 1 respectively. 3. Result analysis The excel solver was used to execute the branch and bound algorithm and the results are shown in the tables and figures below. Table 2 LP Solution for F1 X1 X2 X3 X4 X5 X6 X7 Objective 1 1 1 1 1 1 1 6 Constraint 1 1 1 1 1 1 0 0 4 4 Constraint 2 0 1 1 1 1 1 0 6 4 Constraint 3 0 0 1 1 1 1 1 4 4 Constraint 4 1 0 0 1 1 1 1 4 4 Constraint 5 1 1 0 0 1 1 1 4 4 Constraint 6 1 1 1 0 0 1 1 4 4 Constraint 7 1 1 1 1 0 0 1 4 4 Bound 0 0 0 0 0 0 0 Decisions 0 2 0 2 0 2 0 World Journal of Advanced Research and Reviews, 2025, 27(01), 1430-1439 1435 Figure 2 Branch and Bound Enumeration Tree for solution of F1 Table 3 LP solution for F2 X1 X2 X3 X4 X5 X6 X7 Objective 1 1 1 1 1 1 1 3 constraint 1 1 1 1 1 1 0 0 2 2 constraint 2 0 1 1 1 1 1 0 3 2 constraint 3 0 0 1 1 1 1 1 2 2 constraint 4 1 0 0 1 1 1 1 2 2 constraint 5 1 1 0 0 1 1 1 2 2 constraint 6 1 1 1 0 0 1 1 2 2 constraint 7 1 1 1 1 0 0 1 2 2 Bound 0 0 0 0 0 0 0 Decisions 0 1 0 1 0 1 0 World Journal of Advanced Research and Reviews, 2025, 27(01), 1430-1439 1436 Similarly, the objective value(minimum) for F3 consists of 7 nodes with Z =9, while the objective value for F4 consists Best of 3 nodes with Z= 1.5. The table below summarizes the optimal solution of the nurse scheduling problem for each grouping. Figure 3 Branch and Bound Tree for Enumeration solution of F2 Table 4 Summary of the optimal solution of the Nurse Scheduling problem Group X1 X2 X3 X4 X5 X6 X7 Objective value (z) F1 0 2 0 2 0 2 0 6 F2 0 1 0 1 0 1 0 3 F3 1 1 1 1 2 1 2 9 F4 1 0 0 0 1 0 0 2 4. Discussion of Results Based on the analysis we obtained the following key findings In the post-natal (1) and (2) ward, Nursery ward and Children ward (F1) which has total availability of 9,6 and 8 employed nurses respectively; (see Table 1), an optimal total of 6 nurses for each of the wards in this group (F1) is needed in order to satisfy their daily requirement of 4 nurses. Also, x2 =2, x4 =2, x6 =2 indicates that two nurses should be assigned to Sunday – Monday off, Tuesday – Wednesday off, Thursday – Friday off respectively; (see table 7), x1=0, x3=0, x5=0, x7=0 implies that no nurse should be assigned to Saturday –Sunday off, Monday –Tuesday off, Wednesday –Thursday off and Friday –Saturday off. In post-natal (3) ward, Anesthesia unit (A R T), Multiple drug-resistant units and out–patients department (F2) which has total of availability of 6,6,2 and 3 employed nurses respectively; (see table 1), an optimal total of 3 nurses for each of the wards/unit in this group (F2) is needed in order to satisfy their daily requirement of 2 nurses. Also, x2=1, x4=1, x6=1 indicates that one nurse should be assigned to Sunday –Monday off Tuesday –Wednesday off, and Thursday –Friday off respectively. (see table 8) Then, x1=0 World Journal of Advanced Research and Reviews, 2025, 27(01), 1430-1439 1437 x3=0 x5=0 and x7=0 implies that no nurse should be assigned to Saturday – Sunday off, Monday –Tuesday off, Wednesday-Thursday off and Friday-Saturday off. In labour ward and Antenatal clinic (F3) which has total of availability of 12 and 6 employed nurses respectively; (see table 1), an optimal total of 9 nurses for each of the wards in this group (F3) is needed in order to satisfy their daily requirement of 2 nurses. Also, x1=1, x2=1, x3=1, x4=1, x6=1 indicates that one nurse should be assigned to Saturday – Sunday off, Sunday –Monday off, Monday –Tuesday off Tuesday –Wednesday off, and Thursday –Friday off respectively. (see table 9) Then, x5=2 and x7=2 implies that two nurses should be assigned to Wednesday-Thursday off and FridaySaturday off. In operating theatre and tuberculosis ward (F4) which has total availability of 2 and 1 employed nurses respectively; (see table 1), an optimal total of 2 nurses for each of the wards/unit in this group (F4) is needed in order to satisfy their daily requirement of 1 nurse. Also, x1=1 x5=1 indicates that one nurse should be assigned to Saturday –Sunday off, and Wednesday –Thursday respectively, (see table 9) Then, x2=0, x3=0 x4=0, x6=0 and x7=0 implies that no nurse should be assigned to Sunday – Monday off, Monday –Tuesday off, Tuesday –Wednesday off, Thursday –Friday off and FridaySaturday off. These results are summarized in table 4 below Table 5 Optimal solution for each ward in mile four hospital Abakaliki, Ebonyi State Ward/units Optimal allocation of Nurse for days off Optimal number of Nurse required X1 X2 X3 X4 X5 X6 x7 Post natal (1) and (2) ward 0 2 0 2 0 2 0 6 Post natal (3) ward 0 1 0 1 0 1 0 3 Nursery 0 2 0 2 0 2 0 6 Labour ward 1 1 1 1 2 1 2 9 Antenatal clinic (A N C) 1 1 1 1 2 1 2 9 Anaesthesia unit (A R T) 0 1 0 1 0 1 0 3 Multiple drug resistant (MDR) 0 1 0 1 0 1 0 3 Out-patient department (OPD) 0 1 0 1 0 1 0 3 Children ward 0 2 0 2 0 2 0 6 Operating theatre 1 0 0 0 1 0 0 2 Admin / Counselling unit 0 1 0 1 0 1 0 3 Tuberculosis ward 1 0 0 0 1 0 0 2 Table 6 Sample of one week Roster for nurse in F1 wards/units Nurse ID number Sunday Monday Tuesday Wednesday Thursday Friday Saturday 1 Off On On On On On Off 2 Off On On On On On Off 3 On Off Off On On On On 4 On Off Off On On On On 5 On On On Off Off On On 6 On On On Off Off On On Required 4 4 4 4 4 4 4 World Journal of Advanced Research and Reviews, 2025, 27(01), 1430-1439 1438 Assigned 4 4 4 4 4 6 4 Excess 0 0 0 0 0 0 0 Table 7 Sample of one week Roster for nurse in F2 wards/units Nurse ID number Sunday Monday Tuesday Wednesday Thursday Friday Saturday 1 Off On On On On On Off 2 On Off Off On On On On 3 On On On Off Off On On Required 2 2 2 2 2 2 2 Assigned 2 2 2 2 2 3 2 Excess 0 0 0 0 0 1 0 Table 8 Sample of one week Roster for nurse in F3 wards/units Nurse ID number Sunday Monday Tuesday Wednesday Thursday Friday Saturday 1 On On On On On Off Off 2 Off On On On On On Off 3 Off Off On On On On On 4 On Off Off On On On On 5 On On Off Off On On On 6 On On On Off On On On 7 On On On Off Off On On 8 On On On On Off Off On 9 On On On On Off Off On Required 6 6 6 6 6 6 6 Assigned 7 7 6 6 6 6 7 Excess 1 1 0 0 0 0 1 Table 9 Sample of one week Roster for nurse in F4 wards/units Nurse ID number Sunday Monday Tuesday Wednesday Thursday Friday Saturday 1 On On On On On Off Off 2 On On Off Off On On On Required 1 1 1 1 1 1 1 Assigned 2 2 1 1 2 1 1 Excess 1 1 0 0 1 0 0