We consider a job-shop scheduling problem with n jobs and the constraint that at most p < n jobs can be processed simultaneously. This model arises in several manufacturing processes, where each operation has to be assisted by one human operator and there are p (versatile) operators. The problem is binary NP-hard even with n = 3 and p = 2. When the number of jobs is fixed, we give a pseudopolynomial dynamic programming algorithm and a fully polynomial time approximation scheme (FPTAS). We also propose an enumeration scheme based on a generalized disjunctive graph, and a dynamic programming-based heuristic algorithm. The results of an extensive computational study for the case with n = 3 and p = 2 are presented.
Agnetis, A., Flamini, M., Nicosia, G., Pacifici, A. (2011). A job-shop problem with one additional resource type. JOURNAL OF SCHEDULING, 14, 225-237.
A job-shop problem with one additional resource type
AGNETIS, ALESSANDRO;
2011-01-01
Abstract
We consider a job-shop scheduling problem with n jobs and the constraint that at most p < n jobs can be processed simultaneously. This model arises in several manufacturing processes, where each operation has to be assisted by one human operator and there are p (versatile) operators. The problem is binary NP-hard even with n = 3 and p = 2. When the number of jobs is fixed, we give a pseudopolynomial dynamic programming algorithm and a fully polynomial time approximation scheme (FPTAS). We also propose an enumeration scheme based on a generalized disjunctive graph, and a dynamic programming-based heuristic algorithm. The results of an extensive computational study for the case with n = 3 and p = 2 are presented.File | Dimensione | Formato | |
---|---|---|---|
a job shop problem with one additional resource type.pdf
non disponibili
Tipologia:
Post-print
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
708.71 kB
Formato
Adobe PDF
|
708.71 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.
https://hdl.handle.net/11365/22382
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo