caa a22 4500 445838647 CHVBK 20180317145337.0 cr unu---uuuuu 170323e20110601xx s 000 0 eng 10.1007/s10951-010-0162-4 doi (NATIONALLICENCE)springer-10.1007/s10951-010-0162-4 A job-shop problem with one additional resource type [Elektronische Daten] [Alessandro Agnetis, Marta Flamini, Gaia Nicosia, Andrea Pacifici] 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. Springer Science+Business Media, LLC, 2010 Job shop nationallicence Scheduling with resource constraints nationallicence Disjunctive graph nationallicence Dynamic programming nationallicence Agnetis Alessandro Dipartimento di Ingegneria dell'Informazione, Università di Siena, Via Roma 56, 53100, Siena, Italy aut Flamini Marta Data Management S.P.A., Largo Lido Duranti, 1, 00128, Roma, Italy aut Nicosia Gaia Dipartimento di Informatica e Automazione, Università Roma Tre, Via della Vasca Navale 79, 00146, Roma, Italy aut Pacifici Andrea Dipartimento di Ingegneria dell'Impresa, Università di Roma Tor Vergata, Via del Politecnico 1, 00133, Roma, Italy aut Journal of Scheduling Springer US; http://www.springer-ny.com 14/3(2011-06-01), 225-237 1094-6136 14:3<225 2011 14 10951 https://doi.org/10.1007/s10951-010-0162-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10951-010-0162-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Agnetis Alessandro Dipartimento di Ingegneria dell'Informazione, Università di Siena, Via Roma 56, 53100, Siena, Italy aut NATIONALLICENCE 700 1- Flamini Marta Data Management S.P.A., Largo Lido Duranti, 1, 00128, Roma, Italy aut NATIONALLICENCE 700 1- Nicosia Gaia Dipartimento di Informatica e Automazione, Università Roma Tre, Via della Vasca Navale 79, 00146, Roma, Italy aut NATIONALLICENCE 700 1- Pacifici Andrea Dipartimento di Ingegneria dell'Impresa, Università di Roma Tor Vergata, Via del Politecnico 1, 00133, Roma, Italy aut NATIONALLICENCE 773 0- Journal of Scheduling Springer US; http://www.springer-ny.com 14/3(2011-06-01), 225-237 1094-6136 14:3<225 2011 14 10951 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer