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, wh
...
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.