[Back]

M. Horn, G. Raidl, C. Blum:
"Job Sequencing with One Common and Multiple Secondary Resources: A Problem Motivated from Particle Therapy for Cancer Treatment";
Talk: International Workshop on Machine Learning, Optimization, and Big Data, Volterra, Italy; 2017-09-14 - 2017-09-17; in: "MOD 2017: Machine Learning, Optimization, and Big Data - Third International Conference", LNCS, 10710 (2017), ISBN: 978-3-319-72925-1; 506 - 518.

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.

http://dx.doi.org/10.1007/978-3-319-72926-8_42

https://publik.tuwien.ac.at/files/publik_284804.pdf