We are always looking for enthusiastic young people who are interested in a research project or thesis in the Bachelor, Master, and PhD programs. There are often topics available that are not listed here, so please contact us if you are interested in a project or thesis within an area of our group's research.
Contents
Enhancements in a 2-Dimensional Cutting Stock Solver Software
- Date: 20.4.2017
- Topic for: Project, Master Thesis, financial support available!
- Contact: Günther Raidl
In the basic 2-dimensional cutting stock problem (2CS) we are given a set of rectangular elements and an unlimited stock of rectangular sheets. The aim is to arrange the small rectangles on the stock sheets in a cutting pattern, such that the number of used stock sheets is minimal. Diverse extended variants of this basic problem, e.g., with restrictions on the available stock sheets or the possible cutting patterns exist. In this context our group has developed a powerful solver software based on large neighborhood search. In collaboration with the industry partners EuroSoft Inc. (USA) and Lodestar Ges.m.b.H. (Austria) we want to bring this solver now further to practical applicability by extending it to consider certain features and restrictions of cutting patterns of modern saws.
Particle Therapy Scheduling
Date: November 2016
Topic for: Master Thesis
Contact: Martin Riedler, Johannes Maschler, or Günther Raidl
One of the most advanced medical centers for Ion Beam Therapy and Research in Europe is currently being established in Wiener Neustadt: MedAustron. The radiation therapies applied will use protons and carbon ions for cancer treatment. The first patient treatments are planned in 2016. In the full operational phase up to 1,200 people per year are expected to benefit from the international first class medicine offered by MedAustron.
Scheduling patient treatments with their large number of individual tasks and specific requirements in order to best utilize the available resources and treat patients as soon and smoothly as possible is a huge challenge. The Algorithms and Complexity Group collaborates with MedAustron in the development of advanced scheduling algorithms and their software implementation to fulfill these needs and to give as many cancer patients as possible a new opportunity.
In this context we are looking for a motivated master student who wants to work on this subject within the scope of her/his master thesis. In particular, the focus will be on the so-called Intra-day Optimization (IDO). IDO considers the scheduling of tasks within a certain day during operation. Initially there is a schedule available that has been determined by the algorithm for the long term optimization. During operation the goal is to follow this schedule as closely as possible. However, sometimes this is not feasible due to disruptions such as malfunction of technical equipment, delays of patients or tasks that require more time than expected. To this end it is necessary to develop algorithms that handle these exceptions by computing a modified schedule adapted to the changed situation. An additional difficulty arises from the fact that the reaction to this short term changes needs to be provided as fast as possible, allowing only computation times of few minutes.
To tackle this optimization problem we intend to use heuristics and metaheuristic techniques such as GRASP or VNS. Depending on the students preferences there might also be the opportunity to consider exact techniques such as mixed interger linear programming or constraint programming in a later stage. The selection of individual methods will depend on the students interests and the requirements of the considered optimization aspect.
Needed skills:
- Basic knowledge in (meta-)heuristic optimization methods (e.g., from Heuristic Optimization Techniques, Algorithmics)
- Profound programming skills (C++)
- The thesis should be written in English
Graph Drawing
Date: June 2016
Topic for: Bachelor/Master Theses
Contact: Martin Nöllenburg
Graph Drawing is concerned with algorithms to compute geometric representations of graphs and networks. Applications of graph drawing range from graph visualizations for human users to hardware layouts and wireless routing. Scientifically, the area offers a wide spectrum of topics for student theses, from theoretical questions (e.g., existence of certain layouts or algorithms with certain properties) to practical questions of modeling the actual requirements of a particular application and designing and implementing algorithms for solving it.
Requirements:
- Proficiency in (graph) algorithmics
- Interest in geometry and visualization
- Practical topics: good programming skills
Algorithmic Cartography and Geometry
Date: June 2016
Topic for: Bachelor/Master Theses
Contact: Martin Nöllenburg
Digital cartography offers a wide spectrum of visualization problems that can be solved by geometric algorithms. The types of maps range from dynamic and interactive maps, e.g., on smart phones and mobile devices, to unconventional diagrammatic or schematic maps. Examples of algorithmic problems comprise label placement for map features, algorithms for constructing cartograms, or schematic destination maps. The area contains both topics with a stronger practical focus or with a more theoretical focus. Thesis topics in computational geometry without direct links to cartography are also possible.
Requirements:
- Proficiency in algorithmics and geometric algorithms
- Interest in maps and interdisciplinary work
- Practical topics: good programming skills
