Bearbeiten von „KIF425:AK Scheduling“

Zur 42,5 soll http://www.redseat.de/page/konferenz.php getestet werden. Wir sind alle gespannt, wie das angenommen wird.


Wir wollen die zeitliche (und raeumliche) Platzierung von AKs auf Raeume optimieren.

Wir wollen, dass moeglichst viele Leute moeglichst viele fuer sie interessante AKs besuchen koennen.

Wir wollen, dass (insbes. kleinere) Fachschaften ein moeglichst grosses Angebot an AKs abdecken koennen.

= Vorueberlegungen =

* hard constraints
** AK-Leiter kann nur einen AK gleichzeitig leiten

* soft constraints
** kleine FS-Delegationen bevorzugt

* Umsetzung
** anonym irgendwie?
** mit SDAPS Befragungszetteln?
*** Zettel mit "AK #1...99" vorbereiten, Zuweisung #->AK im Plenum an der Wand
** online interface?
** gewichtete praeferenzen (muss da hin, will gerne, interesse)
** AKs haben unterschiedliche Dauer, evtl Abhaengigkeiten untereinander (X muss vor/nach Y stattfinden)

* AK-Zuteilungen wurden schon mal behandelt in [[KIF400:Meta]]. [[KIFfel:Andreas|Andreas]] trägt mit den anderen Kiffels aus diesem AK die damaligen Erkenntnisse noch zusammen.

* evtl. "emergen" bei der optimierung "tracks", sprich viele leute bleiben im gleichen raum fuer mehrere AKs
** ueberlegen, ob man will, dass sich leute nicht durchmischen (<-> moerderspiel promoten?)

= Der AK =

Es werden 13 Leute gezaehlt.

Redseat wird von den Karlsruhern vorgestellt. Anfang 2006, ein Fest, bei dem Erstis helfen sollten. Online-Helferanmeldung, Leute auf Jobs einteilen mit Algorithmus. Aber noch weitere Bedingungen, z.B. faire Belohnung von Gruppen (vs. first come first serve). Wurde spaeter auch fuer Tutorieneinteilung an der Fak. benutzt. Der Entwickler war dann mit dem Studium fertig und das System wurde ausgegruendet.

System konnte dieses Mal nicht verwendet werden, weil die Nebenbedingungen/Restriktionsarten und die Modellierung vorher nicht kommuniziert waren. Die Modellierung braucht Zeit und Ueberlegung (ich brauche 1 Slot, oder 2 Stunden, oder ...). Die Teilnehmer muessen wissen, wie sie ihre Wuensche formulieren koennen. Das Interface danach sei relativ banal.

Daten von der 42,5 koennen rausgegeben werden, weil keine direkt persoenlich identifizierbaren Informationen enthalten sind. Es gibt auch Mitschriften der verbalen Praeferenzaeusserungen vom Plenum.

Variable AK-Laengen waeren modellierbar, wenn man sinnvolle Daten erhebt. Auch Zeiten, zu denen man einen AK nicht besuchen kann, sind modellierbar. Feste Zeiteinheiten sind aber bedeutend einfacher.

Wichtige Restriktion: AKs die nicht gleichzeitig sein koennen (weil jemand sie selbst leitet), oder Folge-AKs. Das sei einfach zu modellieren.

Es wird angeregt, beliebte oder wichtige AKs nicht an den Rand des Tages zu legen. Hingegen, unbeliebte Sachen werden an den Rand gedrueckt und das waere schade.

"Stable Marriage" wird angesprochen. Dass von einer Uni wenigstens einer zu einem AK gehen kann.

Menschliche Erfahrung macht einiges aus.

Linear Programs: "AK X findet zu dieser Zeit mit Gewicht 0.68 statt, zu anderer Zeit zu 0.12, .."

Linear Integer Programs ("AK findet mit p=1.0 hier statt") machens unglaublich schwieriger. Mixed Integer das etwas einfacher.

Tiefere Diskussion ueber die Ansaetze wird fuer zu technisch fuer den AK befunden.
* Simplex, Ellipsoid, Baumsuche an Entscheidungsknoten
* SAT Solver nicht sinnvoll, weil kein Entscheidungsproblem, sondern Optimierung

Modellierungssprachen, quasi-LaTeX Notation, frisst ein Solver:
* OPL (IBM)
* AMPL
* ...

Solverimplementierungen: CPLEX, ...

Solver nennen eine Entfernung zum Optimum. Solver verfeinern eine schlechte Loesung schnell "gut", aber das flacht dann auch ab. Nach langer Zeit dann kommt der Beweis, dass die Loesung nach 2 Minuten schon fast optimal war.

Eine gute Idee ist, nur ueber Logik (Domaenen) zu gehen, nicht ueber Gleitkommazahlen. In Logik ist man freier, kann z.B. auch "Multiplikation" benutzen.

Alles, was zu einer befriedigenden Loesung fuehrt, ist gut. Menschliche Heuristiken (von z.B. Stundenplanern einer Uni) sind gute Ansaetze. Heuristiken sind aber sehr problemspezifisch

Ein guter plausibler Plan reicht. Man braucht nicht das Optimum.

Subjektiv schlechte Plaene manuell anpassen? D.h. Zielfunktion aendern? Das will man nicht, weil die Zielfunktion (Spielregeln) schon an die Leute kommuniziert wurde.

Gut geht, Modelle mit Heuristiken zu verbinden. In der Heuristik trifft man Entscheidungen, im Modell wird dafuer eine Loesung gesucht.

Lazy Restraints. Erstmal ohne Heuristik loesen. Dann durch Mensch pruefen, Modell manuell um Restriktionen erweitern. Iterieren.

Es sind Entscheidungs-Unterstuetzungs-Systeme. Leute koennen nicht vorneweg alles formalisieren, was sie im Kopf haben.

Manuelle Planungssysteme fuer Konferenzen, z.B. von der GOR Tagung, werden auch manuell gefixt, bis ein Mensch das fuer OK befindet.

Scheduling schlaegt fehl, wenn Anwender schlecht mit den Modellierern kommunizieren. Dann fehlen Restraints und Vorlesungen werden parallel gelegt, obwohl sie nicht sollten.

TU Berlin: Vorlesungen werden an ihrem traditionellen Slot gewuenscht, aber nirgends sonst. Man muss den Leuten Vorgaben geben, damit sie auch Spielraum einraeumen, den sie von selbst nicht einraeumen wuerden.

Cherry Picking: Leute waehlen ihren Lieblingstermin Prioritaet A, alles andere Prio X (Ranglistensystem). Dagegen kann man arbeiten, wenn man Leuten klar macht, dass sie faire Praeferenzen abgeben (z.B. durchschnittlich neutrale Prio).

Mechanism Design: wie bringe ich Leute dazu, ihre ehrliche Meinung abzugeben? Man muss aufpassen, dass Leute nicht strategisch Praeferenzen abgeben.

Restriktionen sind nicht alle "hart", sonst kaeme potenziell kein Plan raus. Restriktionen duerfen verletzt werde (Fruehschicht direkt nach Spaetschicht gewuenscht, aber illegal). Welche Restriktionen will man brechen, welche nicht? Ueberschneidungen sollten soft sein, doppelte Raumbelegungen sollten hart sein, es sei denn die AKs halten sich zusammen in einem Raum aus.

Eine GUI (fuer Benutzer) will man nicht ueberladen. Das kann man (Admin) manuell in den Daten noch zurechtbiegen.

Events mit vielen Slots und 1000+ Teilnehmern seien locker auf einem Laptop in einer Stunde loesbar.

Bestimmte Arten von menschlich formulierten Restriktionen sehen nachher im Modell gleich aus. Einfach modellierbar: staerkeres Gewicht an Individuen einer kleinen Fachschaft.

Fixe Termine kann man trivial setzen.

Verschiedene Raumgroessen koennten ein Kriterium sein. Kann man mit ins Modell nehmen (macht es anpassbarer). Oder man sortiert nach Veranstaltungsgroesse und sortiert dann in den groessten Raum.

GUIs muessen benutzbar und schoen sein, sonst kriegt man die Bewertungsdaten nicht aus den Leuten heraus. In den sauren Apfel muss man beissen.