The complexity of makespan minimization for pipeline transportation
SPTP is a model for the pipeline transportation of petroleum products. It uses a directed graph G, where arcs represent pipes and nodes represent locations. In this paper, we analyze the complexity of finding a minimum makespan solution to SPTP. This problem is called SPTMP. We prove that, for any fixed epsilon > 0, there is no eta(1-epsilon) -approximate algorithm for the SPTMP unless P = NP, where eta is the input size. This result also holds if G is both planar and acyclic. If G is acyclic, then we give a m-approximate algorithm to SPTMP, where m is the number of arcs in G. (C) 2003 Elsevier B.V. All rights reserved.
complexity transportation petroleum oil pipeline approximability