Tournament scheduling issues

Question

Currently I'm working on a 1 day tournament scheduling application. Since, each year the number of participating teams is different, I want to automate the scheduling.

Teams are split in 2 groups. each group plays a single round robin tournament. I managed to generate all the games to play, but I'm struggling with the planning.

additionally, the teams need to compete in 3 different sport disciplines, with each a dedicated field. (e.g. football field, volleybal field)

Given: - games to play - fields per sport + available timeslots per field (slots of +-15 minutes)

assumptions: - timeslots are not limited - 1 field per sport available - schedule doesn't need to be balanced in 1st iteration

problems: - the quality of my schedule is not that good. in fact, not all timeslots are fully filled, even if there is a solution. the 'density' of my schedule also depends on the order of games processed.

code snippet:

        //algo
        while (_games.Any())
        {
            gameToPlan = _games.Dequeue();

            var occupiedHomeTeam = GetTimeslotsOccupiedByTeam(gameToPlan.HomeTeam);
            var occupiedAwayTeam = GetTimeslotsOccupiedByTeam(gameToPlan.AwayTeam);
            var occupiedTeams = occupiedHomeTeam.Union(occupiedAwayTeam);

            var availableFields = fields.Where(f => f.AllowedSports.Contains(gameToPlan.Sport))
                                        .Where(f => f.Timeslots.Any(t => t.Game == null &&
                                                                        !t.Occupied &&
                                                                        !occupiedTeams.Any(oc => oc.Start == t.Start &&
                                                                                                 oc.End == t.End)));
            if (!availableFields.Any())
            {
                _games.Enqueue(gameToPlan);
                continue;
            }
            var field = availableFields.First();
            var timeSlots = field.Timeslots.Where(t => t.Game == null && 
                                               !t.Occupied && 
                                               !occupiedTeams.Any(oc => oc.Start == t.Start && 
                                                                        oc.End   == t.End))
                                    .OrderBy(t => t.Start);
             if (!timeSlots.Any())
             {
                _games.Enqueue(gameToPlan);
                continue;
            }   
            var ts = timeSlots.First();
            ts.Occupied = true;
            ts.Game = gameToPlan;
            gameToPlan.Timeslot = ts;
            gameToPlan.TimeslotId = ts.Id;
            _uow.Save();
        }

Can anyone give me an overview of approach, available algorithms,...?

thanks in advance

Answer 1

Regarding your problem, this is clearly a discrete optimization problem. For tournament/timetable problems, you should think about using constraint programming solvers. You need to be familiar with linear/integer programming to do so. For example you can use Choco solver which is in Java. Fun fact is that the last question on their forum is related to tournament scheduling.