Exact methods for shift design and break scheduling

Abstract

Shift design and break scheduling problems are important employee scheduling problems that have been investigated recently in the literature. The shift design problem arises in a variety of large organizations. It involves efficient usage of personnel resources to reduce costs as much as possible, while satisfying several constraints. Break scheduling problem is important in several organizations that needs a high level of concentration. Therefore, it is important that the workers have from time to time breaks to keep the concentration level high. The purpose of the shift design problem is to find a minimum number of legal shifts, that reduce the shortages and excesses of workers in every time slot during the planning period. In the break scheduling, the breaks are assigned within their shifts conveniently with respect to several constraints and also trying to keep the deviation of workforce for the time slots as minimal as possible. In this thesis, we introduced integer linear programming formulation explicitly for solving shift design and break scheduling problems. The explicit model is investigated based on enumeration of each shift or break from the possible shift or breaks starts and lengths. To solve the integer programming model for the shift design problems from the literature, we performed experiments with state-of-the-art solvers Cplex and Gurobi. The Cplex Solver shows better time performance compared to Gurobi Solver. Our results show that these solvers can be used successfully for the shift design problem. Indeed, new optimal solutions are obtained for several benchmark examples. Exact method shows also superior performance for break scheduling problem with using Cplex Solver. However, our formulation fails to run in the real life instances of break scheduling problem, due to introduced restrictions in our problem formulation. We improved the previous solutions for several randomly generated examples in break scheduling problem.