2022-01-18T16:40:09Zhttps://digital.csic.es/dspace-oai/requestoai:digital.csic.es:10261/1647492020-12-13T09:15:29Zcom_10261_60com_10261_4col_10261_439
Job sequencing with one common and multiple secondary resources: A problem motivated from particle therapy for cancer treatment
Horn, Matthias
Raidl, Gunther
Blum, Christian
Austrian Science Fund
Scheduling
Learning systems
Integer programming
Patient treatment
Optimization
Diseases
We 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.
We gratefully acknowledge the financial support of the Doctoral Program “Vienna Graduate School on Computational Optimization” funded by Austrian Science Foundation under Project No W1260-N35.
Peer Reviewed
2018-05-11T12:25:45Z
2018-05-11T12:25:45Z
2017-09-15
2018-05-11T12:25:45Z
artículo
doi: 10.1007/978-3-319-72926-8_42
issn: 03029743
isbn: 978-331972925-1
Machine Learning, Optimization, and Big Data, Third International Conference, MOD 2017, Volterra, Italy, September 14–17, 2017, Revised Selected Papers. LNCS 10710: 506-518 (2018)
http://hdl.handle.net/10261/164749
http://dx.doi.org/10.1007/978-3-319-72926-8_42
http://dx.doi.org/10.13039/501100002428
Sí
none
Springer