 |
Programmierpraktikum Sportligaplanung SS 06 |
Termine:
| Programmierpraktikum (P4): |
| Mi | 14:15-15:45 | Raum 69/E23 |
Inhalt:
Es sollen verschiedene Teilprobleme im Bereich der Sportligaplanung betrachtet
und Algorithmen hierfür implementiert werden.
Das Grundproblem für die Planung einer Sportliga lässt sich wie folgt
formulieren:
Gegeben ist eine Liga bestehend aus 2n Mannschaften, wobei jede Mannschaft
genau k mal gegen jede andere spielen soll. Um diese n(2n-1)k Spiele
auszutragen, stehen (2n-1)k Runden (Spieltage) zur Verfügung, wobei in
jeder Runde jede der 2n Mannschaften genau ein Spiel austragen soll. Für
jede Runde r=1,...,(2n-1)k muss somit festgelegt werden, welche Mannschaften
i,j aus {1,...,2n} in dieser Runde gegeneinander spielen und für jedes
dieser Spiele i-j, ob es bei Mannschaft i (als Heimspiel für i) oder bei j
(als Auswärtsspiel für i) stattfindet.
Bei der Spielplanung gibt es im Allgemeinen eine sehr große Anzahl von
Nebenbedingungen die berücksichtigt werden sollen (z.B. möglichst
gleichmäßige Verteilung von Heim- und Auswärtsspielen, Unverfügbarkeiten
von Mannschaften bzw. Spielstätten zu bestimmten Terminen, möglichst
gleichmäßige Verteilung von interessanten Spielpaarungen über den
gesamten Saisonverlauf, Sicherheits- und Medienaspekte, usw.).
Die zur Lösung dieser Probleme angewandten Techniken sind z.B.
graphentheoretische Überlegungen, Methoden für ressourcenbeschränkte
Projektplanungsprobleme, Constraint Propagation, Lineare Programmierung,
Lokale Suche, Genetische Algorithmen.
Ziele des Praktikums:
- Erwerb theoretischer Kenntnisse im Bereich Sportligaplanung
- Verbesserung der Programmierfähigkeiten
- Arbeiten mit Softwarepaketen (Constraint Propagation, Lineare
Programmierung)
- Arbeiten im Team an einem größeren Softwareprojekt
(Projektarbeit, Qualitätssicherung, Reviews, Programmierrichtlinien, Testen,
Fehlersuche, Dokumentation)
- Präsentation von Kurzvorträgen
- Unterstützung der aktuellen Forschung in der Arbeitsgruppe
Vorkenntnisse:
Programmierkenntnisse in Java.
Kenntnisse aus den Vorlesungen Graphenalgorithmen, Optimierung oder
Scheduling sind nützlich, aber nicht notwendig.
Schein:
Voraussetzung für den Erwerb eines Scheins zur Veranstaltung ist die
regelmäßige aktive Teilnahme am Praktikum, die Mitarbeit an der Programmierung
und Dokumentation und das Halten eines Kurzvortrages.
Teilnehmer:
Teilnehmen können alle interessierten Studierende aus den Studiengängen
Mathematik, Angewandte Systemwissenschaft und Cognitive Science.
Insbesondere können
im Anschluss an das Praktikum Bachelor- oder Diplomarbeiten vergeben werden.
Literatur:
- Bartak, R.:
Online Guide to Constraint Programming
- Bartak, R.:
Constraint propagation and backtracking-based search,
First international summer school on CP, September 11-15, 2005, Maratea, Italy.
- Drexl, A., Knust, S. (2004):
Sports league scheduling: graph- and resource-based models,
Osnabrücker Schriften zur Mathematik, Reihe P, Nr. 255,
to appear in Omega.
- Easton, K., Nemhauser, G., Trick, M. (2004):
Sports scheduling,
in: J.T. Leung (ed.): Handbook of Scheduling, CRC Press, 52.1-52.19.
- Knust, S., von Thaden, M. (2005):
Balanced home-away assignments,
Osnabrücker Schriften zur Mathematik, Reihe P, Nr. 262.
- Miyashiro, R., Iwasaki, H., Matsui, T. (2003):
Characterizing feasible pattern sets with a minimum number of
breaks,
in: E. Burke and P. De Causmaecker (eds.), PATAT 2002, Lecture Notes in
Computer Science 2740, Springer, 78-99.
- Regin, J.-C. (1999):
Minimization of the number of breaks in sports scheduling problems
using constraint programming,
in: DIMACS Workshop on Constraint Programming and Large Scale Discrete
Optimization.
- Urrutia, S., Ribeiro, C.C. (2006):
Maximizing breaks and bounding solutions to the mirrored traveling
tournament problem, Discrete Applied Mathematics 154, 1932-1938.
- Trick, M.A. (2001):
A schedule-then-break approach to sports timetabling,
in: E. Burke and W. Erben (eds.), PATAT 2000, Lecture Notes in
Computer Science 2079, Springer, 242-252.