Multivariate Algorithms for High Multiplicity Scheduling

调度和规划问题属于算法中的基本问题。这些问题中的许多都不太可能采用保证在多项式时间内提供最优解的程序。因此，在过去的几十年里，针对这类问题已经开发了数百种近似算法。在这个项目中，我们处理一种替代方法来调度问题具有高多重性，其中大量的作业必须计划，可以分为几个类别。例如，降落飞机的排序就会出现这样的问题，其安全间隔距离主要取决于各自飞机属于少数飞机类型中的哪一种。我们的目标是开发固定参数算法，该算法在时间上提供最优解，该解多项式地依赖于输入大小，并且仅在少数类别中提供超多项式。通过这种方式，我们将多项式时间算法推广到更现实的模型中，同时改进了固定参数算法的运行时间，因为固定参数算法需要对每个作业进行大量编码。

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.