Seminar Sportliga-Planung SS 04

Termine:

Inhalt:

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 Seminars:

• Kennenlernen verschiedener Probleme und Modelle von Sportligaplanungsproblemen
• Kennenlernen verschiedener Methoden zur Lösung kombinatorischer Optimierungsprobleme
• Schriftliche Ausabeitung: einen wissenschaftlichen Text selbständig verstehen und strukturiert wiedergeben können (Vorbereitung für Examensarbeit); Recherche weiterführender Literatur
• Vortrag: einen wissenschaftlichen Vortrag ausarbeiten und vor einem kleinen Zuhörerkreis präsentieren können
• als Zuhörer: Wissen aus einem Vortrag erwerben können; kritisches Zuhören

Inhalt der einzelnen Termine:

1	07.04.04 Sigrid Knust	Organisatorisches, Einführung in die Thematik
2	DI 20.04.04 Niklas Hoppe	Ein grundlegendes graphentheoretisches Modell zur Sportligaplanung Werra, D. de (1981): Scheduling in sports, in: P. Hansen (Ed.), Studies on Graphs and Discrete Programming, 381-395.
3	DI 04.05.04 Natascha Helmich	Erweiterungen des graphentheoretischen Modells Werra, D. de (1988): Some models of graphs for scheduling sports competitions, Discrete Applied Mathematics 21, 47-65.
4	05.05.04 Florian Groß	Planung einer Basketballliga Nemhauser, G.L., Trick, M. A. (1998): Scheduling a major college basketball conference, Operations Research 46, 1-8. Henz, M. (2001): Scheduling a major college basketball conference-revisited, Operations Research 49, 163-168.
5	12.05.04 Konrad Diwold	Das Travelling Tournament Problem Easton, K., Nemhauser, G., Trick, M. (2001): The travelling tournament problem: description and benchmarks, in: Proceedings CP'01, Lecture Notes in Computer Science 2239, Springer, 580-585. Easton, K., Nemhauser, G., Trick, M. (2003): Solving the travelling tournament problem: a combined integer programming and constraint programming approach, in: E. Burke and P. De Causmaecker (Eds.), PATAT 2002, Lecture Notes in Computer Science 2740, Springer, 100-109. Anagnostopoulos, A., Michel, L., Van Hentenryck, P., Vergados, Y. (2003): A simulated annealing approach to the traveling tournament problem, Proceedings CPAIOR'03
6	19.05.04 Dennis Egbers	Planung eines Tennisturniers Della Croce, F., Tadei, R., Asioli, P.S. (1999): Scheduling a round robin tennis tournament under courts and players availability constraints, Annals of Operations Research 92, 349-361.
7	26.05.04 Alle	Allgemeine Seminar-Besprechung Rückblick auf die bereits gehaltenen Vorträge Wie halte ich einen guten Seminarvortrag? Was ist bei einer schriftlichen Ausarbeitung zu beachten?
8	09.06.04 Marianne Greve	Planung der deutschen und österreichischen Fussballliga Bartsch, T., Drexl, A., Kröger, S. (2002): Scheduling the professional soccer leagues of Austria and Germany, Report 557, Institut für Betriebswirtschaftslehre, Universität Kiel.
9	16.06.04 Kyoung-ho Park	Planung einer Eishockeyliga Costa, D. (1995): An evolutionary tabu search algorithm and the NHL scheduling problem, INFOR 33, 161-178.
10	DI 22.06.04 Martin Schneider	Planung eines Schachturniers Kujansuu, E., Lindberg, T., Mäkinen, E. (1999): The stable roommates problem and chess tournament pairings, Divulgaciones Matematicas Vol. 7, 19-28. Gusfield, D., Irving, R.W. (1998): The stable marriage problem, MIT Press (Chapter 4).
11	DI 29.06.04 Christian Fiekers	Planung einer Tischtennisliga Schönberger, J., Mattfeld, D.C., Kopfer, H. (2000): Automated timetable generation for rounds of a table-tennis league, Proc. of the 2000 Congress on Evolutionary Computation, 277-284.
12	07.07.04 Michael von Thaden	"First break, then schedule" 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.
13	FR 09.07.04 Gastvortrag: Jörn Schönberger	Memetische Algorithmen und die Lösung kombinatorischer Optimierungsprobleme mit Nebenbedingungen Schönberger, J., Mattfeld, D.C., Kopfer, H. (2004): Memetic algorithm timetabling for non-commercial sport leagues, European Journal of Operational Research 153, 102-116. Abstract
	Oleksandr Kolomiyets	"First schedule, then break" 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. Elf, M., Jünger, M., Rinaldi, G. (2003): Minimizing breaks by maximizing cuts, Operations Research Letters 31, 343-349.
	Maximus G. Haddad	Meisterschaftsproblem Bernholt, T., Gülich, A., Hofmeister, T., Schmitt, N., Wegener, I. (2002): Komplexitätstheorie, effiziente Algorithmen und die Bundesliga, Informatik Spektrum 16, 488-502.

Vorkenntnisse:

Schein:

Teilnehmer:

Insbesondere können im Anschluss an das Seminar Bachelor- oder Diplomarbeiten vergeben werden.

Literatur:

• oben angegebene Arbeiten
• D. Jungnickel (1987): Graphen, Netzwerke und Algorithmen, BI-Verlag
• P. Rechenberg (2003): Technisches Schreiben (nicht nur) für Informatiker, Hanser
• R. Bromme, R. Rambow (1993): Die Verbesserung der muendlichen Praesentation von Referaten: Ein Ausbildungsziel und zugleich ein Beitrag zur Qualitaet der Lehre, Das Hochschulwesen (41. Jg., Heft 6, S. 289-297), Leitfaden zur Vorbereitung und Durchführung mündlicher Seminarpräsentationen