Netzwerkflussprobleme mit nicht-linearen Kosten Teil 1: Fully polynomial time approximation schemes (FPTAS) Teil 2: Anwendungen

点击翻译按钮获取中文摘要

Zahlreiche Probleme aus Produktion und Logistik, Supply Chain Management, der Lagerhaltung und Losgrößenplanung können als Minimaikosten-Netzwerkflussprobleme mit in der Regel nicht-linearen Kosten formuliert werden, s. Blazewicz et al. (2001). Im Unterschied zum linearen Fall, der in der Literatur ausführlich untersucht und dessen klassische Lösungsverfahren allgemein bekannt sind, sind nicht-lineare Netzwerkflussprobleme meist streng NP-schwer. Es gibt Ergebnisse zur polynomialen Lösbarkeit im Falle konvexer Kostenstrukturen etwa für Dial-a-Ride Probleme, Inverse-Spanning Tree Probleme, Time-Cost Trade-off Probleme in der Projektplanung oder auch Just-in-Time Scheduling (s. Ahuja / Hochbaum / Orlin, 2003). In all diesen Fällen ist die Problemformulierung als duales Netzwerkflussproblem möglich, was schon von Roundy (1986) erfolgreich auf mehrstufige, Mehrprodukt-Losgrößenprobleme angewendet wurde.Netzwerkflussprobleme mit allgemeiner Kostenstruktur sind bisher nur unzureichend untersucht worden, insbesondere sind Approximationsschemta (FPTAS) und darauf aufbauende Approximatiosnverfahren für viele dieser Probleme, z.B. aus dem Supply Chain Management, der Lagerhaltung und Losgrößenplanung und der Ablaufplanung nicht bekannt. Die Bedeutung zur Untersuchung dieser Probleme rührt aus unseren Ergebnissen zum kapazitierten Economic- Lot-Sizing Problem (CELSP)für das wir bei allgemeiner Kostenstruktur eine FPTAS herleiten können. Das CELSP lässt sich ebenfalls als Netzwerkflussproblem formulieren. Ausgehend vom CELSP wollen wir allgemeinere und schwierigere Probleme betrachten, die sich als NP-schwere Netzwerkflussprobleme mit nicht-linearer Kostenstruktur formulieren lassen. Einige unserer Ideen aus Chubanov et al. (2005a) lassen sich dabei verallgemeinern.Ferner entwickeln wir auch heuristische und exakte Lösungsverfahren für ausgewählte Netzwerkflussprobleme mit allgemeiner Kostenstruktur. Ein Hauptaugenmerk soll hier auf Enumerationsverfahren vom Typ Branch and Bound (evtl. auch Branch and Price und Branch and Cut) liegen. Die Verwendung von FPTAS zum Ausloten der Teilprobleme und zum Finden lokaler Optima in Local Search Verfahren, deren expontentielle Nachbarschaften in polynomialer Zeit durchsuchbar sind, liefert dann Heuristiken mit Gütegarantie.