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.
Agnetis, A., Flamini, M., Nicosia, G., Pacifici, A. (2010). Scheduling three chains on two parallel machines. EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 202, 669-674 [10.1016/j.ejor.2009.07.001].
Scheduling three chains on two parallel machines
AGNETIS, Alessandro;FLAMINI, MARTA;NICOSIA, GAIA;Pacifici, Andrea
2010-01-01
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.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
