An Improved Memetic Algorithm for Break Scheduling

In this paper we consider solving a complex real life break scheduling problem. This problem of high practical relevance arises in many working areas, e.g. in air traffic control and other fields where supervision personnel is working. The objective is to assign breaks to employees such that various constraints reflecting legal demands or ergonomic criteria are satisfied and staffing requirement violations are minimised.

In our previous work we proposed a memetic algorithm for the assignment of breaks. We improve in this paper the previous method by proposing a new memetic representation, a new crossover and selection operator, and a penalty system that helps to select memes that have a better chance to be improved by a local search. Our approach is influenced by various parameters, for which we experimentally evaluate different settings. The impact of each parameter is statistically assessed. We compare our algorithm to state of the art results on a set of existing real life and randomly generated instances. Our new algorithm returns improved results on 28 out of the 30 benchmark instances. To the best of our knowledge, these results constitute current upper bounds for the respective instances.