\section{Work Scheduling with Overtime}\label{S:WorkScheduling}

\newpar
Integer linear programming is frequently used to solve problems related to scheduling. In this project, we address such a problem, one faced by a state government seeking to meet prison
guard staffing needs at a detention facility, in as cost-effective manner as possible. \footnote{Based upon Maynard, \cite{Maynard_PrisonGuards}, (1980).}

\newpar
Each guard works five consecutive days per week and has the option of working
overtime on one or both of his two days off. The larger the regular workforce, the more costly to the state are fringe
benefit expenditures paid to the guards. On the other hand, the smaller the workforce, the more the
state pays in overtime wages. The problem then becomes one of determining the workforce size and method
of scheduling that meets staffing needs yet minimizes labor costs stemming from
regular wages, overtime wages, and fringe benefits.
	
\newpar
For the sake of simplicity, we focus on the 8 A.M. to 4 P.M. shift and for the sake of notational convention, we assume that the days of
the week are numbered so that Monday corresponds to day 1, Tuesday to day 2, etc. Each
prison guard is assigned to work the same 8-hour shift on five consecutive days, with the option
of working the same shift on one or both of his following two days off. To say that a guard is assigned to work
schedule $k$, means that his standard work week begins on day $k$.

\newpar
We define the decision variables for this model using the following notation
	\bi
	\item $x_k$, where $1 \leq k \leq 7$: The number of guards assigned to work schedule $k$.
    \item $u_k$, where $1 \leq k \leq 7$: The number of guards assigned to work schedule $k$, who work overtime on their first day off.
    \item  $v_k$, where $1 \leq k \leq 7$: The number of guards assigned to work schedule $k$, who work overtime on their second day off.
    \ei
\newpar
Staffing costs stem from wages, both regular and overtime, as well as fringe benefits and
summarized as follows:

\bi
\item The regular pay rate for guards is \$10 per hour, except on Sundays, when it is \$15 per hour instead.
\item A guard who works on one or more of his or her two days off is paid at a rate of \$15 per hour
on each of those days.
\item Each guard receives fringe benefits amounting to 30\% of his or her regular wages.
\ei

\be
\item Construct the objective function for this ILP, which consists of total staffing costs due to regular wages, overtime wages, and fringe benefits.

\item Now formulate a set of constraints for the ILP. They arise from the following requirements:
\be
	\item Prison requirements stipulate at least 50 guards be present each day.
	The exception to this rule occur on Sunday's when 55 guards are required during family visitation.
    \item To prevent guard fatigue, on any given day the number of prison guards working overtime can comprise no more
    than 25\% of the total staff working that day..
    \item To provide sufficient opportunities for guards to earn overtime wages, union rules
    dictate that on any given day, at least 10\% of the total staff working that day consists of guards working
    overtime.
\ee

\item Now use Maple to solve the ILP that minimizes the objective from (1), subject to the
constraints from (2).

\ee
