Scheduling three chains on two parallel machines

We consider the problem of scheduling n tasks subject to chain-precedence constraints on two identical machines with the objective of minimizing the makespan. The problem is known to be strongly NP-hard. Here, we prove that it is binary NP-hard even with three chains. Furthermore, we characterize the complexity of this case by presenting a pseudopolynomial time algorithm and a fully polynomial time approximation scheme.

MoreLess

Year of publication:	2010
Authors:	Agnetis, Alessandro ; Flamini, Marta ; Nicosia, Gaia ; Pacifici, Andrea
Published in:	European Journal of Operational Research. - Elsevier, ISSN 0377-2217. - Vol. 202.2010, 3, p. 669-674
Publisher:	Elsevier
Keywords:	Computational complexity Scheduling Parallel machines Approximation

Online Resource

Check full text access |

More access options

Check Google Scholar

In libraries world-wide (WorldCat)

In German libraries (KVK)

subito order

I need help

More details

Type of publication:	Article
Source:	RePEc - Research Papers in Economics

Persistent link: https://www.econbiz.de/10008483252