| Journal: | Publicaciones en ciencias y tecnología |
| Database: | PERIÓDICA |
| System number: | 000398648 |
| ISSN: | 1856-8890 |
| Authors: | Perdomo, Jorge1 Lara, Hugo1 |
| Institutions: | 1Universidad Centroccidental "Lisandro Alvarado", Decanato de Ciencias y Tecnología, Barquisimeto, Lara. Venezuela |
| Year: | 2013 |
| Season: | Jul-Dic |
| Volumen: | 7 |
| Number: | 2 |
| Pages: | 127-141 |
| Country: | Venezuela |
| Language: | Español |
| Document type: | Artículo |
| Approach: | Analítico |
| Spanish abstract | El problema de elaboración de calendarios deportivos ha centrado la atención de la comunidad de investigación de operaciones por la variedad de modelos y la complejidad computacional de las soluciones (ver por ejemplo Ribeiro (2010)). En torneos tipo Round Robin de ida y vuelta el calendario se propone asignando la etiqueta de local o visitante a cada equipo, en un itinerario preestablecido de manera que se minimice el recorrido total de los equipos durante el torneo. En términos de investigación de operaciones lo modelamos como un problema de optimización cuadrática binaria con restricciones lineales. Suzuka, Miyashiro, Yoshise, y Matsui (2005) lo tratan como uno de encontrar el corte mínimo con restricciones (Min-Res-Cut) en un grafo no dirigido, proporcionando una formulación de optimización combinatoria. En el presente trabajo estudiamos la estructura del problema de asignación local-visitante, y proponemos una simplificación de la formulación de optimización combinatoria. Resolvemos de forma exacta con una búsqueda exhaustiva instancias pequeñas del problema, y resolvemos de forma aproximada con una búsqueda aleatoria instancias mayores |
| English abstract | The sports scheduling problem has been center of attention in the Operational Research community due to their variety of models, and computational complexity of solutions (see for example Ribeiro (2010)). In a Round Robin tournament, the schedule is proposed by assigning a “home” or “away” labels to a preestablished itinerary, in a such way that the total distance traveled by the teams during the tournament is minimized. In terms of operation research, the problem is modeled as a binary quadratic programming problem with linear constraints. In Suzuka y cols. (2005) the problem is treated as a MIN-RES-CUT. In this work we study the structure of the home-away assignment problem, and propose a simplification of the combinatorial formulation. We solve exactly small instances of the problem with an exhaustive search, and also approximately solve larger instances with a random search |
| Disciplines: | Matemáticas, Ciencias de la computación |
| Keyword: | Matemáticas aplicadas, Programación, Investigación de operaciones, Combinatoria, Calendarización, Deportes, Problema de asignación local-visitante |
| Keyword: | Mathematics, Computer science, Applied mathematics, Programming, Operations research, Combinatorics, Scheduling, Sports, Traveling tournament problem |
| Full text: | Texto completo (Ver PDF) |
