Senior Design Project By Philip I. Thomas
Advised by Associate Professor Heinz Schaettler
Preston M. Green Department of Electrical and Systems Engineering
Washington University in St. Louis
Completed May 2013
Download the Paper
An algorithm for weekly workforce scheduling with 4-hour discrete resolution that optimizes for employee satisfaction is formulated. Parameters of employee availability, employee preference, required employees per shift, and employee weekly hours are considered in a binary integer programming model designed for automated schedule generation.
Recent healthcare legislation in the United States is affecting workforce management. The Patient Protection and Affordable Care Act defines full-time employees as those who work 30 or more hours per week, on average. Under the legislation, businesses with 50 or more employees are required to provide healthcare benefits to full-time employees, or pay a substantial fine (Source).
This legislation is disrupting workforce management. Specifically, the Wall Street Journal notes that these changes are driving employers to schedule more employees with more strict hour requirements (Source). Rather than employing a workforce of full-time employees, employers are increasingly hiring a larger workforce of part-time employees for 29-hour or less workweeks to avoid the penalty
Scheduling more employees with additional constraints increases the difficulty of the scheduling problem, and current analog scheduling methods are proving inadequate.
With the decreasing cost of computers and the rise of software as a service products, business owners are becoming more receptive to technological solutions to common problems. In addition, with the recent big data trend, operations research and applied statistics are becoming mainstream. Tools like Mapquest and Google Search use complex mathematical models, yet have become integrated into consumers' everyday lives.
Scheduling is a classic operations research problem. By minimizing employee labor cost, a large system optimization is often used to place employees in shifts. Constraints such as shift lengths, employee weekly hours, and minimum number of shifts are often considered.
Corporations such as Taco Bell use binary or mixed integer programing models \cite{taco} with success to schedule thousands of employees every week. Recent trends show the propagation of optimized scheduling techniques to more businesses and organizations.
This project was motivated by a coffee shop that operates 24-hours per day. It already schedules employees in four-hour shifts throughout the week, and employees consist of a mixture of full-time and part-time workers.
Currently, scheduling is done manually by the manager. Because of the long hours of the shop, employees availability on a weekly basis must be considered. In addition, employees have a strong preference for shift, specifically between night, morning, and afternoon shifts.
Current scheduling software does not meet the needs of the shop because it aims to minimize employee working hours, and because it treats an employee's preferred shift as a hard constraint. In addition, because the shop has few employees and already schedules in 4-hour shifts, the software package's minimization of labor costs provides little benefit.
The coffee shop seeks new scheduling software that treats employee preference as a soft constraint, in addition to availability as a hard constraint. When provided with the number of employees required for each shift, and with the availability and preferred shifts of each employee, it should return a suitable work schedule. Constraints such as shifts per week and number of shifts per day should be considered. Furthermore, employees who choose not to prioritize shifts should not be penalized during scheduling.
The main goal of this project is to design an algorithm that automates workforce scheduling in a way that provides a recognizeable benefit for small workforces of less than 100 employees where current cost-saving optimizations provide less utility.
A binary integer programming model was chosen because, based on treating shifts as immutable 4-hour blocks, it allows for efficient solving relative to other nonlinear models. In addition, the application of heuristics is more straightforward.
When considering other models, meeting constraints of number of employee shifts per time period becomes computationally difficult. In models that optimize based on minimizing labor costs, this becomes a variable instead of a constraint, and hence the model is more applicable.
The following characteristics are unique to this scheduling approach:
A boolean matrix signifies whether employee i works shift j1 if employee i is scheduled to work shift j; 0 otherwise. $$x_{i,j} \in \left\{ { 0 , 1 }\right\} $$
There must be enough employees to cover each shift$$\sum\limits_{i} Availability_{i,j} \ge Employee_{min,j}$$
An employee may not work more than two shifts in a 24-hour period.For each i and each j: $$\sum\limits_{k=j}^{j+5} x_{i,( k \bmod{ count(j) })} \le 2 $$
The modulus means that this constraint wraps into the next week.
An employee must work between their minimum and maximum shifts per week, inclusive.$$ Shift_{min,i}\le \sum\limits_{j}x_{i,j} \le Shift_{max,i}$$
The employee preference parameter is created to allow employees to designate shifts they prefer. The model then optimizes to give employees the shifts they desire.
The preferences parameter is calculated such that:
$$\sum\limits_{j}Preference_{i,j} = \sum\limits_{j}Availability_{i,j}$$Should an employee choose not to specify priority shifts, or if an employee chooses to prioritize all shifts, the preference matrix should thus be equally weighted, and equal to the availability parameter:
$$Preference_{i,j} = Availability_{i,j}$$Based on the objective function, priority shifts are upweighted, and based on the specified constraints the non-priority shifts must be downweighted. The upweighting factor is designated as $\alpha$ and the downweighting factor is designated as $\beta$.
Considering j = 4 with one specified priority shift:
$$ (1 + \alpha) + (1-\beta) + (1-\beta) + (1-\beta) = 4 $$Thus, in this case: $$\alpha = 3\beta$$
Clearly, $\beta$ must always be less than one. However, we also consider that employees who specify only a single priority shift have more weight placed on that shift than someone who prioritizes all but one shift. We specify that a prioritized shift may be no more than twice as weighted as a non-weighted shift, thus $\alpha<1$.
If an employee prioritizes only one shift, they are almost twice as likely to be assigned it. Every additional shift they prioritize decreases the likelihood that they will be placed in their desired shifts.$$\alpha_{i} = \frac{\sum\limits_{j}Availability_{i,j} - \sum\limits_{j}Preference_{i,j}}{\sum\limits_{j}Availability_{i,j}}$$
Thus,
$$\beta_{i} = \alpha \frac{\sum\limits_{j}Preference_{i,j}}{\sum\limits_{j}Availability_{i,j} - \sum\limits_{j}Preference_{i,j}}$$In addition, if $\sum\limits_{j}Availability_{i,j}=0$ or if $\sum\limits_{j}Availability_{i,j} = \sum\limits_{j}Preference_{i,j}$, $$ \beta_{i} = \alpha_{i} = 0 $$
If an employee prioritizes every shift, it is no different than choosing not to prioritize any shifts.$$ \beta_{i} = \alpha_{i} = 0 $$
The weighted preference matrix is this computed for each i:
$$ WeightedPreference_{i,j} \begin{cases} 0, Availability_{i,j} = 0\\ 1 + \alpha, Availability_{i,j} = 1 \& Preference_{i,j} = 1 \\ 1 - \beta, Availability_{i,j} = 1 \& Preference_{i,j} = 0\\ \end{cases}$$Employee Satisfaction is maximized by maximizing the number of employees who are assigned to the shifts they want.$$ max~Z = \sum\limits_{i,j} x_{i,j} \cdot WeightedPreference_{i,j}$$
A working implementation in Excel using the Solver package is available. Download Excel Implementation
Based on the solver package parameters, this basic implementation schedules 4 employees over 18 shifts. This equates to 72 decision variables and 98 constraints, which are successfully optimized by the package's GRG Nonlinear engine in approximately one hour when the decision variable is initialized as a null matrix.
A greedy heuristic of using the employee preference matrix as the first iteration of the decision variable increases the speed of the model. In tests, using a heuristic of a Linear Programming Relaxation rounded to binary values proved to be little effective due to the high number of feasible shifts and low number of scheduled shifts.
Many Binary Integer Programming libraries exist, but because this is an NP-Complete problem, the runtime is non-deterministic.
In a real-world implementation where there exist multiple roles in a workforce, for example having both a cook and a dishwasher who cannot fill each others roles, this algorithm should be implemented to treat every role in a company as an independent model with independent solutions.
Due to the low cost and high speed of modern computing, converting this algorithm into a Software as a Service (SaaS) product would be the ideal user interface, particularly because it makes collecting employee availability and preferencees from the remote workforce easier for the manager. The difficulty in a real-world implementation is handling infeasible inputs - for instance, not having enough employees who may work at a particular shift.
Basic scheduling needs are met by the model, and it excels at speed relative to other workforce management algorithms because the only nonlinearity is the binary aspect of the decision variables. However, the next step in a more advanced model is adding contiguity constraints such that there is a minimum break between non-continuous shifts. Such a nonlinear constraint adds significant computational difficulty.
Finally, due to the nondeterministic polynomial runtime of the algorithm and due to the nature of scheduling, the model does not need to be run to completion. Returning a non-optimal but feasible solution still satisfies the original problem statement because it automatically generates a schedule that meets all hard constraints, and any improvement over the worst-case scenario still provides recognizeable benefit to management and employees.