Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 12270))
Included in the following conference series:
1182Accesses
Abstract
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.
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.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 11210
- Price includes VAT (Japan)
- Softcover Book
- JPY 14013
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Conforti, D., Guerriero, F., Guido, R.: Optimization models for radiotherapy patient scheduling. 4OR6(3), 263–278 (2008)
Hansen, P., Mladenović, N., Pérez, J.A.M.: Variable neighbourhood search: methods and applications. Ann. Oper. Res.175(1), 367–407 (2010)
Hansen, P., Mladenović, N., Todosijević, R., Hanafi, S.: Variable neighborhood search: basics and variants. EURO J. Comput. Optim.5(3), 423–454 (2016).https://doi.org/10.1007/s13675-016-0075-x
Horn, M., Maschler, J., Raidl, G., Rönnberg, E.: A*-based construction of decision diagrams for a prize-collecting scheduling problem. Technical report AC-TR-18-011, Algorithms and Complexity Group, TU Wien (2018)
Horn, M., Raidl, G., Blum, C.: Job sequencing with one common and multiple secondary resources: an A*/Beam Search based anytime algorithm. Artif. Intell.277(103173) (2019)
Horn, M., Raidl, G., Rönnberg, E.: A* search for prize-collecting job sequencing with one common and multiple secondary resources. Ann. Oper. Res. (2020)
Horn, M., Raidl, G.R., Rönnberg, E.: An A\(^*\) algorithm for solving a prize-collecting sequencing problem with one common and multiple secondary resources and time windows. In: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling, PATAT 2018, pp. 235–256 (2018)
Horn, M., Raidl, G., Blum, C.: Job sequencing with one common and multiple secondary resources: a problem motivated from particle therapy for cancer treatment. In: Nicosia, G., Pardalos, P., Giuffrida, G., Umeton, R. (eds.) MOD 2017. LNCS, vol. 10710, pp. 506–518. Springer, Cham (2018).https://doi.org/10.1007/978-3-319-72926-8_42
Kapamara, T., Sheibani, K., Haas, O., Petrovic, D., Reeves, C.: A review of scheduling problems in radiotherapy. In: Proceedings of the International Control Systems Engineering Conference, pp. 207–211. Coventry University Publishing (2006)
Kaufmann, T.: A variable neighborhood search for the job sequencing with one common and multiple secondary resources problem. Master’s thesis, TU Wien, Vienna, Austria (2019)
López-Ibáńez, M., Dubois-Lacoste, J., Pérez Cáceres, L., Stützle, T., Birattari, M.: The irace package: iterated racing for automatic algorithm configuration. Oper. Res. Perspect.3, 43–58 (2016)
Maschler, J., Raidl, G.R.: Multivalued decision diagrams for a prize-collecting sequencing problem. In: Proceedings of the 12th International Conference of the Practice and Theory of Automated Timetabling, PATAT 2018, pp. 375–397 (2018)
Maschler, J., Riedler, M., Stock, M., Raidl, G.R.: Particle therapy patient scheduling: first heuristic approaches. In: Proceedings of the 11th International Conference of the Practice and Theory of Automated Timetabling, PATAT 2016, pp. 223–244 (2016)
Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res.24(11), 1097–1100 (1997)
Schiavinotto, T., Stützle, T.: A review of metrics on permutations for search landscape analysis. Comput. Oper. Res.34(10), 3143–3153 (2007).https://doi.org/10.1016/j.cor.2005.11.022
Van der Veen, J.A.A., Wöginger, G.J., Zhang, S.: Sequencing jobs that require common resources on a single machine: a solvable case of the TSP. Math. Program.82(1–2), 235–254 (1998)
Author information
Authors and Affiliations
Institute of Logic and Computation, TU Wien, Vienna, Austria
Thomas Kaufmann, Matthias Horn & Günther R. Raidl
- Thomas Kaufmann
You can also search for this author inPubMed Google Scholar
- Matthias Horn
You can also search for this author inPubMed Google Scholar
- Günther R. Raidl
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toMatthias Horn.
Editor information
Editors and Affiliations
Leiden University, Leiden, The Netherlands
Thomas Bäck
Leiden University, Leiden, The Netherlands
Mike Preuss
Leiden University, Leiden, The Netherlands
André Deutz
Sorbonne University, Paris, France
Hao Wang
Sorbonne University, Paris, France
Carola Doerr
Leiden University, Leiden, The Netherlands
Michael Emmerich
University of Münster, Münster, Germany
Heike Trautmann
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Kaufmann, T., Horn, M., Raidl, G.R. (2020). A Variable Neighborhood Search for the Job Sequencing with One Common and Multiple Secondary Resources Problem. In: Bäck, T.,et al. Parallel Problem Solving from Nature – PPSN XVI. PPSN 2020. Lecture Notes in Computer Science(), vol 12270. Springer, Cham. https://doi.org/10.1007/978-3-030-58115-2_27
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-030-58114-5
Online ISBN:978-3-030-58115-2
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative