Scheduling time-relaxed double round-robin tournaments with availability constraints

In the time-relaxed double round-robin problem with availability constraints, we are given a set of slots and a set of teams that meet one another a fixed number of times. Furthermore, each team provides slots in which it can host a game, and slots in which it cannot play at all. Since time-relaxed schedules contain (many) more slots than there are matches per team, the number of rest days between two consecutive matches of the same team can vary considerably. Ideally, a team has at least R days rest between two consecutive matches in order to avoid injuries. Hence, we apply a penalty each time a team has less than R days between two consecutive matches; this penalty increases as the number of rest days decreases. The goal is to find a schedule that minimizes the total penalty. To solve this problem, we first propose fix-and-relax decomposition methods based on the teams as well as on time-intervals. Basically, fix-and-relax methods initially solve a relaxed IP-formulation and then gradually reoptimize the model with the integrality constraints enabled for a small subset of variables. The method then fixes the variable values of the selected group and repeats the procedure until all variables have an integral value. Second, we propose a genetic algorithm enhanced with an improvement heuristic that sequentially solves a transportation problem which (re)schedules all home games of a team. For numerous artificial and real-life instances, these heuristics generate near-optimal schedules using considerably less computational resources compared to integer programming (Gurobi)