Analyzing the nursing organizational structure and process from a scheduling perspective

Abstract

The efficient and effective management of nursing personnel is of critical importance in a hospital’s environment comprising approximately 25 % of the hospital’s operational costs. The nurse organizational structure and the organizational processes highly affect the nurses’ working conditions and the provided quality of care. In this paper, we investigate the impact of different nurse organization structures and different organizational processes for a real-life situation in a Belgian university hospital. In order to make accurate nurse staffing decisions, the employed solution methodology incorporates shift scheduling characteristics in order to overcome the deficiencies of the many phase-specific methodologies that are proposed in the academic literature.

Appendix A: The problem formulation

For our case study, we use the model and the branch-and-price solution methodology of [20]. The problem formulation is decomposed according to the Dantzig-Wolfe decomposition into a master problem and a subproblem formulation. The theoretical background of both the master problem and subproblem for the problem under study can be found back in [20].

1.1 A.1 The master problem formulation

The master problem is a multi-objective generalized set partitioning problem that uses column variables to appoint a nurse directly to a certain duty roster and a specific department. The master problem is modelled as a generalized set partitioning type problem and can be formulated as a linear integer programming problem as follows,

Notation

$N^{r} / N^{e} / N^{t}$ :

Set of regular/extra/temporary nurses to be scheduled (index n)

G :

Set of skill categories (index g)

$F_{n}^{r} / F_{n}^{e} / F_{n}^{t}$ :

Set of feasible schedules for regular/extra/temporary nurse n with respect to all time related constraints (index f)

W :

Set of wards (index w)

D :

Set of days in the planning horizon (index d)

S :

Set of shifts including the assignment having a day off (index s)

$R_{wgds}$ :

Required number of nurses of skill category g for shift s on day d in ward w

$a^{r}_{nfwgds} / a^{e}_{nfwgds} / a^{t}_{nfwgds}$ :

1 if schedule f for regular/extra/ temporary nurse n covers the required skill competency g of shift s on day d in ward w, 0 otherwise

$c^{r}_{nf} / c^{e}_{nf} / c^{t}_{nf}$ :

Penalty cost of schedule f for regular/ extra/temporary nurse n

$c^{u}_{wgds}$ :

Penalty cost for understaffing skill competency g on shift s on day d in ward w

$c^{o}_{wgds}$ :

Penalty cost for overstaffing skill competency g on shift s on day d in ward w

$y^{r}_{nf} / y^{e}_{nf} / y^{t}_{nf}$ :

1 if regular/extra/temporary nurse n is assigned to schedule f, 0 otherwise

$p^{u}_{wgds}$ :

The number of nurses that are additionally needed to satisfy the coverage requirements of skill competency g for shift s on day d in ward w

$p^{o}_{wgds}$ :

The number of nurses that are scheduled in surplus to perform skill competency g for shift s on day d in ward w

Master Problem Formulation

$$\begin{array}{rll}\text{Min} \qquad Z_{IP} &=& \sum\limits_{n \in N^{r}}\sum_{f \in F_{n}^{r}} c^{r}_{nf} y^{r}_{nf}+ \sum\limits_{n \in N^{e}}\sum\limits_{f \in F_{n}^{e}} c^{e}_{nf} y^{e}_{nf}\\&&+ \sum\limits_{n \in N^{t}}\sum\limits_{f \in F_{n}^{t}} c^{t}_{nf} y^{t}_{nf}\\&&+ \sum\limits_{w \in W}\sum_{g \in G}\sum\limits_{d \in D}\sum\limits_{s \in S} c^{u}_{wgds} p^{u}_{wgds}\\&&+ \sum\limits_{w \in W}\sum\limits_{g \in G}\sum_{d \in D}\sum\limits_{s \in S} c^{o}_{wgds} p^{o}_{wgds}\end{array}$$

(1)

$$\begin{array}{lll}&&\mathrm{s.t.}\\&&\qquad\sum\limits_{n \in N^{r}}\sum\limits_{f \in F_{n}^{r}} a^{r}_{nfwgds} y^{r}_{nf}+ \sum\limits_{n \in N^{e}}\sum\limits_{f \in F_{n}^{e}} a^{e}_{nfwgds} y^{e}_{nf}\\&&\qquad\; + \sum\limits_{n \in N^{t}}\sum\limits_{f \in F_{n}^{t}} a^{t}_{nfwgds} y^{t}_{nf} + p^{u}_{wgds} - p^{o}_{wgds} = R_{wgds}\\&&\qquad\;\;\;\forall w \in W, g \in G, d \in D, s \in S\end{array}$$

(2)

$$\begin{array}{lll}&&\sum\limits_{f \in F_{n}^{r}}y^{r}_{nf} \leq 1 \qquad \qquad \qquad \forall n \in N^{r}\\ &&\sum\limits_{f \in F_{n}^{e}}y^{e}_{nf} \leq 1 \qquad \qquad \qquad \forall n \in N^{e}\\&& \sum\limits_{f \in F_{n}^{t}}y^{t}_{nf} \leq 1 \qquad \qquad \qquad \forall n \in N^{t}\end{array}$$

(3)

$$\begin{array}{lll}&&\quad y^{r}_{nf} \in \{0,1\} \qquad\qquad\qquad\qquad \forall n \in N^{r}, f \in F_{n}^{r}\\&&\quad y^{e}_{nf} \in \{0,1\} \qquad\qquad\qquad\qquad \forall n \in N^{e}, f \in F_{n}^{e}\\&&\quad y^{t}_{nf} \in \{0,1\} \qquad\qquad\qquad\qquad \forall n \in N^{t}, f \in F_{n}^{t}\\&&p^{u}_{wgds}, p^{o}_{wgds} \geq 0 \qquad \forall w \in W, g \in G, d \in D, s \in S\end{array}$$

(4)

This nurse assignment is guided by the objective function Eq. (1) that tries to minimize the penalty costs associated with the schedules assigned to the nurses, the number of times the ward is confronted with a shortage of personnel and the number of times too many nursing staff are assigned. The set of nurses should satisfy the staffing requirements for each skill category Eq. (2) and each nurse can be assigned to at most one duty roster Eq. (3). Equation (4) assures the integrality of the variables.

1.2 A.2 The subproblem formulation

The individual schedules are defined by the subproblem that aims to construct a feasible roster line with respect to all time-related constraints for one single employee. This problem is a resource constrained shortest path problem and can be modeled as a single commodity flow network optimization problem. In this appendix, we provide a mathematical problem formulation for composing an individual schedule for nurse n that is assigned to the rheumatology department.

Notation

G :

Set of skill categories (index g)

D :

Set of days in the planning horizon (index d)

$D_{we}$ :

Set of days that correspond to the weekend days in the planning period (index d)

S :

Set of shifts (index s) with $\mid S \mid$ as the day off assignment

$S_{night}$ :

Set of night shifts (index s)

$B_{s}$ :

Set of assignments that are prohibited to succeed shift assignment s (with $B_{s}\subset S$)

$I_{n}$ :

Set of prohibited assignments (g, w, d, s) for nurse n (index i)

$h_{s}$ :

Number of working hours for shift s

$hrs_{n}^{min}$ :

Minimum number of working hours

$hrs_{n}^{max}$ :

Maximum number of working hours

$duties_{n}^{min}$ :

Minimum number of working duties

$duties_{n}^{max}$ :

Maximum number of working duties

$ass_{ns}^{min}$ :

Minimum number of assignments of shift type s

$ass_{ns}^{max}$ :

Maximum number of assignments of shift type s

$cs_{n}^{max}$ :

Maximum consecutive number of working days (standard)

$cs^{ext}$ :

Maximum consecutive number of working days (extreme with $cs^{ext} \geq cs_{n}^{max}$)

$cs_{n}^{min}$ :

Minimum consecutive number of working days

$csni^{min}$ :

Minimum consecutive number of free days after a night shift

$pref_{n}^1$ :

The preference threshold that, if exceeded, leads to unmotivated nurses

$pref_{n}^2$ :

The preference threshold that, if exceeded leads to nurse turnover

$p^{1}$ :

Penalty cost for assigning overtime hours

$p^{2}$ :

Penalty cost for assigning overtime duties

$p^{3}_{j}$ :

Penalty cost for violating the constraint maximum j consecutive number of working days

$p^{4}$ :

Penalty cost for violating the constraint minimum consecutive number of working days

$p^{5}_{s}$ :

Penalty cost for a change in the day-to-day schedule assignments from shift type s to another assignment

$p^{6}$ :

Penalty cost for exceeding the preference threshold $pref_{n}^1$

$p^{7}$ :

Penalty cost for exceeding the preference threshold $pref_{n}^2$

$p^{8}_{nds}$ :

Penalty preference cost of nurse n to work shift s on day d

$p^{9}_{nw}$ :

Penalty preference cost of assigning nurse n to ward w

$p_{n}^{10}$ :

Penalty wage cost for hiring nurse n

$x_{ngwds}$ :

1 if nurse n is assigned to performing skill competency g, in ward w for shift s on day d, 0 otherwise

$z^{1}$ :

Number of overtime hours

$z^{2}$ :

Number of overtime duties

$z^{3}_{dj}$ :

1, if the constraint maximum j consecutive number of working days is violated (with d as the first day of the consecutive series), 0 otherwise

$z^{4}_{d}$ :

Number of days by which the constraint minimum consecutive number of working days is violated (with d as the first day of the consecutive series)

$z^{5}_{gwds}$ :

1, if another assignment is made on day d, shift s, department w and skill competency g, 0 otherwise

$z^{6}$ :

1, if the preference threshold $pref_{1}$ is exceeded, 0 otherwise

$z^{7}$ :

1, if the preference threshold $pref_{2}$ is exceeded, 0 otherwise

Mathematical formulation

$$\begin{array}{rll}\text{Min} \;\;\; Z_{SP}& = &p^{1}z^{1} + p^{2}z^{2} + \sum\limits_{d \in D}\sum\limits_{j = cs_{n}^{max}}^{cs_{n}^{ext}} p_{j}^{3} z_{dj}^{3}\\&&+ \sum\limits_{d \in D} p^{4} z_{d}^{4}\\&&+ \sum\limits_{g \in G}\sum\limits_{w \in W}\sum\limits_{d \in D}\sum\limits_{s \in S } p^{5}_{s} z^{5}_{gwds} + p^{6}z^{6} + p^{7}z^{7}\\&&+ \sum\limits_{g \in G}\sum\limits_{w \in W}\sum\limits_{d \in D}\sum\limits_{s \in S} p_{nds}^{8} x^{ngwds} + p^{9}_{nw} + p_{n}^{10}\end{array}$$

(5)

$$\begin{array}{l}\mathrm{s.t.}\\ \qquad\; \sum\limits_{g \in G}\sum\limits_{d \in D}\sum\limits_{s \in S\setminus \{\mid S\mid\}}h_{s} x_{ngwds} \geq hrs_{n}^{min}\end{array}$$

(6)

$$\sum\limits_{g \in G}\sum\limits_{d \in D}\sum\limits_{s \in S\setminus \{\mid S\mid\}}h_{s} x_{ngwds} - z^{1} \leq hrs_{n}^{max}$$

(7)

$$\sum\limits_{g \in G}\sum\limits_{d \in D}\sum\limits_{s \in S\setminus \{\mid S\mid\}}x_{ngwds} \geq duties_{n}^{min}$$

(8)

$$\sum\limits_{g \in G}\sum\limits_{d \in D}\sum\limits_{s \in S\setminus \{\mid S\mid\}}x_{ngwds} - z^{2} \leq duties_{n}^{max}$$

(9)

$$\sum\limits_{g \in G}\sum\limits_{d \in D}x_{ngwds} \geq ass_{ns}^{min} \qquad\qquad \forall s \in S$$

(10)

$$\sum\limits_{g \in G}\sum\limits_{d \in D}x_{ngwds} \leq ass_{ns}^{max} \qquad\qquad \forall s \in S$$

(11)

$$\begin{array}{r}\sum\limits_{g \in G}\sum\limits_{d}^{d+j}\sum\limits_{s \in S \setminus \{\mid S\mid\}}x_{ngwds} \leq j + z^{3}_{dj} \qquad\qquad \forall d \in D, \\ j = cs_{n}^{max},\ldots, cs_{n}^{ext}\end{array}$$

(12)

$$\begin{array}{l}\sum\limits_{g \in G}\sum\limits_{d}^{d+cs_{n}^{min}-1}\sum\limits_{s \in S \setminus \{\mid S\mid\}}x_{ngwds} \geq cs_{n}^{min} \sum\limits_{g \in G}\sum\limits_{s \in S \setminus \{\mid S\mid\}}x_{ngwds}\\{\kern5pt}-\sum\limits_{g \in G}\sum\limits_{d-cs_{n}^{min}+1}^{d-1}\sum\limits_{s \in S \setminus \{\mid S\mid\}}x_{ngwds} - z^{4}_{d} \quad\quad\forall d \in D\end{array}$$

(13)

$$\begin{array}{r}\sum\limits_{d+1}^{d+csni^{min}} x_{ngwds} \geq csni^{min} (x_{ngwds} - (1 - x_{ngwd\mid S\mid}))\\ \forall d \in D, \forall s \in S_{night}\end{array}$$

(14)

$$\begin{array}{r}\sum\limits_{g \in G}\sum\limits_{w \in W}\sum\limits_{s \in S\setminus \{\mid S\mid\}}x_{ngwds} = \sum\limits_{g \in G}\sum\limits_{w \in W}\sum\limits_{s \in S\setminus \{\mid S\mid\}}x_{ngw(d+1)s}\\ \forall d \in D_{we}\end{array}$$

(15)

$$\begin{array}{r} x_{ngwds} - x_{ngw(d+1)s} \leq z^{5}_{gwds}\;\; \forall g \in G, \forall w \in W,\\ \forall d \in D, \forall s \in S\end{array}$$

(16)

$$\sum\limits_{g \in G}\sum\limits_{s \in S}p^{8}_{nds} x_{ngwds}\leq pref_{n}^{1} + M z^{6}$$

(17)

$$\sum\limits_{g \in G}\sum\limits_{s \in S}p^{8}_{nds} x_{ngwds}\leq pref_{n}^{2} + M z^{7}$$

(18)

$$\sum\limits_{g \in G}\sum\limits_{s \in S}x_{ngwds} = 1\qquad\qquad\forall d \in D$$

(19)

$$\begin{array}{l}\sum\limits_{g \in G}x_{ngwds} + \sum\limits_{g \in G}\sum\limits_{w \in W}\sum\limits_{s \in B_{s}}x_{ngw(d+1)s} \leq 1\\ \qquad\qquad\qquad\qquad\qquad\qquad\; \forall d \in D, \forall s \in S\end{array}$$

(20)

$$x_{ngwds} = 0 \qquad\qquad \forall i \in I_{n}$$

(21)

$$\begin{array}{r}x_{ngwds} \in \{0,1\}\qquad\qquad\forall g \in G, \forall w \in W,\\ \forall d \in D, \forall s \in S\end{array}$$

(22)

$$\forall s \in S$$

(23)

$$\begin{array}{l} z^{1}, z^{2} \geq 0\; and\; integer\\z_{dj}^{3} \in \{0, 1\}\qquad\qquad\qquad \qquad\forall d \in D, \forall j\\z_{d}^{4} \in \{0, 1\} \qquad\qquad\qquad\qquad\qquad \forall d \in D\\ z^{5}_{gwds} \in \{0, 1\} \qquad\qquad\quad \forall g \in G, \forall w \in W, \\\qquad\qquad\qquad\qquad\qquad\qquad\forall d \in D, \forall s \in S\\ z^{6}, z^{7} \in \{0, 1\}\end{array}$$

(24)

Equation (5) of this problem formulation minimizes the weighted sum of penalty costs associated with the different objective function components. Equations (6), (7), (8), (9), (10) and (11) regulate the minimum and maximum number of working hours, duties and assignments per shift type. The deviation variables $z^{1}$ and $z^{2}$ in these constraints allow to register overtime assignments. Equation (12) guarantees that a nurse does not work more than respectively the maximum allowed consecutive number of duties. The variables $z^{3}_{dj}$ allow the violation of these constraints. Equation (13) expresses the restrictions on the minimum number of consecutive duties. Equation (14) guarantees a minimum consecutive number of rest days after a series of night shifts. Equation (15) ensures that nurses have to work the complete weekend. Equation (16) models the day-to-day assignment changes in an individual nurse schedule. Equations (17) and (18) indicate that motivation and nurse turnover problems could occur if the preference penalty score of a nurse exceeds the respective preference thresholds $pref_{n}^{1}$ and $pref_{n}^{2}$. Equation (19) stipulate that each nurse is given an assignment on each day (to one of the working shifts or a rest day). The restrictions on the succession of shifts are imposed in Eq. (20), which guarantee the minimal rest time between shifts and forbids the succession of particular shift types. Equation (21) avoids nurses to be assigned to duties to particular shifts, days, competences and wards that not conform with their contract regulations. Equations (23) and (24) embody the integrality constraints.

1.3 A.3 The solution procedure

The optimization procedure is an integer programming column generation procedure, i.e. branch-and-price. This mathematical programming approach is in line with the academic literature as several authors have proposed mathematical programming procedures to solve the nurse scheduling problem such as integer programming (e.g. [21–24]), column generation (e.g. [4, 17] and branch-and-price approaches (e.g. [19])). The basic idea of branch-and-price consists of combining column generation with branch-and-bound [5]. The column generation procedure relaxes the integrality constraints of the model and solves the linear programming master problem using commercial optimization software LINDO [29]. Since there are too many variables to handle efficiently, only a subset of the variables is taken into consideration when solving the so-called restricted master linear programming model. In order to check the optimality of an LP solution, the subproblem problem is solved with dual information of the master problem to try to identify new variables (i.e. individual roster lines) that may enter the basis. If this minimum value is nonnegative then the value of the linear programming solution will not decrease by considering other variables which are not incorporated in the restricted master LP model. This implies that the optimal solution of the linear programming relaxation has been found. The LP relaxation of the master problem solved by column generation may not have an integral optimal solution. In order to drive the solution to integrality, we will apply a branch-and-bound depth-first search and call upon the column generation procedure at non-root nodes of the branch and bound tree subject to the active branching constraints. The branching methodology combines branching on the original variables and branching on the residual problem [19].

This subproblem can be solved as a network optimization problem. The network structure typically incorporates the competencies of the single nurse, the daily assignment constraint and the shift succession rules. All other rules and regulations (e.g. the minimum number of assignments) are imposed as requirement constraints on the path construction. The corresponding problem defined above finds the column with the lowest reduced cost. Therefore, if a column with negative reduced cost exists, an optimal algorithm will always identify a candidate column. However, due to the problem structure and the complexity of the subproblem this may be computationally prohibitive. Fortunately for the column generation scheme to work, it is not necessary to always select the column with the lowest reduced cost, any column with a negative reduced cost will do. In our procedure a two phase approach is implemented. In the first phase, the procedure tries to generate heuristically columns with negative reduced cost. As in [30] several existing columns with a reduced cost close to zero are selected and employ fast local improvement algorithms to construct columns with a negative reduced cost. More precisely, the heuristic pricing phase exploits different neighborhoods discussed in [7] to alter the selected columns to columns with negative reduced cost as best as possible. Two important mechanisms are the greedy shuffling heuristic and the single-shift day heuristic. The greedy shuffling heuristic executes all possible feasible swaps between subparts of the selected nurse schedules. The single-shift day heuristic tries to change a single nurse assignment on a specific day. In case of failure, the procedure switches to the second phase where the column with the lowest reduced cost is obtained. Hence, the mathematical problem formulation is mainly used for evaluating heuristic columns and in a smaller extent for exact optimization.