Analytics & Optimization

Suche

Abgeschlossene Projekte


Kapazitätssteuerung im Revenue Management — Simulative Evaluierung, neue Steuerungsansätze & branchenspezifische Modellierung

Das Revenue Management repräsentiert eines der erfolgreichsten Anwendungsgebiete des Operations Research, das der Airline Industrie entstammt und aus einem Mix aus Methoden zur Nachfrageprognose, Preisdifferenzierung und Kapazitätsteuerung besteht. Die Preisdifferenzierung, die z.B. bei Fluggesellschaften durch die unterschiedlichen Ticketpreise für gleiche Flugstrecken deutlich wird, dient der Generierung zusätzlicher Nachfrage. Als Folge einer solchen Preisdifferenzierung ergibt sich das Problem, dass im Rahmen einer Kapazitätssteuerung festgelegt werden muss, wie viel Produkte (etwa Sitzplätze auf einem bestimmten Flug) zu welchem Preis zu verkaufen sind. Diese Aufgabe wird dadurch erschwert, dass die Nachfrage unsicher ist und in der Praxis sehr viele Anfragen gleichzeitig eintreffen können, über deren Annahme online zu entscheiden ist. Es ergeben sich somit dynamische, stochastische, online Optimierungsprobleme.

In der Literatur und vor allem in der Praxis wurden zahlreiche Ansätze zur Kapazitätssteuerung für den Personentransport durch Fluggesellschaften entwickelt. Ein Vergleich dieser Ansätze bezüglich ihrer Güte erfolgte jedoch bisher nur in einem eingeschränkten Umfang. Daher wurde im Rahmen der Forschung des Lehrstuhls zunächst eine Simulationsumgebung in JAVA implementiert, die es erlaubt, solche Vergleiche unter einheitlichen Rahmenbedingungen vorzunehmen. Zugleich ist es damit möglich, bestehende Verfahren auf erweiterte Problemstellungen anzuwenden, wie sie etwa bei dem Transport von Fracht, beim Verkauf von Pauschalreisen oder der Vermietung von Automobilen entstehen.

Darüber hinaus wurden alternative Steuerungsmechanismen entwickelt, die darauf beruhen, anstatt der Anzahl an zu verkaufenden Produkten Mindestpreise,die sich auch als Opportunitätskosten bezeichnen lassen, für die Nutzung der benötigten Ressourcen zu bestimmen. Eine Anfrage für einen Sitzplatz auf einer Verbindung München—Frankfurt—New York würde etwa dann verkauft, wenn der erzielte Ticketpreis die Summe der Mindestpreise für die Teilstrecken München—Frankfurt und Frankfurt—New York übersteigt. Dieser Ansatz eignet sich insbesondere für den Einsatz von internetbasierten Verkaufssystemen, da er im Vergleich zu produktbasierten Ansätzen die Übermittlung deutlich kleinerer Datenmengen erfordert und auf einer einfachen Entscheidungsregel beruht.

Des Weiteren wurden auf Basis des verbreiteten DLP-Optimierungsmodells verschiedene branchenspezifische Erweiterungen zur Durchführung einer Kapazitätssteuerung entwickelt.

Literatur

  • Klein, R.: Network capacity control using self-adjusting bid-prices. OR Spectrum 29 (2007), S. 39–60.
  • Kimms, A. und R. Klein (Hrsg.): Special issue on revenue management. OR Spectrum 29 (2007).
  • Kimms, A. und R. Klein: Revenue Management im Branchenvergleich, Zeitschrift für Betriebswirtschaft, Ergänzungsheft 1 "Revenue Management" (2005), S. 1–30.
  • Domschke, W. und R. Klein: Bestimmung von Opportunitätskosten am Beispiel des Produktionscontrolling. Zeitschrift für Planung und Unternehmenssteuerung 15 (2004), S. 275–294.
  • Klein, R. und A. Petrick: Revenue Management — Eine weitere Erfolgsstory des Operations Research. GOR News 1 (2003), S. 5–9.
  • Klein, R.: Revenue Management: Quantitative Methoden zur Erlösmaximierung in der Dienstleistungsproduktion. Betriebswirtschaftliche Forschung und Praxis 53 (2001), S. 245–259.

Ressourcenbeschränkte Projektplanung

in Zusammenarbeit mit Prof. Dr. Armin Scholl, Universität Jena

Das Problem der ressourcenbeschränkten Projektplanung stellt eines der am stärksten diskutierten Scheduling Probleme der vergangenen Jahre mit zahlreichen praktischen Anwendungsmöglichkeiten nicht nur im Projektmanagement dar. Es geht davon aus, dass zur Durchführung eines Projekts der Abschluss einer Menge von Vorgängen, die durch Reihenfolgebeziehungen miteinander verknüpft sein können, erforderlich ist. Dabei beanspruchen die Vorgänge knappe Ressourcen, die die Möglichkeiten der gleichzeitigen Bearbeitung mehrer Vorgänge einschränken können. Das Ziel besteht darin, Beginnzeitpunkte für die Vorgänge so festzulegen, dass ein zulässiger Terminplan mit möglichst kurzer Projektdauer bestimmt werden.

Ein wesentliche Voraussetzung für die Entwicklung effizienter Lösungsverfahren für dieses Problem stellt die Berechnung unterer Schranken für die kürzestmögliche Projektdauer dar. Ein wesentlicher Beitrag auf diesem Gebiet wurde durch die Einführung des Konzeptes des Destructive Improvement geleistet. Dieses Konzept vereint Ideen der klassischen Schrankenberechnung, wie sie im Operations Research üblich ist, mit Ideen aus dem Constraint Programming, das der angewandten Informatik entstammt. Der grundlegende Ansatz besteht darin, eine potenzielle untere Schranke für die Projektdauer zu betrachten und ein entsprechendes Zulässigkeitsproblem zu definieren. Gelingt es, mit Hilfe logischer Tests die Existenz einer zulässigen Lösung zu widerlegen, so kann die untere Schranke erhöht werden. Dieser Ansatz erweist sich als sehr erfolgreich und wurde daher von zahlreichen Forschern aufgegriffen und verfeinert. So habe ich in der Zwischenzeit zahlreiche Arbeiten dazu begutachtet, die vornehmlich auf dem Gebiet des Constraint Programming angesiedelt sind.

Selbst wenn es gelingt, scharfe untere Schranken für das ressourcenbeschränkte Projektplanungsproblem zu berechnen, scheitert die Bestimmung optimaler Lösungen oft daran, dass diese nicht gefunden werden. Besonders im Rahmen von Branch-and-Bound Verfahren ist dies darauf zurückzuführen, dass der Lösungsraum statisch abgesucht wird. Daher wurde ein Ansatz entwickelt, der eine Flexibilisierung der Suche erlaubt, indem dynamisch, in Abhängigkeit vom Lösungsfortschritt unterschiedliche Bereiche des Lösungsraums betrachtet werden.

Trotz der mit den obigen Forschungsergebnissen erzielten Fortschritte ist es nicht möglich, optimale Lösungen für praxisrelevante Problemgrößen zu bestimmen. Daher kommt der Entwicklung geeigneter Heuristiken eine entscheidende Bedeutung zu. Ein grundlegender, im Rahmen des Projekts entwickelter Ansatz, um die Effizienz solcher Verfahren zu erhöhen, besteht in der bidirektionalen Einplanung von Vorgängen. Damit gelingt es bereits, die Leistungsfähigkeit einfacher, prioritätsregelbasierter Verfahren deutlich zu verbessern. Noch bessere Ergebnisse lassen sich durch den Einsatz der Metaheuristik Tabu Search erzielen.

Literatur

  • Klein, R. und A. Scholl: PROGRESS: Optimally solving the generalized resource-constrained project scheduling problem. Mathematical Methods of Operations Research 52 (2000), S. 467–488.
  • Klein, R.: Project scheduling under time-varying resource constraints. International Journal of Production Research 38 (2000), S. 3937–3952.
  • Klein, R. und A. Scholl: Scattered branch and bound: An adaptive search strategy applied to resource-constrained project scheduling. Central European Journal of Operations Research 7 (2000), S. 177–201.
  • Klein, R.: Bidirectional Planning: Improving priority rule cased heuristics for scheduling resource-constrained projects. European Journal of Operational Research 127 (2000), S. 619–638.
  • Klein, R.: Scheduling of resource-constrained projects. Kluwer, Boston u.a., 2000.
  • Klein, R. und A. Scholl: Computing lower bounds by destructive improvement — an application to resource-constrained project scheduling. European Journal of Operational Research 112 (1999), S. 322–346.

Konfiguration und Betrieb von Fließfertigungssystemen

in Zusammenarbeit mit Prof. Dr. Armin Scholl, Universität Jena

Fließfertigungssysteme kommen insbesondere in der Massen- und Serienproduktion zum Einsatz. Dabei werden die Produktiveinheiten (Arbeitsstationen) im Rahmen einer Fließlinie hintereinander angeordnet und von den herzustellenden Produkten entsprechend dieser Reihenfolge durchlaufen. Jeder Station ist eine Menge von Operationen (Arbeitsgänge) zugewiesen, die innerhalb einer gewissen Zeitspanne (Taktzeit) zu bearbeiten sind, bevor die Übergabe des Produkts an die nächste Arbeitsstation erfolgt. Grundsätzlich ist zwischen einer Einprodukt- und einer Variantenfließfertigung zu unterscheiden.

Ein wesentliches Problem bei der mittelfristigen Konfiguration solcher Systeme besteht in der Zuweisung von Arbeitsgängen zu Stationen. Im Fall der Einproduktfertigung wird zumeist versucht, für eine gegebene Taktzeit, die sich aus den herzustellenden Mengen an Produkten ableiten lässt, die Anzahl der benötigten Stationen zu minimieren. Darüber hinaus kann es bei der Modifikation der Produkte sinnvoll sein, ein Neuzuordnung von Arbeitsgängen für eine gegebene Stationsanzahl so vorzunehmen, dass die Taktzeit minimiert wird. Im Rahmen des Projekts wurden Branch-and-Bound Verfahren entwickelt, die auf einer neuartigen Verzweigungsstrategie (Local Lower Bound Method) beruhen und eine Reihe neuer Methoden zur Berechnung unterer Schranken sowie Dominanzregeln beinhalten.

Im Fall der Variantenfertigung verkompliziert sich die Arbeitsgangzuweisung dadurch, dass sich die Bearbeitungszeiten der Arbeitsgänge, aber auch die Menge der durchzuführenden Arbeitsgänge je nach Variante unterscheiden können. Hinzu kommt, dass die Auswirkungen der Konfiguration auf die kurzfristige Reihenfolgeplanung antizipiert werden müssen, bei der eine Abfolge der Produkte so festzulegen ist, dass Ineffizienzen (Arbeitsüberlastung, Anhalten der Produktion, Einsatz von Springern) minimiert werden. Im Rahmen des Projekts wurden verschiedene Zielsetzungen für die geeignete Konfiguration untersucht. Des Weiteren wurde ein Verfahren zur Bestimmung effizienter Reihenfolgen, das auf der heuristischen Metastrategie Tabu Search beruht, entwickelt.

Weitere Informationen zum vorliegenden Gebiet finden sich auf der Web-Seite von Herrn Professor Dr. Scholl www.assembly-line-balancing.de, die ein internationales Informationsportal zur Distribution neuester Forschungsergebnisse darstellt.

Literatur

  • Scholl, A. und R. Klein: ULINO: Optimally balancing u-shaped JIT assembly lines. International Journal of Production Research 37 (1999), S. 721–736.
  • Scholl, A. und R. Klein: Balancing assembly lines effectively — a computational comparison. European Journal of Operational Research 114 (1999), S. 50–58.
  • Scholl, A.; R. Klein und W. Domschke: Pattern based vocabulary building for effectively sequencing mixed model assembly lines. Journal of Heuristics 4 (1998), S. 359–381.
  • Scholl, A. und R. Klein: SALOME: A bidirectional branch and bound procedure for assembly line balancing. INFORMS Journal on Computing 9 (1997), S. 319–334.
  • Domschke, W.; R. Klein und A. Scholl: Antizipative Leistungsabstimmung bei moderner Variantenfließfertigung. Zeitschrift für Betriebswirtschaft 66 (1996), S. 1465–1490.
  • Klein, R. und A. Scholl: Maximizing the production rate in simple assembly line balancing — A branch and bound procedure. European Journal of Operational Research 91 (1996), S. 367–385.