How computers help to find the optimal schedule
Some problems look easier than they are. A famous case in point is the travelling salesman who needs to visit a number of different cities and is looking for the shortest route that takes him to all the cities. The solution is simple: go through all the different possibilities and then choose the best route. This simplicity is deceptive, however, since the number of possible solutions increases very rapidly with the number of cities. Just 15 cities leave you with 43 billion possible solutions to try out, and the figure reaches 645 billion with 16 cities. This will quickly take even the most powerful computer to the limits of its computational capacity. In computer science, the example of the traveling salesman falls into the category of the so-called “NP-hard” problems, a class of problems that involves a high degree of computational complexity. Another - and socially highly relevant - example of a problem that comes within this group is workforce shift scheduling, where the number of possible solutions also reaches dizzying heights very quickly. In the context of a project funded by the Austrian Science Fund FWF, a research group led by the computer scientist Nysret Musliu from TU Wien has now tried to find particularly efficient algorithms for such complex computational tasks.
Different problems
The topic actually consists of a whole series of different questions, Musliu explains: “The planning of duty rosters for nurses is a typical case of shift scheduling. A problem of a completely different nature is break planning, something that is needed, for instance, in call centres or air traffic control rooms, where there are legally prescribed breaks.” Musliu mentions the planning of timetables in schools as another complex example of scheduling. The common denominator of all these problems is that they belong to the “NP-hard” category, i.e. their computation is of similar complexity to the itinerary of the travelling salesman. In addition, using IT methods is not yet really common practice in this context: “Actually, these schedules are very often drawn up by hand. There are people who are very good at making them. But when it comes to larger companies and finding the best solution, it’s almost impossible to do manually”, the researcher reports in the interview with scilog. Consequently, researchers have for some time been taking an interest in these issues which frequently arise in working life and which are summarised under the umbrella term “General Employee Scheduling” or “GES” in short. “Of course, many questions from this sphere have already been described in science literature. There are good solutions for certain areas of application to the end”, notes Musliu. However, the details of some of these problems, such as employee scheduling at airports or drawing up school timetables, are subject to different regulations in different countries. Therefore, a new approach is needed if one wants to avoid having to start from scratch on every occasion.
Describing the general problem
“We aimed not only at solving individual problems, but wanted to go further and offer a cover-all solution for the GES problem as such”, says Musliu. According to Musliu, the team has more or less taken a step back from applied to basic research. “We analysed various problems found in the literature and tried to develop a general format that covers all of these sub-problems.” Although the results are the outcome of a basic research project, the solutions found are close to practice: “In principle, practical problems can be solved immediately in this way; the tasks only have to be converted into this new format.” This new framework also helps companies to take a reverse approach to the problem. The aim is no longer to distribute employees according to a specific shift model, but to ask which scheduling plan is the best option for a specific company.
Sudoku as a model for time planning
In order to test the new approaches, Musliu and his group have addressed a number of specific questions within the framework of the project. One of the things they developed is methods for solving Sudoku puzzles. “There are certain similarities with Sudoku, although Sudoku is much easier. But we were able to show that certain methods that are good for Sudoku can also produce good results in GES”, says Musliu. “We have compared our method with previous benchmarks in the scientific literature and were able to show that we can achieve better results in certain areas. In the case of a problem known as ‘torpedo scheduling’, which originates from the steel industry and involves the routing of hot metal across plants in so-called torpedoes, Lucas Kletzander, a master student involved in the project, won an international competition for coming up with the best algorithm.
Starting point for new research
The project started in 2012 and was originally scheduled for three years, but was then extended to five years at no extra cost and was completed last year. The results provided the starting point for a recently approved Christian Doppler Laboratory for Artificial Intelligence and Optimization for Planning and Scheduling, headed by Musliu. One part of that research unit deals with more complex employee scheduling problems and engages in closer co-operation with partners from industry. Nysret Musliu emphasises that “the FWF project has been very helpful in gaining a foothold in this field”.
Personal details Nysret Musliu is a computer scientist at Technische Universität (TU) Wien. His research interests include artificial intelligence, machine learning and optimisation, as well as planning and scheduling.
Publications
