In many a tournament players manage to enter the finals in two or three disciplines. This requires some scheduling in order to maximize rest times for these players. Does anyone know of a software or (better) an algorithm to perform this scheduling? My umpire software can already do this, but its approach is rather simple; it simply evaluates every possible order. For up to 10 matches, this is feasible, because there are only 3628800 possible orders of matches, and far fewer for the common match counts 8, 7, and 5. However, when multiple age groups come in play (the test case I had included 22 disciplines), and players can even play across age groups, the number of possible schedules quickly grows to far more than humanity's current computing capacity. I am currently considering a combination of: custom-built heuristics (for instance, put all matches of 3-match-players at the very start, and continue appending the matches to the schedule that promise the longest pauses) generic genetic algorithms (swap anything) constraint programming (assume all pauses are longer than 5 matches, and figure something out. Continue to increase pause length until no solution or near-solution is found). neural nets (as in I give up, let the AI figure it out) None of these seem particularly comforting when compared with the certainty and simplicity of the brute force approach.
In my study, we often uses Particle Swarm Optimization algorithm. At some case studies in my sector (electricity supply/demand or grid power control, in the presence of unpredictable renewable energy), PSO often shows best results compared to other algorithms, including genetic algorithm. But I cannot guarantee the same case for scheduling problem
I've heard about PEAST Algorithm used in workforce scheduling. My friend in Sweden told me about this algorithms. A paper of it: The PEAST algorithm - The key to optimising workforce management and professional sports league schedules (Int. J. Process Management & Benchmarking Vol.4 No.4 2014) Author: Kimmo Nurmi, Jari Kyngäs and Nico Kyngäs DOI: 10.1504/IJPMB.2014.065520 Abstract: This paper summarises our work with real-world workforce scheduling and professional sports league scheduling. Furthermore, the paper presents a computational intelligence method called the PEAST algorithm. The algorithm has been used to solve school timetabling problems, many different workforce management problems and several sports scheduling problems.
First of all, thank you very much for the answer! I am pleasantly surprised to get very good answers on this forum. Regarding PSO, if my understanding is correct, this algorithm does not really apply to discrete problems, especially not ones with such a small set of possible values per dimension. Even if dimensions are clumped together, I see no way to apply it.
