-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathpaper.methods.tex
193 lines (181 loc) · 9.74 KB
/
paper.methods.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
In this section, we present an application of integer linear programming to solve the clinician
scheduling problem presented in Section~\ref{sec:problem}.
An integer linear program (ILP) consists of a linear objective function and linear constraints,
with integer-valued variables. The optimal solution to the ILP must lie within the space
defined by the constraints while also maximizing the objective value.
First, we describe
the sets, indices and variables necessary for the formulation of the problem. We
then write the constraints given in Table~\ref{tbl:constraint-summary} as
linear functions of the variables, and define the objective function of the ILP.
\subsection{Sets and Indices}\label{sec:meth-sets-indices}
We denote the set of all services
that clinicians in a single department can provide as $\mathcal{S}$.
The set of all clinicians in the department is denoted as
$\mathcal{C}$. The sets of blocks and weekends
are denoted as $\mathcal{B}$ and $\mathcal{W}$ respectively. The block size
used in our experiments is 2 weeks, but the following LP formulation does not
require a particular size for blocks, and so it can be adapted for other cases.
A subset of weekends are denoted $\mathcal{L} \subset \mathcal{W}$, corresponding to statutory
long/holiday weekends such as the Thanksgiving weekend in the United States and Canada. Lastly,
the block and weekend time-off requests of clinicians are denoted as the following
subsets of all blocks and weekends: $\mathcal{U}_c \subset \mathcal{B}$ and $\mathcal{V}_c \subset \mathcal{W}$, respectively.
For instance, if clinician $c$'s time-off requests intersect with blocks 1 and 2, and weekend
1, then $\mathcal{U}_c = \{1, 2\}$ and $\mathcal{V}_c = \{1\}$. Table~\ref{tbl:sets-indices} presents a summary of the sets and indices described.
\begin{table}[h]
\centering
\caption{Description of sets and indices in the problem}%
\label{tbl:sets-indices}
\begin{tabular}{ c c l }
\toprule
\textbf{Set} & \textbf{Index} & \textbf{Description}
\\ \midrule
$\mathcal{S} = \{1, \ldots, S \}$ & $s$ & services
\\
$\mathcal{C} = \{1, \ldots, C \}$ & $c$ & clinicians
\\
$\mathcal{B} = \{1, \ldots, B \}$ & $b$ & blocks
\\
$\mathcal{W} = \{1, \ldots, W \}$ & $w$ & weekends
\\
$\mathcal{L} \subset \mathcal{W}$ & & long weekends
\\
$\mathcal{U}_c \subset \mathcal{B}$ & & block requests of
clinician $c$ \\
$\mathcal{V}_c \subset \mathcal{W}$ & & weekend requests of
clinician $c$ \\
\bottomrule
\end{tabular}
\end{table}
\subsection{Variables}\label{sec:meth-variables}
Since each clinician may be assigned to work on any service, during any block of
the year, we denote such an assignment as a binary variable $X_{c, b, s} \in \{0,1\}$.
% JK: I know its implied but if its easy to spell it out might as well.
A value of 1 indicates that clinician $c$ is assigned to service $s$ during block $b$,
while a value of 0 indicates they are not assigned.
Weekend assignments are similarly defined using a binary
variable $Y_{c, w} \in \{0,1\}$, but without a service index, as clinicians are expected to
provide all services during the weekends. We then define
$m_{c, s}$ and $M_{c, s}$ to represent the minimal and maximal number of blocks of service $s$
that clinician $c$ is required to work during the year.
Table~\ref{tbl:variables-constants} presents a summary of the constants and variables
in the problem.
\begin{table}[h]
\centering
\caption{Description of variables and constants in the problem}%
\label{tbl:variables-constants}
\begin{tabular}{ c l }
\toprule
\textbf{Name} & \textbf{Description}
\\ \midrule
$X_{c, b, s} \in \{0, 1\}$ & assignment of clinician $c$ to service $s$ on
block $b$ \\
$Y_{c, w} \in \{0, 1\}$ & assignment of clinician $c$ on weekend $w$
\\
$m_{c, s}$ & minimum number of blocks clinician $c$ should
cover on service $s$ \\
$M_{c, s}$ & maximum number of blocks clinician $c$ should
cover on service $s$ \\
\bottomrule
\end{tabular}
\end{table}
\subsection{Constraints}\label{sec:meth-constraints}
We now formalize the hard constraints in Table~\ref{tbl:constraint-summary}
using the variables defined above.
The BC (block coverage) and WC (weekend coverage) constraints,
are given by Eqns. (\ref{eqn:constr-block-cov}) and (\ref{eqn:constr-weekend-cov}), respectively.
\begin{align}
&\sum_{c=1}^{C} X_{c, b, s} = 1 &&\forall b\in \mathcal{B}, s \in \mathcal{S} \label{eqn:constr-block-cov} \\
&\sum_{c=1}^{C} Y_{c, w} = 1 &&\forall w\in \mathcal{W} \label{eqn:constr-weekend-cov}
\end{align}
The MM (min/max) constraint is given by:
\begin{align}
&m_{c, s} \leq \sum_{b=1}^{B} X_{c, b, s} \leq M_{c, s} &&\forall\
c\in\mathcal{C}, s\in\mathcal{S} \label{eqn:constr-min-max}
\end{align}
The NCB (no consecutive blocks) and NCW (no consecutive weekends) constraints are
given by Eqns. (\ref{eqn:constr-no-consec-blocks}) and (\ref{eqn:constr-no-consec-weekends}), respectively.
\begin{align}
&X_{c, b, s} + X_{c, b + 1, s} \leq 1 &&\forall c\in\mathcal{C}, b \leq B - 1,
s\in\mathcal{S} \label{eqn:constr-no-consec-blocks} \\
&Y_{c, w} + Y_{c, w + 1} \leq 1 &&\forall c\in\mathcal{C}, w \leq W - 1 \label{eqn:constr-no-consec-weekends}
\end{align}
The EW (equal weekend) and EH (equal holidays) constraints are given by Eqns. (\ref{eqn:constr-equal-weekends})
and (\ref{eqn:constr-equal-holidays}), respectively.
\begin{align}
&\floor*{\frac{W}{C}} \leq \sum_{w=1}^W Y_{c, w} \leq \ceil*{\frac{W}{C}}
&&\forall c\in\mathcal{C} \label{eqn:constr-equal-weekends} \\
&\floor*{\frac{\abs{\mathcal{L}}}{C}} \leq \sum_{w\in\mathcal{L}} Y_{c, w} \leq
\ceil*{\frac{\abs{\mathcal{L}}}{C}} &&\forall c\in\mathcal{C}
\label{eqn:constr-equal-holidays}
\end{align}
\subsection{Objectives}\label{sec:meth-objectives}
As described in Section~\ref{sec:problem}, the soft constraints of the clinician
scheduling problem include: satisfying clinician block off requests (BR),
satisfying clinician weekend off requests (WR), and assigning weekends closer to
blocks (BWA). We convert these soft constraints into linear objective functions
of the binary variables defined in Section~\ref{sec:meth-variables}.
Objectives BR and WR are given in Eqns. (\ref{eqn:obj-block-requests}) and (\ref{eqn:obj-weekend-requests})
as linear functions of $X$ and $Y$:
\begin{align}
&Q_1(X) = \sum_{c=1}^{C} \sum_{b=1}^{B} \sum_{s=1}^{S}
{(-1)}^{\ind(b\,\in\,\mathcal{U}_c)}\cdot X_{c, b, s}
\label{eqn:obj-block-requests}\\
&Q_2(Y) = \sum_{c=1}^{C} \sum_{w=1}^{W}
{(-1)}^{\ind(w\,\in\,\mathcal{V}_c)}\cdot Y_{c, w}
\label{eqn:obj-weekend-requests}
\end{align}
where $\ind(P)$ is the indicator function that has value 1 when predicate $P$
holds and 0 otherwise. In the above two objectives, we penalize any assignments
that conflict with a block or weekend request, and aim to maximize the
non-conflicting assignments.
The BWA objective is optimized by considering the product $X_{c, b, s}\cdot Y_{c, w}$
for values of $w$ ``adjacent'' to the value of $b$. This
leads to the maximization objective:%avoid editorial adjectives
\begin{align}
&Q_3(X, Y) = \sum_{c=1}^{C} \sum_{b=1}^{B} \sum_{s=1}^{S} X_{c, b, s}\cdot Y_{c,
w=\varphi(b)} \label{eqn:obj-block-weekend-adj}
\end{align}
where $\varphi(b)$ is a one-to-one mapping of a block to an adjacent weekend, by
some appropriate definition of adjacency. For instance, clinicians might want to
be assigned during a weekend that falls within an assigned block. In this case,
we will have $\varphi(b) = 2b-1$.
However, as it is, $Q_3$ is not a linear function of the assignment variables
$X$ and $Y$, and cannot be optimized in a linear programming framework.
An approach used to convert such
functions into linear objectives involves introducing a helper variable and
additional constraints~\cite{hammer_boolean_1968}.
In our case, we introduce a variable $Z_{c, b, s}$
for every product $X_{c, b, s} \cdot Y_{c, w}$ with $w = \varphi(b)$, and
constraining $Z$ such that
\begin{align}
&Z_{c, b, s} \leq X_{c, b, s} \label{eqn:helper-x-constraint}\\
&Z_{c, b, s} \leq Y_{c, w=\varphi(b)} &&\forall s\in\mathcal{S}
\label{eqn:helper-y-constraint}
\end{align}
Since $X_{c, b, s}$ and $Y_{c, w}$ are binary variables, $Z_{c, b, s}$ will be constrained
to 0, unless both $X_{c, b, s}$ and $Y_{c, w}$ are 1. Therefore, it suffices to maximize
the following linear function of $Z$,
\begin{align}
&Q_3(Z) = \sum_{c=1}^{C} \sum_{b=1}^{B} \sum_{s=1}^{S} Z_{c, b, s}
\end{align}
to get the correct adjacency maximization objective.
In order to optimize all objectives simultaneously, we optimize a weighted sum
of the normalized objective functions,
\begin{equation}
\max_{X, Y, Z} \alpha_1 \bar{Q}_1(X) + \alpha_2 \bar{Q}_2(Y) + \alpha_3
\bar{Q}_3(Z)
\end{equation}
subject to the constraints defined in Section \ref{sec:meth-constraints},
where $\bar{Q}_i$ is the normalization of objective $Q_i$, and $0 \leq \alpha_i \leq 1$.
This method guarantees an optimal solution to be Pareto optimal~\cite{stanimirovic_linear_2011}.
Currently, the most efficient approach to finding an exact solution for
an ILP is called Branch-and-Cut~\cite{mitchell_branch-and-cut_2002}.
This method involves iteratively solving
LP relaxations of the ILP, then constraining the relaxed problems and
considering various sub-problems until it finds integral solutions to the
original ILP.
In the intermediate relaxations, the integer assignment variables can
take on real values, allowing the problem to be solved efficiently using
the Simplex method~\cite{shamir_efficiency_1987}. The
complexity of finding an optimal integral solution thus lies in the
branching search structure of Branch-and-Cut.