English español

Repositorio de la Universidad de Oviedo. > Producción Bibliográfica de UniOvi: RECOPILA > Capítulos de libros >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10651/34022

Title: Improving heuristic estimations with constraint propagation in searching for optimal schedules
Author(s): Mencía Cascallana, Carlos
Sierra Sánchez, María Rita
Varela Arias, José Ramiro
Keywords: Job shop scheduling
Heuristic search
A* algorithm
Branch and bound
Constraint propagation
Issue date: 2009
Publisher: Asociación Española para la Inteligencia Artificial
Abstract: We face the Job Shop Scheduling Problem by means of branch and bound and A ∗ search. Our main contribution is a new method, based on constraint propagation rules, that allows improving the heuristic estimations. We report results from an experimental study across conventional instances with different sizes showing that A ∗ takes profit from the improved estimations. Both algorithms can reach optimal solutions for medium size instances and, in this case, the branch and bound algorithm is better than A ∗ . However, for very large instances that remain unsolved in both cases, A ∗ returns much better lower bounds due to the improved estimation
URI: http://hdl.handle.net/10651/34022
ISBN: 978-84-692-6424-9
Sponsored: This work 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.
Project id.: MEC-FEDER/TIN2007-67466-C02-01
Appears in Collections:Capítulos de libros

Files in This Item:

File Description SizeFormat
Mencia2009_postprint.pdfMencia2009_postprint145,08 kBAdobe PDFView/Open

Exportar a Mendeley

This item is licensed under a Creative Commons License
Creative Commons

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Base de Datos de Autoridades Biblioteca Universitaria Consultas / Sugerencias