Skip to content. | Skip to navigation

Personal tools

Sections

Nachbargebiete

next up previous contents
Next: Transformationen Up: Übersicht über das Spektrum Previous: Raumverteilung (Room Allocation)

Nachbargebiete

Employee Timetabling
Dieses Problem unterscheidet sich von der automatischen Stundenplanerstellung nur dadurch, daß es noch wesentlich kompliziertere Nebenbedingungen gibt, die zumeist durch gewerkschaftliche Regelungen entstanden sind. Die bekanntesten Beispiele sind Personalplanungen bei Bus und Bahn, aber auch die Wachpläne in Krankenhäusern[MK98] und die Verteilung von Gebetszeiten[CO97] zählen hierzu.
Sportveranstaltungen
Dieses Problem ist dem Examination-Timetabling sehr ähnlich, zeichnet sich aber in der Praxis durch eine große Zahl von Symmetrien aus.
Flight Scheduling
Das Flight Scheduling Problem besteht in der Zuordnung von Flugzeugen zu Flugstrecken und Zeiten. Die Bedingungen unterscheiden sich wesentlich von denen des Timetablings, da z.B. die Geographie eine wesentlich größere Rolle spielt. Als zusätzliche Einschränkungen treten verschiedene Flugzeugtypen, Wartungsintervalle etc. auf. Ziel ist es, die Zahl der Leerflüge zu minimieren.
Crew Roostering
Das Crew Pairing ist der zweite Schritt bei der Flugplanung. Jeder Mannschaft wird eine Flugstrecke zugeteilt, die bei demselben Flughafen (einer Crew-Base) startet und endet, d.h. der Graph der Flugbewegungen muß in disjunkte Kreise zerlegt werden. Soweit es aus der betrachteten umfangreichen Literatur ersichtlich ist, versucht niemand diese beiden Probleme simultan zu lösen.
Processor Scheduling
Dies ist normalerweise ein dynamischer und preemptiver Fall, der von der Timetabling-Thematik weitgehend abweicht und häufig mit Online - Algorithmen behandelt wird. Stellt man aber Echtzeitanforderungen und muß entschieden werden, ob ein neuer Task noch angenommen werden kann, so ist das Problem bei Annahme eines minimalen Quotas für die Prozessorzuteilung mit dem Timetablingim wesentlichen identisch. Im Bereich des Compilerbaus kann auch die statische Variante auftreten, wenn z.B. mehrere unabhängige Ausführungseinheiten in einem Computer gegeben sind, die von dem zu erstellenden Programm exklusiv genutzt werden können. Dies ähnelt, je nach Parallelisierbarkeit des Codes, aber eher dem job-shop Problem. Etwas ähnliches tritt auch bei der Registerverteilung auf; die hier verwendeten Graphen sind aber, sofern es keine verschiedenen Registertypen gibt, perfekt (s.u.).


next up previous contents
Next: Transformationen Up: Übersicht über das Spektrum Previous: Raumverteilung (Room Allocation)

(c) Martin Loehnertz 1999