Operating Hours Assistant
A system for design of shifts
The aim in this project was to develop efficient algorithms for the shift design problem. The algorithms should be able to find good solutions in most real cases in a reasonable amount of the time. The algorithms should be also included in the commercial product Operating Hours Assistant (OPA). OPA should include the appropriate interaction in relaxing the constraints and change of weighs of criteria.
Results of research
For shift design problem, we considered iterative solution methods. We proposed repair steps (moves) to explore the neighborhood of solutions for this problem. In order to generate the neighborhood and accept the solution for the next iteration, basic principles of the so called tabu search technique are used. However, while tabu search finds acceptable solutions for this problem, the complete exploration of the neighborhood (using all defined moves) during each iteration is very time-consuming. We proposed a new approach in combination with tabu search in order to make the search more effective. The basic idea is to exploit knowledge about the shift design problem during the search. Based on the temporal workforce of the current solution and given workforce requirements (distance of the current solution to the optimal solution with respect to most important criteria), selecting repair steps during each iteration is guided so that the repair steps that have a greater chance to improve the solution are used. As a result of this knowledge about the problem, the neighborhood is selectively explored during each iteration, which makes the search more effective. Furthermore, we propose an algorithm for generating a good initial solution, which further improves the effectiveness of the search. Computational results in a real life problems and in randomly generated problems) show the advantages of these ingredients. (for detailed description of algorithms see publications)
The iterative search methods were included in the commercial product called Operating Hours Assistant. This product is in use since early 2001 by the consultants of the XIMES GmbH and it has been successfully applied in several organization. The OPA is suitable for generation of shifts in different areas. It has been already used in call centers, hospitals etc. (screenshots of system)