Advanced search

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

David Van Bulck (UGent) and Dries Goossens (UGent)
Author
Organization
Abstract
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).
Keywords
Time-relaxed sports scheduling, Fix-and-relax, Evolutionary algorithms

Citation

Please use this url to cite or link to this publication:

Chicago
Van Bulck, David, and Dries Goossens. 2018. “Scheduling Time-relaxed Double Round-robin Tournaments with Availability Constraints.” In 6th Student Conference on Operational Research (SCOR18), Abstracts.
APA
Van Bulck, D., & Goossens, D. (2018). Scheduling time-relaxed double round-robin tournaments with availability constraints. 6th Student Conference on Operational Research (SCOR18), Abstracts. Presented at the 6th Student Conference on Operational Research (SCOR18).
Vancouver
1.
Van Bulck D, Goossens D. Scheduling time-relaxed double round-robin tournaments with availability constraints. 6th Student Conference on Operational Research (SCOR18), Abstracts. 2018.
MLA
Van Bulck, David, and Dries Goossens. “Scheduling Time-relaxed Double Round-robin Tournaments with Availability Constraints.” 6th Student Conference on Operational Research (SCOR18), Abstracts. 2018. Print.
@inproceedings{8578010,
  abstract     = {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).},
  author       = {Van Bulck, David and Goossens, Dries},
  booktitle    = {6th Student Conference on Operational Research (SCOR18), Abstracts},
  keyword      = {Time-relaxed sports scheduling,Fix-and-relax,Evolutionary algorithms},
  language     = {eng},
  location     = {Nottingham (UK)},
  title        = {Scheduling time-relaxed double round-robin tournaments with availability constraints},
  year         = {2018},
}