Annualised hours

Optimisation with heuristic algorithm

Bachelor thesis (2018)

Authors

J.H. Keim Electrical Engineering, Mathematics and Computer Science

Contributors

J.T. van Essen (mentor)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2018 Josephine Keim
More Info
expand_more

Published Date

05-06-2018

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

In this thesis, we analyse the optimisation of an annualised hours problem. Annualised hours problems are a widely studied subjects, in which the working hours for a given number of employees per week are minimised. We approach this problem with a mixed integer linear program, where the objective function of this problem is divided into two parts; the first is to find the minimisation on the maximum over and under staffing per week, the second to find working hours for each employee as close as possible to their contract hours. Additionally, we have a number of restrictions on the duration of a shift and the minimum and maximum amount of shifts in a given period.
The project is done in collaboration with the company ORTEC. ORTEC provided a random data generator, to test the model with different methods. The model is intended for application on a dataset of 100 employees and 52 weeks. However, we test the model on different data sets of 52 weeks with 50, 100, 150, 200, 250, 1000 employees and for 100 employees with 26, 52, 78 weeks.
Besides analysing the model, we compare different algorithms. We use a Gurobi solver for an exact solution. Further, we consider Lagrangian relaxation, a heuristic method. In this method one of the constraints is put in the objective function. Besides this we consider a heuristic of hill climbing algorithm in combination with different local search algorithms. For the local search we use two neighbourhoods, one based on the employees, the other based on the weeks.
We found that a Gurobi solver solves the model in reasonable computation time with an average of 6 seconds for a data set of 100 employees and 52 weeks. For Lagrangian relaxation, we found an even better computation time than with the Gurobi solver. However, this difference is hardly notable for a data set of 100 employees and 52 weeks and the effect of Lagrangian relaxation is more clear for bigger data sets. The hill climbing algorithm had a consistent and low computation time, but the objective function value differs considerably from the exact solution and resulted in most cases a difference of more than 10 percent.