Por favor, use este identificador para citar o enlazar a este item:
http://hdl.handle.net/10261/197461
COMPARTIR / EXPORTAR:
SHARE CORE BASE | |
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL | DATACITE | |
Título: | Job sequencing with one common and multiple secondary resources: An A*/Beam Search based anytime algorithm |
Autor: | Horn, Matthias; Raidl, Günther; Blum, Christian CSIC ORCID | Palabras clave: | Sequencing Scheduling A* algorithm Beam search Particle therapy patient scheduling |
Fecha de publicación: | dic-2019 | Editor: | Elsevier | Citación: | Artificial Intelligence 277: 103173 (2019) | Resumen: | We consider a sequencing problem that arises, for example, in the context of scheduling patients in particle therapy facilities for cancer treatment. A set of non-preemptive jobs needs to be scheduled, where each job requires two resources: (1) a common resource that is shared by all jobs and (2) a secondary resource, which is shared with only a subset of the other jobs. While the common resource is only required for a part of the job's processing time, the secondary resource is required for the whole duration. The objective is to minimize the makespan. First we show that the tackled problem is NP-hard and provide three different lower bounds for the makespan. These lower bounds are then exploited in a greedy construction heuristic and a novel exact anytime A algorithm, which uses an advanced diving mechanism based on Beam Search and Local Search to find good heuristic solutions early. For comparison we also provide a basic Constraint Programming model solved with the ILOG CP optimizer. An extensive experimental evaluation on two types of problem instances shows that the approach works even for large instances with up to 2000 jobs extremely well. It typically yields either optimal solutions or solutions with an optimality gap of less than 1%. | Versión del editor: | http://dx.doi.org/10.1016/j.artint.2019.103173 | URI: | http://hdl.handle.net/10261/197461 | DOI: | 10.1016/j.artint.2019.103173 | ISSN: | 0004-3702 |
Aparece en las colecciones: | (IIIA) Artículos |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
Job sequencing with one common and multiple secondary resources: An A*/Beam Search based anytime algorithm.pdf | 986,79 kB | Adobe PDF | Visualizar/Abrir |
CORE Recommender
SCOPUSTM
Citations
3
checked on 25-abr-2024
WEB OF SCIENCETM
Citations
1
checked on 22-feb-2024
Page view(s)
207
checked on 26-abr-2024
Download(s)
174
checked on 26-abr-2024
Google ScholarTM
Check
Altmetric
Altmetric
NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.