Algorithmus Konferenzen ohne Überschneidung
-
Hallo,
gibt es einen intelligenten Algorithmus, der folgendes bewältigen kann? Gegeben ist eine Liste, die eingelesen werden kann:
Name Fach
Mister x Mathe
Mister x Sport
Mister y Deutsch
....Nun sollen meinetwegen an 4 oder 6 Terminen Fachkonferenzen stattfinden (die auch doppelt belegt sein können, z.B. Deutsch und Mathe zur selben Zeit), allerdings so, dass natürlich niemand eine verpasst. Mathe und Sport dürften deshalb nicht an einem Termin stattfinden.
-
Na ob der Algorithmus so intelligent ist weiß ich nicht, aber ich würde einfach die Liste für jeden Tag von oben nach unten durchgehen und von jedem Lehrer der noch keinen Termin an dem Tag hat ein Fach für diesen Tag "buchen", bis entweder kein Lehrer mehr frei ist oder die maximalanzahl an der Terminen für einen Tag erreicht ist.
-
Das ist genau das Problem, eine minimale Knotenfärbung eines Graphen zu finden.
-
Bist du eigentlich an einem optimalen Algorithmus interessiert, oder willst du das Problem einfach nur mal praktisch gelöst haben? Falls letzteres, bitte sehr, war ganz lustig. (Laufzeit ist unterirdisch, aber ich vermute mal das ist hier bei egal.) (Und ja man könnte einfach die Fächer auf die Tage mappen, aber das schien mir so praktischer.)
-
Ich weiß leider nicht, nach was optimiert werden soll.
Wie ich die Lehrer kenne nach Anzahl der Termine.
Dann ist die optimale Lösung EINE Fachkonferenz, an der alle Lehrer teilnehmen. Bei kleineren Schulen durchaus möglich.Oder darf kein Lehrer an einer Fachkonferenz teilnehmen, dessen Fach er nicht belegt? Dann dürften aber normalerweise keine Tage zusammengelegt werden können, mit steigender Leherzahl immer unwahrscheinlicher. Nee, das kann es nicht sein.
Man möchte zum Beispiel die unstressigen Fächer Kunst, Religion, Textiles Gestalten, Ethik, Bewerbungstraining, EDV, Musik zusammenlegen, weil diese Konfz zwar fast alle Lehrer zieht, aber erfahrungsgemäß mit 1-2 Fällen in 10 Minuten durch ist. Diese Fächer zusammenzulegen mit Hauptfächern wäre furchtbar.
Deutsch und Englisch zusammen, weil die Masse der Lehrer des einen Fachs auch das andere gibt, und die Masse der Problemfälle hier sind. Lieber eine lange Konferenz als zwei Nachmittage mit Arbeit zwerstören.Ich glaube, da fehlen mir viel zu viele Randbedingungen, daß es sinnig wird.
-
Die Graphenfärbung kommt selbstverständlich erst ins Spiel, wenn man sich festgelegt hat, welche Konferenzen es geben soll. Solange man noch Themen zusammenlegen kann, soll man das tun. Das ist aber keine algorithmische Frage ...