Scheduling is a complicated matter, especially in the industry: Which machines should perform which tasks in which order – so that everything is finished on time and neither time nor resources are wasted? Such tasks are challenging problems in computer science. Usually, it’s not possible to calculate every conceivable possibility to determine the most efficient variant – cleverly thought-out solutions are needed.

Felix Winter is developing algorithms for such scheduling tasks at TU Wien Informatics’ Institute of Logic and Computation as part of the Christian Doppler Laboratory for AI and Optimization in Planning and Scheduling. Winter applies abstract concepts of theoretical computer science on practical use cases in the industry: his ideas are now being applied to the work scheduling of paint shops and the production of dentures. For his outstanding achievements, Felix Winter has been awarded TU Wien’s Ressel Prize on October 14, 2022.

Simple and complex problems

In what order should an industrial robot paint car parts? This question is more complex than you might think: “There are a whole series of conditions that must be met simultaneously,” says Felix Winter. Specific numbers of car parts have to be painted in certain colors by a particular time. Every color change costs time, so objects of the same color have to be painted sequentially whenever possible. In addition, some colors can’t be used after one another. If you want to take all this into account and create the most efficient schedule possible for the next day, you quickly reach human limits.

Letting the computer search for the optimal sequence is challenging in a different sense: “In computer science, a distinction is made between so-called P and NP problems,” explains Felix Winter. P problems are comparatively easy to solve – sorting playing cards, for example. The more playing cards you have, the longer it takes to sort them. But the number of necessary steps only increases with a certain power of the number of cards, e.g. with the square of the number of cards, depending on the sorting algorithm used.

NP problems are much more challenging because the number of necessary steps increases at least exponentially. Thus, you quickly need computing power that even the most advanced computers can no longer handle. “Scheduling tasks, such as creating a schedule for paint shops, are difficult NP problems,” says Felix Winter. “In practice, the number of possible production sequences is often higher than ten to the power of five hundred – compared to this, the number of atoms in our universe is tiny.”

Mathematical logic and heuristic methods

In some cases, formal logic can be used to let the computer find the optimal solution – similar to solving a Sudoku puzzle logically, without checking every possible number distribution. “For certain tasks, mathematically proving that the determined solution is the best one is possible,” says Felix Winter. “But there is a complexity threshold that can’t be surpassed this way.” Then you have to resort to so-called heuristic methods: One applies certain rules of thumb and basic assumptions, similar to what a human would do when creating a schedule. In doing so, you may not necessarily determine the very best solution, but at least a pretty good one – and in a manageable amount of time. “Adapting such methods to the specific task is often tricky,” Felix Winter points out. “It also requires human experience.” The parameters of the algorithms have to be chosen wisely, you have to use the appropriate methods, and you work with logic and artificial intelligence.

The research group of Prof. Nysret Musliu, Felix Winter’s doctoral supervisor, has a lot of experience with all these methods: “We not only investigate the scientific basis of such problems, but we want to use them for solving very specific tasks from industry,” Felix Winter explains. In addition to paint shops in the automotive industry, Winter investigated the production of dental prostheses. Prostheses pose surprisingly similar challenges – different colors are used, and efficiency can be increased through clever time planning.

The collaboration included MCP Algorithm Factory, a management consultancy and software development company that specializes in solving scheduling problems in the industry. “Scheduling methods will play an increasing role in the future,” Felix Winter is convinced. “After all, better planning always means more efficiency and less waste – both in terms of time resources and energy or raw materials.”

About Felix Winter

Felix Winter completed his master’s degree in computer science at TU Wien with honors in 2016. Along the way, he gained experience in the software industry and attended the Franz Schubert Conservatory in Vienna to learn jazz guitar – he is still active in a band. In 2017, he started his Ph.D. studies at TU Wien Informatics. On October 14, 2022, Felix Winter was awarded the Ressel Prize of TU Wien. The Ressel Prize of TU Vienna is awarded annually to outstanding young scientists and is endowed with € 13,000 – mainly entrusted for scientific research.

Curious about our other news? Subscribe to our news feed, calendar, or newsletter, or follow us on social media.