比赛安排问题

Question

目前我正在开发一个为期 1 天的锦标赛日程安排应用程序。因为每年参赛队伍的数量都不一样，所以想把排程自动化。

团队分为 2 组。每组进行单循环赛。我设法生成了所有要玩的游戏，但我正在为计划而苦苦挣扎。

此外，团队需要参加 3 个不同的运动项目，每个项目都有一个专门的领域。（例如足球场、排球场）

鉴于： - 玩游戏 - 每项运动的场数 + 每场可用的时间段（+-15 分钟的时间段）

假设： - 时间段不限 - 每项运动 1 个场地 - 第一次迭代不需要平衡进度

问题： - 我的日程安排质量不是很好。事实上，即使有解决方案，也并非所有时隙都已满。我的日程安排 'density' 还取决于处理游戏的顺序。

代码片段：

        //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();
        }

谁能给我概述一下方法、可用的算法……？

提前致谢

Answer 1

关于你的问题，这显然是一个离散优化问题。对于 tournament/timetable 问题，您应该考虑使用 约束规划 求解器。您需要熟悉线性/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 与锦标赛安排有关。

比赛安排问题

Tournament scheduling issues

algorithm

tournament