Talks and Poster Presentations (with Proceedings-Entry):
Th. Kaufmann, M. Horn, G. Raidl:
"A Variable Neighborhood Search for the Job Sequencing with One Common and Multiple Secondary Resources Problem";
Talk: International Conference on Parallel Problem Solving From Nature (PPSN),
Leiden, The Netherlands;
- 2020-09-09; in: "Parallel Problem Solving from Nature - PPSN XVI",
LNCS / Springer,
In this work we consider a scheduling problem where a set of non-preemptive jobs needs to be scheduled such that the makespan is minimized. Each job requires two resources: (1) a common resource, shared by all jobs and (2) a secondary resource, shared with only a subset of the other jobs. The secondary resource is required during the jobīs entire processing time whereas the common resource is only required during a part of a jobīs execution. The problem models, for instance, the scheduling of patients during one day in a particle therapy facility for cancer treatment. We heuristically tackle the problem by a general variable neighborhood search (GVNS) based on move and exchange neighborhoods and an efficient evaluation scheme to scan the neighborhoods of the current incumbent solution. An experimental evaluation on two benchmark instance sets, including instances with up to 2000 jobs, shows the effectiveness of the GVNS. In particular for larger instances our GVNS outperforms an anytime A ∗ algorithm that was the so far leading method in heuristic terms as well as a constrained programming model solved by ILOG CP optimizer.
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Electronic version of the publication:
Created from the Publication Database of the Vienna University of Technology.