Nurse Scheduling

Abstract

The cost of health care is increasing dramatically every year in the United States. For instance, according to the Towers Perrin healthcare survey, healthcare costs increased an average of 6% in 2008 compared to 2007 (Perrin 2008). Cost of developing new technologies and treatments, rising personnel income, America’s aging population, and a relatively increased demand for health care are some of the reasons for this rapid growth. The Centers for Medicare and Medicaid Services estimated that by 2018, the cost of health care will be more than 4.3 trillion dollars, which is 20.3% of the total GDP (Foundation 2009).

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

3.1 Introduction

The cost of health care is increasing dramatically every year in the United States. For instance, according to the Towers Perrin healthcare survey, healthcare costs increased an average of 6% in 2008 compared to 2007 (Perrin 2008). Cost of developing new technologies and treatments, rising personnel income, America’s aging population, and a relatively increased demand for health care are some of the reasons for this rapid growth. The Centers for Medicare and Medicaid Services estimated that by 2018, the cost of health care will be more than 4.3 trillion dollars, which is 20.3% of the total GDP (Foundation 2009). Over 50% of healthcare costs are for hospital resources, physicians and clinical services, as shown in Fig. 3.1.

Fig. 3.1

Distribution of national spending (Foundation 2009)

One of the main concerns in many healthcare systems is to provide high quality services at lower costs to patients. People deserve to get the care that they need. The care should be patient centered and efficient in a safe and timely manner without wasting resources. For this purpose, inefficiencies and variabilities in the usage of resources should be identified; proper activities should be introduced and suitable solution methods should be provided. Operations Research techniques are useful to provide optimal or efficient schedules to improve different aspects of healthcare systems, such as resource utilization, hospital patient flow, medical supply chain, staff scheduling and medical decision-making, to name a few, resulting in cost reductions. In this chapter, we focus on nurse scheduling.

Nurse shortage is a problem worldwide (Ulrich et al. 2002). Not having enough skilled nurses in clinical settings has caused a significant negative impact on patient outcomes, including mortality (Aiken et al. 2002). Under this epidemic of nurse shortage, hospital administrators and nurse managers are in dire need to optimally utilize and retain currently available nurses without jeopardizing their job satisfaction. When one schedules nursing staff, it is known that considering their shift preferences can increase job satisfaction, which leads to savings in labor costs due to reduced nurse turnover and other issues, such as retention rates, patient safety, and healthcare quality (Bester et al. 2007; Blythe et al. 2005; Cheng et al. 1997; Chiaramonte and Chiaramonte 2008). Therefore, it is essential to develop nurse scheduling tools that will optimally utilize and retain currently available nurses. Scheduling nurses to meet a hospital’s daily demand and satisfy staffing policies, such as those dictated by a union contract and regulations mandating specific nurse-to-patient ratios, is an extremely complex task to perform. Confounding this environment is the fact that the nurses are non homogeneous with respect to their skill set, experience, employment type (e.g., part time versus full time, and nurse availability). Furthermore, the demand for nurses varies in accordance with patient census. Because some of these objectives may conflict with each other, nurse scheduling must be carefully done to capture appropriate tradeoffs among different objectives.

Assigning each available nurse to the right place at the right time is a major concern among many healthcare organizations. Well-designed schedules can generate an efficient work plan that should be able to precede restrictions and variabilities and have a predefined solution for addressing those constraints and expectations. However, it can be an extremely difficult task to develop a schedule that is robust against all constraints and variabilities in real-world problems. There are some inherently common rules in all hospital staffing that can be applied to most departments of a hospital, except for operating suites. Operating suites are considered to be the living heart of the hospital, and provide the largest amount of revenue for the hospital (Belien and Demeulemeester 2008). Since there is an increasing demand for surgeries caused by an aging population (Cardoen et al. 2010) and most operating suites face nurse shortages, it is essential for managers to develop suitable and effective scheduling plans for operating suites. Similarly, operating suites have nurse and shift restrictions along with regulatory and union requirements to schedule their nurses. However, specific limitations and the importance of surgery procedures that are associated with the patient’s life can affect nurse scheduling procedures. For instance, nurses must not leave an operating room to take a break unless the surgery is finished or someone else is available to relieve them.

Consequently, we divide nurse scheduling problem into two categories: Nurse Scheduling Problem in a General Clinic and Nurse Scheduling Problem in an Operating Suite.

3.2 Nurse Scheduling Problems

In this section, two nurse scheduling problems are discussed: nurse scheduling problem in a general clinic and nurse scheduling problem in an operating suite. For each nurse scheduling problem, the attributes that are required to develop efficient nurse scheduling models are explained.

3.2.1 Nurse Scheduling Problem in a General Clinic

A general clinic is an area in a hospital or some other healthcare organization that provides healthcare services to patients with similar needs. These services are provided by healthcare professionals such as physicians and nurses, who have been trained in that specialty. Different attributes of a general clinic can be discussed as follows:

Patients. Patients can be divided into two groups: inpatients and outpatients. An outpatient is a patient who is not hospitalized overnight but needs to visit the department to receive medical attention, care, or treatment. On the other hand, an inpatient needs to stay in the hospital overnight or for an indecisive amount of time. Patient workload can be defined to be more than simply a care unit’s census. Rather, patient workload is viewed as a factor for the care unit’s case mix for a given shift. If the case mix is high, there will be a correspondingly high workload placed on nurses and, in turn, patient workload will be high. In effect, a high patient workload implies a higher workload for the nurses. Similarly, if the case mix is low, there will be low workload for the nurses. For example, if a patient comes for an MRI, he may need to receive a preliminary examination, a dye injection, and the MRI procedure. Therefore, this patient requires three different services, which can be considered as three separate workloads.

Nurse Categories in a General Clinic. A nurse is a healthcare professional who provides medical care and treatment to patients as prescribed by physicians. Note that, nurse practitioners are excluded as they may operate independently in some situations. Nurses, one of the largest human resources in a hospital, can be classified into different groups. Based on the number of working hours, nurses can be categorized as full time and part time (contracted and staff nurses). A full time nurse typically works 40 hours a week while part time nurses work based on their weekly contracted work hours. Also, nurses can be categorized into different grades based on their skill levels, experience, education, knowledge, and certificates. Nurses are distinguished from each other by their area of specialty. Therefore, each patient can receive medical care from nurses who can provide specific treatments. Different nurses with the same specialty area can do the same task at varying time durations based on their skill levels and experiences. If patient workload is less than nursing capacity, there will be idle nurses. However, this is not common in many clinics due to nurse shortages. In the case of shortages, many schedulers consider downgrading in which higher skilled nurses are assigned to shifts that lower skilled nurses are capable of performing. However, the reverse is not true.

Shift Limitations. Providing patients with medical attention is an every day task. Therefore, a general clinic should make sure that there are available nurses at all times responding to the patient workload. On the other hand, nurses are not allowed to work more than their scheduled daily work hours. So there should be nurses assigned to multiple consecutive shifts per day.

3.2.2 Nurse Scheduling Problem in an Operating Suite

An operating suite is an area in a hospital or other healthcare organization which provides surgical procedures and consists of several operating rooms (OR). An operating room is designed to perform different types of surgeries; however, some rooms are equipped for special treatment needs such as robotic rooms that have different robots or brain surgery rooms that provide MRI during surgery. Services in an OR are provided by surgeons, nurses, and anesthesia professionals who have been trained for different specialties. Different attributes of an operating suite can be discussed as follows:

Surgery Specialty. Surgery is a medical operation, using instruments and techniques on a patient to treat or improve a disease or injury. Each operating suite in a hospital can provide different surgery specialty services. For instance, in a cancer center, there can be surgery specialties such as neurosurgery, plastic surgery, head and neck surgery, to name a few.

Surgery Procedure Complexity. Each surgery can have different procedure complexities. Each procedure in a surgery can be classified as easy, moderate, or complex.

Surgery Case. We define a surgery case as a series of surgery operations with different surgery specialties and procedure complexities that should be performed on one patient in one operating room in a scheduled day. Many surgery cases may require multiple operations performed by different surgeons in different times in one OR. Each surgery case should be scheduled in advance, unless it is an emergency situation. Therefore, surgery specialties, procedure complexity, required equipments, nurses types, and surgery case duration are often known beforehand. Surgery duration can be defined as the time that is required to finish a surgery case starting from transferring the patient to the operating room (patient-in time), proceeding by performing the surgery (surgery time) and finishing by moving the patient out of the operating room (patient-out time). Also, each surgery has a nurse demand, which is the number of different nurses required for each surgery case at each time period to do different roles with various specialties.

Nurse Categories in an Operating Suite. An OR nurse is a healthcare professional who provides technical and medical help to the surgeon during a surgery and to the patient before and after surgery. Also, nurses can be categorized by different types based on their skill level, experience, education, knowledge, and certification. Some attributes of nurses in an operating suite are as follows:

• Nurse role: Nurses can have different roles during a surgery based on their skill level. The most recognized roles in surgeries are circulation and scrub. Both roles are essential during a surgery to provide smooth surgery operation on a patient.

• Nurse specialty: Different nurses can work on different specialties based on their skill levels and certifications.

• Nurse procedure competency: Not all nurses can support surgeries with complex procedures. Nurses can handle surgery procedure complexities based on their skill level and experience. They can work on simple, moderate, or complex procedures. Nurses who have enough experience to work on more complex procedures can also work on easier procedures.

Shift Limitations. Generally, operating suites have various predefined shifts during a working day. All nurses upon their hiring will be assigned to these established shifts based on their contracts. Each shift has its own regulations and limitations, such as break and lunch hours, overtime rules, and nurse availability.

Variability. Operating rooms are associated with many variabilities, such as human behavior, surgery time, and nurse availability. An excessively complicated model will be the result of considering all these variabilities.

3.2.3 Problem Statement

We introduced two different nurse scheduling problems (NSP): nurse scheduling problem in a general clinic and nurse scheduling problem in an operating suite. For both problems, the purpose is to develop a decision-making tool that assigns nurses to the right place at the right time to do the right job. Researchers may develop different nurse scheduling tools for each NSP by finding proper answers for the following questions.

• What input parameters are available or should be provided for each NSP?

• What are the goals associated with each NSP?

• What limitations and constraints should be considered in each NSP?

• What are the proposed methods for each NSP?

• What will be the outcome of each NSP?

The problem in a general clinic is to develop a decision-making tool that assigns nurses to shifts based on nurse preference and patient workload requirements. It is assumed that decision makers have complete information about the number of available skilled nurses, different categories of nurse skill level, nurse shift preference, patient workload types, patient workload durations, and working contract options. Therefore, the purpose is to develop nurse scheduling tools that consider different goals, such as minimizing costs, patient dissatisfaction, and nurse idle time and overtime, and maximizing nurse job satisfaction by incorporating nurse preferences. The problem to optimize in an operating suite is similar to the nurse scheduling problem in a general clinic. The main goal is to assign nurses to surgery cases in each shift by incorporating nurse specialty, nurse availability, role abilities, and surgery case requirements in optimization models. The purpose is to develop nurse scheduling tools that consider different goals, such as minimizing nurse overtime, idle time, and delays during the day; and maximizing surgery case demand satisfaction.

3.3 A Review of Optimization Applications and Methods

Nurse scheduling is a complex and time-consuming task that has a daily effect on hospital staffing. Developing mathematical or heuristic approaches that can easily provide solutions can efficiently improve the time and effort required for scheduling. These solution algorithms can provide more balanced and practical schedules as well as improve staff satisfaction.

Massive amounts of work to introduce models and solution algorithms for the nurse scheduling problem have been done recently. In this section, the literature on nurse scheduling problem is categorized into two main sections. The first provides models and solution algorithms for the general nurse scheduling problem and the second into emphasizes on the nurse scheduling problem in an operating suite. Several nurse scheduling models are introduced, decision variables and constraints are expressed and solution algorithms are discussed for each nurse scheduling problem.

3.3.1 Nurse Scheduling Problem in a General Clinic

Given the significance of healthcare scheduling and the severity of the problem, a great deal of work has recently been directed toward the nurse scheduling problem.

3.3.1.1 Primary Nurse Scheduling Problems

Fries (1976) presented a bibliography of early methods for personnel rostering in healthcare institutions. Many of those early approaches relied on manual procedures, following a set of arbitrary rules. They are too restricted to be directly applicable to problems faced in modern hospitals. The large size of clinics as well as many limitations, such as shift and regulatory limitations, consecutivity requirements, different types of treatment needs, are some of the main challenges that should be considered nowadays. Burke et al. (2004) mentioned that one of the first optimization models in nurse scheduling was introduced by Warner and Prawda (1972). The main contribution of this model was its emphasis on maintaining the integral and capacity constraints of the nurse scheduling problem. A mixed-integer quadratic programming formulation was presented to calculate the number of nurses from a certain skill category to undertake a number of shifts per day. Three non-overlapping shift types of 8 hours each are used. The objective function aimed at minimizing the difference between a given lower limit for the number of nurses and the variables. The minimum staffing requirements should consider the possibility of replacing personnel members with different skills as well as the organization’s established standards. We describe the model’s decision variables, model formulation, and the proposed solution method as follows.

3.3.1.1.1 Decision Variables

The parameters for this problem defined as: $R =R_{\rm int}$ denote a demand for nursing care services matrix; $U={U_{\rm imnt}}$ denote an allocation of nursing time matrix; $Q_{\rm imnt},$ for $i \in I, m, n \in N$ and $t \in T,$ is the ratio at which a nurse of skill class m is able to substitute for a nurse of skill class n on ward i during shift t; $W_{\rm int}$ is the relative seriousness of a deviation between $R_{\rm int}$ and $X_{\rm int}; \; B_n$ is the number of nurse-shifts of type n nurse that are available to be scheduled over $i \in I$ and $t \in T;$ and $A_{\rm int}$ is the percentage of the nursing personnel requirement of skill class n nurse that must be provided on ward i during shift t.

Let $X = X_{\rm int}$ be an allocation of the nurses matrix, which is considered as the decision variables.

3.3.1.1.2 Optimization Model

$$ \hbox{Min} \,C(U|R)=\sum_{i \in I}{\sum_{n \in N}{\sum_{t \in T}{W_{\rm int}(R_{\rm int}-\sum_{m}{Q_{\rm imnt}U_{\rm imnt}})}}} $$

(3.1)

$$ \sum_{p}{U_{\rm inpt}}-X_{\rm int} \le 0, \qquad \forall i \in I, n \in N, t \in T $$

(3.2)

$$ \sum_{i \in I}{\sum_{t \in T}{X_{\rm int}}} \le B_n, \qquad \forall n \in N $$

(3.3)

$$ X_{\rm int} \ge A_{\rm int}R_{\rm int}, \qquad \forall i \in I, n \in N, t \in T $$

(3.4)

$$ X_{\rm int} \le R_{\rm int} + e_{\rm int}, \qquad \forall i \in I, n \in N, t \in T, e_{\rm int} \ge 0 $$

(3.5)

$$ X_{\rm int} \; \hbox{integer}, \qquad \forall i \in I, n \in N, t \in T $$

(3.6)

$$ U_{\rm imnt} \ge 0, \qquad \forall i \in I, m, n \in N, t \in T $$

(3.7)

Constraints (3.2) ensure that the total number of nurses with skill class n assigned as any skill class $p \in N$ cannot exceed the total number of skill class n nurses assigned during scheduling. Also resource capacity is included as a constraint in Eq. 3.3 and $B_n$ is defined as the number of nurse-shifts of type n nurse which are available to be scheduled over $i \in I$ and $t \in T.$ The next constraint (3.4) is developed based on the assumption that there exists some minimum amount of nursing care services of each skill class that must be provided in order to maintain minimum professional standards of care. The last constraint limits the amount of substitution of nursing tasks among skill classes, where $e_{\rm int} \ge 0$ is a given scalar that establishes upper bounds on the feasible range of applying the substitution ratios $Q_{\rm imnt}.$

3.3.1.1.3 Solution Method

The problem was decomposed by a primal resource-directive approach into a multiple-choice programming master problem, with quadratic programming subproblems. Initial results suggested that a linear programming formulation, with a post-optimal feasibility search scheme, may be substituted for the multiple-choice master problem.

Burke et al. (2004) mentioned that this early approach could not consider the current needs of hospitals. Also there was no possibility of including personal preferences in this model. All the nurses were anonymous. An excess of nursing supply for a particular skill category could absorb the shortage of other skills. A drawback of the approach was that an accurate forecast of personnel demand could not be trustworthy for a period longer than 4 days.

3.3.1.2 Single-Objective Nurse Scheduling Problems

The articles by Cheang et al. (2003) and Burke et al. (2004) are two of the most comprehensive surveys in nurse scheduling and rostering problems. Burke et al. (2004) described a general nurse scheduling and rostering problem, and evaluated various models and solution approaches found in more than 140 articles and PhD dissertations. Some of these papers can be found in (Aickelin and Dowsland 2004; Berrada et al. 1996; Dowsland 1998; Miller et al. 1976). Integer programming (IP) has been widely used for solving the NSP problem (Aickelin and Dowsland 2004; Aickelin and Li 2007; Aickelin and White, 2004; Aickelin et al. 2007; Bai et al. 2010; Bard and Purnomo 2005; 2007; Li and Aickelin 2003; Ogulata et al. 2008; Purnomo and Bard 2006). Most of the proposed optimization models deal with a single objective function. Minimizing costs and maximizing nurse preferences are the two most common objectives introduced in the literature.

3.3.1.2.1 Cost as an Objective Function

The cost of assigning nurses to each shift is one of every hospital’s main concerns. Typically, the total cost includes salary, benefits, and any other extra expenses that the hospital must be responsible for hiring nurses.

Bai et al. (2010) developed a pattern-based optimization model to minimize the penalty cost of assigning different nurses to different shift patterns. The contribution of this paper is the presentation of a robust hybrid algorithm for the nurse rostering problem. The hybrid algorithm is, in fact, very flexible and can be readily adapted to many other constrained optimization problems. This problem was motivated by a real nurse rostering problem faced by a large U.K. hospital. The formulation employed in this model represents a generic nurse rostering problem and has been used in several other studies. The problem is to make weekly schedules for about 30 nurses. Each day’s schedule consists of a day shift and a night shift. For each shift, a feasible solution has to assign sufficient nurses to cover the actual demands, which are subject to changes throughout the week. Two practical constraints have made this problem particularly challenging. First, nurses have three different grades. A higher grade nurse can cover the demand for a lower grade nurse but not vice versa. Second, there are some part-time nurses who can only work a certain number of hours each week and may also not be able to work on certain shifts. The schedule should also be able to satisfy “day-off” requests by nurses. It should also spread some unpopular shifts (e.g., night and weekend shifts) among nurses for fairness.

3.3.1.2.2 Decision Variables

Given a number of nurses (n) with each nurse having a grade among the range from 1 to g, let $G_r$ be the set of nurses with grades r or higher, $R_{kr}$ the minimal demand of nurses of grade r for shift k, and $F_i$ the set of feasible shift pattern for nurse i. Set $a_{jk} = 1$ if pattern k covers shift j and 0 otherwise. Let $p_{ij}$ be the penalty cost of nurse i working on pattern j.

The decision variables are defined as $x_{ij}$ such that $x_{ij}$ is 1 if nurse i works on pattern j and 0, otherwise.

3.3.1.2.3 Optimization Model

The model is as follows:

$$ \hbox{Min} \; f=\sum_{i=1}^{n}{\sum_{j \in F_i}{p_{ij}x_{ij}}} $$

(3.8)

$$ \sum_{j \in F_i}{x_{ij}}=1, \qquad \forall i \in \{1,\cdots,n\} $$

(3.9)

$$ \sum_{i \in G_r}{\sum_{j \in F_i}{a_{jk}x_{ij}}} \ge R_{kr}, \qquad \forall k,r $$

(3.10)

Constraints (3.9) ensure that each nurse must work on exactly one specific shift pattern. Also, it is important to make sure that there are sufficient nurses to cover each shift at each grade (3.10). The objective, shown in Eq. 3.8, is to minimize the total penalty cost of assigning nurses to different patterns. Several methods have been used to tackle the constraints (3.10), which make the solution search space severely constrained.

3.3.1.2.4 Solution Method

Evolutionary algorithms are inspired from the natural evolution and selection principle of “survival of the fittest.” For an optimization problem, a solution is usually encoded in a specially designed string. A population of individuals is maintained and evolves from one generation to another through some genetic operations and a selection method until some stopping criteria are met. Penalty functions are commonly used to transform the constrained optimization problem into an unconstrained one by introducing a penalty term into the objective function to penalize constraint violations. Let X be the vector of decision variables and f(X) be the original objective function. The transformed objective function $\phi(X)$ is then presented in the form of

$$ \phi(X)=f(X)+\lambda\varphi(g_{\pi}(X)); \quad \pi \in \Uppi $$

(3.11)

where $\lambda$ is the associated penalty coefficient and $\varphi(g_{\pi}(X))$ is the function that measures the severity of violations of the following constraints

$$ g_{\pi}(X)\ge 0; \quad \pi \in \Uppi $$

(3.12)

In the case of the nurse rostering problem addressed in this paper, the following function was used to measure the violation of the covering constraints (3.10).

$$ \varphi(g_{\pi}(X))=\sum_{k=1}^{14}{\sum_{r=1}^{g}{\left\{ \hbox{\rm max}\left\{0,R_{kr}-\sum_{i \in G_r}{\sum_{j \in F_i}{a_{jk}x_{ij}}}\right\}\right\}}} $$

(3.13)

Another type of constraint handling method is stochastic ranking. The underlying idea is to “fuzzify” the common ranking criteria by introducing a ranking probability $P_f.$ The ranking can be obtained by a procedure similar to a stochastic version of the bubble-sort algorithm with N sweeps. In this method, the ranking is based on an objective function only if all the individuals are feasible. Otherwise, the ranking is stochastic. Denote by $P_w$ the probability of an individual winning a comparison with an adjacent individual.

$$ P_{w}=P_{fw}P_f+P_{\varphi w}(1-P_f) $$

(3.14)

where $P_{fw}$ and $P_{\varphi w}$ are, respectively, the probability of the individual winning according to the objective function and the penalty function. By fixing the number of sweeps n and by adjusting the probability $P_f,$ the dominance of the objective function f and the penalty function $\varphi[10]$ can be balanced. The number of sweeps is fixed to N = S. When $P_f < 0.5,$ the ranking is mainly dominated by the objective function f and $P_f > 0.5$ means the ranking favors smaller penalty function values $\varphi.$ Since the ultimate purpose is to search for the best feasible solution, the parameter should be set to $P_f < 0.5.$ Finally, a hybrid algorithm was developed to solve the problem. The hybrid algorithm combines a genetic algorithm and a simulated annealing hyper heuristic (SAHH). In this algorithm, a stochastic ranking method was used to improve the constraint handling capability of the genetic algorithm while an SAHH procedure was incorporated in order to locate local optima more efficiently. The hybrid algorithm is developed based on a total of nine simple low-level heuristics. Here is the complete list of these heuristics.

• Heuristic 1: Change the shift-pattern of a random nurse to another random feasible shift-pattern.

• Heuristic 2: Similar to Heuristic 1, except the acceptance criteria is “1st improving $\varphi$ value.”

• Heuristic 3: Same as Heuristic 1 but “1st improving $\varphi$ and not deteriorating f.”

• Heuristic 4: Same as Heuristic 1 but “1st improving f.”

• Heuristic 5: Same as Heuristic 1 but “1st improving f and not deteriorating $\varphi.$”

• Heuristic 6: Switch the shift-pattern type (i.e., from day to night and vice versa) of a random nurse if the solution is unbalanced.

• Heuristic 7: This heuristic tries to generate a balanced solution by switching the shift-pattern type [i.e., change a day shift-pattern with a night one if night shift(s) is unbalanced and vice versa. If both days and nights are not balanced, swap the shift patterns of two nurses who are working on different shift-pattern types].

• Heuristic 8: This heuristic tries to find the first move that improves f by changing the shift pattern of a random nurse and assign the abandoned shift pattern to another nurse.

• Heuristic 9: Same as Heuristic 8 but “1st improving f without worsening $\varphi.$”

Compared with genetic algorithms that use penalty function methods as a constraint handling approach, the stochastic ranking method has demonstrated better performance with regard to feasibility. To improve the solution quality in terms of the objective function value, an SAHH algorithm was hybridized with the genetic algorithm. Experimental results have demonstrated the high-performance and consistency by this hybrid approach when compared with the genetic algorithm with stochastic ranking and the simulated annealing alone.

3.3.1.2.5 Nurse Preferences as an Objective Function

Fulltime nurses are vital components in hospital operations. However, nursing shortages has been an issue worldwide. This is due to lack of trained nurses and low job satisfaction, to name a few factors (Ulrich et al. 2002). Many approaches have been developed to address this issue, such as the score card approach to adopt nurse preferences on shift assignment (Bard and Purnomo 2005) and the auction approach (Chiaramonte and Chiaramonte 2008; Koeppel 2004). In the score card approach, each nurse is given a sheet of upcoming empty shift assignments. Based on their personal preference, the nurse is asked to assign penalty scores in such a way that a smaller penalty should be assigned to a preferred shift while a higher penalty should be given to an undesirable shift. Some master schedulers may share this round of schedule preferences among nurses and resolve some conflicting shifts that no one wants to take or everyone wants to take.

Purnomo and Bard (2006) proposed a new integer programming model for cyclic preference scheduling and hourly workers. The objective of cyclic scheduling is to generate a set of rosters that minimizes the number of uncovered shifts, while in the preference scheduling the objective is to minimize a “dissatisfaction” cost associated with violations of soft constraints. The problem combines elements of both cyclic and preference approaches and includes five different shift types. The first three divide the day evenly into non-overlapping periods of 8 hours each and are referred to as day (D), evening (E), and night (N). The remaining two divide the day into 12 hour, non-overlapping periods and are called a.m. and p.m. The objective function aims to minimize the weighted sum of preference violations and the cost of covering gaps with outside nurses.

3.3.1.2.6 Decision Variables

The parameters for this problem are defined as: $r_a$ denotes penalty assigned to a roster that has a violation; $h_t$ denotes length of shift t (hours); $M_t$ is a large number representing the cost of an outside nurse for shift t; $H_i$ is number of hours nurse i is contracted to work every 2 weeks; $LD_{dt}(UD_{dt})$ is lower (upper) demand requirement for shift t and day d; $D_t^{\rm maxon}$ presents maximum number of consecutive days that nurse i is permitted to work; $W_i^{\rm max}$ presents number of weekend shifts nurse i must work every 2 weeks; $V_{\rm max}$ denotes maximum number of violations allowed for each nurse; $TR_{\rm max}$ denotes maximum number of transitions from one shift type to another on consecutive days allowed in 14 days; and $O_{dt}^{\rm max}$ presents maximum number of outside nurses that can be assigned to shift t on day d.

The decision variables for the problem are: $x_{idt}$ is 1 if nurse i works in shift t on day d, and 0 otherwise; $w_{im}$ is 1 if nurse i works on weekend m, and 0 otherwise; $v_{i\alpha}$ is 1 if nurse i has $\alpha$ violations, and 0 otherwise; $b_{id}$is 1 if nurse $i \in N_R$ works in shift $t_1$ on day d and shift $t_2$ on day d+1, and 0 otherwise. Let $p_{id}=1$ when nurse i has a 0-1-0 pattern that starts on day d, and 0 otherwise, and $q_{id}=1$ when nurse i has a 1-0-1 pattern that starts on day d, and 0 otherwise. Let $y_{dt}$ denote the number of outside nurses assigned to shift t on day d and $s_{dt}$ present excess number of nurses assigned to shift t on day d.

3.3.1.2.7 Optimization Model

$$ \theta_{ip}=\hbox{Min} \sum_{i \in N}{\sum_{a=1}^{V_{\rm max}}{r_{a}v_{ia}}}+\sum_{d \in D}{\sum_{t \in T}{M_{t}y_{dt}}}, $$

(3.15)

$$ \sum_{i \in N}{x_{idt}} - {s_{dt}} + {y_{dt}} = LD_{dt},\qquad \forall d \in D,t \in T $$

(3.16)

$$ \sum_{d \in D}{x_{idt}} \ge {P_{it}},\qquad \forall i \in {N_R},t \in {T_i} $$

(3.17)

$$ \sum_{d \in D}{\sum_{t \in T_i}{{h_t}{x_{idt}}}} = H_i,\qquad\forall i \in N $$

(3.18)

$$ \sum_{t \in T_i} {{x_{idt}}} \le 1,\qquad \forall i \in N,d \in D $$

(3.19)

$$ {x_{id{t_2}}} + {x_{i,d + 1,{t_1}}} \le 1,\qquad \forall i \in {N_{BB}},d \in D $$

(3.20)

$$ \sum_{l = d}^{d + D_{i}^{\rm maxon}} {\sum_{t \in {T_i}}{{x_{ilt}}}} \le D_i^{\rm maxon} ,\qquad \forall i \in N,d \in D $$

(3.21)

$$ \sum_{d \in {D_w}} {\sum_{t \in {T_i}} {{x_{idt}}}} = W_i^{max }{w_{im}},\qquad \forall i \in N,m \in W $$

(3.22)

$$ \sum_{m \in W} {{w_{im}}} = 1,\qquad \forall i \in N $$

(3.23)

$$ \sum_{t \in {T_i}} {{x_{idt}}} + ( {1 - \sum_{t \in {T_i}} {{x_{i,d + 1,t}}} } ) + \sum_{t \in {T_i}} {{x_{i,d + 2,t}}} + {p_{id}} \ge 1,\qquad\forall i \in N,d \in D $$

(3.24)

$$ ( {1 - \sum_{t \in {T_i}} {{x_{idt}}} } ) + \sum_{t \in {T_i}} {{x_{i,d + 1,t}}} + ( {1 - \sum_{t \in {T_i}} {{x_{i,d + 2,t}}} } ) + {q_{id}} \ge 1,\qquad \forall i \in N,d \in D $$

(3.25)

$$ 1 - {x_{id{t_\alpha }}} + 1 - {x_{i,d + 1,{t_\beta }}} + {b_{id}} \ge 1,\qquad \forall d \in D,\alpha \ne \beta $$

(3.26)

$$ \sum_{d \in D} {{b_{id}}} \le T{R_{\max }},\qquad \forall i \in {N_R} $$

(3.27)

$$ \sum_{d \in D} {({p_{id}} + {q_{id}} + {b_{id}})} = \sum_{a = 1}^{{V_{max }}} {a{v_{ia}}} ,\qquad\forall i \in N $$

(3.28)

$$ \sum_{a = 1}^{{V_{max }}} {{v_{ia}}} \le 1,\qquad\forall i \in N $$

(3.29)

$$ 0 \le {s_{dt}} \le U{D_{dt}} - L{D_{dt}}, 0 \le {y_{dt}} \le O_{dt}^{max },\qquad \forall t,d $$

(3.30)

$$ {b_{id}},{p_{id}},{q_{id}} \ge 0, \forall i,t,d; \quad {v_{ia}} \in \{ 0,1\} , \forall i,a; \quad {w_{im}} \in \{ 0,1\} ,\forall i,m $$

(3.31)

$$ {x_{idt}} \in \{ 0,1\} , \forall i,t,d, \quad \hbox{where}\; {x_{i,14 + l,t}} \equiv {x_{ilt}}, l = 1,\ldots ,D_i^{\rm maxon} $$

(3.32)

There are two sets of constraints. Constraints (3.16–3.23) are hard constraints and the rest are soft constraints. Constraints (3.16) correspond to the demand requirement for each shift $t \in T$ on day $d \in D.$ These constraints, along with constraints (3.30) show that the number of nurses assigned to shift t must be at least $LD_{dt},$ and no more than $UD_{dt}.$ Constraints (3.17) guarantee that for all $i \in N_R$ at least $P_{it}$ shifts of type t are assigned every 2 weeks. Equations (3.18) state that the total number of hours assigned to nurse i must be equal to the number of hours $H_i$ that she is obligated to work every 2 weeks contractually. Constraints (3.19) restrict a nurse to at most one shift assignment within 24 hours. Constraints (3.20) rule out back-to-back shifts. Constraints (3.21) ensure that the work stretch of nurse i is not more than $D_i^{\rm maxon}$ days in any time window of $D_i^{\rm maxon}+1$ consecutive days. Together, constraints (3.22) and (3.23) require that nurse i works exactly $W_i^{\rm max}$ weekend days every 2 weeks. Constraints (3.24–3.29) determine the quality of the schedules. The undesirable patterns including $0-1-0$ and $1-0-1$ are counted by the variable $p_{id}$ and the summation $\sum_{d\in D}{p_{id}+q_{id}}$ in constraints (3.24) and (3.25) respectively. Constraints (3.26) detect a shift transition that nurse i may have during consecutive days. The maximum number of permitted transitions is given by $TR_{\rm max}$ in (3.27). Constraints (3.28–3.29), count the number of preference violations and determine which penalty coefficient $r_a$ will be in effect, respectively. Finally the bounds in constraints (3.30), on the $y_{dt}$ and $s_{dt}$ variables limit the amount of under-and over coverage, respectively, for each shift on each day.

3.3.1.2.8 Solution Method

A branch-and-price algorithm was developed for solving the problem. An IP-based neighborhood search heuristic was proposed, which always found the best solutions and enabled the algorithm to converge in a matter of minutes in most cases. The problem was decomposed and two approaches were investigated to modify branching rules in the construction of the search tree, one based on the master problem variables and the other on subproblem variables. It can be shown that the former was more suited for instances with a large number of nurses and profiles, while the latter was more efficient for small- and medium-sized problems. A unique feature of the formulation is that the master problem contains integer rather than binary variables.

3.3.1.3 Multi-Objective Nurse Scheduling Problems

Although many researchers have focused on only one objective function to model nurse scheduling problems, NSP is truly a multiple objective optimization problem (Burke et al. 2010; Maenhout and Vanhoucke 2010; Parr and Thompson 2007). There can be many goals in scheduling nurses such as minimizing the nurse assignment cost, maximizing nurse job satisfaction, or any other goals that the hospital has due to different sets in terms of scheduling nurses. Some of these may have conflicts of interests. Maenhout and Vanhoucke (2010) presented a branch and price algorithm for solving a multi-objective nurse scheduling problem incorporating some penalty scores associated with scheduling inefficiencies. Other relevant nurse scheduling papers can be found in (Azaiez and Al Sharif 2005; Jaumard et al. 1998).

Hadwan and Ayob (2010) proposed a greedy constructive heuristic algorithm based on the idea of generating the most required shift patterns to solve the nurses’ rostering problem that arises in University Kebangsaan Malaysia Medical Centre (UKMMC), Malaysia. This work aims to ensure the availability of enough nurses by giving them fair consideration during the rostering period. The complexity of the solution search space was reduced by generating all the allowed two-day and three-day shift patterns to build up the roster. Due to different sets of soft constraints, they proposed a weighted method approach to model the problem different from other objectives in the literature. The objective function aimed to minimize the total penalty cost that occurs due to the violations of soft constraints.

3.3.1.3.1 Decision Variables

The parameters and indexes for this problem are: I denotes the set of nurses available; ${I_s}$ denotes the set of senior nurses ${I_s} \subset I;$ D denotes the set of days; G denotes the set of grades; W presents the set of weights; S presents the set of shifts. The possible shifts are considered as: morning, evening, night, and day off. These four shifts are respectively represented by the set $S= \{1,2,3,4\}.$ P presents the set of possible night patterns; d is the ${d^{th}}$ day where $d \in D;$ s is the ${s^{th}}$ shift where $s \in S;$ w is the ${w^{th}}$ weight where $w \in W;$ p is the ${p^{th}}$ possible pattern where $p \in P; \,{R_{ds}}$ denotes the demand for day d on shift s; ${d_p}$ denotes the starting date for pattern p.

The decision variables are defined as: ${X_{ids}}$ is 1 if nurse i works on day d shift s, and 0 otherwise; and ${Y_{pi}}$ is 1 if pattern p is worked by nurse i, and 0 otherwise.

3.3.1.3.2 Optimization Model

$$ \hbox{Min} \; {w_1}\sum\limits_{i \in I} {(d1_i^ + + d1_i^ - ) + {w_2}} \sum\limits_{i \in I} {d2_i^ + } + {w_3}\sum\limits_{i \in I} {\sum\limits_{d \in D} {d3_{id}^ - } + {w_4}\sum\limits_{i \in I} {\sum\limits_{d \in D} {d4_{id}^ - } + {w_5}\sum\limits_{p \in P} {d5_p^ + } } } $$

(3.33)

Subject to:

$$ \sum\limits_{i \in I} {{X_{id(1)}}} \ge {R_{d(1)}}, \qquad \forall d \in D $$

(3.34)

$$ \sum\limits_{i \in I} {{X_{id(2)}}} \ge {R_{d(2)}}, \qquad \forall d \in D $$

(3.35)

$$ \sum\limits_{i \in I} {{X_{id(3)}}} \ge {R_{d(3)}}, \qquad \forall d \in D $$

(3.36)

$$ \sum\limits_{s \in S} {{X_{ids}}} = 1, \qquad \forall i \in I,d \in D $$

(3.37)

$$ \sum\limits_{i \in {I_s}} {{X_{ids}}} \ge 1, \qquad \forall d \in D,s = 1\ldots 3 $$

(3.38)

$$ {X_{id(4)}} + {X_{i(d + 1)(1)}} + {X_{i(d + 1)(2)}} + {X_{i(d + 1)(3)}} + {X_{i(d + 2)(4)}} \le 2, \quad \forall i \in I,\quad d = 1\ldots |D| - 2 $$

(3.39)

$$ \sum\limits_{d \in D} \sum\limits_{s \in S - \{ 4\} } {{X_{ids}}} \le 12, \qquad \forall i \in I $$

(3.40)

$$ \sum\limits_{d \in D} \sum\limits_{s \in S - \{ 4\} } {{X_{ids}}} \ge 10, \qquad \forall i \in I $$

(3.41)

$$ {X_{id4}} + {X_{i(d + 1)4}} + {X_{i(d + 2)4}} + {X_{i(d + 3)4}} + {X_{i(d + 4)4}} \ge 1, \qquad \forall i \in I,\quad d = 1\ldots |D| - 4 $$

(3.42)

$$ \sum\limits_{i \in I} {Y_{pi}} = 1, \qquad p \in P $$

(3.43)

$$ \sum\limits_{p \in P} {{Y_{pi}}} \le 1, \qquad i \in I $$

(3.44)

$$ \sum\limits_{i \in I} {Y_{pi}}(\sum_{l=0}^{l=3}{X_{i{(d_p+l)}(3)}} + \sum_{l=4}^{l=5}{X_{i({d_p} + l)(4)}}) = 6, \qquad p = 1 \ldots 9 $$

(3.45)

$$ \sum\limits_{i \in I} {Y_{pi}}({X_{i{d_p}3}} + {X_{i({d_p} + 1)3}}) = 2, \qquad p = 10,11 $$

(3.46)

$$ \sum\limits_{d \in D} {{X_{id4}} \ge 2} ,\qquad \forall i \in I $$

(3.47)

$$ \sum\limits_{d \in D} \sum\limits_{s \in S - \{ 4\} } {{X_{ids}}} + (d1_i^ + - d1_i^ - ) = 11,\qquad \forall i \in I $$

(3.48)

$$ {X_{i(6)(4)}} + {X_{(i)(7)(4)}} + {X_{i(13)(4)}} + {X_{i(14)(4)}} + (d2_i^ + - d2_i^ - ) = 1,\qquad \forall i \in I $$

(3.49)

$$ {X_{id(1)}} + {X_{i(d + 1)(2)}} + (d3_{id}^ + - d3_{id}^ - ) = 1,\qquad \forall i \in I,\quad d = 1\ldots |D| - 1 $$

(3.50)

$$ {X_{id(2)}} + {X_{i(d + 1)(1)}} + (d4_{id}^ + - d4_{id}^ - ) = 1, \qquad \forall i \in I,\quad d = 1\ldots |D| - 1 $$

(3.51)

$$ (\sum\limits_{i \in I} [{Y_{pi}} \times ({X_{i(7)(2)}} + {X_{i(7)(4)}})] + (d5_p^ + - d5_p^ - ) = 1, \quad p \in \{ 1,2,3\} $$

(3.52)

$$ (\sum\limits_{i \in I} {[{Y_{pi}} \times ({X_{i(11)(2)}} + X_{i(11)(4)}})]) + (d5_p^ + - d5_p^ - ) = 1, \qquad p \in \{ 4,5,6\} $$

(3.53)

Constraints (3.34–3.47) represent the hard constraints. Constraints (3.34, 3.35 and 3.36) ensure that the demand is fulfilled at all times, while, constraints (3.37) state that each nurse is working one shift a day at the most. In addition, constraints (3.38) assign at least one senior nurse for each shift. Furthermore, constraints (3.39) ensure not to give an isolated working day. Next, constraints (3.40) ensure that the maximum number of working days during the whole rostering period is 12 days. However, constraints (3.41) ensure that the minimum number of working days during the whole rostering period is not more than 10 days. Meanwhile constraints (3.42) ensure the maximum number of consecutive working days is 4 days. Then, (3.43, 3.44, 3.45 and 3.46) ensure that the patterns are covered exactly with one nurse for each. Constraints (3.47) state that each nurse is subject to having at least 2 days off during the roster period, which is 14 days.

Constraints (3.48–3.53) represent soft constraints. Constraints (3.48) are to give a fair number of working days and days off to all of the nurses, which is the average between the maximum and minimum working days. Constraints (3.49) ensure that each nurse has at least one day off in the weekend during the roster period. Constraints (3.50) and (3.51) attempt to give stable shifts, either consecutive morning or evening. Constraints (3.52) and (3.53) attempt to give either a day off or an evening shift after the days off that followed the night shift. The objective function in the problem concerns minimizing the total penalty that occurs due to the violations of soft constraints. In order to incorporate the soft constraints in the rostering model, our goals are: $d1_i^ - \,(d1_i^ + )$ is the amount of negative (positive) deviations from goal 1 (Minimizing the violation of (3.48)) for nurse i. Both positive and negative deviations are penalized. $d2_i^ - \,(d2_i^ + )$ is the amount of negative (positive) deviation from goal 2 (Minimizing the violation of (3.49)) for nurse i. Negative deviations are penalized. $d3_i^ - \,(d3_i^ + )$ is the amount of negative (positive) deviation from goal 3 (Minimizing the violation of (3.50)) for day d and nurse i. Negative deviations are penalized. $d4_i^{-} (d4_i^{+} )$ is the amount of negative (positive) deviation from goal 4 (Minimizing the violation of (3.51)) for day d and nurse i. Negative deviations are penalized. $d5_i^{-} (d5_i^{+} )$ is the amount of negative (positive) deviation from goal 5 (Minimizing the violation of (3.52) and (3.53)) for day d and nurse i. Positive deviations are penalized.

3.3.1.3.3 Solution Method

In order to solve NRP, a modified shift patterns approach was proposed, followed by a simulated annealing algorithm to generate a good quality roster. Generally, the approach was divided into three main stages: (1) Initialize the problem by reducing search space and generating valid shifts sequence patterns; (2) Construct feasible or near feasible initial solution; and (3) Optimize the initial solution that was constructed in the previous two stages to get the optimal or near optimal solution. It can be shown that the proposed approach is capable of accommodating all the hard and soft constraints experienced by the rostering system at UKMMC.

3.3.1.4 Constraint-Based and Heuristic-Oriented Nurse Scheduling Problems

Many researchers have used mathematical programming to find optimal solutions for nurse scheduling problems. However, due to the large size it is extremely difficult to solve the problems optimally when many hard and soft constraints are involved. To tackle this challenge, some researchers have restricted the problem dimensions and developed simplified models. However, this leads to solutions that are not applicable to real hospitals. Therefore other researchers attempt to focus on heuristic approaches that provide good feasible solutions in a reasonable amount of time for NSP (Bai et al. 2010; Burke et al. 2010; He and Qu 2009; Sundaramoorthi et al. 2009).

We describe a hybrid model of integer programming and variable neighborhood search (VNS) for highly constrained nurse scheduling problems developed by Burke et al. (2010). They partitioned the constraint sets in such a way that those with lower complexity and higher importance have more priority to be included in the subproblem solved using IP.

3.3.1.4.1 Decision Variables

The parameters for this problem are defined as: i denotes the set of nurses available; j denotes the set of indices of the last day of each week within the scheduling period; and k presents the set of shift types 1(early), 2(day), 3(late), 4(night). ${I_t}|t \in \{ 1,2,3\}$ denotes the subset of nurses that work 20, 32, 36 hours per week respectively; $k^{\prime}$ presents the set of undesirable shift type succession $\{(2,1),(3,1),(3,2),(1,4)\}; \,{d_{jk}}$ is the coverage requirement of shift type k on day $j \in \{ 1,\ldots ,7|J|\} ; \,{m_i}$ is the maximum number of working days for nurse i; ${n_1}$ and ${n_2}$ are the maximum number of consecutive night shifts and working days, respectively; ${c_k}$ is the desirable upper bound of consecutive assignments of shift type k; ${g_t}$ and ${h_t}$ are upper and lower bounds of weekly working days for the $t^{th}$ subset of nurses.

The decision variables are presented as: ${x_{ijk}}$ is 1 if nurse i is assigned to shift type k in day j, and 0 otherwise.

3.3.1.4.2 Optimization Model

$$ Min G(x) = [{g_1}(x),{g_2}(x),{g_3}(x),{g_4}(x),{g_5}(x),{g_6}(x),{g_7}(x),{g_8}(x)], $$

(3.54)

Subject to:

$$ \sum\limits_{i \in I} {{x_{ijk}} = {d_{jk}}}, \qquad \forall {j \in \{ 1,\ldots ,7|J|\}, k \in {\fancyscript{K}}} $$

(3.55)

$$ \sum\limits_{k \in K} {{x_{ijk}}} \le 1, \qquad \forall{ i \in I,j \in \{ 1,\ldots ,7|J|\}} $$

(3.56)

$$ \sum\limits_{j = 1}^{7|J|} {\sum\limits_{k \in K} {{x_{ijk}}} \le {m_i}}, \qquad \forall i \in I $$

(3.57)

$$ \sum\limits_{j \in J} {\sum\limits_{k \in K} {{x_{ijk}}} \le 3,} \qquad \forall i \in I $$

(3.58)

$$ \sum\limits_{j = 1}^{7|J|} {{x_{ij4}}} \le 3, \qquad \forall i \in I $$

(3.59)

$$ {x_{i(j - 1)4}} - {x_{ij4}} + {x_{i(j + 1)4}} \ge 0 \qquad \forall i \in I,\;j \in \{ 2,\ldots ,7|J| - 1\} $$

(3.60)

$$ {x_{i(j - 1)4}} - \sum\limits_{k = 1}^3 {{x_{ijk}}} + \sum\limits_{k = 1}^3 {{x_{i(j + 1)k}}} \le 1, \qquad \forall i \in I,\;j \in \{ 2,\ldots ,7|J| - 1\} $$

(3.61)

$$ {x_{i(j - 1)4}} + \sum\limits_{k = 1}^3 {{x_{ijk}}} - \sum\limits_{k = 1}^3 {{x_{i(j + 1)k}}} \le 1, \qquad \forall i \in I,\;j \in \{ 2,\ldots ,7|J| - 1\} $$

(3.62)

$$ {x_{i(j - 1)4}} + \sum\limits_{k = 1}^3 {{x_{ijk}}} + \sum\limits_{k = 1}^3 {{x_{i(j + 1)k}}} \le 2, \qquad \forall i \in I,\;j \in \{ 2,\ldots ,7|J| - 1\} $$

(3.63)

$$ \sum\limits_{j = r}^{r + {n_1}} {{x_{ij4}}} \le {n_1}, \qquad \forall i \in I,\;r \in \{ 1,\ldots ,7|J| - {n_1}\} $$

(3.64)

$$ \sum\limits_{j = r}^{r + {n_2}} {\sum\limits_{k \in K} {{x_{ijk}}} } \le {n_2}, \qquad \forall i \in I,\;r \in \{ 1,\ldots ,7|J| - {n_2}\} $$

(3.65)

$$ {x_{16(j)3}} = 0, \qquad \forall j \in \{ 1,\ldots ,7|J|\} $$

(3.66)

$$ \sum\limits_{k \in K} [{x_{i(j - 1)k}} - {x_{ijk}}] + s_{ij}^1 - s_{ij}^2 = 0, \qquad \forall i \in I,\;j \in J $$

(3.67)

$$ \sum\limits_{k \in K} [{x_{i(j - 1)k}} - {x_{ijk}} + {x_{i(j + 1)k}}] + s_{ij}^3 \ge 0, \qquad \forall i \in I,\;j \in \{ 2,\ldots ,7|J| - 1\} $$

(3.68)

$$ \sum\limits_{k \in K} [{x_{i(j - 1)k}} - {x_{ijk}} + {x_{i(j + 1)k}}] - s_{ij}^4 \le 1, \qquad \forall i \in I,\;j \in \{ 2,\ldots ,7|J| - 1\} $$

(3.69)

$$ \sum\limits_{j = r}^{r + 3} {{x_{ijk}}} - s_{irk}^5 \le {c_k}, \qquad \forall i \in I,\;r \in \{ 1,\ldots ,7|J| - 3\} ,\;k \in \{ 1,3\} $$

(3.70)

$$ {x_{i(j - 1)k}} - {x_{ijk}} + {x_{i(j + 1)k}} + s_{ijk}^6 \ge 0,\qquad \forall i \in I,\;j \in \{ 2,\ldots ,7|J| - 1\} ,\;k \in \{ 1,3\} $$

(3.71)

$$ \sum\limits_{j = 7w - 6}^{7w} {\sum\limits_{k \in K} {{x_{ijk}} - s_{tiw}^7} \le {g_t}}, \qquad \forall t \in \{ 1,2,3\} ,\;i \in {I_t},\;w \in \{ 1,\ldots ,|J|\} $$

(3.72)

$$ \sum\limits_{j = 7w - 6}^{7w} {\sum\limits_{k \in K} {{x_{ijk}}} + s_{tiw}^8} \ge {h_t}, \qquad \forall t \in \{ 1,2,3\} ,\;i \in {I_t},\;w \in \{ 1,\ldots ,|J|\} $$

(3.73)

$$ \sum\limits_{j = r}^{r + 3} {\sum\limits_{k \in K} {{x_{ijk}}} } - s_{ir}^9 \le 3, \qquad \forall i \in {I_1},\;r \in \{ 1,\ldots ,7|J| - 3\} $$

(3.74)

$$ {x_{ij{k_1}}} + {x_{i(j + 1){k_2}}} - s_{ijk^{\prime}}^{10} \le 2, \qquad \forall i \in I,\;j \in \{ 1,\ldots ,7|J| - 1\} ,\;k^{\prime} = ({k_1},{k_2}) \in K^{\prime} $$

(3.75)

Where

$$ {g_1}(x) = \sum\limits_{i \in I} {\sum\limits_{j \in J} {(s_{ij}^1 + s_{ij}^2)} ,} $$

(3.76)

$$ {g_2}(x) = \sum\limits_{i \in I} {\sum\limits_{j = 2}^{7|J| - 1} {s_{ij}^3,} } $$

(3.77)

$$ {g_3}(x) = \sum\limits_{i \in I} {\sum\limits_{j = 2}^{7|J| - 1} {s_{ij}^4} ,} $$

(3.78)

$$ {g_4}(x) = \sum\limits_{i \in I} {\sum\limits_{r = 1}^{7|J| - 3} {\sum\limits_{k \in \{ 1,3\} } {s_{ijk}^5} ,} } $$

(3.79)

$$ {g_5}(x) = \sum\limits_{i \in I} {\sum\limits_{j = 2}^{7|J| - 1} {\sum\limits_{k^{\prime} \in \{ 1,3\} } {s_{ijk^{\prime}}^6} ,} } $$

(3.80)

$$ {g_6}(x) = \sum\limits_{t = 1}^3 {\sum\limits_{i \in {I_t}} {\sum\limits_{w = 1}^{|J|} {(s_{tiw}^7 + s_{tiw}^8} ),} } $$

(3.81)

$$ {g_7}(x) = \sum\limits_{i \in {I_1}} {\sum\limits_{r = 1}^{7|J| - 3} {s_{ir}^9,} } $$

(3.82)

$$ {g_8}(x) = \sum\limits_{i \in I} {\sum\limits_{j = 1}^{7|J| - 1} {\sum\limits_{k^{\prime} \in K^{\prime}} {s_{ijk^{\prime}}^{10}} } .} $$

(3.83)

The problem has hard and soft constraints. Constraints (3.55–3.66) are hard constraints. Constraints (3.55) correspond to the daily requirement of each shift type. Constraints (3.56) restrict a nurse to at most one shift assignment for each day. Constraints (3.57), (3.58), and (3.59) are related to the maximum number of total working days, on-duty weekends, and night shifts during the scheduling period, respectively. Constraints (3.60) guarantee no standalone night shift. Three sub-constraints (3.61–3.63) state a minimum of two free days after a series of night shifts. Constraints (3.64) and (3.65) correspond to the maximum number of consecutive night shifts and working days, respectively. Constraints (3.66) ensure there are no late shifts for one particular nurse.

The problem has the following additional soft constraints and the objective is to satisfy them as much as possible. Constraints (3.67) ensure nurses work either no shifts or two shifts in weekends. Constraints (3.68) guarantee that there is no stand-alone shift (i.e., a single day between 2 days off). Constraints (3.69) are related to the minimum number of free days after a series of shifts. Constraints (3.70) and (3.72) correspond to the maximum/minimum number of consecutive assignments of shifts, weekly working days respectively. Constriants (3.74) restrict the number of consecutive working days for part-time nurses to its maximum number, and finally constraints (3.75) rule out certain shift-type successions.

3.3.1.4.3 Solution Method

The advantages of both the IP and the VNS for global optimization are combined. First, IP is used to solve the subproblem including the full set of hard constraints and a subset of soft constraints. Then, a VNS with the neighborhood of swapping blocks of shifts is used to make the improvement on the IP’s resulting solution, mainly from the aspects of satisfying the excluded constraints from the preceding IP model. It is claimed that the proposed hybrid model was able to handle all the requirements and constraints of nurse rostering in complex hospital environments.

3.3.2 Nurse Scheduling Problem in an Operating Suite

Cardoen et al. (2010) have provided a comprehensive overview of recent operational research method developments on operating room planning and scheduling. They evaluated multiple domains related to problem settings, performance measures, solution methods, and uncertainty considerations. Established upon the survey, many researchers have ventured either to develop patient-room scheduling models or to propose improvement methods associated with performance measures. Many researchers have tried to optimally utilize surgery scheduling to find the best surgery-room assignments, surgery-physician assignments, and surgery-block time assignments (Cardoen 2010; Dexter et al. 1999, 2010a, b; Fei et al. 2009; Feia et al. 2008; Lamiri et al. 2008; Ozkarahan 2000).

Most of the literature in operating room scheduling focuses on either providing the optimal allocation of surgeries to operating rooms, surgeries to available time intervals, and surgeries to physicians or to find the best possible surgery sequencing with minimum costs and variabilities. However, there is little literature in operating room scheduling that considers the effect of nurse assignments to surgeries and their vital influence on surgery performance.

3.3.2.1 Integrated Operating Room Scheduling

Belien and Demeulemeester (2008) have developed an integrated nurse and surgery scheduling problem using IP. A schematic overview of the general idea is presented in Fig. 3.2.

Fig. 3.2

Schematic overview of the general idea

The input for the nurse scheduling process consists of the restrictions implied on the individual nurse roster lines on the one hand and the workload distribution over time on the other hand. Individual roster line was developed that can be viewed as a sequence of days on and days off, where each day on contains a single shift identified by a label such as day, evening, or night. A set covering model was developed for this problem. The workload distribution itself is determined by the master surgery schedule introduced as workload model. In order to be able to deduce the workload from the surgery schedule one also has to know the workload contributions of each specific type of surgery. Finally an integrated nurse scheduling model was presented to satisfy nurse preferences as well as surgery block assignments. They showed how the column generation technique approach can easily cope with their model extension. They showed that by means of a large number of computational experiments an idea of the cost saving opportunities and required solution times was provided.

3.3.2.1.1 Initial Optimization Model

This nurse scheduling problem consists of generating a configuration of individual schedules over a given time horizon. The configuration of nurse schedules is generated so as to fulfill collective agreement requirements and the hospital staffing demand coverage while minimizing the salary cost.

3.3.2.1.2 Decision Variables

If j is the set of feasible roster lines j, and i is the set of demand periods i; $d_i \in R^+ \forall i \in I$ denotes the required number of nurses scheduled during period i. Also $a_{ij}$ is 1 if roster line j contains an active shift during period i and 0 otherwise.

The integer decision variable $x_j \forall j \in J$ indicates the number of individual nurses that are scheduled by roster line j.

3.3.2.1.3 Optimization Model

The nurse scheduling problem (NSP) can now be stated as follows:

$$ \hbox{Minimize} \sum_{j \in J}{x_j} $$

(3.84)

$$ \sum_{j \in J}{a_{ij}x_j} \ge d_i, $$

(3.85)

$$ x_j \in \{0, 1, 2, \cdots \} \qquad\forall j \in J . $$

(3.86)

Coverage constraints imply how many nurses of appropriate skills have to be scheduled for each demand period.

3.3.2.1.4 Workload Optimization Model

In the NSP, the right-hand side values of the coverage constraints were considered to be fixed. However, instead of assuming the demand values to be fixed, a general NSP was developed considering that demand values should be dependent on the number and type of patients undergoing surgery in the hospital at each moment. By manipulating the master surgery schedule hospital management can create a number of different workload distributions, further referred to as workload patterns.

3.3.2.1.5 Decision Variables

k denotes the set of possible workload patterns that could be generated by modifying the surgery schedule. These were obtained by enumerating all possible ways of assigning operating blocks to the different surgeons, subject to surgery demand and to capacity restrictions. Each workload pattern k is described by a number of periodic demands $d_{ik} \in \{0, 1, 2, \cdots \} \forall i \in I.$

Decision variable $z_k$ was defined as 1 if the surgery schedule that corresponds to workload k was chosen, and 0 otherwise.

3.3.2.1.6 Optimization Model

The problem was stated as follows:

$$ \hbox{Minimize} \sum_{j \in J}{x_j} $$

(3.87)

$$ \sum_{j \in J}{a_{ij}x_j} \ge \sum{k \in K}{d_{ik}z_k}, $$

(3.88)

$$ \sum_{k \in K}{z_k}=1, $$

(3.89)

$$ x_j \in \{0, 1, 2, \cdots \} \qquad\forall j \in J, $$

(3.90)

$$ z_k \in \{0,1\} \qquad\forall k \in K . $$

(3.91)

Coverage constraints imply how many nurses of appropriate skills have to be scheduled for each demand period and which workload patterns should be assigned to them.

3.3.2.1.7 Final Optimization Model

A new workload pattern can be obtained by building a new surgery schedule. In the application, a new surgery schedule was built by solving an integer program. To find a new workload pattern with minimal reduced cost given the current set of roster lines and workload patterns, the objective function minimizes the dual price vector of the demand constraints (3.88) multiplied by the new demands. Two types of constraints should be considered. Surgery demand constraints determine how many blocks must be preserved for each surgeon. Capacity constraints ensure that the number of blocks assigned during each period do not exceed the available capacity.

3.3.2.1.8 Decision Variables

$y_{rt} \,(\forall r \in R$ and $t \in T)$ is the number of blocks assigned to surgeon r in period t where t represents the set of active periods and r the set of surgeons. It is assumed that $q_r$ was the number of blocks required by each surgeon r, and $b_t$ is the maximal number of blocks available in period t. $w_{rti} \in R^+$ denotes the contribution to the workload of demand period i of assigning one block to surgeon r in period t.

3.3.2.1.9 Optimization Model

The integer program to construct a new surgery schedule (and at the same time price out a new workload pattern k) is developed as follows:

$$ \hbox{Minimize} \sum_{i \in I}{\pi_{i}d_{ik}} $$

(3.92)

$$ \sum_{t \in T}{y_{rt}} = q_r, $$

(3.93)

$$ \sum_{r \in R}{y_{rt}} \le b_t, $$

(3.94)

$$ \sum_{r \in R}{\sum_{t \in T}{w_{rti}y_{rt}}} \le d_{ik}, $$

(3.95)

$$ y_{rt} \in \{0, 1, 2, \cdots, \hbox{min}{q_r,b_r} \} \quad\forall r \in R, \quad \forall t \in T, $$

(3.96)

$$ d_{ik} \in \{0, 1, 2, \cdots \} \qquad\forall i \in I. $$

(3.97)

The first set of constraints implies that each surgeon obtains the number of required blocks. Also, it is essential to ensure that the number of blocks assigned does not exceed the available number of blocks in each period. Finally, $d_{ik}$ values are assigned to the appropriate integer values.

3.3.2.1.10 Solution Method

The column generation method is utilized to solve the model. The column generation technique can easily cope with their model extension. The approach involves the solution of two types of pricing problems, the first one is solved with a standard dynamic programming approach using recursion, the second one by means of a state-of-the-art mixed integer programming optimizer. A constraint branching scheme is proposed to drive the solution into integrality with respect to the workload patterns while the integrality of the roster lines is left out of the scope of the paper. They also calculate, through a large number of computational experiments, cost savings and required solution times.

The schematic overview of the branch-and-price to solve the models is presented in Fig. 3.3.

Fig. 3.3

Schematic overview of the GNSP branch-and-price algorithm

The results show that, first of all, column generation is a good technique to deal with the extra problem dimension of modifying surgery schedules. Second, the results from the integrated approach can be used to quantify the shares of the two sources of waste: waste due to the workforce surplus per shift and waste due to the inflexibility of roster lines. Third, unlike the NSP, the GNSP turns out to become harder to solve when the collective agreement requirements are more strict. They indicated that considerable savings could be achieved by using this approach to build nurse and surgery schedules.

3.3.2.2 Nurse Scheduling in an Operating Suite Problem

Mobasher and Lim (2011) focus on the nurse scheduling problem in an operating suite by developing nurse scheduling optimization models for an actual operating suite in Texas, USA. A multi-objective integer programming nurse scheduling model in an operating suite is introduced that considers different aspects of the scheduling problem such as demand satisfaction, idle time and over times and job changes. The model called “Nurse Assignment Model”, assigns nurses to different surgery cases based on their specialties and competency levels. Different heuristics are applied to develop solution methods for the multi-objective nurse assignment model. Real data are gathered from a cancer center in Texas and used to show the efficiency of the optimization models and solution methods.

The objective is to determine which nurses should be assigned to each surgery case. It is essential to provide schedules with minimum overtime, non-consecutivity, and changes during surgery procedures as well as maximum demand satisfaction.

3.3.2.2.1 Decison variables

Several input parameters were used for this modeling. These parameters can provide enough information about each nurse and surgery case.

• $P_{is}^1$ = 1, if If nurse $i\in {\fancyscript{I}}$ is working in shift $s \in {\fancyscript{S}};$ 0, otherwise.

• $P_{ikqp}^2$ = 1, if nurse $i\in {\fancyscript{I}}$ can do role $k \in {\fancyscript{K}}$ in specialty $q \in {\fancyscript{Q}}$ with competency level $p \in {\fancyscript{P}};$ 0, otherwise.

• $P_{it}^3$= 1, if nurse $i\in {\fancyscript{I}}$ has job level $t \in {\fancyscript{T}};$ 0, otherwise.

• $P_{cj}^4$= 1, if case $c\in {\fancyscript{C}}$ is scheduled to happen in OR $j \in {\fancyscript{J}};$ 0, otherwise.

• $P_{cqph}^5$= 1, if case $c\in {\fancyscript{C}}$ needs specialty $q \in {\fancyscript{Q}}$ with procedure complexity $p \in {\fancyscript{P}}$ in time interval $h \in {\fancyscript{H}};$ 0, otherwise.

• $P_{ckh}^6$= Required number of nurses for case $c \in {\fancyscript{C}},$ who can do role $k \in {\fancyscript{K}}$ in time interval $h\in {\fancyscript{H}}.$

• $P_{ch}^7$= 1, if case $c\in {\fancyscript{C}}$ is in progress during time interval $h\in {\fancyscript{H}};$ 0, otherwise.

• $P_c^8$= Case $c \in {\fancyscript{C}}$ duration (lenght of surgery).

• $P_{sh}^9$= 1, if shift $s\in {\fancyscript{S}}$ contains time interval $h\in {\fancyscript{H}}$ as regular working hours; 0, otherwise.

• $P_{sh}^{10}$= 1, if shift $s\in {\fancyscript{S}}$ contains time interval $h\in {\fancyscript{H}}$ as authorized overtime hours; 0, otherwise.

Decision variables were defined as $y_{ickh} \hbox{ is } 1, \hbox{if nurse } i \in {\fancyscript{I}} \hbox{ works on case } c \in {\fancyscript{C}} \hbox{ at time } h \in {\fancyscript{H}} \hbox{ doing role } k \in {\fancyscript{K}}, \hbox{ and } 0, \hbox{otherwise}.$

3.3.2.2.2 Optimization Model

3.3.2.3 Constraints

The constraints introduced for this integer programming model are as follows.

$$ \sum_{c \in {\fancyscript{C}}}{\sum\limits_{k \in {\fancyscript{K}}}{y_{ickh}}} \le 1, \qquad i \in {\fancyscript{I}}, h \in {\fancyscript{H}} , $$

(3.98)

$$ y_{ickh} \le \sum\limits_{s \in S} {\left(P_{is}^1 \times (P_{sh}^9 + P_{sh}^{10})\right)}, \qquad i \in {\fancyscript{I}}, c \in {\fancyscript{C}}, k \in {\fancyscript{K}}, h \in {\fancyscript{H}} , $$

(3.99)

$$ \sum_{c \in {\fancyscript{C}}}{\sum_{k \in {\fancyscript{K}}}{\sum\limits_{h \in {{\fancyscript{H}}}}{y_{ickh}}}} \le \sum_{s \in {\fancyscript{S}}}{\sum\limits_{h \in {{\fancyscript{H}}}} {\left(P_{is}^1 \times (P_{sh}^9 + P_{sh}^{10})\right)}}, \qquad i \in {\fancyscript{I}}, $$

(3.100)

$$ y_{ickh} \le P_{ch}^7 \times \left(\sum_{q \in {\fancyscript{Q}} ,}{\sum\limits_{ p \in {\fancyscript{P}}} {{P_{cqph}^5 \times P_{ikqp}^2}}}\right), \qquad i \in {\fancyscript{I}}, c \in {\fancyscript{C}}, k \in {\fancyscript{K}}, h \in {\fancyscript{H}} , $$

(3.101)

$$ \sum\limits_{i \in {\fancyscript{I}}}{y_{ickh}} \ge P_{ch}^7, \qquad c \in {\fancyscript{C}}, k \in {\fancyscript{K}}, h \in {\fancyscript{H}}, $$

(3.102)

$$ \sum\limits_{h \in {{\fancyscript{H}}}}{y_{ickh}} \le M \times d_{ick}^2, \qquad \forall{i \in {\fancyscript{I}}, c \in {\fancyscript{C}}, k \in {\fancyscript{K}}}, $$

(3.103)

$$ \sum\limits_{k \in {\fancyscript{K}}}{d_{ick}^2} \le 1, \qquad \forall{i \in {\fancyscript{I}}, c \in {\fancyscript{C}}}, $$

(3.104)

$$ \sum_{i \in {\fancyscript{I}}}{\sum_{c \in {\fancyscript{C}}}{\sum_{ k \in {\fancyscript{K}}}{\sum_{h \in {{\fancyscript{H}}}}{{\sum\limits_{t = 1} {y_{ickh} \times P_{it}^3}}}}}} \ge \alpha (\sum_{i \in {\fancyscript{I}}}{\sum_{c \in {\fancyscript{C}}}{\sum_{ k \in {\fancyscript{K}}}{\sum_{h \in {{\fancyscript{H}}}}{{\sum\limits_{t \in {\fancyscript{T}}} {y_{ickh} \times P_{it}^3}}}}}} ) , $$

(3.105)

$$ \sum_{i \in {\fancyscript{I}}}{\sum_{c \in {\fancyscript{C}}}{\sum_{ k \in {\fancyscript{K}}}{\sum_{h \in {{\fancyscript{H}}}}{{\sum\limits_{t = 2} {y_{ickh} \times P_{it}^3}}}}}} \le (1-\alpha) (\sum_{i \in {\fancyscript{I}}}{\sum_{c \in {\fancyscript{C}}}{\sum_{ k \in {\fancyscript{K}}}{\sum_{h \in {{\fancyscript{H}}}}{{\sum\limits_{t \in {\fancyscript{T}}} {y_{ickh} \times P_{it}^3}}}}}} ) , $$

(3.106)

$$ \sum\limits_{i \in {\fancyscript{I}}}{y_{ickh}} + {{de_{ckh}}} \ge P_{ckh}^6 \times P_{ch}^7, \qquad \forall{c \in {\fancyscript{C}}, k \in {\fancyscript{K}}, h \in {{\fancyscript{H}}}} $$

(3.107)

$$ {DEM} \ge \sum\limits_{h \in {{\fancyscript{H}}}}{de_{ckh}}, \qquad \forall{c \in {\fancyscript{C}}, k \in {\fancyscript{K}}} $$

(3.108)

$$ \sum\limits_{k \in {\fancyscript{K}}, c \in {\fancyscript{C}}, h \in {{\fancyscript{H}}}} {y_{ickh}} \times P_{cj}^4 \le M\cdot X_{ij} \qquad \forall{i \in {\fancyscript{I}}, j \in {\fancyscript{J}}} $$

(3.109)

$$ \sum\limits_{j \in {\fancyscript{J}}}{X_{ij}} \le {XX},\qquad \forall{i \in {\fancyscript{I}}} $$

(3.110)

$$ \sum_{s \in {\fancyscript{S}}}{P_{is}^1 \cdot P_{sh}^{10}} \times (\sum\limits_{c \in {\fancyscript{C}} , k \in {\fancyscript{K}}}{y_{ickh}} + \sum_{s \in {\fancyscript{S}}}{P_{is}^1 \times P_{sh}^{10}} - {d_{ih}^4}) \le \sum_{s \in {\fancyscript{S}}}{P_{is}^1 \cdot P_{sh}^{10}}, \qquad \forall{i \in {\fancyscript{I}}, h \in {{\fancyscript{H}}}} $$

(3.111)

$$ P_{is}^1 \times (P_{s(h+1)}^{9}+P_{s(h+1)}^{10}) \times |\mathop{\sum\limits_{c \in {\fancyscript{C}}}\limits}_{k \in {\fancyscript{K}}}{y_{ick(h+1)}} \times -\mathop{\sum\limits_{c \in {\fancyscript{C}}}\limits}_{k \in {\fancyscript{K}}}{y_{ickh}}| \le {d_{ih}^7}, \qquad \forall{i \in {\fancyscript{I}}, h \in {{\fancyscript{H}}}} $$

(3.112)

$$ DMs \ge \sum\limits_{h \in {{\fancyscript{H}}}}{d_{ih}^7}, \qquad \forall{i \in {\fancyscript{I}}} $$

(3.113)

$$ DMf \ge \sum\limits_{h \in {{\fancyscript{H}}}}{d_{ih}^4}, \qquad \forall{i \in {\fancyscript{I}}} $$

(3.114)

$$ \sum\limits_{k \in {\fancyscript{K}}, h \in {{\fancyscript{H}}}}{y_{ickh}}-\sum\limits_{h \in {{\fancyscript{H}}}}{P_{ch}^7}+cd_{ic}+M \cdot (1-nc_{ic}) \ge 0, \qquad \forall{i \in {\fancyscript{I}}, c \in {\fancyscript{C}}} $$

(3.115)

$$ \sum\limits_{k \in {\fancyscript{K}}, h \in {{\fancyscript{H}}}}{y_{ickh}}\le M \cdot nc_{ic}, \qquad \forall{i \in {\fancyscript{I}}, c \in {\fancyscript{C}}} $$

(3.116)

$$ \sum\limits_{c \in {\fancyscript{C}}}{nc_{ic}} \le {nct}, \qquad \forall{i \in {\fancyscript{I}}} $$

(3.117)

$$ \sum\limits_{c \in {\fancyscript{C}}}{cd_{ic}} \le {cdt}. \qquad \forall{i \in {\fancyscript{I}}} $$

(3.118)

The constraints were divided into two sets: hard and soft constraints. Shift limitations, nurse skill level, staffing ratio, and case requirements belong to hard constraints, to name a few. Although some nurses have sufficient skill levels to work on different roles, they cannot be assigned to do different jobs at the same time. Therefore, each nurse should be assigned to one case doing one specific role in each time interval. This constraint is shown in (3.98). Constraints (3.99) and (3.100) make sure that nurses will be assigned to the cases that are in progress during their shift hours. Also, the total working hours of a nurse in each day should be less than her total regular and overtime working hours. Each nurse is allowed to work at most 4 hours overtime and 8 or 10 hours regular time.

Constraints (3.101) and (3.102) show that a nurse can be assigned to a case if she has sufficient skills to handle the case specialty requirements. In addition, the nurse should have sufficient competency to deal with case procedure complexities. Also, a nurse should be assigned to the surgery case at time interval h if the case is in progress at that time interval.

Besides, at any time, the total ratio of RN/Scrub techs assignments should be $\alpha/(1-\alpha)$ during the day based on the current hiring plans of most hospitals. Different ratios can be used for different hospitals. This limitation is demonstrated by constraints (3.105) and (3.106).

Finally, it is not acceptable to assign nurses to do different jobs in one specific surgery. For this purpose, a binary decision variable $d_{ick}^2$ is introduced which takes value 1 when a nurse i is assigned to case c to do job k. This decision variable is demonstrated in constraint (3.103). Constraints (3.104) make sure that the maximum number of times that a nurse will be assigned to perform on different roles during a surgery duration is at most one.

Soft Constraints can be violated to some extent. Each deviation in a soft constraint is defined as a decision variable. Surgery demand for each case at each time interval should be satisfied. Therefore, if the case is in progress during time interval h, the required number of nurses for each role should be assigned to the case unless we do not have enough nurses to satisfy all demand at the time. To handle this shortage, we define two integer deviation variables called $de_{ckh}$ and DEM, which are the missing number of nurses that should have been assigned to the surgery case if there were enough nurses available for case c to do role k at time interval h and maximum demand shortages for each case c, respectively. By minimizing DEM, we ensure that surgery demand for each case will be satisfied to the greatest extent. The constraints related to the $de_{ckh}$ and DEM deviations are shown in equations (3.107) and (3.108).

It is preferred to assign nurses to work continuously during their shift hours and perform on the same role for the whole surgery duration rather than moving around between different cases to do different jobs. To minimize these movements, we introduce a binary deviation variable $d_{ih}^7$ and an integer deviation variable DMs in constraints (3.112) and (3.113). By minimizing DMs, we ensure that the maximum number of times that nurses will work non-consecutively will be reduced and nurses will work sequentially as much as possible without too many idle assignments until nurse shift working hours are finished.

Constraints (3.109) and (3.110) demonstrate the preference for assigning nurses to work continuously on one operating room for their working day rather than moving around between different rooms. To minimize these movements, we introduce two binary deviation variables $X_{ij}$ and XX. By minimizing XX, we ensure that the maximum number of ORs that a nurse will be assigned to work on is reduced as much as possible.

We prefer to not have schedules with nurses who are assigned to overtime hours. To minimize these assignments, we define a binary deviation variable called $d_{ih}^4$ and an integer deviation variable called DMf. The $d_{ih}^4$ will obtain value 1 if a nurse is assigned to overtime hours. Constraints (3.111) show the overtime deviations. By minimizing DMf shown in constraint (3.114), we ensure that the maximum number of times that a nurse is assigned to overtime hours is reduced and the nurses will not be assigned to overtime hours unless it is a necessity.

Constraints (3.115), (3.116), (3.117), and (3.118), with deviations $nc_{ic}, \,cd_{ic},$ nct, and cdt, make sure that if a nurse is assigned to a surgery case, she will stay for the whole surgery duration, unless there is need for that nurse due to nurse shortages. Also, by minimizing the max number of cases that a nurse can work on, we will make sure that nurses will not move between different cases continuously.

3.3.2.3.1 Objective Function

Considering all the deviations explained previously, a multi-objective function is developed for NAM to minimize these deviations.

$$ \hbox{Min} \,DEM, \; \hbox{Min} \,DMf, \; \hbox{Min} \,DMs, \; \hbox{Min} \,XX, \; \hbox{Min} \,nct, \; \hbox{Min} \,cdt $$

(3.119)

This objective function ensures that the maximum deviations for each goal (worst case results) will be minimized for all nurses and all surgery cases

3.3.2.3.2 Solution Method

Since the Nurse Assignment Model introduced in this paper has multiple objectives, a Solution Pool Method (SPM) is presented. This solution method utilizes the idea of solution pools to generate alternate feasible solutions for each deviation in the objective function (3.119). Obtaining information about alternate good feasible solutions can be a useful tool in cases where a mixed integer multiobjective problem is developed. Although it may be computationally complicated to solve a multi-objective model considering all deviations simultaneously, it may be easier to use the solution pool feature in order to find alternate good feasible solutions for each deviation. The solution pool feature generates and stores multiple solutions to the mixed integer programming (MIP) model for each deviation and then chooses the solution among these optimal solutions that have the smallest deviations. The solution pool-based method has three steps. In the first step, a single objective optimization model is developed for each deviation containing all hard constraints and soft constraints related to the current deviation. In the second step, the solution pool approach is applied to generate alternate good feasible solutions (with the absolute gap of less than 0.01) for each single objective model developed in Step 1. For each generated solution, a cumulative weighted index is obtained. It is assumed that a predetermined importance weight for each deviation was in hand. The decision maker can provide the appropriate weights associated with each goal based on operating suite regulations and policies. Finally, in Step 3, the comparison indexes can be compared and the best solution introduced for NAM. Numerical results indicated that this model can provide more efficient and reliable nurse schedules for operating suites.

3.4 Summary

The growing shortage of nurses continues to hamper the effective delivery of health care. Not having enough skilled nurses in clinical settings can cause a significant negative impact on nurse retention rates, patient safety, and healthcare quality. Due to the nurse shortages, hospital managers are in dire need to optimally utilize and retain current available nurses without jeopardizing their job satisfaction.

Assigning each available nurse to the right place at the right time to do the right job is a major concern for healthcare organizations. As the types of services and treatments offered by such organizations increase so do the skill requirements of their staff. In this chapter different nurse scheduling problems were introduced and optimization models and solution approaches that have been introduced in the literature have been demonstrated. These models and solution methods further assuage our ability to generate efficient daily schedules, the main objective of this chapter.

3.5 Future Directions

Although there is a vast amount of literature in NSP, not many of the optimization models have addressed the impact of patient workload in nurse scheduling problems.

Healthcare organizations nowadays are dealing with many uncertainties such as nurse shortages, call-ins, cancellations, and workload uncertainty. Therefore, it is essential for researchers to consider these uncertainties in their models and develop more simple, easy to understand solution methods that can tackle variabilities with more time efficient approaches.