𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The complexity of makespan minimization for pipeline transportation

✍ Scribed by Ruy Luiz Milidiú; Artur Alves Pessoa; Eduardo Sany Laber

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
254 KB
Volume
306
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

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 ÿnding a minimum makespan solution to SPTP. This problem is called SPTMP. We prove that, for any ÿxed ¿ 0, there is no Á 1--approximate algorithm for the SPTMP unless P = NP, where Á 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.

📜 SIMILAR VOLUMES

Job sequencing rules for minimizing the
Job sequencing rules for minimizing the expected makespan in flexible machines
✍ Amiya K. Chakravarty; Nagraj Balakrishnan 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 863 KB

We consider scheduling of a deteriorating flexible machine that is capable of processing a number of diverse jobs with negligible setup times between jobs. Specifically, we develop rules for sequencing N jobs on such a machine such that its expected makespan (sum of all job processing times and mach

The minimal average latency of multiconf
The minimal average latency of multiconfigurable pipelines
✍ Jürgen Tappe 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 136 KB

It is shown that the average latencies of all sequences of optimal cycles through a fixed vertex in the state graph of a multiconfigurable pipeline have a common limit, provided that their initiation numbers are unbounded and approximate the same ratio of the underlying operations. This leads to a d