2

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

Visually, where 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.

  • I think you are too pessimistic about the usefulness of a scoring function, see my answer. – Doc Brown Apr 12 '18 at 11:05
1

A simple way of approaching this in a pragmatic manner could be:

  • allow games to be scheduled initially on slots violating the contraints, so you can start with a schedule where each game gets a slot

  • afterwards run an evolutionary algorithm like simulated annealing to minimize a score which measures the "degree of constraint violation".

This approach requires a simple modification operation, which could be something like exchanging the content of two randomly chosen slots.

Measuring the degree of violation should be quite simple in your case: just sum up the waiting hours of each team which are over the allowed maximum, or under the allowed minimum. If that sum reaches 0, your algorithm found a solution and can be stopped immediately.

This is not a 100% algorithm, not guaranteeing that in case there is a solution, it will always find it. However, I would expect if there are several possible solutions, chances are high this algorithm finds one where the score reaches zero (which means all constraints are fulfilled). If the algorithm does not find a solution within a reasonable amount of time, there are probably no solutions, or only so few that they are actually hard to find.

But for your case, this may be good enough, SA is actually very easy to implement, and it can be probably extended by all kinds of constraints in case it is necessary.

There is also a simple improvement which might help: whenever the algorithm finds a score which is lower than the ones found before, run do a greedy "hill climbing" search, by trying out all pairs of slots and check if there a swap of those slots can reduce the score further.

  • Thank you very much, I will have a look at it. Hopefully I understand how to implement this approach in my current algorithm. And indeed, even though a perfect solution would be ideal, finding a good enough result is the current goal. – dabadaba Apr 12 '18 at 11:09
  • Although I'm realizing if I do it this way, we could end up with a schedule with games violating the wait time constraint right? This shouldn't happen. Unscheduled matched are acceptable, but ones that break the rules are not. – dabadaba Apr 12 '18 at 11:11
  • @dabadaba: sure, as I already wrote, you use schedules which are not an allowed solution (and if you are unlucky, the algorithm does not find a better one). The idea I presented here makes use of the fact even such schedules might be gradually improved until the constraints all hold. If the algorithm does not find such a solution, chances are high there is no such schedule. – Doc Brown Apr 12 '18 at 11:29
  • ... the other advantage here is: this algorithm is quite simple because it does not have to deal with unscheduled games, all games are always scheduled. If in case there is no solution (which means the algorithm returns you an invalid one), you can always unschedule games afterwards (maybe in a greedy fashion) until the constraints hold for the scheduled ones. – Doc Brown Apr 12 '18 at 11:35
  • Alright I have read that article. I am having trouble trying to understand how it works. In my case the initial state would be the calculated schedule without the wait time constraint. In each iteration we pick a random neighbor which I assume in my scenario would be swapping the slots of any two random games (I also assume that if this swap breaks any other constraint, this neighbor is not valid). Then we have a function that evaluates the schedule; as you said, this would be the total sum of time, for each team for instance, over the maximum and under the minimum... – dabadaba Apr 12 '18 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.