Minimization of the number of breaks in sports scheduling problems using constraint programming
Minimization of the number of breaks in sports scheduling problems using constraint programming
复制标题
使用约束规划最小化体育调度问题中的休息次数
DOI：
10.1090/dimacs/057/07
复制
发表时间：
1998
影响因子：
6.1
通讯作者：
Jean
中科院分区：
文献类型：
--
作者：
Jean
本文旨在展示约束规划对最小化运动调度问题中休息次数的兴趣。我们考虑偶数队的单循环赛问题。在这个问题中，我们有n支球队和n1个时间段，在每个时间段，每支球队必须在主场或客场与另一支球队进行比赛，这样每支球队在所有时间段内正好与另一支球队进行一次比赛。一个球队的休息时间是连续两场主场比赛或连续两场客场比赛。对于所考虑的问题，Schreuder已经证明了最小断裂数为n2。我们提出了一个使用约束规划的模型，该模型能够有效地证明这个结果。对于20支球队来说，这只需要0.61秒，而对于60支球队来说，这只需要不到1分钟。这样做的主要原因是使用了几个与强大的过滤算法相关联的全局约束。此外，该模型可以很好地适应于解决初始问题的一些变化，其中添加了新的约束，例如：对于每支球队来说，客场和主场比赛的数量必须平衡，禁止连续两次休息等。我们还能够找到并证明一些给定时间表的团队的最小休息次数。
This paper aims to show the interest of constraint programming for minimizing the number of breaks in sports scheduling problems. We consider single round-robin problems with an even number of teams. In such a problem we are given n teams and n1 periods and for each period each team has to play either at home or away game against another team such that every team plays every other team exactly once during all the periods. A break for a team is deened to be two consecutive home matches or two consecutive away matches. For the considered problem, it has been proven by Schreuder that the minimal number of breaks is n 2. We propose a model using constraint programming that has the capability to eeciently prove this result. For 20 teams this takes a mere 0.61s and for 60 teams it still takes less than 1 minute. The main reason for this is the use of several global constraints with which powerful ltering algorithms are associated. Moreover, this model is well adapted to solve some variations of the initial problem in which new constraints are added such as: for each team the number of away and home matches has to be balanced, it is forbidden to have two consecutive breaks, etc. We are also able to nd and prove the minimal number of breaks for some given timetables of teams.