Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
481152 | European Journal of Operational Research | 2010 | 6 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Alessandro Agnetis, Marta Flamini, Gaia Nicosia, Andrea Pacifici,