English   español  
Por favor, use este identificador para citar o enlazar a este item: http://hdl.handle.net/10261/164749
COMPARTIR / IMPACTO:
Estadísticas
logo share SHARE logo core CORE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:
Título

Job sequencing with one common and multiple secondary resources: A problem motivated from particle therapy for cancer treatment

AutorHorn, Matthias; Raidl, Gunther; Blum, Christian
Palabras claveScheduling
Learning systems
Integer programming
Patient treatment
Optimization
Diseases
Fecha de publicación15-sep-2017
EditorSpringer
CitaciónMachine Learning, Optimization, and Big Data, Third International Conference, MOD 2017, Volterra, Italy, September 14–17, 2017, Revised Selected Papers. LNCS 10710: 506-518 (2018)
ResumenWe consider in this work the problem of scheduling a set of jobs without preemption, where each job requires two resources: (1) a common resource, shared by all jobs, is required during a part of the job¿s processing period, while (2) a secondary resource, which is shared with only a subset of the other jobs, is required during the job¿s whole processing period. This problem models, for example, the scheduling of patients during one day in a particle therapy facility for cancer treatment. First, we show that the tackled problem is NP-hard. We then present a construction heuristic and a novel A* algorithm, both on the basis of an effective lower bound calculation. For comparison, we also model the problem as a mixed-integer linear program (MILP). An extensive experimental evaluation on three types of problem instances shows that A* typically works extremely well, even in the context of large instances with up to 1000 jobs. When our A* does not terminate with proven optimality, which might happen due to excessive memory requirements, it still returns an approximate solution with a usually small optimality gap. In contrast, solving the MILP model with the MILP solver CPLEX is not competitive except for very small problem instances. © Springer International Publishing AG 2018.
URIhttp://hdl.handle.net/10261/164749
Identificadoresdoi: 10.1007/978-3-319-72926-8_42
issn: 03029743
isbn: 978-331972925-1
Aparece en las colecciones: (IIIA) Comunicaciones congresos
Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
accesoRestringido.pdf15,38 kBAdobe PDFVista previa
Visualizar/Abrir
Mostrar el registro completo
 


NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.