Mostrar el registro sencillo del ítem
Partially informed depth-first search for the job shop problem
dc.contributor.author | Mencía Cascallana, Carlos | |
dc.contributor.author | Sierra Sánchez, María Rita | |
dc.contributor.author | Varela Arias, José Ramiro | |
dc.contributor.editor | Brafman, Ronen I. | |
dc.contributor.editor | Geffner, Hector | |
dc.contributor.editor | Hoffmann, Jörg | |
dc.contributor.editor | Kautz, Henry A. | |
dc.date.accessioned | 2015-12-14T08:21:25Z | |
dc.date.available | 2015-12-14T08:21:25Z | |
dc.date.issued | 2010 | |
dc.identifier.isbn | 978-1-57735-449-9 | |
dc.identifier.uri | http://www.aaai.org/ocs/index.php/ICAPS/ICAPS10/paper/view/1429 | spa |
dc.identifier.uri | http://hdl.handle.net/10651/34020 | |
dc.description.abstract | We propose a partially informed depth-first search algorithm to cope with the Job Shop Scheduling Problem with makespan minimization. The algorithm is built from the well-known P. Brucker's branch and bound algorithm. We improved the heuristic estimation of Brucker's algorithm by means of constraint propagation rules and so devised a more informed heuristic which is proved to be monotonic. We conducted an experimental study across medium and large instances. The results show that the proposed algorithm reaches optimal solutions for medium instances taking less time than branch and bound and that for large instances it reaches much better lower and upper bounds when both algorithms are given the same amount of time | spa |
dc.description.sponsorship | This research has been supported by the Spanish Ministry of Science and Education under research project MEC-FEDER TIN2007-67466-C02-01 and by the Principality of Asturias under grant FICYT-BP09105. | spa |
dc.format.extent | p. 113-120 | spa |
dc.language.iso | eng | spa |
dc.publisher | AAAI Publications | spa |
dc.relation.ispartof | ICAPS 2010. Twentieth International Conference on Automated Planning and Scheduling | spa |
dc.rights | CC Reconocimiento - No comercial - Sin obras derivadas 4.0 Internacional | |
dc.rights | © 2010 Association for the Advancement of Artificial Intelligence (www.aaai.org) | |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | |
dc.subject | Heuristic search | spa |
dc.subject | Depth-first | spa |
dc.subject | Branch and bound | spa |
dc.subject | Scheduling | spa |
dc.subject | Job shop | spa |
dc.subject | Constraint propagation | spa |
dc.subject | Heuristics | spa |
dc.subject | Artificial intelligence | spa |
dc.title | Partially informed depth-first search for the job shop problem | spa |
dc.type | book part | spa |
dc.relation.projectID | MEC-FEDER/TIN2007-67466-C02-01 | spa |
dc.relation.projectID | FICYT/BP09105 | |
dc.rights.accessRights | open access | spa |
dc.type.hasVersion | AM |
Ficheros en el ítem
Este ítem aparece en la(s) siguiente(s) colección(ones)
-
Capítulos de libros [5889]
-
Informática [755]