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.

Scheduling three chains on two parallel machines

AGNETIS, ALESSANDRO;
2010

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:
File Dimensione Formato  
scheduling three chains on two parallel machines.pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 334.55 kB
Formato Adobe PDF
334.55 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11365/24042
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo