Multi-League Sports Scheduling with Team Interdependencies: An Optimization Model

Davari et al. propose an algorithm that minimizes the number of capacity violations of a schedule, which does not respect team interdependencies, though [7]. For the special case of all teams of a club playing at home in the same weeks without allowing capacity constraint violations, they prove this version of the problem to be $𝒩𝒫$-complete via a polynomial reduction from vertex coloring. Li et al. extend this work by a computational study [22], a construction and improvement heuristic that minimizes constraint violations, and a multi-objective approach minimizing both traveling distances and constraint violations [23].

Other approaches rather aim at creating an optimal schedule for just a few divisions. Schönberger solves the scheduling problem on the level of single matches by means of mixed-integer programming, focusing on the optimization of player substitution opportunities [30, 31]. A computational study shows that solving the mixed-integer programming involves large efforts even for small instances. Creating optimal schedules for single (professional) leagues is a well-addressed topic in prior work [24, 9, 11, 2, 19, 34]. Further research concentrates on scheduling sports competitions based on other objectives, such as balancing and minimizing breaks [8, 26, 14, 3, 18, 13, 25], traveling distances [16, 10, 29, 15], required venues [32], scheduling matches in specific rounds [5], or introducing additional matches [20, 6].

To the best of our knowledge, none of the existing approaches aims at scheduling a large number of interdependent divisions, respecting both capacity constraints, team interdependencies and constraints from super-ordinate schedules.

In this paper, we address the identified research gap by extending the definition of the multi-league sports scheduling problem to take team interdependency constraints (which also have implications on the venue utilization) and constraints from super-ordinate schedules into account. The optimization goal is to minimize the overall number of deviations in actual and required schedules, whereby those are guaranteed to be at least similar for all teams. Thereby, the problem definition comes closer to the requirements of sports scheduling in practice. We prove the extended multi-league sports scheduling problem to be $𝒩𝒫$-complete by a polynomial reduction from 3-SAT, and underpin the practical applicability of our approach by scheduling German table tennis leagues of a certain district. Further experiments on generated data demonstrates the scalability of our approach.

The remainder of this paper is organized as follows: An overview of the problem domain and the proposed solution approach is provided in Sect. 2. The multi-league sports scheduling problem is formally defined in Sect. 3, before an integer linear program is constructed based on this definition in Sect. 4. The decision problem corresponding to multi-league sports scheduling problem is proven to be $𝒩𝒫$-complete in Sect. 5, and a practical implementation is sketched in Sect. 6. We apply our implementation to a real-world case study and evaluate its runtime performance in Sect. 7, before Sect. 8 summarizes the main results and sketches promising directions for future research.

The basic concepts of the problem definition comprise clubs, teams, and divisions. Each team belongs to exactly one club and one division.

An example instance with 18 teams allocated to three divisions is shown in Tab. 1 (ignoring the columns “Key” and “WS” for the moment). Each team is represented by the name of its club, while most clubs have teams in multiple divisions. It is also possible that multiple teams of a club play in one division, such as two teams of “Austin” in Men’s division.

double round robin tournaments comprise multiple rounds, which are usually scheduled in consecutive weeks. To create schedules, grids are used that determine which matches are scheduled in which week.

An example grid for a division of up to six teams is depicted in Tab. 2. It can be read as follows: 1 - 6 in the first row of week W1 means that team 1 plays team 6 at home. The matches in W6 - W10 correspond to those in W1 - W5, swapping the home and away teams.

The numbers in a grid serve as placeholders for the teams of a division. In the following, these numbers are denoted as keys (an example allocation of teams to keys can be found in the respective columns of Tab. 1):

To ensure that venues can be shared between two teams, it is important that they do not play at home in the same week. Grids have opposite pairs of keys, e.g., $1/4$, $2/5$ and $3/6$ in the example of Tab. 2. By choosing the keys for interdependent teams accordingly, it can be assured that at most one team plays at home each week.

Using such standardized grids, team interdependencies can be defined across multiple divisions. For grids of different sizes (which are necessary for divisions with different numbers of teams), there must be a notion of which keys correspond to each other, i.e., for which keys home games are scheduled in the same weeks. Keys fulfilling this property are denoted as parallel keys:

In contrast to professional leagues, in which matches are often shown in the media, the order of matches or the allocation of matches to certain weeks is not that critical for amateur leagues. It is far more important for clubs to define which teams should have their matches at home in opposite weeks (such that they can share one venue) or in parallel weeks (such that players can attend matches of two teams, given they do not take place on the same day).

In order to express this requirement, week schemes are used: Teams of a club that follow the same week scheme play at home in the same weeks, whereas teams that follow an opposite week scheme play at home in opposite weeks. There is also a distinguished week scheme $W_0$ to express that there are no dependencies to other teams. This can happen if a club has only one team, or the capacity of its venue(s) is sufficient to host matches of all teams at the same time (without this being an explicit requirement for the club).

The “WS” column of Tab. 1 provides examples for week schemes. The women’s and youth teams of Detroit follow opposite week schemes ${\check{W}}_1$ and ${\widehat{W}}_1$, whereas the week scheme $W_0$ for the men’s team indicates that there are no interdependencies to other teams. The women’s and men’s teams of El Paso follow independent week schemes ${\check{W}}_2$ and ${\check{W}}_1$, meaning that there are no interdependencies to each other, but potentially to other teams of the club.

Apparently, each key can only be assigned once per division (the constraint will be specified formally in Def. 12). Without weakening the requirement for opposite and parallel keys, instances of realistic size are barely feasible. A simple example can be found in the men’s division of Table 1: Austin and Austin II follow the same week scheme ${\widehat{W}}_1$, which means that they should be assigned the same key, which would directly lead to an infeasible system (which was already pointed out by Davari et al. in prior work [7]).

To overcome this non-exceptional problem, similar keys are defined for grids, meaning that only a few deviations from the intended sequence of home and away matches occur. In Tab. 2, one can observe that the keys $1$ and $6$ only differ in two weeks (W1 and W6), just as the keys $3$ and $4$. Therefore, keys $1/6$ and $3/4$, respectively, can be considered as similar keys that can be assigned in case the required key is not available.

In this subsection, we elaborate on the assignment of keys to clubs (one key per week scheme), and based on that, the assignment of keys to teams. Before keys can be assigned to week schemes of clubs, it must be clear to which grid the keys refer. Regarding teams, the grid is predefined by the divisions the teams play in, whereas such an automatism does not exist for clubs. Therefore, a reference grid is defined for each pair of opposite week schemes.

Based on the reference grid, keys can be assigned to week schemes of clubs according to Def. 9. Note that opposite keys must be assigned for opposite week schemes, which is formalized in Eq. 6.

As mentioned in Sect. 1.1 and 1.2, the scheduling task is usually distributed between multiple schedulers for different levels (e.g., national, federal state and regional level). Despite having a potentially negative impact on the solution quality, this approach is indispensable to cope with the number of divisions that have to be scheduled, especially when schedules are created mostly manually. Usually, schedules for super-ordinate leagues are created first, and impose constraints for scheduling sub-ordinate leagues. In particular, key assignments for clubs that have teams in super-ordinate leagues are fixed in advance:

The assignment of keys to teams is specified in Def. 11.

In the remainder of this section, a connection will be established between the key assignments of clubs and their respective teams. As mentioned beforehand, we must also ensure that each key is unique within a division, i.e., is assigned to at most one team per division, which is specified in Def. 12.

A central requirement for clubs is that – while minor deviations are allowed – teams that follow the same week scheme are assigned keys in a way that they play at home in the same weeks. Therefore, the keys of clubs and their teams must be aligned with respect to the different week schemes. In particular, each team’s key must be similar to its club’s key of the respective week scheme, which is specified in Def. 13.

Using the previous sets of constraints, we define satisfiability for problem instances of multi-league sports scheduling problem in Def. 14.

While it is necessary in practice to assign similar keys in case the required key is unavailable, this should be avoided whenever possible, as it can, e.g., reduce the number of capacity violations. Thus, the optimization goal is to minimize the number of teams that receive a key that is not parallel to the key which is assigned to their club for the week scheme the team follows. The resulting optimization problem is specified in Def. 15.

We applied our approach to create the schedules for a district of the West-German Table Tennis Association for three seasons [36]. The characteristics of the three input instances are summed up in Tab. 5. They differ with respect to the number of teams, clubs, and divisions involved. It can be further observed that for the majority of teams, dependencies were defined (i.e., week schemes other than $W_0$ according to Def. 6 were used). Five week schemes were available for the clubs as predefined by the West-German Table Tennis Association. For a few clubs, key assignments were fixed by the schedulers of super-ordinate levels according to Def. 10.

For all three instances, the application returns an optimal solution within a few seconds in all ten test runs. It can be concluded that the implementation is suitable for solving instances of realistic size. Limitations will be investigated in the following performance evaluation.

As the implementation comprises an exact approach to determine the scheduling solution, the runtime is expected to increase exponentially for larger inputs. Other characteristic parameters (cf. Tab. 5) may also have an impact on the runtime and solution quality.

We compared our implementation to the approach of Li et al. [22], who determine optimal schedules based on capacity constraints without defining interdependencies between teams. They implemented both a heuristic and an exact approach and applied them on instances with 3,5 and 10 divisions with different numbers of teams (cf. Tab. 7). All instances were made publicly available [21], such that we were able to implement an adapter for their file format and run experiments on the same input data.

Optimal results could be determined in all 60 test runs. The median values of the measured runtimes for 10 instances which were constructed with equal characteristics are shown in Tab. 7. Our implementation performs relatively well compared to the heuristic approach and clearly outperforms the exact approach. Interestingly, our approach takes most time for the instances with only three divisions, which can be explained by the reduced possibilities to avoid conflict situations.

The exact approach of Li et al. and our approach share the optimization goal (minimizing constraint violations) and the general setting (teams play double round robin tournament tournaments in several groups, clubs’ venues have capacity constraints). The main reason for the differences in runtime performance is that the search space constructed by Li et al. is much larger, as they use decision variables for every single match, while our approach operates on the level of assigning keys to teams. Li et al. can potentially further reduce the number of constraint violations via a sophisticated allocation of bye weeks to teams, or by stretching the schedule of smaller divisions to more weeks than necessary. However, our approach allows clubs to define that two specific teams should play in turn or in parallel, while Li et al. solely aim at minimizing the number of capacity constraint violations.

Revisiting our research questions, it can be stated that our approach is suitable to be applied on real-world instances (Q1). Its scalability is mainly restricted by the number of divisions and teams involved (Q2), but performs well in comparison to existing approaches (Q3).

The conducted experiments have a few limitations to be discussed in the following. Due to the lack of real-world examples, all instances used in the experiments of the performance evaluation (Sect. 7.2) were artificially generated. The time-out was set to a rather low value, which was indeed sufficient to identify whether modifying a characteristic parameter increases or decreases runtime and solution quality. Using more than one solver for the experiments and varying the characteristic parameters in combination could give more reliable insights into performance bottlenecks.

Furthermore, the differences with respect to runtime and solution quality often varied noticeably between test runs of the same configuration (cf. Appendices A.1 and A.2). This implies that the grouping of teams into divisions has a major impact on the problem complexity, which was not covered by the performance analysis. Usually, teams are not distributed randomly over the groups, but according to regional aspects. This means that the generated instances are probably harder to solve than practical use cases.

Finally, the presented evaluation was purely technical, whereas the validity of the applied quality metrics should be evaluated in the course of a user study.