People Scheduling Service: an Employee Scheduling Algorithm based on Stochastic Workloads

Abstract

In this thesis, a model and solution approach is proposed for the employee scheduling problem in a very flexible and general setting, encountered in practice at the online supermarket Picnic Technologies. It is called the People Scheduling Service (PSS). The purpose is to make a schedule that minimizes expected costs, where the costs considered are (1) lost revenue in case workload cannot be completed; (2) excess personnel costs in case of overcapacity; (3) employee satisfaction costs incurred when a schedule is unfavorable for an employee. People are assigned to shifts, based on a workload model called "workload packages", which work as follows: at some known release time, an amount of workload (in the form of small, independently executable tasks) is made available to employees. Employees can work on the workload until some known deadline, after which any uncompleted workload is lost. The release time and deadline time do not have to correspond to the start and end time of a shift, adding flexibility to the workload planning system. On top of that, it is not assumed that perfect information is available: the amount of workload in each package is modeled as a random variable. The model, therefore, minimizes the expected costs. On the scheduling side, very few restrictive assumptions are made. Shifts may overlap and they may vary in length. Employees may have full-time or part-time contracts and even contracts where the number of hours is not fixed. The model is formulated in a manner that makes it very easy to change the scheduling constraints that are applied to a given scheduling instance. This is necessary to support operations in an international environment, where the applicable laws can differ between jurisdictions. All in all, PSS is, compared to many other scheduling solutions considered in other papers, very versatile and widely applicable. The contributions of this paper are: (1) a mixed integer linear program (MILP) formulation of the scheduling problem explained above, which is much more general and practically applicable than many other papers in the field; (2) a comparison between two solution approaches: direct application of an off-the-shelf MILP-solver and the L-shaped algorithm, which is a specific implementation of Benders’ decomposition for two-stage stochastic optimization problems; (3) a comparison between scheduling with and without workload uncertainty taken into account, resulting in a clear practical use case for stochastic optimization; (4) a comparison between the performance of SCIP (an open-source MILP-solver) and Gurobi (a commercial MILP-solver) when applied to the scheduling problem considered in this thesis. PSS has been implemented and taken into production in practice. Practical experience shows that the proposed model works well and saves a lot of manual work. The experiments in this thesis show firstly the direct MILP-solver approach is much faster than the implementation of the L-shaped algorithm proposed in this thesis when applied to most real-world test instances (on very large instances in combination with SCIP as the solver, the L-shaped algorithm is faster). Secondly, there is real value in taking uncertainty into account: schedules created without uncertainty in the model had expected costs of up to approximately 60% higher compared to the ones created with uncertainty in the model. Thirdly, Gurobi was a lot faster than SCIP. When using a direct MILP-solver approach, Gurobi never took more than five minutes to reach an optimality gap of at most 1% on any of the test instances. SCIP, on the other hand, could not reach a 1% gap in two hours for the larger test cases. In two cases, it did not even find a feasible solution at all. Further research can be done to extend the model to contain a more general workload model (for example, one where the workload can both be lost or put on a back-log when the deadline is reached), a better uncertainty model modeling more uncertainty in workload more accurately and taking other sources of uncertainty into account as well and doing more practical testing.