Parallel algorithms for the maximum flow problem with minimum lot sizes

Mujahed Eleyat (), Dag Haugland (), Magnus Lie Hetland () and Lasse Natvig ()
Additional contact information
Mujahed Eleyat: Miriam AS, Halden, Norway & IDI, NTNU
Dag Haugland: University of Bergen
Magnus Lie Hetland: Norwegian University of Science and Technology (NTNU)
Lasse Natvig: Norwegian University of Science and Technology (NTNU)

A chapter in Operations Research Proceedings 2011, 2012, pp 83-88 from Springer

Abstract: Abstract 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.

Keywords: Parallel Algorithm; Start Node; Main Thread; Network Flow Problem; Serial Implementation (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-642-29210-1_14

Ordering information: This item can be ordered from
http://www.springer.com/9783642292101

DOI: 10.1007/978-3-642-29210-1_14

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().