Logo Institute for Algorithms and Complexity (E-11)
Institute for Algorithms and Complexity (E-11)
Logo Institute for Algorithms and Complexity (E-11)
Institute for Algorithms and Complexity (E-11)
EN
Place
Search
EN
Place
Search
ALGO > Projects > 2017-2021: Multivariate algorithms for high-multiplicity scheduling

Multivariate Algorithms for High-Multiplicity Scheduling

(2017-2021, funded by DFG, principal investigator: Professor Dr. M. Mnich)

Scheduling and planning problems belong to the fundamental questions in algorithms. Many of those problems are highly unlikely to admit procedures that guarantee to deliver an optimal solution in polynomial time. Therefore, hundreds of approximation algorithms have been developed for such problems in the past decades.In this project we deal with an alternative approach for scheduling problems with high multiplicity, in which a large number of jobs must be planned which can be categorized into few categories. Such problems arise in, for instance, sequencing of landing aircraft, whose safety separation distances mainly depend on which of few aircraft type the respective planes belong to. Our goal is the development of fixed-parameter algorithms, which deliver optimal solutions in time that depends polynomially on the input size and superpolynomially only in the small number of categories. This way, we generalize polynomial-time algorithms for special cases of those problems with only constantly many job categories to more realistic models, and simultaneously improve the run times of fixed-parameter algorithms which so far require a lavish encoding of every single job.

 

Associated publications

2024

2023

2021

2020

2019

TU Hamburg
Institute for Algorithms and Complexity
Blohmstr. 15
21079 Hamburg
E-mail : algo@tuhh.de
Phone : +49 (40) 42878-4907
Links
Contact
Sitemap
Activities