A Column Generation Method for Minimization of Shift Costs at an Airport

Abstract: This thesis addresses the problem with minimizing the cost of labor shifts for the workforce at an airport. The cost of idle time is specifically a difficulty for the employer. With idle time means time that it is not a break at the same time as there is no work task to be performed. This originates from big variations in the traffic flow which lead to the workload to be characterized by peaks and valleys. This situation has increased the demand among airport service companies for efficient staff schedules. Even small reductions of the idle time mean considerable savings for the employer. This thesis uses authentic data from an international airport in Europe. The method used to solve the task is an algorithm based on column generation. The mathematical model used has a high flexibility and handles breaks, multi-activity, such as boarding, and non-splittable tasks, in other words tasks that has to be performed by one employee in one shift. The subproblem is a binary integer program that generates feasible shifts following certain rules and is solved using a commercial solver. The results have shown possible improvements. In the best test scenario, the idle time is reduced to 4.7 percent of the total worktime. There is room for improvement of the model and the results. One possible improvement is to reduce the running time of the program which also could lead to improved results.