Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Parallel algorithms for the maximum flow problem with minimum lot sizes
verfasst von : Mujahed Eleyat, Dag Haugland, Magnus Lie Hetland, Lasse Natvig
Erschienen in: Operations Research Proceedings 2011
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In many transportation systems, the shipment quantities are subject to minimum lot sizes in addition to regular capacity constraints. This means that either the quantity must be zero, or it must be between the two bounds. In this work, we prove that the maximum flow problem with minimum lot-size constraints on the arcs is strongly NP-hard, and we enhance the performance of a previously suggested heuristic. Profiling the serial implementation shows that most of the execution time is spent on solving a series of regular max flow problems. Therefore, we develop a parallel augmenting path algorithm that accelerates the heuristic by an average factor of 1.25.