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(3), 225-237 [10.1007/s10951-010-0162-4].

A job-shop problem with one additional resource type

PACIFICI, ANDREA
2011-01-01

Abstract

We consider a job-shop scheduling problem with n jobs and the constraint that at most p
2011
Pubblicato
Rilevanza internazionale
Articolo
Sì, ma tipo non specificato
Settore MAT/09 - RICERCA OPERATIVA
English
Con Impact Factor ISI
Disjunctive graph; Dynamic programming; Job shop; Scheduling with resource constraints
http://link.springer.com/article/10.1007%2Fs10951-010-0162-4
Agnetis, A., Flamini, M., Nicosia, G., Pacifici, A. (2011). A job-shop problem with one additional resource type. JOURNAL OF SCHEDULING, 14(3), 225-237 [10.1007/s10951-010-0162-4].
Agnetis, A; Flamini, M; Nicosia, G; Pacifici, A
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
afnp-JOS10.pdf

solo utenti autorizzati

Licenza: Copyright dell'editore
Dimensione 616.41 kB
Formato Adobe PDF
616.41 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: https://hdl.handle.net/2108/10989
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 51
  • ???jsp.display-item.citation.isi??? 45
social impact