Introduction
The policy background of the new round of medical and health system reform has prompted hospitals to urgently establish a modern management system, which covers all aspects of hospital management such as human resources, quality, safety, and financial accounting. The ultimate goal is to improve the efficiency and effectiveness of employment, thus promoting lower operating costs and higher revenue for hospital management. Labor costs are the main component of hospital operation cost. How to reduce labor costs and achieve high efficiency, low consumption, and sustainable development is an issue worthy of deep consideration by hospital managers. Nurse resources as an important part of hospital human resources, how to reasonably utilize nurse resources has been the focus of decision-makers. In Sichuan Province, for example, the total number of registered nurses was 228,548 by the end of 2017, with 2.8 nurses per 1000 population, a large distance from what is required in the implementation plan of the National Nursing Career Development Plan (2016–2020). Therefore, under the current situation of a total nurse shortage, how to scientifically and rationally scheduling the existing nurse resources has become a pressing problem for the government and nursing managers to solve.
When there is a shortage of nurses, there are two main methods of rescheduling that are most generally used by hospitals today. The first is to reschedule existing nurses, but this rescheduling method can lead to inequities such as overtime, which in turn can have adverse reactions such as affecting the mood of nurses. The second type is rescheduling between different departments. However, this scheduling method also has certain disadvantages. First, such rescheduling requires the presence of vacant nurses, which is usually unpredictable. Second, when there are no vacant nurses, hospitals choose to keep patients waiting. This can lead to patient dissatisfaction, which in turn can affect the hospital’s reputation. Therefore, to avoid the above-mentioned adverse effects, we examine the actual situation using the following types of rescheduling methods in this paper after the hospital survey visit: (i) rescheduling between different departments in the same hospital; (ii) rescheduling between the same departments in different hospitals; (iii) rescheduling between different departments in different hospitals; (iv) outsourcing nurses.
Anzeige
Moreover, in real life, the number of patients is usually not accurately predicted, which leads to uncertainty in the number of nurses needed each day (or each period). At present, for the uncertainty problem, many researchers use stochastic programming. Although stochastic programming problems require different models and solution techniques depending on the problem settings, they are all based on the same assumption: the probability distributions of the random variables are precisely known (or can be estimated). In practice, however, estimating the accurate probability distribution of future events is often difficult or impossible.
To tackle this issue, we employ the distributionally robustness to handle the demand of nurse through so-called ambiguity sets defined by only partial distribution information, in which the distributions of uncertain demands of the nurses are assumed to reside. In this way, distributionally robust optimization aims to minimize a certain worst-case criterion over all of the possible distributions within the ambiguity set [8, 10, 28, 35]. The reasons for employing distributionally robust optimization are threefold: (i) it allows uncertain parameters to follow an arbitrary distribution resided in the ambiguity set, instead of a given distribution, or fuzzy number that is needed for stochastic optimization and fuzzy optimization which are two popular methods for handing uncertainty; (ii) the solution obtained from the distributionally robust model is usually robust and flexible when encountering uncertainty in future, although the negative effect of the worst-case scenarios with low possibility and high penalty is substantial; and (iii) the decision-makers can control the conservatism level by varying the parameters in the ambiguity set.
Motivated by the aforementioned observations, we consider the nurse rescheduling problem with multiple rescheduling methods under uncertain demands of the nurse. In this study, two kinds of departments are involved in hospital: (i) general department, the nurse in these departments can be rescheduling between each other in general departments; and (ii) special department, nurses in these departments require special skills and can only be rescheduling between each other in special departments. Moreover, four rescheduling methods are meaningful: The first three rescheduling methods can reassign the vacant nurses to the needed departments according to the real situation, which can alleviate the dilemma of nurse shortage in some departments on the one hand and improve the utilization rate of nurses on the other. The fourth rescheduling method is designed to meet the demands of patients, enhance patient satisfaction and improve the reputation of the hospital. The main contributions of this study are as follows:We organize the rest of this study as follows: in the next section, we briefly review the relevant studies. In the following section, we formally define the problem, present the stochastic model and distributionally robust model, and reformulate them into an integer program. In the next section, a case study is presented and extensive numerical studies are considered. A concluding discussion is provided in the last section.
-
For the first time, we present a novel nurse rescheduling problem with multiple rescheduling methods under uncertain demands of the nurse. For the uncertain demand of the nurse, we consider the stochastic programming model and the distributionally robust model. Here the ambiguity sets characterize a set of distributions using limited distributional information about the support, mean, and upper bounds on the dispersion of demands.
-
We show that the stochastic model and distributionally robust model can be reformulated into a tractable formulation, respectively.
-
We consider a case study to verify the validity of the model. In addition, we perform extensive numerical studies to assess the benefit of considering uncertainty and distributional robustness. We also conduct sensitivity analysis on important model parameters to derive some meaningful managerial insights.
Literature review
The nurse scheduling problem (NSP) has been widely studied for more than two decades. The NSP aims at building a schedule for a set of nurses over a certain period of time (typically two weeks or one month) while ensuring a certain level of service and respecting collective agreements. We refer to Ernst et al. [9] and Jorne et al. [12] for literature reviews on solution methods and models, as well as a classification of staff scheduling problems and to Burke et al. [5] for a review focusing on nurse scheduling.
Anzeige
However, in real life, there may be interruptions that make the existing schedule unfeasible, and these interruptions generally fall into two types. The first type is when nurses are overstaffed and the second type is when nurses are understaffed. Therefore, nurses need to be rescheduling to maintain care level. Moz and Pato [19] are the first to publish a study on nurse rescheduling. They describe in detail in the context of nurse scheduling and formulated as an integer multicommodity flow problem with additional constraints, in a multi-level acyclical network. And a heuristic is introduced as a first approach to solving the problem. Moz and Pato [20] then conduct a study based on a case study of a public hospital in Portugal. They present two new integer multicommodity flow formulations for the rescheduling problem, besides a computational experiment performed using real data. The results obtain show that the second integer multicommodity flow formulation outperforms the first, both in terms of solution quality, as well as in computational time. Chiaramonte and Caswell [6] develop a method to both schedule and reschedule. For rescheduling, they use a one-to-one shift change to get an optimal solution that minimizes the number of shift changes. The latest study on the nurse rescheduling problem is provided by Wickert et al. [27]. They extend a general integer scheduling model taking multi-skilled nurses into account by specific rescheduling constraints. Thus, the objective function includes scheduling as well as rescheduling objectives. To generate a solution approach for practical use, which does not require a commercial solver, a variable neighborhood heuristic is presented which performs well in terms of solution time with only small deductions in schedule quality.
It is worth noting that the above literature only focuses on nurse rescheduling in a single department, i.e., employing nurses from other departments was not possible. In contrast, the application of nurse rescheduling in more departments is considered to improve nurse utilization, reduce staff costs, and build strong competitiveness for nurses to work in multiple departments. Maenhout and Vanhoucke [17] propose a more compact integrated staffing and scheduling model for a long-term nurse management problem over multiple departments. They showed that staffing multiple departments simultaneously and integrating nurse characteristics into the staffing decisions can lead to substantial improvements in schedule quality. Wright and Mahar [33] tackle the staffing and scheduling problem and achieve reduced cost and improved nurse satisfaction by scheduling cross-trained nurses, which come from multiple departments in a centre nurse pool. Wright and Bretthauer [29] present coordinated decision-making models to coordinate nurses inside the hospital, and agent nurses outside the hospital to reduce labour cost, as well as overtime workload. The results show how centralised scheduling can be used to reduce costs and improve nurse satisfaction. As can be seen from the above literature, the existing literature focuses on one hospital for nurse rescheduling. To our best knowledge, there is no literature that considers nurse rescheduling between multiple hospitals. Moreover, all these literature studies assume a deterministic setting.
Healthcare systems, like many other service systems, are featured with non-stationary and uncertain demands: the number of patients fluctuates over time in a stochastic manner. Defraeye and Nieuwenhuyse [7] provide a state-of-the-art literature review on staffing and scheduling approaches that account for non-stationary demand, mainly focusing on applications in call centres and emergency departments. In healthcare systems, patient demand uncertainty is prominent. Most hospitals enforce a patient-to-nurse ratio. Therefore, uncertainty should be taken into account in the decision-making to produce a nurse schedule. Stochastic programming is a well-developed method to model
decision-making under uncertainty in a flexible way, which imposes real-world constraints relatively easily. Bard and Purnomo [2] consider the problem of short-term nurse rescheduling for daily fluctuation in patient demand, where a given mid-term schedule is revised to cover the shortage. Zhu and Sherali [37] address a multi-category workforce planning problem for functional areas located at different service centres, each having office-space and recruitment capacity constraints, and facing fluctuating and uncertain workforce demand. To deal with the demand uncertainty, they proposed a two-stage stochastic program. Kim and Mehrotra [14] study the problem of integrated staffing and scheduling under demand uncertainty. This problem is formulated as a two-stage stochastic integer program with mixed-integer recourse. The here-and-now decision is to find initial staffing levels and schedules. A modified multicut approach in an integer L-shaped algorithm with a prioritized branching strategy was proposed, and the results showed that compared with a deterministic model, the two-stage stochastic model leads to significant cost savings. Bagheri et al. [1] use a sample average approximation method to obtain an optimal schedule with the minimum regular and overtime assignment cost in NSP. He et al. [11] formulate an integrated nurse staffing and scheduling model under patient demand uncertainty into a two-stage stochastic programming model with an emphasis on understaffing risk control. Also, they consider the conditional value-at-risk (CVaR) in the model.
On the other hand, distributionally robust optimization has been developed in recent years and became an attractive approach for addressing optimization problems contaminated by uncertainty. In distributionally robust optimization, the distribution of uncertain parameters is assumed to reside in a so-called ambiguity set and optimization is based on the worst-case distribution within the ambiguity set. The details can be refer to Delage and Ye [8], Goh and Sim [10], Wiesemann et al. [28], and Zhang et al. [35]. Currently, distributionally robust optimization has been applied to a number of fields, including location allocation [3, 16, 22], relief management [15, 25, 34, 36], and healthcare management [13, 18, 21, 23, 24, 26]. Among them, the multiple advantages of distributed robustness further promote its application in healthcare management. For instance, Kong et al. [13] investigate a stochastic appointment-scheduling problem in an outpatient clinic with a single doctor. The objective is to minimize the expectation of patient waiting time and provider overtime. They consider a cross-moment ambiguity set and derive a convex conic programming reformulation of the distributionally robust model. Mak et al. [18] consider a marginal-moment ambiguity set and derive tractable reformulations based on linear program and second-order conic program. Moreover, the author study the optimality of sequencing jobs in increasing order of job duration variance. Qi [21] proposes a new quality measure called the Delay Unpleasantness Measure to describe an individual’s dissatisfaction with a waiting process. Then, given a number of heterogeneous patients, the author lexicographically minimize the worst DUM to make both sequencing and scheduling decisions to mitigate the delay and unfairness in the appointment system. Wang et al. [26] consider a surgery block allocation problem, which includes determining the ORs to open and assigning the surgeries in a daily listing to the ORs, towards minimizing the weighted sum of OR opening costs and expected overtime penalty costs. The author propose a distributionally robust model reformulate it as a mixed integer linear programming model using the duality theory. Wang et al. [24] focus on the blood supply network design problem considering random demand incurred by disasters, and propose a two-stage distributionally robust model. To address this distributionally robust model with binary recourse, the authors develop an approximate approach to transform it into a semidefinite program. Shehadeh et al. [23] derive an equivalent mixed-integer linear programming formulation for the outpatient colonoscopy scheduling problem. Finally, the authors present a case study based on extensive numerical experiments.
In summary, no existing models in the literature cover all aspects of our problem (especially multiple hospitals and departments, and uncertainty of demand using a distributed robust approach). Our work builds upon and complements previous work by employing stochastic programming and allocation robust optimization methods to optimize the problem of rescheduling nurses between different departments in different hospitals to proactively consider such uncertainty, and assessing the different methods to deal with uncertainty differences.
Problem description and model formulations
In this section, we first formally introduce the problem we consider, and then develop a stochastic and distributionally robust model for the problem and further reformulate it as an intractable formulation.
Problem description
In a finite planning horizon \(T=\{1,2,\ldots ,|T|\}\), suppose there exists a set of hospital \(h = \{1,2,\ldots , |H|\}\), and each hospital h has departments with different functions. Depending on the function of the department, the department can be divided into general departments and special departments. Let \(d \in D\) be the general department and \(s\in S\) be the special department. For each department, the number of patients receiving admissions per day is uncertain, as it is not possible to accurately predict the number of patients arriving and their corresponding conditions. This can lead to a shortage of nurses in some departments of some hospitals. Let \({\tilde{q}}_{hd}^t\) and \({\tilde{q}}_{hs}^t\) denotes the demand of nurses in each hospital h for general department d and special department s in each time period t, respectively. In addition, because of the limited number of beds in each department, there is a limit on the number of nurses in each department in each hospital, let \(Q_{hd}\) and \(Q_{hs}\) be the maximum number of nurses in general department d and special department s in hospital h, respectively. However, due to factors such as the location and equipment of some hospitals h, the number of patients received in each time period t is low and stable, which leads to the existence of vacant nurses. Based on the existing nurse scheduling system and through historical data, the number of vacant nurses \(n_{hd}^t\) and \(n_{hs}^t\) for general department d and special department s in each hospital h at each time period t can be obtained.
Therefore, in the above description, we assume that the rescheduling among nurses is divided into the following four methods. (1) Rescheduling between different departments of the same hospital; (2) rescheduling between the same departments of different hospitals; (3) rescheduling between different departments of different hospitals; and (4) rescheduling from other hospitals. Due to the different implementation costs of the different options and the impact of the inter-departmental nurse work environment, each rescheduling has different costs. Let \(c_d\), \(c_s\), \(c_{hd}\), and \(c_o\) represent the unit cost of each of the four rescheduling methods. It should be noted that nurses from general departments cannot be deployed to special departments because of the high occupational skill requirements of nurses in special departments.
The decision-makers, for each time period, need to determine the amounts of nurses rescheduling to the general department and the special department. The optimization criteria in this paper only consider the cost of operations, that is, minimizing the total rescheduling cost for all time periods.
Stochastic model
In this section, we first introduce the nurse rescheduling model with stochastic nurse demand. Second, we discuss the limitations of stochastic optimization. For the uncertain demands of the nurse, we use the sample mean approximation (SAA) method to construct stochastic programming models. Let \(\Omega \) denotes all the possible scenarios, on the basis of this, let \(q_{hd}^{t\zeta }\) and \(q_{hd}^{t\zeta }\) be the demand of nurses in the general department d and special department s in the hospital h at the time period t on the scenario \(\zeta \), respectively. To formally set up the stochastic model (SM) for the problem we consider, we introduce the following variables.With the above decision variables, we formulate the SM as follows:
-
\(s_{hdd'}^{t\zeta }:\) Amount of nurses will be rescheduling from the general department d in hospital h to general department \(d'\) in hospital h at time period t on the scenario \(\zeta \).
-
\(s_{hss'}^{t\zeta }:\) 1 Amount of nurses will be rescheduling from the special department s in hospital h special department \(s'\) in hospital h at time period t on the scenario \(\zeta \).
-
\(s_{hh'd}^{t\zeta }:\) Amount of nurses will be rescheduling from the general department d in hospital h to general department d in hospital \(h'\) at time period t on the scenario \(\zeta \).
-
\(s_{hh's}^{t\zeta }:\) Amount of nurses will be rescheduling from the special department s in hospital h to special department s in hospital \(h'\) at time period t on the scenario \(\zeta \).
-
\(s_{hh'dd'}^{t\zeta }:\) Amount of nurses will be rescheduling from the general department d in hospital h to general department \(d'\) in hospital \(h'\) at time period t on the scenario \(\zeta \).
-
\(s_{hh'ss'}^{t\zeta }:\) Amount of nurses will be rescheduling from the special department s in hospital h to special department \(s'\) in hospital \(h'\) at time period t on the scenario \(\zeta \).
-
\(s_{ohd}^{t\zeta }:\) Amount of nurses will be rescheduling from other hospital to general department d in hospital h at time period t on the scenario \(\zeta \).
-
\(s_{ohs}^{t\zeta }:\) Amount of nurses will be rescheduling from other hospital to special department s in hospital h at time period t on the scenario \(\zeta \).
$$\begin{aligned} \min&\frac{1}{|\Omega |}\left( \sum _{\zeta \in \Omega }\sum _{t \in T}\sum _{h \in H}c_d\left( \sum _{d,d' \in D} s_{hdd'}^{t\zeta } + \sum _{s,s' \in S} s_{hss'}^{t\zeta }\right) \right. \nonumber \\&\quad \left. + \sum _{\zeta \in \Omega }\sum _{t \in T}\sum _{h,h' \in H}c_h\left( \sum _{d \in D} s_{hh'd}^{t\zeta } + \sum _{s \in S} s_{hh's}^{t\zeta }\right) \right. \end{aligned}$$
(1a)
$$\begin{aligned}&\left. + \sum _{\zeta \in \Omega }\sum _{t \in T}\sum _{h,h' \in H}c_{hd}\left( \sum _{d,d' \in D} s_{hh'dd'}^{t\zeta } + \sum _{s,s' \in S} s_{hh'ss'}^{t\zeta }\right) \right. \nonumber \\&\quad \left. + \sum _{\zeta \in \Omega }\sum _{t \in T}\sum _{h \in H}c_{o}\left( \sum _{d \in D} s_{ohd}^{t\zeta } + \sum _{s \in S} s_{ohs}^{t\zeta }\right) \right) \end{aligned}$$
(1b)
$$\begin{aligned} \text{ s.t. } \nonumber \\&\sum _{d' \in D}s_{hd'd}^{t\zeta } + \sum _{h' \in H}s_{h'hd}^{t\zeta } + \sum _{h' \in H}\sum _{d' \in D}s_{h'hd'd}^{t\zeta } + s_{ohs}^{t\zeta }\nonumber \\&\quad \le Q_{hd}, \forall h \in H, d \in D, t \in T, \zeta \in \Omega \end{aligned}$$
(1c)
$$\begin{aligned}&\sum _{s' \in S}s_{hs's}^{t\zeta } + \sum _{h' \in H}s_{h'hs}^{t\zeta } + \sum _{h' \in H}\sum _{s' \in S}s_{h'hs's}^{t\zeta } + s_{ohs}^{t\zeta } \nonumber \\&\quad \le Q_{hs}, \forall h \in H, s \in S, t \in T, \zeta \in \Omega \end{aligned}$$
(1d)
$$\begin{aligned}&\sum _{d' \in D}s_{hdd'}^{t\zeta } + \sum _{h' \in H}s_{hh'd}^{t\zeta } + \sum _{h' \in H}\sum _{d' \in D}s_{hh'dd'}^{t\zeta } \nonumber \\&\quad \le n_{hd}^t, \forall h \in H, d \in D, t \in T, \zeta \in \Omega \end{aligned}$$
(1e)
$$\begin{aligned}&\sum _{s' \in S}s_{hss'}^{t\zeta } + \sum _{h' \in H}s_{hh's}^{t\zeta } + \sum _{h' \in H}\sum _{s' \in S}s_{hh'ss'}^{t\zeta } \nonumber \\&\quad \le n_{hs}^t, \forall h \in H, s \in S, t \in T, \zeta \in \Omega \end{aligned}$$
(1f)
$$\begin{aligned}&{\mathbb {P}}\left( \left( \sum _{d' \in D}s_{hd'd}^{t\zeta } + \sum _{h' \in H}s_{h'hd}^{t\zeta } + \sum _{h' \in H}\sum _{d' \in D}s_{h'hd'd}^{t\zeta } + s_{ohd}^{t\zeta }\right) \right. \nonumber \\&\quad \left. \ge q_{hd}^{t\zeta } \right) \ge 1-\varepsilon _{hd}, \forall h \in H, d \in D, t \in T, \zeta \in \Omega \end{aligned}$$
(1g)
$$\begin{aligned}&{\mathbb {P}}\left( \left( \sum _{s' \in S}s_{hs's}^{t\zeta } + \sum _{h' \in H}s_{h'hs}^{t\zeta } + \sum _{h' \in H}\sum _{s' \in S}s_{h'hs's}^{t\zeta } + s_{ohs}^{t\zeta }\right) \right. \nonumber \\&\quad \left. \ge q_{hs}^{t\zeta } \right) \ge 1-\varepsilon _{hd}, \forall h \in H, s \in S, t \in T, \zeta \in \Omega \end{aligned}$$
(1h)
$$\begin{aligned}&s_{hd'd}^{t\zeta },s_{hs's}^{t\zeta }, s_{hh'd}^{t\zeta }, s_{hh's}^{t\zeta }, s_{hh'dd'}^{t\zeta }, s_{hh'ss'}^{t\zeta }, s_{ohd}^{t\zeta }, s_{ohs}^{t\zeta } \in {\mathbb {N}}, \nonumber \\&\quad \forall h \in H, d \in D, s \in S, t \in T, \zeta \in \Omega . \end{aligned}$$
(1i)
The objective function (1a)–(1b) minimizes the sum of the operating cost. Constraint set (1c) and (1d) ensure that the number of nurses rescheduling to general department d and special department s in hospital h at time period t on the scenario \(\zeta \) cannot exceed the capacity limit of that department, respectively. Constraint set (1e) and (1f) ensure that the number of nurses rescheduling from general department d and special department s in hospital h at time period t on the scenario \(\zeta \) to other departments cannot exceed the number of vacant nurses, respectively. Constraints (1g) and (1h) are opportunity constraints that aim to ensure that the number of nurses rescheduling to general department d and special department s in hospital h at time period t on the scenario \(\zeta \) should meet the demand for nurses in the corresponding departments as much as possible.
However, the model cannot be solved directly due to the presence of constraints (1g) and (1h) in the model, so we turn the constraints into an equivalent form by introducing auxiliary variables \(v_{hd}^{t\zeta }\) and \(v_{hd}^{t\zeta }\) as follows: where \(v_{hd}^{t\zeta }\) and \(v_{hd}^{t\zeta }\) are equal to 1 indicates that the number of nurses rescheduling to general department d and special department s in hospital h at time period t cannot meet the demand for nurses in the corresponding departments and are equal to 0, otherwise.
$$\begin{aligned}&q_{h d}^{t \zeta }-\left( \sum _{d' \in D} s_{h d' d}^{t \zeta }+\sum _{h' \in H} s_{h' h d}^{t \zeta }+\sum _{h' \in H} \sum _{d' \in D} s_{h' h d' d}^{t \zeta }+s_{ohd}^{t \zeta }\right) \nonumber \\&\quad \le M v_{h d}^{t \zeta }, \forall h \in H, d \in D, t \in T, \zeta \in \Omega \end{aligned}$$
(2a)
$$\begin{aligned}&\sum _{\zeta \in \Omega }\left( 1-v_{h d}^{t \zeta }\right) \ge \left[ |\Omega |\left( 1-\epsilon _{h d}\right) \right] , \forall h \in H, d \in D, t \in T \end{aligned}$$
(2b)
$$\begin{aligned}&q_{h s}^{t \zeta }-\left( \sum _{s' \in S} s_{h s' s}^{t \zeta }+\sum _{h' \in H} s_{h' h s}^{t \zeta }+\sum _{h' \in H} \sum _{s' \in S} s_{h' h s' s}^{t \zeta }+s_{ohs}^{t \zeta }\right) \nonumber \\&\quad \le M v_{h s}^{t \zeta } \forall h \in H, s \in S, t \in T, \zeta \in \Omega \end{aligned}$$
(2c)
$$\begin{aligned}&\sum _{\zeta \in \Omega }\left( 1-v_{h s}^{t \zeta }\right) \ge \left\lceil |\Omega |\left( 1-\epsilon _{h s}\right) \right] , \forall h \in H, s \in S, t \in T, \end{aligned}$$
(2d)
Thus, the SM is equivalent to the following linear programming model, denoted as SMIP model:
$$\begin{aligned} \min&\frac{1}{|\Omega |}\left( \sum _{\zeta \in \Omega }\sum _{t \in T}\sum _{h \in H}c_d\left( \sum _{d,d' \in D} s_{hdd'}^{t\zeta } + \sum _{s,s' \in S} s_{hss'}^{t\zeta }\right) \right. \nonumber \\&\quad \left. + \sum _{\zeta \in \Omega }\sum _{t \in T}\sum _{h,h' \in H}c_h\left( \sum _{d,d' \in D} s_{hh'd}^{t\zeta } + \sum _{s,s' \in S} s_{hh's}^{t\zeta }\right) \right. \end{aligned}$$
(3a)
$$\begin{aligned}&\left. \quad + \sum _{\zeta \in \Omega }\sum _{t \in T}\sum _{h,h' \in H}c_{hd}\left( \sum _{d,d' \in D} s_{hh'dd'}^{t\zeta } + \sum _{s,s' \in S} s_{hh'ss'}^{t\zeta }\right) \right. \nonumber \\&\quad \left. + \sum _{\zeta \in \Omega }\sum _{t \in T}\sum _{h \in H}c_{o}\left( \sum _{d \in D} s_{ohd}^{t\zeta } + \sum _{s \in S} s_{ohs}^{t\zeta }\right) \right) \nonumber \\ \text{ s.t. }&(1c-1f), (2a-2d). \end{aligned}$$
(3b)
This stochastic programming model has two major drawbacks: first, it is difficult to estimate each scenario and its respective probability of occurrence with a high degree of accuracy since we have to estimate the probabilities of all possible demands, and there can be arbitrarily many demands. Second, even when accurate information of probabilities is available, the problem can be solved to optimality within a reasonable time only when the total number of scenarios (cardinality of \(\Omega \)) is limited. In the following section, we propose a distributionally robust model to mitigate the effects of these drawbacks by dealing with problem setups in which partial information on the demands of nurses is available in advance.
Distributionally robust model
Since the number of patients arriving each period is difficult to predict and the related conditions of the patients cannot be accurately predicted as well. This results in an unpredictable number of demands of nurses for each department in each hospital. Thus, the true distribution \({\mathbb {P}}\) and \({\mathbb {Q}}\) for \({\tilde{q}}_{hd}^t\) and \({\tilde{q}}_{hs}^t\) are not exactly known and only partial information on the distribution is available. In particular, we allow for the distribution \({\mathbb {P}}\) and \({\mathbb {Q}}\) to be ambiguous and vary within the following ambiguity set:where \(\tilde{\mathbf{q }}_d=({\tilde{q}}_{hd}^t)_{h \in H, d \in D, t \in T}\), and \({\underline{\mu }}=({\underline{\mu }}_{hd}^t)_{h \in H, d \in D, t \in T}, {\overline{\mu }}=({\overline{\mu }}_{hd}^t)_{h \in H, d \in D, t \in T}, \mu =(\mu _{hd}^t)_{h \in H, d \in D, t \in T}, \sigma =(\sigma _{hd}^t)_{h \in H, d \in D, t \in T},\underline{\mathbf{q }_d}=({\underline{q}}_{hd}^t)_{h \in H, d \in D, t \in T}\) and \(\overline{\mathbf{d }_d}=({\overline{q}}_{hd}^t)_{h \in H, d \in D, t \in T}\) with \(\mu \in [{\underline{\mu }},{\overline{\mu }}]\subseteq [\underline{\mathbf{q }_d},\overline{\mathbf{d }_d}]\) are the estimated inputs for the ambiguity set. Andwhere \(\tilde{\mathbf{q }}_s=({\tilde{q}}_{hs}^t)_{h \in H, s \in S, t \in T}\), and \({\underline{\nu }}=({\underline{\nu }}_{hs}^t)_{h \in H, s \in S, t \in T}, {\overline{\nu }}=({\overline{\nu }}_{hs}^t)_{h \in H, s \in S, t \in T}, \nu =(\nu _{hs}^t)_{h \in H, s \in S, t \in T}, \rho =(\rho _{hs}^t)_{h \in H, s \in S, t \in T},\underline{\mathbf{q }_s}=({\underline{q}}_{hs}^t)_{h \in H, s \in S, t \in T}\) and \(\overline{\mathbf{d }_s}=({\overline{q}}_{hs}^t)_{h \in H, s \in S, t \in T}\) with \(\nu \in [{\underline{\nu }},{\overline{\nu }}]\subseteq [\underline{\mathbf{q }_s},\overline{\mathbf{d }_s}]\) are the estimated inputs for the ambiguity set.
$$\begin{aligned} {\mathbb {F}}_d=\left\{ {\mathbb {P}} \Bigg | \begin{array}{llll} {\mathbb {E}}_{{\mathbb {P}}}\left( \tilde{\mathbf{q }}_d\right) \in [{\underline{\mu }},{\overline{\mu }}] \\ {\mathbb {E}}_{{\mathbb {P}}}\left( \left| {\tilde{q}}_{hd}^t -\mu _{hd}^t\right| \right) \le \sigma _{hd}^t, \quad \forall h \in H, d \in D, t \in T \\ {\mathbb {P}}\left( \tilde{\mathbf{q }}_d\in \left[ \underline{\mathbf{q }_d}, \overline{\mathbf{q }_d}\right] \right) =1 \end{array}\right\} \nonumber \\, \end{aligned}$$
(4)
$$\begin{aligned} {\mathbb {F}}_s=\left\{ {\mathbb {Q}} \Bigg | \begin{array}{l} {\mathbb {E}}_{{\mathbb {Q}}}\left( \tilde{\mathbf{q }}_s\right) \in [{\underline{\nu }},{\overline{\nu }}] \\ {\mathbb {E}}_{{\mathbb {Q}}}\left( \left| {\tilde{q}}_{hs}^t -\nu _{hs}^t\right| \right) \le \rho _{hs}^t, \quad \forall h \in H, s \in S, t \in T \\ {\mathbb {P}}\left( \tilde{\mathbf{q }}_s\in \left[ \underline{\mathbf{q }_s}, \overline{\mathbf{q }_s}\right] \right) =1 \end{array}\right\} \nonumber \\ \end{aligned}$$
(5)
Although there are various expressions for ambiguity sets, the fuzzy set chosen in this paper has the following advantages. On the one hand, due to the high uncertainty of demand of nurses, the corresponding mean and variance can be obtained from historical data. On the other hand, the proposed ambiguity set in this paper is more relaxed compared to other first-order ambiguity sets.
To formally set up the distributionally robust model (DRM) for the problem we consider, we introduce the following variables.With the above decision variables, we formulate the DRM as follows: where the objective function (6a–6b) and constraints set (6c–6f) are similar with (1a–1f). Constraint sets (6d) and (6h), to which we referred to as DR chance constraints, ensures that the amount of nurses rescheduled to general department \(d \in D\) and special department \(s \in S\) in hospital \(h \in H\) at time period \(t \in T\) being no less than the realized demand is guaranteed to satisfy with a probability of at least \(1-\epsilon _{hd}\) and \(1-\epsilon _{hs}\) with regard to all probability distributions \({\mathbb {P}}\) and \({\mathbb {Q}}\) belonging to \({\mathbb {F}}_d\) and \({\mathbb {F}}_s\), respectively.
-
\(s_{hdd'}^{t}:\) Amount of nurses will be rescheduling from the general department d in hospital h to general department \(d'\) in hospital h at time period t.
-
\(s_{hss'}^{t}:\) 1 Amount of nurses will be rescheduling from the special department s in hospital h special department \(s'\) in hospital h at time period t.
-
\(s_{hh'd}^{t}:\) Amount of nurses will be rescheduling from the general department d in hospital h to general department d in hospital \(h'\) at time period t.
-
\(s_{hh's}^{t}:\) Amount of nurses will be rescheduling from the special department s in hospital h to special department s in hospital \(h'\) at time period t.
-
\(s_{hh'dd'}^{t}:\) Amount of nurses will be rescheduling from the general department d in hospital h to general department \(d'\) in hospital \(h'\) at time period t.
-
\(s_{hh'ss'}^{t}:\) Amount of nurses will be rescheduling from the special department s in hospital h to special department \(s'\) in hospital \(h'\) at time period t.
-
\(s_{ohd}^{t}:\) Amount of nurses will be rescheduling from other hospital to general department d in hospital h at time period t.
-
\(s_{ohs}^{t}:\) Amount of nurses will be rescheduling from other hospital to special department s in hospital h at time period t.
$$\begin{aligned} \min&\sum _{t \in T}\sum _{h \in H}c_d\left( \sum _{d,d' \in D} s_{hdd'}^{t} + \sum _{s,s' \in S} s_{hss'}^{t}\right) \nonumber \\&\qquad + \sum _{t \in T}\sum _{h,h' \in H}c_h\left( \sum _{d,d' \in D} s_{hh'd}^{t} + \sum _{s,s' \in S} s_{hh's}^{t}\right) \end{aligned}$$
(6a)
$$\begin{aligned}&\qquad + \sum _{t \in T}\sum _{h,h' \in H}c_{hd}\left( \sum _{d,d' \in D} s_{hh'dd'}^{t} + \sum _{s,s' \in S} s_{hh'ss'}^{t}\right) \nonumber \\&\qquad + \sum _{t \in T}\sum _{h \in H}c_{o}\left( \sum _{d \in D} s_{ohd}^{t} + \sum _{s \in S} s_{ohs}^{t}\right) \end{aligned}$$
(6b)
$$\begin{aligned} \text{ s.t. } \nonumber \\&\sum _{d' \in D}s_{hd'd}^{t} + \sum _{h' \in H}s_{h'hd}^{t} + \sum _{h' \in H}\sum _{d' \in D}s_{h'hd'd}^{t} + s_{ohs}^{t} \nonumber \\&\quad \le Q_{hd}, \forall h \in H, d \in D, t \in T \end{aligned}$$
(6c)
$$\begin{aligned}&\sum _{s' \in S}s_{hs's}^{t} + \sum _{h' \in H}s_{h'hs}^{t} + \sum _{h' \in H}\sum _{s' \in S}s_{h'hs's}^{t} + s_{ohs}^{t} \nonumber \\&\quad \le Q_{hs}, \forall h \in H, s \in S, t \in T \end{aligned}$$
(6d)
$$\begin{aligned}&\sum _{d' \in D}s_{hdd'}^{t} + \sum _{h' \in H}s_{hh'd}^{t} + \sum _{h' \in H}\sum _{d' \in D}s_{hh'dd'}^{t} \nonumber \\&\quad \le n_{hd}^t, \forall h \in H, d \in D, t \in T \end{aligned}$$
(6e)
$$\begin{aligned}&\sum _{s' \in S}s_{hss'}^{t} + \sum _{h' \in H}s_{hh's}^{t} + \sum _{h' \in H}\sum _{s' \in S}s_{hh'ss'}^{t} \nonumber \\&\quad \le n_{hs}^t, \forall h \in H, s \in S, t \in T \end{aligned}$$
(6f)
$$\begin{aligned}&\inf _{{\mathbb {P}} \in {\mathbb {F}}_d}{\mathbb {P}}\left( \left( \sum _{d' \in D}s_{hd'd}^{t} + \sum _{h' \in H}s_{h'hd}^{t} + \sum _{h' \in H}\sum _{d' \in D}s_{h'hd'd}^{t} + s_{ohd}^{t}\right) \right. \nonumber \\&\quad \left. \ge q_{hd}^{t} \right) \ge 1-\varepsilon _{hd}, \forall h \in H, d \in D, t \in T \end{aligned}$$
(6g)
$$\begin{aligned}&\inf _{{\mathbb {Q}} \in {\mathbb {F}}_s} {\mathbb {Q}}\left( \left( \sum _{s' \in S}s_{hs's}^{t} + \sum _{h' \in H}s_{h'hs}^{t} + \sum _{h' \in H}\sum _{s' \in S}s_{h'hs's}^{t} + s_{ohs}^{t}\right) \right. \nonumber \\&\quad \left. \ge q_{hs}^{t} \right) \ge 1-\varepsilon _{hs}, \forall h \in H, s \in S, t \in T \end{aligned}$$
(6h)
$$\begin{aligned}&s_{hd'd}^{t},s_{hs's}^{t}, s_{hh'd}^{t}, s_{hh's}^{t}, s_{hh'dd'}^{t}, s_{hh'ss'}^{t}, s_{ohd}^{t}, s_{ohs}^{t} \nonumber \\&\qquad \in {\mathbb {N}}, \forall h \in H, d \in D, s \in S, t \in T \end{aligned}$$
(6i)
Similarly, the DRM cannot be solved directly due to the presence of constraint set (6d) and (6h), and in the following, we focus on transforming the DRM into a solvable formulation.
To reformulate the DR chance constraint set (6d), let us begin by introducing an auxiliary lemma.
Lemma 3.1
Constraintsare equivalent to the following constraints:where \(\kappa _l^{*}=\frac{{\underline{\kappa }}_l+{\overline{\kappa }}_l}{2}\) and \(\tau _l=\frac{{\overline{\kappa }}_l-{\underline{\kappa }}_l}{2}\).
$$\begin{aligned} \sum _{l\in L}u_l\kappa _l\ge a,\forall \kappa _l\in [{\underline{\kappa }}_l,{\overline{\kappa }}_l] \end{aligned}$$
$$\begin{aligned} \sum _{l\in L}(u_l\kappa _l^{*}-\tau _l|u_l|)\ge a, \end{aligned}$$
Proof
The proof is straightforward. \(\square \)
Let \(q_{hd}^{*t}=\frac{{\overline{q}}_{hd}^{t}+{\underline{q}}_{hd}^{t}}{2}\) and \(\tau _{hd}^{t}=\frac{{\overline{q}}_{hd}^{t}-{\underline{q}}_{hd}^{t}}{2}\) for all \(h\in H, d\in D, t\in T\). The next lemma provides the equivalent reformulation of Constraint set (6g) in the DRM.
Lemma 3.2
The DR chance constraint set (6g) is equivalent to the following constraint system: where \(A_{h d}^{t}=\left| \phi _{h d}^{t+}-\phi _{h d}^{t-}+\psi _{h d}^{t+}-\psi _{h d}^{t-}-1\right| \), \(B_{h d}^{t}=\left| \phi _{h d}^{t+}-\phi _{h d}^{t-}+\psi _{h d}^{t+}-\psi _{h d}^{t-}\right| \), and \(\Delta _{hd}^{t} = \sum _{d' \in D} s_{h d' d}^{t}+\sum _{h' \in H} s_{h' h s}^{t}+\sum _{h' \in H} \sum _{d' \in D} s_{h' h d' d}^{t}+s_{o h d}^{t}\).
$$\begin{aligned}&{\overline{\mu }}_{hd}^{t}\phi _{hd}^{t+}-{\underline{\mu }}_{hd}^{t}\phi _{hd}^{t-}+\sigma _{hd}^{t}(\psi _{ j'_s }^{t+}+\psi _{hd}^{t-}) +\theta +\iota \epsilon _{hd}^t\nonumber \\&\quad \le 0,\forall h \in H, d\in D,t\in T \end{aligned}$$
(7a)
$$\begin{aligned}&(\phi _{hd}^{t+}-\phi _{ hd}^{t-}+\psi _{hd}^{t+}-\psi _{hd}^{t-})q_{hd}^{*t}-\tau _{hd}^{t}A_{hd}^{t})\nonumber \\&\qquad - \mu _{hd}^{t}(\psi _{hd}^{t+}-\psi _{hd}^{t-})+\theta +\Delta _{hd}^{t}+\iota \nonumber \\&\quad \ge q_{hd}^{*t},\forall h \in H, d\in D,t\in T\end{aligned}$$
(7b)
$$\begin{aligned}&(\phi _{hd}^{t+}-\phi _{ hd}^{t-}+\psi _{hd}^{t+}-\psi _{hd}^{t-})q_{hd}^{*t}-\tau _{hd}^{t}B_{hd}^{t})\nonumber \\&\qquad - \mu _{hd}^{t}(\psi _{hd}^{t+}-\psi _{hd}^{t-})+\theta \ge 0,\forall h \in H, d\in D,t\in T\end{aligned}$$
(7c)
$$\begin{aligned}&\qquad -A_{hd}^{t}\le \phi _{hd}^{t+}-\phi _{ hd}^{t-}+\psi _{hd}^{t+}\nonumber \\&\qquad -\psi _{hd}^{t-}-1, \forall h \in H, d\in D, t\in T\end{aligned}$$
(7d)
$$\begin{aligned}&\phi _{hd}^{t+}-\phi _{ hd}^{t-}+\psi _{hd}^{t+}-\psi _{hd}^{t-}\nonumber \\&\qquad -1\le A_{hd}^{t}, \forall h \in H, d\in D, t \in T\end{aligned}$$
(7e)
$$\begin{aligned}&-B_{hd}^{t}\le \phi _{hd}^{t+}-\phi _{ hd}^{t-}+\psi _{hd}^{t+}\nonumber \\&\qquad -\psi _{hd}^{t-},\forall h \in H, d\in D,t\in T\end{aligned}$$
(7f)
$$\begin{aligned}&\phi _{hd}^{t+}-\phi _{ hd}^{t-}+\psi _{hd}^{t+}-\psi _{hd}^{t-}\nonumber \\&\quad \le B_{hd}^{t},\forall h \in H, d\in D,t\in T\end{aligned}$$
(7g)
$$\begin{aligned}&\phi _{hd }^{t+},\phi _{hd}^{t-},\psi _{hd }^{t+},\psi _{hd}^{t-},A_{hd}^{t},B_{hd}^{t}\nonumber \\&\quad \ge 0, \forall h \in H, d\in D, t\in T, \end{aligned}$$
(7h)
Proof
Given any \(h \in H\), \(d\in D\), and \(t\in T\), and let \(\Delta _{hd}^{t} = \sum _{d' \in D} s_{h d' d}^{t}+\sum _{h' \in H} s_{h' h s}^{t}+\sum _{h' \in H} \sum _{d' \in D} s_{h' h d' d}^{t}+s_{o h d}^{t}\), we define the worst-case conditional value-at-risk (CVaR) at level \(1-\varepsilon _{hd}^t\) with respect to the distribution \({\mathbb {P}}\in {\mathbb {F}}_d\) as value-at-risk of a random variable \({\tilde{q}}_{hd}^t - \Delta _{hd}^{t}\) governed by the distribution \({\mathbb {P}}\) as follows:By Theorem 2.2 in Zymler et al. [38], Constraint (6h) is equivalent to the following constraint: Now, we show how to reformulate \(\sup \nolimits _{{\mathbb {P}}\in {\mathbb {F}}_d}{\mathbb {E}}_{{\mathbb {P}}}\Big (\max \Big \{{\tilde{q}}_{hd}^t - \Delta _{hd}^{t}-\iota ,0\Big \}\Big )\). By the strong duality [4], the dual problem can be formulated as follows: Let \(\phi _{j_s}^{t+}\), \(\phi _{j_s}^{t-}\), \(\psi _{j_s}^{t+}\), \(\psi _{j_s}^{t-}\) and \(\theta \) be the dual variables associated with the Constraint sets (9b)–(9f), respectively. By the strong duality, the dual problem can be formulated as follows:
$$\begin{aligned}&{\mathbb {P}}-CVaR_{\varepsilon _{j_s}^t}\left\{ {\tilde{q}}_{hd}^t - \Delta _{hd}^{t}\right\} \\&\quad =\inf \limits _{\iota \in {\mathbb {R}}}\left\{ \iota +\frac{1}{\varepsilon _{hd}^t}{\mathbb {E}}_{{\mathbb {P}}}\left( \max \left\{ {\tilde{q}}_{hd}^t - \Delta _{hd}^{t}-\iota ,0\right\} \right) \right\} . \end{aligned}$$
$$\begin{aligned}&\sup \limits _{{\mathbb {P}}\in {\mathbb {F}}_d}{\mathbb {P}}-CVaR_{\varepsilon _{hd}^t}\left\{ {\tilde{q}}_{hd}^t - \Delta _{hd}^{t}\right\} \le 0 \end{aligned}$$
(8a)
$$\begin{aligned}&\quad \Leftrightarrow \sup \limits _{{\mathbb {P}}\in {\mathbb {F}}_d}\inf \limits _{\iota \in {\mathbb {R}}}\left\{ \iota +\frac{1}{\varepsilon _{hd}^t}{\mathbb {E}}_{{\mathbb {P}}}\left( \max \left\{ {\tilde{q}}_{hd}^t - \Delta _{hd}^{t}-\iota ,0\right\} \right) \right\} \le 0 \end{aligned}$$
(8b)
$$\begin{aligned}&\quad \Leftrightarrow \inf \limits _{\iota \in {\mathbb {R}}}\left\{ \iota +\frac{1}{\varepsilon _{hd}^t}\sup \limits _{{\mathbb {P}}\in {\mathbb {F}}_d}{\mathbb {E}}_{{\mathbb {P}}}\left( \max \left\{ {\tilde{q}}_{hd}^t - \Delta _{hd}^{t}-\iota ,0\right\} \right) \right\} \le 0. \end{aligned}$$
(8c)
$$\begin{aligned} \sup&\int _{{\tilde{q}}_{hd}^{t} \in \left[ {\underline{q}}_{hd}^{t}, {\overline{q}}_{hd}^{t}\right] }\max \left\{ {\tilde{q}}_{hd}^t - \Delta _{hd}^{t}-\iota ,0\right\} \ d {\mathbb {P}} ({\tilde{d}}_{hd}^{t})\nonumber \\ \text{ s.t. }&\end{aligned}$$
(9a)
$$\begin{aligned}&\quad \int _{{\tilde{q}}_{hd}^{t} \in \left[ {\underline{q}}_{hd}^{t}, {\overline{q}}_{hd}^{t}\right] } {\tilde{q}}_{ hd}^{t}d {\mathbb {P}} ({\tilde{q}}_{hd}^{t})\le {\overline{\mu }}_{hd}^{t},\end{aligned}$$
(9b)
$$\begin{aligned}&\quad \int _{{\tilde{q}}_{hd}^{t} \in \left[ {\underline{q}}_{hd}^{t}, {\overline{q}}_{hd}^{t}\right] } {\tilde{q}}_{hd}^{t}d {\mathbb {P}} ({\tilde{q}}_{hd}^{t})\ge {\underline{\mu }}_{hd}^{t}, \end{aligned}$$
(9c)
$$\begin{aligned}&\quad \int _{{\tilde{q}}_{hd}^{t} \in \left[ {\underline{q}}_{hd}^{t}, {\overline{q}}_{hd}^{t}\right] } \left( {\tilde{q}}_{hd}^{t}-\mu _{hd}^{t}\right) d {\mathbb {P}} ({\tilde{q}}_{hd}^{t})\le \sigma _{j_s}^{t}, \end{aligned}$$
(9d)
$$\begin{aligned}&\quad \int _{{\tilde{q}}_{hd}^{t} \in \left[ {\underline{q}}_{hd}^{t}, {\overline{q}}_{hd}^{t}\right] } -\left( {\tilde{q}}_{hd}^{t}-\mu _{hd}^{t}\right) d {\mathbb {P}} ({\tilde{q}}_{hd}^{t})\le \sigma _{hd}^{t}, \end{aligned}$$
(9e)
$$\begin{aligned}&\quad \int _{{\tilde{q}}_{hd}^{t} \in \left[ {\underline{q}}_{hd}^{t}, {\overline{q}}_{hd}^{t}\right] } d {\mathbb {P}} ({\tilde{q}}_{hd}^{t})=1. \end{aligned}$$
(9f)
$$\begin{aligned}&\min {\overline{\mu }}_{hd}^{t}\phi _{hd}^{t+}-{\underline{\mu }}_{hd}^{t}\phi _{hd}^{t-}+\sigma _{hd}^{t}(\psi _{ j'_s }^{t+}+\psi _{hd}^{t-}) +\theta \nonumber \\ \text{ s.t. }&\end{aligned}$$
(10a)
$$\begin{aligned}&{\tilde{q}}_{hd}^{t}(\phi _{hd}^{t+}-\phi _{ hd}^{t-})+({\tilde{q}}_{hd}^{t}-\mu _{hd}^{t})(\psi _{hd}^{t+}-\psi _{hd}^{t-})+\theta \nonumber \\&\quad \ge {\tilde{q}}_{hd}^{t}-\Delta _{hd}^{t}-\iota ,\forall {\tilde{q}}_{hd}^{t} \in \left[ {\underline{q}}_{hd}^{t}, {\overline{q}}_{hd}^{t}\right] \end{aligned}$$
(10b)
$$\begin{aligned}&{\tilde{q}}_{hd}^{t}(\phi _{hd}^{t+}-\phi _{hd}^{t-})+({\tilde{q}}_{ hd}^{t}-\mu _{hd}^{t})(\psi _{hd}^{t+}-\psi _{hd}^{t-}))+\theta \nonumber \\&\quad \ge 0,\forall {\tilde{q}}_{hd}^{t} \in \left[ {\underline{q}}_{hd}^{t}, {\overline{q}}_{hd}^{t}\right] \end{aligned}$$
(10c)
$$\begin{aligned}&\phi _{hd }^{t+},\phi _{hd}^{t-},\psi _{hd }^{t+},\psi _{hd}^{t-} \ge 0. \end{aligned}$$
(10d)
Let \(A_{hd}^{t}=|\phi _{hd}^{t+}-\phi _{ hd}^{t-}+\psi _{hd}^{t+}-\psi _{hd}^{t-}-1|\) and \(B_{hd}^{t}=|\phi _{hd}^{t+}-\phi _{ hd}^{t-}+\psi _{hd}^{t+}-\psi _{hd}^{t-}|\). By Lemma 3.1, we can replace Constraint sets (10b) and (10c) with the following constraints:
$$\begin{aligned}&(\phi _{hd}^{t+}-\phi _{ hd}^{t-}+\psi _{hd}^{t+}-\psi _{hd}^{t-}-1)q_{hd}^{*t}-\tau _{hd}^{t}A_{hd}^{t})\nonumber \\&\quad - \mu _{hd}^{t}(\psi _{hd}^{t+}-\psi _{hd}^{t-})+\theta \ge -\sum _{ i \in I}q_{i j_{s}}^{t}-\iota ,\end{aligned}$$
(11a)
$$\begin{aligned}&(\phi _{hd}^{t+}-\phi _{ hd}^{t-}+\psi _{hd}^{t+}-\psi _{hd}^{t-})q_{hd}^{*t}-\tau _{hd}^{t}B_{hd}^{t})\nonumber \\&\quad - \mu _{hd}^{t}(\psi _{hd}^{t+}-\psi _{hd}^{t-})+\theta \ge 0,\end{aligned}$$
(11b)
$$\begin{aligned}&-A_{hd}^{t}\le \phi _{hd}^{t+}-\phi _{ hd}^{t-}+\psi _{hd}^{t+}-\psi _{hd}^{t-}-1,\end{aligned}$$
(11c)
$$\begin{aligned}&\phi _{hd}^{t+}-\phi _{ hd}^{t-}+\psi _{hd}^{t+}-\psi _{hd}^{t-}-1\le A_{hd}^{t},\end{aligned}$$
(11d)
$$\begin{aligned}&-B_{hd}^{t}\le \phi _{hd}^{t+}-\phi _{ hd}^{t-}+\psi _{hd}^{t+}-\psi _{hd}^{t-},\end{aligned}$$
(11e)
$$\begin{aligned}&\phi _{hd}^{t+}-\phi _{ hd}^{t-}+\psi _{hd}^{t+}-\psi _{hd}^{t-}\le B_{hd}^{t},\end{aligned}$$
(11f)
$$\begin{aligned}&A_{hd}^{t},B_{hd}^{t}\ge 0. \end{aligned}$$
(11g)
Then, for the constraint sets (6h), let \(q_{hs}^{*t}=\frac{{\overline{q}}_{hs}^{t}+{\underline{q}}_{hs}^{t}}{2}\) and \(\tau _{hs}^{t}=\frac{{\overline{q}}_{hs}^{t}-{\underline{q}}_{hs}^{t}}{2}\) for all \(h\in H, s\in S, t\in T\). The next lemma provides the equivalent reformulation of Constraint set (6h) in the DRM.
Lemma 3.3
The DR chance constraint set (6h) is equivalent to the following constraint system: where \(A_{h s}^{t}=\left| \varphi _{h s}^{t+}-\varphi _{h s}^{t-}+\chi _{h s}^{t+}-\chi _{h s}^{t-}-1\right| \), \(B_{h s}^{t}=\left| \varphi _{h s}^{t+}-\varphi _{h s}^{t-}+\chi _{h s}^{t+}-\chi _{h s}^{t-}\right| \), and \(\Delta _{hs}^{t} = \sum _{s' \in S} s_{h s' s}^{t}+\sum _{h' \in H} s_{h' h s}^{t}+\sum _{h' \in H} \sum _{s' \in S} s_{h' h s' s}^{t}+s_{o h s}^{t}\).
$$\begin{aligned}&{\overline{\nu }}_{hs}^{t}\varphi _{hs}^{t+}-{\underline{\nu }}_{hs}^{t}\varphi _{hs}^{t-}+\rho _{hs}^{t}(\chi _{ hd }^{t+}+\chi _{hs}^{t-}) +\vartheta \nonumber \\&\qquad +\iota \epsilon _{hs}^t\le 0,\forall h \in H, s\in S,t\in T\end{aligned}$$
(12a)
$$\begin{aligned}&(\varphi _{hs}^{t+}-\varphi _{ hs}^{t-}+\chi _{hs}^{t+}-\chi _{hs}^{t-})q_{hs}^{*t}-\tau _{hs}^{t}A_{hs}^{t})\nonumber \\&\qquad - \nu _{hs}^{t}(\chi _{hs}^{t+}-\chi _{hs}^{t-})+\theta +\Delta _{hs}^{t}+\iota \nonumber \\&\quad \ge q_{hs}^{*t},\forall h \in H, s\in S,t\in T\end{aligned}$$
(12b)
$$\begin{aligned}&(\varphi _{hs}^{t+}-\varphi _{ hs}^{t-}+\chi _{hs}^{t+}-\chi _{hs}^{t-})q_{hs}^{*t}-\tau _{hs}^{t}B_{hs}^{t})\nonumber \\&\qquad - \nu _{hs}^{t}(\chi _{hs}^{t+}-\chi _{hs}^{t-})+\theta \ge 0,\forall h \in H, s\in S,t\in T\end{aligned}$$
(12c)
$$\begin{aligned}&-A_{hs}^{t}\le \varphi _{hs}^{t+}-\varphi _{ hs}^{t-}+\chi _{hs}^{t+}\nonumber \\&\qquad -\chi _{hs}^{t-}-1, \forall h \in H, s\in S, t\in T\end{aligned}$$
(12d)
$$\begin{aligned}&\varphi _{hs}^{t+}-\varphi _{ hs}^{t-}+\chi _{hs}^{t+}-\chi _{hs}^{t-}-1\le A_{hs}^{t}, \forall h \in H, s\in S, t \in T\end{aligned}$$
(12e)
$$\begin{aligned}&-B_{hs}^{t}\le \varphi _{hs}^{t+}-\varphi _{ hs}^{t-}+\chi _{hs}^{t+}-\chi _{hs}^{t-},\forall h \in H, s\in S,t\in T\end{aligned}$$
(12f)
$$\begin{aligned}&\varphi _{hs}^{t+}-\varphi _{ hs}^{t-}+\chi _{hs}^{t+}-\chi _{hs}^{t-}\le B_{hs}^{t},\forall h \in H, s\in S,t\in T\end{aligned}$$
(12g)
$$\begin{aligned}&\varphi _{hs }^{t+},\varphi _{hs}^{t-},\chi _{hs }^{t+},\chi _{hs}^{t-},A_{hs}^{t},B_{hs}^{t}, \vartheta \ge 0, \forall h \in H, s\in S, t\in T, \end{aligned}$$
(12h)
Proof
The proof is similar with Lemma 3.2. \(\square \)
Theorem 3.4
Given the ambiguity sets \({\mathbb {F}}_d\) and \({\mathbb {F}}_s\), the DRM is equivalent to the following linear programming model, denoted as DRMIP model:
$$\begin{aligned} \begin{aligned} \min&\sum _{t \in T}\sum _{h \in H}c_d\left( \sum _{d,d' \in D} s_{hdd'}^{t} + \sum _{s,s' \in S} s_{hss'}^{t}\right) \\&+ \sum _{t \in T}\sum _{h,h' \in H}c_h\left( \sum _{d,d' \in D} s_{hh'd}^{t} + \sum _{s,s' \in S} s_{hh's}^{t}\right) \\&+ \sum _{t \in T}\sum _{h,h' \in H}c_{hd}\left( \sum _{d,d' \in D} s_{hh'dd'}^{t} + \sum _{s,s' \in S} s_{hh'ss'}^{t}\right) \\&+ \sum _{t \in T}\sum _{h \in H}c_{o}\left( \sum _{d \in D} s_{ohd}^{t} + \sum _{s \in S} s_{ohs}^{t}\right) \\ \text {s.t.}&\quad (6c-6f), (7a-7h), (13a-13h)\\. \end{aligned} \end{aligned}$$
Case study
In this section, we take a group hospital in Sichuan province as a case study, which contains three hospitals, located in Chengdu, Guanghan, and Chongzhou. We test the SMIP and DRMIP for some of the departments in these hospitals. The detailed case values and related parameters are presented in the following subsections. The models are coded in Java, and linear programming models were solved by CPLEX 12.8. All runs were conducted on a 64-bit 2.4 GHz Intel Core processor-equipped computer and 8 GB of RAM.
Data and parameters
In each hospital, we consider three types of departments, namely obstetrics and gynecology, urology, and gastroenterology. Among them, we set up obstetrics and gynecology as a special department because of its special characteristics, which means that nurses from other departments cannot perform the requirements of obstetrics and gynecology. We collected data on the demand for nurses in each department in each hospital for each day of the year and will present the relevant parameters in detail in the following.
Definition of distributional ambiguity sets
Through survey interviews, several of the hospitals involved in this case study typically conduct daily nurse scheduling at a rate of every 5 days. Therefore for the SMLP model using the SAA method, we consider every five days of the year as a period, i.e., we have data for 73 scenarios. In addition, we set the parameters of the distributional ambiguity sets \({\mathbb {F}}_d\) and \({\mathbb {F}}_s\) as follows:
-
The parameters \(\mu \) and \(\nu \) are estimated from mean values of data, respectively;
-
The parameters \(\underline{\mathbf{q }_d}\) (resp, \(\underline{\mathbf{q }_s}\)) and \(\overline{\mathbf{q }_d}\) (resp., \(\overline{\mathbf{q }_s}\)) are estimated by the lower and upper bounds of data, respectively;
-
The parameters \({\underline{\mu }}\) (resp, \({\underline{\nu }}\)) and \({\overline{\mu }}\) (resp., \({\overline{\nu }}\)) are set to \((1-0.5)\mu \) (resp, \((1-0.5)\nu \)) and \((1+0.5)\mu \) (resp, \((1+0.5)\nu \));
-
The parameters \(\sigma \) and \(\rho \) are set to \(\frac{1}{73}\sum \nolimits _{k=1}^{73}|\widetilde{\mathbf{q }}_d^k-\mu |\) and \(\frac{1}{73}\sum \nolimits _{k=1}^{73}|\widetilde{\mathbf{q }}_s^k-\nu |\), respectively.
Other parameter choices
According to the data, we can derive the number of vacant nurses in each department in each hospital during the period, and the detailed data are shown in Table 1.
Table 1
The number of vacant nurse in each department in each hospital at time period
Hospital | Department | Period | ||||
|---|---|---|---|---|---|---|
\(T=1\) | \(T=2\) | \(T=3\) | \(T=4 \) | \(T=5 \) | ||
Chengdu | O&G | 3 | 3 | 2 | 2 | 2 |
Urology | 3 | 3 | 4 | 4 | 3 | |
Gastroenterology | 3 | 3 | 3 | 3 | 3 | |
Guanghan | O&G | 0 | 0 | 0 | 0 | 0 |
Urology | 0 | 0 | 0 | 0 | 0 | |
Gastroenterology | 0 | 0 | 0 | 0 | 0 | |
Chongzhou | O&G | 0 | 0 | 0 | 0 | 0 |
Urology | 0 | 0 | 0 | 0 | 0 | |
Gastroenterology | 0 | 0 | 0 | 0 | 0 | |
Moreover, the maximum number of nurses in each departments can be also derived by the data, and the detailed data are shown in Table 2.
Table 2
The maximum number of nurses in each department
Chengdu | Guanghan | Chongzhou | |||||||
|---|---|---|---|---|---|---|---|---|---|
O&G | Urology | Gastroenterology | O&G | Urology | Gastroenterology | O&G | Urology | Gastroenterology | |
Q | 20 | 12 | 12 | 5 | 7 | 8 | 7 | 7 | 8 |
In addition, for the cost of four rescheduling methods, By surveying the real situation of each hospital, the range of each cost is estimated based on the costs related to hospital distance, overtime costs, training costs, etc. However, since the costs contain multiple factors, we randomly generate the corresponding costs based on the range of costs. Moreover, in real life, there are situations where there are not enough nurses to allow for the timely admission of patients. When a patient is not admitted to the hospital in a timely manner, it can have a bad impact on the hospital and we assume that there is a corresponding penalty cost for this situation. Let \(c_p\) be the penalty cost. The cost generated as follows:
-
\(c_d\) is generated uniformly from [10, 50];
-
\(c_h\) is generated uniformly from [50, 150];
-
\(c_hd\) is generated uniformly from [150, 300];
-
\(c_o\) is generated uniformly from [300, 500];
-
\(c_p\) is generated uniformly from [1000, 2000];
Case result
In this section, the objectives of the numerical experiments we consider are twofold: (i) demonstrate the advantages of the considered model by comparing a real-life hospital nurse scheduling model with the considered model; and (ii) provide reasonable management insights for decision-makers by comparing the effects of different parameters on the model.
Benefit of considering uncertainty and distributional robustness
In this subsection, we evaluate the difference between the considered model and the real-life model (RM). We generated the 100 instances according to the data to achieve a fair comparison and called these instances as training samples.
Table 3 shows the average total cost (ATC), the average cost of the first rescheduling method (ACFirRM), the average cost of the second rescheduling method (ACSecRM), the average cost of the third rescheduling method (ACTirRM), the average cost of the fourth rescheduling method (ACForRM), the average cost of penalty (ACP), and the average time (AT).
Table 3
Comparison result of SM, DRM, and RM
Model | ATC | ATFirRM | ATSecRM | ATTirRM | ATForRM | ATP | AT(ms) |
|---|---|---|---|---|---|---|---|
SM | 39228.52 | 169.64 | 3460.30 | 218.17 | 35380.39 | 0 | 790.10 |
DRM | 112565 | 974.39 | 1342.93 | 0 | 110247.70 | 0 | 14.65 |
RM | 184284.60 | 233.95 | 0 | 0 | 0 | 184050.60 | 5.78 |
Fig. 1
Comparison results with different \(\upvarepsilon \)
×
![]()
On the one hand, in the comparison of the three models, from the first column in Table 3, we can observe that the total cost of both the SM and DRM is lower than that of RM, with SM and DRM reducing the cost of RM by 78.71% and 38.92%, respectively. This result occurs because there is a shortage of nurses in RM, which in turn incurs a significant penalty cost. This indicates that both models we consider in this paper can be effective in helping hospitals to reduce their total costs. From the second to the sixth column in Table 3, from the second to the sixth column, the ATP in the RM is much higher than in the other two models, which is expected because the RM has only two scheduling methods. the results also demonstrate the advantages of the DRM and SM over the DM when encountering uncertainty, verifying the benefit of considering uncertainty. Moreover, from the seventh column, we can see that the time to solve RM is the shortest, while the time to solve SM is the longest, which is because the model of RM is simpler than SM and DRM. It should be noted that although the time to solve DRM is slower than RM, the speed difference is not significant, and DRM is less than RM on ATC, which shows the advantage of DRM to help decision-makers control hospital costs without affecting the solution time.
On the other hand, in the SM and DRM comparison, we observed that SM was lower than DRM in ATC, ATFirRM and ATForRM, while in ATSecRM and ATTirRM, SM was higher than DRM. This is because DRM obtains more conservative solutions that require more nurses. However, in our data, the number of vacant nurses is not enough, so more nurses of the fourth rescheduling method will be needed, which leads to high costs. If decision-makers can add hospitals with more vacant nurses to the joint hospitals, then the cost of ATForRM can be reduced significantly, which in turn can further reduce the total costs.
Sensitive analysis
In this section, we investigate the impacts of reliable levels \(\epsilon _{hs} = \epsilon _{hs} = \epsilon \) on the results. To compare the differences, we consider four indices similar to the subsection of Benefit of considering uncertainty and distributional robustness. Figure 1 illustrates the variations of the TC, ACFirRM, ACSecRM, ACTirRM, and ACForRM when varying the values of \(\epsilon \in \{0.1,0.2,\ldots ,0.9\}\).Although the value of \(\epsilon \) affects the cost of both models, for a service sector like hospitals, hospitals need to satisfy the demands of their patients as much as possible, i.e. the value of \(\epsilon \) fluctuates less. Thus, from the above observations, we can see that DRM is obviously more stable than SM, which indicates that DRM is more suitable for such decision-makers as hospitals than SM.
-
From Fig. 1a, the ATC and ACForRM in DRM decrease as the increase of \(\epsilon \). However, there is an important threshold (\(\epsilon =0.3\)). When \(\epsilon <0.3\), both the TC and ACForRM keep unchanged. However, when \(\epsilon >0.3\), both ATC and ACForRM decrease as the increase of \(\epsilon \). These observations indicate that the DRM is not sensitive on \(\epsilon \) when \(\epsilon <0.3\).
-
From Fig. 1b, we can see that ACFirRM and ACSecRM in DRM gradient increase and decrease with the increase of \(\epsilon \), respectively. When \(0.3<\epsilon \le 0.6\), ACFirRM and ACSecRM remain unchanged because when the number of nurses in demand decreases, hospitals are the first to reduce the number of the fourth rescheduling method, while the number of the other rescheduling methods remains the same. And when epsilon continues to increase, i.e., \(\epsilon > 0.6\), we can see ACFirRM and ACSecRM begin to decrease and increase, respectively. This result is expected because in our data, vacant nurses are concentrated in one hospital and when the number of nurses in demand within that hospital decreases, the number of the first rescheduling method is used decreases. Conversely, these vacant nurses will go to other hospitals by the second rescheduling method, which leads to an increase in the cost of the second rescheduling.
-
From Fig. 1c, the ATC and ACForRM in SM decrease as the increase of \(\epsilon \). In addition, we can see that more decreasing costs in SM than DRM, due to the fact that as \(\epsilon \) increases, the number of nurses needed in the SM decreases substantially.
-
From Fig. 1d, ACFirRM and ACSecRM in SM decrease as the increase of \(\epsilon \), while ACTirRM increases and then decreases as the increase of \(\epsilon \). When \(\epsilon <0.5\), as the demand for nurses decreases, the vacant nurses are rescheduled by the third method. And when \(\epsilon >0.5\), the total nurse demand will gradually be less than the number of vacant nurses, which leads to a reduction in the cost of all rescheduling methods.
Conclusion
Nurse rescheduling problems show non-stationary and uncertain demand. When patient demand fluctuates, overstaffing or understaffing may occur. In particular, understaffing needs to be paid more attention to as it can severely deteriorate the quality of care. Thus, this study extends the literature on nurse rescheduling problem in three ways: (i) using multiple rescheduling methods to meet the demand for nurses in each hospital department as much as possible; (ii) constructing stochastic programming models based on historical data; and (ii) using distributionally robust optimization to address the difficulties of high uncertainty in demand and the limitations of the lack of sufficient historical data. In sum, we develop a novel stochastic model and a distributionally robust model of nurse rescheduling problem under uncertain demand of nurses. Since the developed DRM is intractable, we translate it into an integer program by the duality theory of linear programming. Based on a real case study, the designed model can effectively reduce hospital costs. In addition, the model comparison demonstrates the superiority and robustness of the developed DRM which provides more reliable and flexible solutions when encountering uncertainty in the future, compared with the SM. We also perform extensive sensitivity analysis on several major parameters, which helps the decision-makers to make relatively stable and efficient relief decisions.
Future research may consider the following. First, we construct the ambiguity sets of uncertain emergence demands and travel times using only the first-order moment knowledge. It is worth exploring different uncertainty sets using the second-order moment knowledge or carrying some correlations. Second, For the uncertainty of demand, this paper uses the estimation based on the historical data, and the corresponding ambiguity set may be inaccurate when the variance of the data is large. Therefore, it makes sense to use a scenario-based approach, where uncertainty can be represented as part of a scenario, and each scenario represents a possible realization of the demand (see [30‐32]). Third, it is interesting to study the dynamic nurse rescheduling in the presence of disruption events, such as emergency patient arrivals, nurse leaves of absence, and so on. Finally, it is vital to investigate an integrated model with other metrics, such as patient wait time, rescheduling response time, to derive more meaningful management insights.
Acknowledgements
This paper was supported in part by the Key Project of Sichuan Provincial Health Commission under Grant 19ZD014.
Declarations
Conflict of interest
The corresponding author states that there is no conflict of interest.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.