Abstract

The personnel scheduling problem is a well-known NP-hard combinatorialproblem. Due to the complexity of this problem and the size of the real-worldinstances, it is not possible to use exact methods, and thus heuristics,meta-heuristics, or hyper-heuristics must be employed. The majority ofheuristic approaches are based on iterative search, where the quality ofintermediate solutions must be calculated. Unfortunately, this iscomputationally highly expensive because these problems have many constraintsand some are very complex. In this study, we propose a machine learningtechnique as a tool to accelerate the evaluation phase in heuristic approaches.The solution is based on a simple classifier, which is able to determinewhether the changed solution (more precisely, the changed part of the solution)is better than the original or not. This decision is made much faster than astandard cost-oriented evaluation process. However, the classification processcannot guarantee 100% correctness. Therefore, our approach, which isillustrated using a tabu search algorithm in this study, includes a filteringmechanism, where the classifier rejects the majority of the potentially badsolutions and the remaining solutions are then evaluated in a standard manner.We also show how the boosting algorithms can improve the quality of the finalsolution compared with a simple classifier. We verified our proposed approachand premises, based on standard and real-world benchmark instances, todemonstrate the significant speedup obtained with comparable solution quality.

 

Introduction (beta)

None

 

Conclusion (beta)

None