论文标题
与延误的工作链的参数化复杂性
Parameterized Complexity of Scheduling Chains of Jobs with Delays
论文作者
论文摘要
在本文中，我们考虑以下调度问题的参数化复杂性。我们必须在$ m $机器上安排许多作业，每个作业的单位长度为单位长度，优先限制的图由一组链组成。每个优先限制都用一个整数标记，该整数表示作业之间的确切（或最小）延迟。我们研究不同的病例；延迟可以以一元和二进制给出，并且我们拥有一台机器的情况是单独讨论的。我们考虑通过链数和实例的厚度参数参数的此问题的复杂性，该链的链数是其释放日期和截止日期重叠之间的间隔的最大链数。 我们表明，即使我们拥有一台机器（$ m = 1 $），当通过厚度参数（$ m = 1 $）时，对于所有$ t $，对于所有$ t $而言，这个附属延迟的调度问题都是$ w [t] $。当通过链数参数化时，当我们拥有单个或恒定数量的机器数量时，此问题为$ W [1] $ - 完成时，当机器数为变量时，$ W [2] $ - 完成。最小延迟（以一元）给出的最小延迟的问题是由链的数量（并且作为简单的推论，当通过厚度参数化时）为$ W [1] $ - 对于单个或恒定数量的机器而言，很难或$ W [2] $ - 当机器数量可变时，很难。 使用动态编程算法，当通过厚度或链数参数化时，可以在任何数量的机器中显示XP中的成员资格，以确切和最小延迟，以确切和最小的延迟。对于一台机器，具有二进制延迟的精确延迟，通过链数进行了参数，可以通过分支和求解差异约束系统显示XP中的成员资格。对于所有其他二进制延迟的情况，XP中的会员资格开放。
In this paper, we consider the parameterized complexity of the following scheduling problem. We must schedule a number of jobs on $m$ machines, where each job has unit length, and the graph of precedence constraints consists of a set of chains. Each precedence constraint is labelled with an integer that denotes the exact (or minimum) delay between the jobs. We study different cases; delays can be given in unary and in binary, and the case that we have a single machine is discussed separately. We consider the complexity of this problem parameterized by the number of chains, and by the thickness of the instance, which is the maximum number of chains whose intervals between release date and deadline overlap. We show that this scheduling problem with exact delays in unary is $W[t]$-hard for all $t$, when parameterized by the thickness, even when we have a single machine ($m = 1$). When parameterized by the number of chains, this problem is $W[1]$-complete when we have a single or a constant number of machines, and $W[2]$-complete when the number of machines is a variable. The problem with minimum delays, given in unary, parameterized by the number of chains (and as a simple corollary, also when parameterized by the thickness) is $W[1]$-hard for a single or a constant number of machines, and $W[2]$-hard when the number of machines is variable. With a dynamic programming algorithm, one can show membership in XP for exact and minimum delays in unary, for any number of machines, when parameterized by thickness or number of chains. For a single machine, with exact delays in binary, parameterized by the number of chains, membership in XP can be shown with branching and solving a system of difference constraints. For all other cases for delays in binary, membership in XP is open.
