I am working on a sports scheduling algorithm with several different constraints, one (two) of them being a minimum and/or maximum wait time between games. Of the same team, that is.
So if Team Blue is scheduled at 4pm (finishes at 5pm) in Field 1, and we have a maximum wait of 3 hours and a minimum of 1, then its next game ought to be scheduled:
between 6pm and 8pm, or
between 12pm and 2pm
M is the scheduled match we are talking about and
X the eligible slots:
+------+------+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | 11am | 12pm | 1pm | 2pm | 3pm | 4pm | 5pm | 6pm | 7pm | 8pm | 9pm | +------+------+-----+-----+-----+-----+-----+-----+-----+-----+-----+ | | X | X | X | | M | | X | X | X | | +------+------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
This constraint is tricky because every time a new game is scheduled, two new limitations are posted: one for each team making up the game.
The scenario where this calendar scheduling algorithm is used is having a list of games (i.e. round-robin) that need to be assigned any of the available slots. A slot is made up of a field, a start date and an end date. An example competition would be:
Weekend Tournament: 8 teams playing a double round-robin (14 games each). The Club provides 3 fields and is open Saturday all day (9am-9pm) and Sunday morning (9am-14pm). Additional constraints may be posted.
The current scheduling algorithm works in a very non-complicated way: it iterates the list of matches and attempts to schedule it in the first eligible slot.
for game in games: for slot in slots: if eligible(game, slot): schedule(game, slot)
In practice the algorithm does more things, aiming at different targets, but this is the essence of the way it operates.
If not all games could be scheduled (due to constraints), an additional process is started to try to improve the result. Since these games could not be scheduled in open slots, we look at used slots. If any of these slots is eligible, we try to reschedule the other game currently occupying it, first looking at open slots, then at used slots (the process is repeated until a certain depth). If that other game is rescheduled, the former slot is now open and given to the unscheduled game.
Perhaps the pseudocode gives a better picture:
for unscheduled_game in unscheduled_games: for used_slot in used_slots: if eligible(unscheduled_game, used_slot) and (reschedule(used_slot.game, open_slots) or reschedule(used_slot.game, used_slots)): schedule(unscheduled_game, used_slot)
And that is about it. The point of this post is trying to figure out ways to try to handle the wait time constraint. It is a really punishing constraint, and is a huge detriment to the effectiveness of the algorithm.
What is the aim of this post? Looking for suggestions, known scheduling algorithms, anything that could help me work with the minimum/maximum wait time constraint.
I need to implement this solution on top of the existing algorithm, so constraint programming would not be a feasible solution (pun not intended) because it would require modelling and reformulating the problem entirely from scratch, and I don't have the resources for that.
Introducing a scoring function would not work either. Right now constraints work in a black-or-white type of way: either you pass them or you do not. There are no greys.
I would like to add that I have been trying ways to solve it myself, but none were successful. One of them is:
For each unscheduled game, we look at any eligible slot, ignoring the wait time constraint. Then we try to eliminate the "block" by rescheduling the games that are causing it. If we can reschedule all of them, the conflict disappears and the slot now becomes eligible for the game, effectively scheduling it. In pseudocode:
for unscheduled_game in unscheduled_games: for slot in slots: if eligible(unscheduled_game, slot, except=WAIT_TIME): conflicting_games = find_conflicts(unscheduled_game, slot, constraint=WAIT_TIME) if all([reschedule(g) for g in conflicting_games]): schedule(unscheduled_game, slot) break
But as I said, this is not very helpful. No improvement is observed whatsoever, because rescheduling the conflicts is very hard. I think this happens for the same reasons the unscheduled games could not be scheduled in the first place. The constraint block is too tight and too spread.
Lastly, I want to add that I am working in Python. Mentioning it in case this is relevant at all.