A Lagrangian approach for minimum cost single round robin tournaments

A Lagrangian approach for minimum cost single round robin tournaments

0.00 Avg rating0 Votes
Article ID: iaor20117147
Volume: 39
Issue: 3
Start Page Number: 718
End Page Number: 727
Publication Date: Mar 2012
Journal: Computers and Operations Research
Authors: ,
Keywords: scheduling, combinatorial optimization
Abstract:

Single round robin tournaments are a well known class of sports leagues schedules. We consider leagues with a set T of n teams where n is even. Costs are associated to each match and period. Since matches are carried out at one of the both opponents venues matches may be forbidden in certain periods due to unavailability of stadiums. The goal is to find a minimum cost tournament among those having no match scheduled infeasible. We employ a Lagrangian relaxation approach in order to obtain tight lower bounds. Moreover, we develop a cost‐oriented repair mechanism yielding a feasible tournament schedule to each solution of the relaxed problem.

Reviews

Required fields are marked *. Your email address will not be published.