Advanced search
2 files | 2.68 MB Add to list

Handling fairness issues in time-relaxed tournaments with availability constraints

David Van Bulck (UGent) and Dries Goossens (UGent)
Author
Organization
Abstract
Sports timetables determine who will play against whom, where, and on which time slot. In contrast to time-constrained sports timetables, time-relaxed timetables utilize (many) more time slots than there are games per team. This offers time-relaxed timetables additional flexibility to take into account venue availability constraints, stating that a team can only play at home when its venue is available, and player availability constraints stating that a team can only play when its players are available. Despite their flexibility, time-relaxed timetables have the drawback that the rest period between teams’ consecutive games can vary considerably, and the difference in the number of games played at any point in the season can become large. Besides, it can be important to timetable home and away games alternately. In this paper, we first establish the computational complexity of time-relaxed timetabling with availability constraints. Naturally, when one also incorporates fairness objectives on top of availability, the problem becomes even more challenging. We present two heuristics that can handle these fairness objectives. First, we propose an adaptive large neighborhood method that repeatedly destroys and repairs a timetable. Second, we propose a memetic algorithm that makes use of local search to schedule or reschedule all home games of a team. For numerous artificial and real-life instances, these heuristics generate high-quality timetables using considerably less computational resources compared to integer programming models solved using a state-of-the-art solver.
Keywords
Management Science and Operations Research, Modelling and Simulation, General Computer Science

Downloads

  • (...).pdf
    • full text (Accepted manuscript)
    • |
    • UGent only
    • |
    • PDF
    • |
    • 827.95 KB
  • (...).pdf
    • full text (Published version)
    • |
    • UGent only
    • |
    • PDF
    • |
    • 1.85 MB

Citation

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

MLA
Van Bulck, David, and Dries Goossens. “Handling Fairness Issues in Time-Relaxed Tournaments with Availability Constraints.” COMPUTERS & OPERATIONS RESEARCH, vol. 115, 2020.
APA
Van Bulck, D., & Goossens, D. (2020). Handling fairness issues in time-relaxed tournaments with availability constraints. COMPUTERS & OPERATIONS RESEARCH, 115.
Chicago author-date
Van Bulck, David, and Dries Goossens. 2020. “Handling Fairness Issues in Time-Relaxed Tournaments with Availability Constraints.” COMPUTERS & OPERATIONS RESEARCH 115.
Chicago author-date (all authors)
Van Bulck, David, and Dries Goossens. 2020. “Handling Fairness Issues in Time-Relaxed Tournaments with Availability Constraints.” COMPUTERS & OPERATIONS RESEARCH 115.
Vancouver
1.
Van Bulck D, Goossens D. Handling fairness issues in time-relaxed tournaments with availability constraints. COMPUTERS & OPERATIONS RESEARCH. 2020;115.
IEEE
[1]
D. Van Bulck and D. Goossens, “Handling fairness issues in time-relaxed tournaments with availability constraints,” COMPUTERS & OPERATIONS RESEARCH, vol. 115, 2020.
@article{8635985,
  abstract     = {Sports timetables determine who will play against whom, where, and on which time slot. In contrast to time-constrained sports timetables, time-relaxed timetables utilize (many) more time slots than there are games per team. This offers time-relaxed timetables additional flexibility to take into account venue availability constraints, stating that a team can only play at home when its venue is available, and player availability constraints stating that a team can only play when its players are available. Despite their flexibility, time-relaxed timetables have the drawback that the rest period between teams’ consecutive games can vary considerably, and the difference in the number of games played at any point in the season can become large. Besides, it can be important to timetable home and away games alternately. In this paper, we first establish the computational complexity of time-relaxed timetabling with availability constraints. Naturally, when one also incorporates fairness objectives on top of availability, the problem becomes even more challenging. We present two heuristics that can handle these fairness objectives. First, we propose an adaptive large neighborhood method that repeatedly destroys and repairs a timetable. Second, we propose a memetic algorithm that makes use of local search to schedule or reschedule all home games of a team. For numerous artificial and real-life instances, these heuristics generate high-quality timetables using considerably less computational resources compared to integer programming models solved using a state-of-the-art solver.},
  articleno    = {104856},
  author       = {Van Bulck, David and Goossens, Dries},
  issn         = {0305-0548},
  journal      = {COMPUTERS & OPERATIONS RESEARCH},
  keywords     = {Management Science and Operations Research,Modelling and Simulation,General Computer Science},
  language     = {eng},
  pages        = {23},
  title        = {Handling fairness issues in time-relaxed tournaments with availability constraints},
  url          = {http://dx.doi.org/10.1016/j.cor.2019.104856},
  volume       = {115},
  year         = {2020},
}

Altmetric
View in Altmetric