paper.experiments.tex

Our goal was to determine if the schedules provided by solving the ILP 
could successfully
(i) enforce all hard constraints; 
(ii) improve fulfillment of soft constraints compared to the manual approach; 
and (iii) assess whether our ILP formulation can be used for a wide range
of configurations.
First, we compared the schedules created by solving the ILP formulation
given in Section~\ref{sec:methods} to schedules that were manually generated,
with respect to adherence to the hard and soft constraints outlined in Section~\ref{sec:problem}.
We then examined the efficiency of the ILP approach in generating schedules
by its runtime on a variety of instances that may be found in the real-world.

\subsection{Implementation}
We developed a Python software package with a user interface that implements the above
linear program and allows configuration of clinicians, to be
used by the ID division at St.\ Michael's Hospital~\cite{landsman_scheduling}. 
The software was used to
generate the results in the following sections, using real data as well as
simulated data as input. All the following experiments were conducted on an
Intel Core i7-4770k CPU @ 3.50 GHz with 16 GB of RAM running 64-bit Windows 10.
Our software package uses COIN-OR Branch-and-Cut open source solver
version 2.9.9~\cite{johnjforrest_coin-or/cbc:_2019}.

\subsection{Comparison with Manually Generated Schedules}
We used clinician time-off requests and minimum/maximum requirements from
2015-2018 as input data for the ILP problem.
Table~\ref{tbl:2018-schedule-comparison} compares the optimal schedule generated using
the software with the manually-created schedule for data from 2018. The
schedule is color-coded to distinguish between the different clinicians.

\input{tbl/2018_schedule_comparison}

First, we evaluated the ILP solution by comparing it with the
manual generation, as in Table~\ref{tbl:2018-schedule-comparison}. Specifically, we examined the adherence of each
schedule to the constraints presented in Table~\ref{tbl:constraint-summary}. As
shown in Table~\ref{tbl:constraints-comparison}, the ILP solution satisfied all 
hard constraints. In contrast,
manual generation did not satisfy all hard constraints. In
particular, we see that the manual generation assigned clinicians to multiple
consecutive blocks in all four years. Moreover, the manual generation did not have
an equal distribution of weekends and holidays for all four years of data.
Considering all objectives, we see that the ILP solution outperforms manual generation
in all four years, by accommodating almost all time-off requests and
ensuring that weekends are always assigned close to blocks.

\input{tbl/constraints_comparison}

\subsection{Influence of Problem Complexity on Runtime}
Next, we examined the influence of the following four parameters on the
runtime of the ILP solver using simulated data:
number of clinicians;
number of services offered;
number of time-off requests per clinician per year;
time-horizon of the schedule.

The effect of increasing the number of clinicians and number of services 
on the runtime of the program is shown in Table~\ref{tbl:runtime-services-clinicians-comparison}.
We executed the algorithm for
$S = \{1, 2, 3\}$ total services and $C = \{10, 20, 30, 50\}$ clinicians in  
total across all services. 
In a department providing a single service, increasing the number of clinicians
did not affect the runtime, and we were able to find an ILP solution in all four cases
within 1 second.
For 2 concurrent services, a roster of 30 or more
clinicians becomes impractical to schedule, as searching for a solution required
over 24 hours. We saw similar issues for a roster of 20 or more clinicians
assigned to a division with 3 concurrent services. However, when removing the
NCB constraint, we saw a great improvement in runtime for divisions with 2 and 3
services, and we were able to generate a schedule with upwards of 50 clinicians
in under 1.5 seconds.

\input{tbl/runtime_services_clinicians}

For the remaining experiments, we simulated a department with 10 clinicians offering 
two services, similar to the department at St.\ Michael's Hospital. 
The effect of an increasing number of requests per clinician on the runtime of
the ILP solver is shown in Figure~\ref{fig:runtime-requests}.
In this experiment, each clinician was configured with 1 to 15 total block requests.
The runtime of the algorithm is constant with respect to the number of requests,
indicating that it can accommodate a lot of flexibility in
clinician requests. Moreover, we see that all runs were completed in under
2 seconds.

\begin{figure}[h]
	\centering
	\def\svgwidth{\columnwidth}
	\caption{Runtime of ILP solver with an increasing number of requests per clinician}
	\input{fig/runtime-requests.pdf_tex}
  \label{fig:runtime-requests}
\end{figure}

Figure~\ref{fig:runtime-blocks} presents the change in runtime when increasing
the number of 2-week blocks in a department with 10
clinicians offering two services. In this experiment, we investigated time horizons
from 5 to 110 blocks. This is equivalent to generating a schedule for up to 4 years ahead.
The trend in the graph indicates a linear growth in runtime with respect to the time-horizon.
Notably, the ILP solver was able to find all solutions in under 6 seconds, indicating very 
good performance for long-term scheduling. 

\begin{figure}[h]
	\centering
	\def\svgwidth{\textwidth}
	\caption{Runtime of ILP solver with an increasing number of 2-week blocks}%
	\input{fig/runtime-blocks.pdf_tex}
  \label{fig:runtime-blocks}
\end{figure}