Data Instances

Braune, R. (2022). Packing-based branch-and-bound for discrete malleable task scheduling. Journal of Scheduling, 25(6), 675-704. https://doi.org/10.1007/s10951-022-00750-w

Dieser Beitrag behandelt die Ablaufplanung kettenartiger Aufgabenstrukturen auf einer einzelnen Multiprozessor-Ressource. Teilaufgaben mit Einheitsdauer und vorgegebener Größe werden zu zusammengesetzten Aufgaben gebündelt, die ohne Unterbrechung, aber mit Flexibilität bei der Ressourcenzuteilung eingeplant werden müssen. Diese Problemstellung entspricht am ehesten dem Scheduling formbarer (malleable) Aufgaben, wobei die Teilaufgaben die kleinste unteilbare Zuteilungseinheit bilden. Die Formbarkeit wird über Vorrangbeziehungen mit minimalen und maximalen Zeitabständen abgebildet. Für dieses Scheduling-Problem wird ein Bin-Packing-Modell aufgestellt und ein darauf zugeschnittener Branch-and-Bound-Algorithmus entwickelt, ergänzt um problemspezifische Schrankenverschärfung, Symmetriebrechung und Dominanzkonzepte. Die Wirksamkeit des Lösungsansatzes wird in umfangreichen Rechenexperimenten gezeigt, unter anderem mit zufällig generierten Instanzen, angepassten Benchmark-Instanzen aus der Literatur und einem kleinen Datensatz aus der Praxis. Im Vergleich zu Formulierungen als gemischt-ganzzahliges Programm und als Constraint-Programm erreicht die neue Methode einen deutlich höheren Anteil optimaler Lösungen bei teils um Größenordnungen kürzeren Rechenzeiten.

Braune, R., Benda, F., Dörner, K. F., & Hartl, R. (2022). A Genetic Programming Learning Approach to Generate Dispatching Rules for Flexible Shop Scheduling Problems. International Journal of Production Economics, 243, Article 108342. https://doi.org/10.1016/j.ijpe.2021.108342

Neben Benchmark-Sets aus der wissenschaftlichen Literatur zum Flexible Job Shop Scheduling umfassen diese auch Instanzen aus dem Praxisszenario. Zusätzlich haben wir zu Trainingszwecken zufällig generierte Probleminstanzen mit denselben Eigenschaften verwendet.

Dieser Beitrag stellt einen Ansatz der genetischen Programmierung (GP) zur Lösung flexibler Shop-Scheduling-Probleme vor. Ziel ist es, Prioritätsregeln in Form eines Ausdrucksbaums für die Zuteilung von Aufträgen zu erzeugen. In einem List-Scheduling-Algorithmus lassen sich die verfügbaren Aufträge so mithilfe der per GP erzeugten, baumbasierten Prioritätsregeln reihen. Diese Prioritätsregeln wurden an Benchmark-Problemstellungen, etwa von Brandimarte und Lawrence, in statischer und dynamischer Umgebung getestet. Anschließend wurden die GP-Ansätze auf einen Sonderfall angewendet, der auf der Problemstellung eines Industriepartners beruht. Ziel war es, die maximale Fertigstellungszeit aller Aufträge (Makespan) zu minimieren. Dazu haben wir die Auftragszuordnung und die Maschinenreihenfolge gleichzeitig in einer Einzelbaum-Darstellung berücksichtigt und diese mit einem Mehrbaum-Ansatz verglichen, bei dem die Terminalmengen (auftrags- und maschinenbezogen) strikt getrennt waren. Daraus ergaben sich zwei parallele GP-Populationen: Die erste entscheidet, welcher Auftrag gewählt wird, die zweite, welcher Maschine er zugeordnet wird. Für beide Baumansätze haben wir außerdem eine iterative Variante umgesetzt, die Informationen aus früheren Ablaufplänen speichert, um weitere Verbesserungen zu erzielen. Die Rechenexperimente zeigten einen durchgängigen Vorteil gegenüber bestehenden fortgeschrittenen Prioritätsregeln aus der Literatur, mit deutlich höherer Leistung bei ungleichartigen parallelen Maschinen und generell bei größeren Instanzen.

Ion Beam Facility: Considering Optional Activities and Time Window Constraints. Journal of Scheduling, 22(2), 137–154 . https://doi.org/10.1007/s10951-018-0574-0

Die Ionenstrahl-Strahlentherapie ist eine moderne Form der Krebsbehandlung, die in spezialisierten Einrichtungen angeboten wird. Die Behandlung besteht aus mehreren, fast täglichen Bestrahlungsterminen, gefolgt von optionalen Bildgebungs- und Kontrollterminen. Die Planung dieser wiederkehrenden Behandlungstermine lässt sich als komplexes Job-Shop-Scheduling-Problem mit besonderen Nebenbedingungen einordnen, etwa wiederkehrenden und optionalen Aktivitäten sowie speziellen Zeitfensterbedingungen. Ziel ist es, die Betriebszeit der Engpassressource, des Teilchenstrahls, zu minimieren und gleichzeitig Strafkosten aus Verletzungen von Zeitfensterbedingungen möglichst gering zu halten. Die Autor*innen formulieren das Problem mathematisch und führen verschiedene maßgeschneiderte Nebenbedingungen ein. Drei metaheuristische Lösungsansätze, nämlich ein genetischer Algorithmus mit eigens entwickelten, zulässigkeitserhaltenden Crossover-Operatoren, eine iterierte lokale Suche und eine Kombination beider Ansätze, liefern bei kleinen wie großen Probleminstanzen gute Ergebnisse. Die einfache Kombination der beiden eigenständigen Algorithmen erzielt jedoch bei praxisnahen Probleminstanzen die besten Ergebnisse.

Beim Pickup-and-Delivery-Problem (PDP) mit alternativen Orten und überlappenden Zeitfenstern müssen Pakete von Verkäufer*innen (Absender*innen), die im Laufe des Tages mehrere wechselnde Abholorte mit nicht überlappenden Zeitfenstern haben können (da das Produkt nicht an zwei Orten gleichzeitig sein kann), zu Käufer*innen (Empfänger*innen) transportiert werden. Diese haben für die Zustellung eine alternative Person zur Verfügung und optional eine rund um die Uhr zugängliche Abholstation, sofern sich eine in der Nähe ihrer Wohnung befindet. Somit können mehrere Personen an verschiedenen Orten gleichzeitig verfügbar sein, um eine Lieferung anzunehmen (daher die überlappenden Zeitfenster). Jede Person (Absender*in oder Empfänger*in) ist einem von 17 Kundenprofilen zugeordnet, woraus sich ein vielfältiger Tagesablauf mit 1 bis 5 verschiedenen Orten pro Tag ergibt. 

Unsere selbst erstellten Instanzen beruhen auf Wiener Zustelldaten eines österreichischen Logistikdienstleisters aus dem Jahr 2017. 700 Orte wurden als „Zuhause“, „Arbeit“ und „sonstige“ wechselnde Orte klassifiziert (Orte, an denen Menschen typischerweise und regelmäßig einen Teil ihrer Zeit verbringen, z. B. Fitnesscenter, Bibliothek, Bildungseinrichtung). Ein Ort kann mehrere Klassifizierungen gleichzeitig haben. Weitere Orte sind rund um die Uhr zugängliche Abholstationen der Österreichischen Post in Wien (mit der eigenen Klassifizierung „Post-Abholstation“). Für diese 799 Orte (einschließlich Depot) stellen wir eine symmetrisierte Reisezeitmatrix (in Minuten) auf Basis kürzester Wege im realen Straßennetz bereit. 

Es wurden 570 Instanzen aus 19 verschiedenen Szenariotypen in drei Größen (30, 50 und 100 Aufträge) erstellt. 

Dragomir, Alina G., Tom Van Woensel, and Karl F. Doerner. "The pickup and delivery problem with alternative locations and overlapping time windows." Computers & Operations Research 143 (2022): 105758.

Wir behandeln ein Planungsproblem von Logistikdienstleistern, die Fracht über weite Strecken transportieren. Gegeben ist eine Menge von Transportaufträgen, deren Start- und Zielorte weit voneinander entfernt liegen. Der Logistikdienstleister muss zulässige Fahrzeugrouten finden, die diese Aufträge zu minimalen Kosten erfüllen. Beim Gütertransport über weite Strecken ist multimodaler Transport eine tragfähige Alternative zum herkömmlichen unimodalen Straßentransport. Wir stellen dieses neue Problem vor, das wir Multimodal Long Haul Routing Problem (MMLHRP) nennen, und formulieren es mathematisch. Zur Lösung des MMLHRP schlagen wir eine Matheuristik vor, die eine iterierte lokale Suche in ein Spaltengenerierungsverfahren einbettet. Die Ergebnisse zeigen, dass sich durch multimodalen Transport im Vergleich zum unimodalen Straßentransport erhebliche Kosten einsparen lassen.

https://ucris.univie.ac.at/portal/de/publications/a-matheuristic-for-a-multimodal-long-haul-routing-problem(eb8bd7c4-5160-4d8a-a33e-bde37917bb88).html

Dragomir, A.-G., Van Woensel, T., & Dörner, K. F. (2022). The pickup and delivery problem with alternative locations and overlapping time windows. Computers & Operations Research, 143, Article 105758. https://doi.org/10.1016/j.cor.2022.105758

Viele Sicherheitsunternehmen bieten Patrouillendienste an, bei denen Wachpersonal regelmäßig Anlagen oder Straßen kontrollieren muss. Die Patrouillenrouten sollen kosteneffizient sein, die Kontrollmuster dürfen für Täter*innen aber nicht vorhersehbar sein. Auch bei Geld- und Werttransporten entstehen Tourenplanungsprobleme, bei denen zwischen Kostenminimierung und Routeninkonsistenz abgewogen werden muss. Wir beschreiben diese Problemstellung als mehrkriterielles periodisches Node-, Edge- und Arc-Routing-Problem mit den Zielen, die Kosten und die Routenkonsistenz zu minimieren. Es wird mathematisch formuliert und in ein asymmetrisches kapazitiertes Tourenplanungsproblem überführt, einmal mit einem einfachen Graphen und einmal mit einem Multigraphen. Zur Lösung schlagen wir vor, ein Verfahren der Adaptive Large Neighborhood Search in mehrkriterielle Lösungsrahmen einzubetten. Wir setzen drei solche Rahmen um: Multi-Directional Local Search (MDLS), ε-Constraint-Heuristik (ECH) und ε-Box-Splitting-Heuristik (EBSH). Die Methoden wurden an künstlichen und an Praxisinstanzen getestet. In einer umfangreichen Rechenstudie zeigen wir, dass EBSH und ECH die überlegenen Methoden zu sein scheinen. Außerdem deuten die Ergebnisse darauf hin, dass die Berücksichtigung mehrerer kürzester Wege zwischen Knoten die Lösungsqualität deutlich erhöhen kann.

Ein Tourenplanungsproblem mit Synchronisationsbedingungen tritt im städtischen Güterverkehr auf, wenn Kund*innen Lieferungen von einem oder mehreren Logistikdienstleistern erhalten. Diese Lieferungen sollen effizient erfolgen, um Wartezeiten am Lieferort zu verringern. Als Wartezeit gilt die Zeit ohne Belieferung zwischen der ersten und der letzten Lieferung, die die Kund*innen erhalten. Wir schlagen eine Strategie mit selbst gesetzten Zeitfenstern vor und vergleichen sie mit einer exakten Bestimmung eines zulässigen Ablaufplans sowie mit festen Zeitfenstern. Die Ergebnisse zeigen, dass sich die Wartezeiten um 54,12 % bis 79,77 % verringern lassen, bei einem durchschnittlichen Kostenanstieg von 9,87 %. Zudem liefern selbst gesetzte Zeitfenster bei kurzen Laufzeiten Lösungen, die um 15,74 % bis 21,43 % günstiger sind als Zulässigkeitsprüfungen und um 13,71 % bis 21,15 % günstiger als feste Zeitfenster.

Schilde, M., Dörner, K., Hartl, R., & Kiechle, G. (2009). Metaheuristics for the Bi-Objective Orienteering Problem. Swarm Intelligence, 3(3), 179-201.

In diesem Beitrag werden heuristische Lösungsverfahren für das mehrkriterielle Orienteering-Problem entwickelt. Ausgangspunkt ist die Planung individueller Tourist*innenrouten in einer Stadt. Jede Sehenswürdigkeit bietet für verschiedene Kategorien (z. B. Kultur, Shopping) unterschiedlichen Nutzen. Tourist*innen gewichten diese Kategorien bei der Auswahl und beim Besuch von Sehenswürdigkeiten (z. B. Museen, Kirchen) unterschiedlich. Daraus ergibt sich eine mehrkriterielle Entscheidungssituation. Um alle Pareto-optimalen Lösungen zu bestimmen, werden zwei metaheuristische Suchverfahren entwickelt und angewendet: Wir verwenden den Pareto-Ant-Colony-Optimization-Algorithmus und erweitern die Variable Neighborhood Search auf den mehrkriteriellen Fall. Beide Verfahren werden mit Path-Relinking-Prozeduren hybridisiert. Die Leistungsfähigkeit der beiden Algorithmen wird an mehreren Benchmark-Instanzen sowie an Praxisinstanzen aus verschiedenen österreichischen Regionen und den Städten Wien und Padua getestet. Die Rechenergebnisse zeigen, dass beide Verfahren das mehrkriterielle Orienteering-Problem gut lösen.

Gansterer, M., & Hartl, R. (2018). Centralized bundle generation in auction-based collaborative transportation. OR Spectrum: quantitative approaches in management, 40(3), 613-635. doi.org/10.1007/s00291-018-0516-4

In horizontalen Kooperationen schließen sich Frachtführer zu Koalitionen zusammen, um Teile ihrer Logistikprozesse gemeinsam durchzuführen. Durch den Austausch von Transportaufträgen können sie effizienter und nachhaltiger arbeiten. Dieser Austausch lässt sich über kombinatorische Auktionen organisieren, bei denen die Partner Aufträge in einen gemeinsamen Pool einbringen. Die Aufträge im Pool werden zu Bündeln zusammengefasst und den teilnehmenden Frachtführern angeboten. In der Praxis ist es nicht handhabbar, alle möglichen Bündel anzubieten, da ihre Zahl exponentiell mit der Zahl der gehandelten Aufträge wächst. Wir zeigen, wie sich die Gesamtmenge der Bündel effizient auf eine Teilmenge attraktiver Bündel reduzieren lässt. Dafür definieren wir das Bundle Generation Problem (BuGP). Ziel ist eine reduzierte Menge angebotener Bündel, die den Gesamtgewinn der Koalition maximiert und zugleich eine zulässige Zuordnung der Bündel zu den Frachtführern garantiert. Die Zielfunktion ließe sich allerdings nur auswerten, wenn die Frachtführer sensible Informationen offenlegen, was unrealistisch wäre. Daher entwickeln wir eine Näherung der Zielfunktion, mit der sich die Attraktivität von Bündeln bei unvollständiger Information beurteilen lässt. Sie wird in einem Rahmen auf Basis genetischer Algorithmen eingesetzt, der attraktive und zulässige Bündel erzeugt, sodass alle Anforderungen des BuGP erfüllt sind. Wir erzielen eine sehr gute Lösungsqualität und verkürzen zugleich die Rechenzeit für das Auktionsverfahren erheblich. Das ist ein wichtiger Schritt hin zu kombinatorischen Auktionen in realer Größenordnung, die bisher wegen ihrer Rechenkomplexität nicht lösbar waren. Stärken und Grenzen des vorgeschlagenen Ansatzes werden diskutiert.

Tricoire, F., Scagnetti, J., & Beham, A. (2018). New insights on the block relocation problem. Computers & Operations Research, 89, 127-139. https://doi.org/10.1016/j.cor.2017.08.010

Dieser Beitrag stellt neue Methoden für das Block-Relocation-Problem (BRP) vor. Während sich ein Großteil der bisherigen Arbeiten auf das eingeschränkte BRP konzentriert, behandeln wir das uneingeschränkte BRP, das mehr Optimierungsmöglichkeiten bietet. Zu unseren Beiträgen zählen schnelle Heuristiken, die sehr große Instanzen in Sekunden bearbeiten, schnelle Metaheuristiken mit sehr konkurrenzfähiger Leistung auf Benchmark-Datensätzen sowie eine neue untere Schranke, die bestehende Schranken verallgemeinert. Wir binden sie in einen Branch-and-Bound-Algorithmus ein und untersuchen anschließend, wie sich verschiedene Faktoren auf die Effizienz von Branch-and-Bound-Algorithmen für das BRP auswirken.

Schneeberger, K., Schilde, M., Doerner, K.F. (2016). Solving a Rich Position-Based Model for Dairy Products. In: Lübbecke, M., Koster, A., Letmathe, P., Madlener, R., Peis, B., Walther, G. (eds) Operations Research Proceedings 2014. Operations Research Proceedings. Springer, Cham. https://doi.org/10.1007/978-3-319-28697-6_71

Im Folgenden werden die Testinstanzen aus dem Beitrag „Solving a Rich Position-Based Model for Dairy Products“ beschrieben. Insgesamt stehen 32 Testinstanzen zur Verfügung. Sie beruhen auf Praxisdaten und gewährleisten ein realistisches Szenario. Die Daten liegen im XML-Format vor, damit sie einfach verwendet werden können. Indem wir das Losgrößenproblem und das detaillierte Reihenfolge- und Ablaufplanungsproblem gleichzeitig in einer sehr realitätsnahen Modellformulierung betrachten, wollen wir die Gesamtleistung des Produktionsprozesses eines Molkereiunternehmens verbessern. Dazu haben wir das von Lütke et al. (Int. J. Prod. Res. 43, 5071–5100, 2005 [5]) eingeführte Position-Based Model erweitert. Auf Basis realer Produktionsdaten haben wir mit unserem Modell exakte Lösungen für sehr kleine Problemstellungen ermittelt. Da selbst bei kleinen Instanzen die Rechenzeit für exakte Lösungen im Allgemeinen zu lang ist, haben wir eine von Fix&Optimize inspirierte Konstruktionsheuristik entwickelt, die für mehrere Produkte eine zulässige Lösung liefert. Die Ergebnisse zeigen, dass die gefundenen Lösungen im Vergleich zur optimalen Lösung konkurrenzfähig sind und deutlich weniger Zeit benötigen.