并行机器调度问题动态规划算法的参数化分析

### 并行机器调度问题动态规划算法的参数化分析 #### 1. 引言 资源受限和有优先级约束的调度问题在生产系统、多核并行机器使用、嵌入式系统设计等多个领域有广泛应用。自六十年代初起，众多学者就致力于开发精确或近似算法来高效解决此类问题。 要解决的基本调度问题是：有一组 $n$ 个非抢占式作业 $T$，需由 $m$ 台相同的机器执行。每个作业 $i \in T$ 有正的处理时间 $p_i$、释放时间 $r_i$ 和截止时间 $d_i$，这些值均为整数。作业 $i$ 的开始时间 $s(i)$ 需满足 $r_i \leq s(i) \leq d_i - p_i$，且每个作业要安排在一台机器上，每台机器一次最多处理一个作业。同时，有向无环图 $G = (T, E)$ 定义了一组优先级约束，对于每条弧 $(i, j) \in E$，有 $s(i) + p_i \leq s(j)$。该问题旨在找到可行的调度方案，用 Graham 符号表示为 $P|prec, r_j, d_j|⋆$。此问题精确求解难度大，例如 $P|prec, p_j = 1|C_{max}$ 问题已被证明是 NP 难的。 固定参数可处理算法（FPT 算法）的发展，为研究困难问题的高效算法提供了可能。FPT 算法能在 $O(f(k)×poly(n))$ 的时间内解决规模为 $n$、参数为 $k$ 的问题实例，其中 $f$ 可以是可计算的超多项式函数，$poly(n)$ 是关于 $n$ 的多项式。 在有优先级约束的关键参数中，优先级图的宽度 $w(G)$ 曾被不少学者考虑，因为它似乎能体现实例的并行性。但该参数大多带来负面结果，如 Bodlaender 和 Fellows 证明，即使对于单位处理时间，$P|prec, p_i = 1|C_{max}$ 问题以 $w(G)$ 和机器数量为参数时是 $W[2]$ 难的。目前已知的唯一积极结果是 van Bevern 等人针对资源受限调度问题，以 $(w(G), λ)$ 为参数的 FPT 算法，其中 $λ$ 是根据优先级约束定义的最早调度计算出的任务最大允许延迟。 此外，Munier Kordon 最近为决策问题 $P|prec, r_j, d_j, p_j = 1|⋆$ 开发了基于动态规划的 FPT 算法，考虑的参数是路径宽度 $\mu = \max_{t\geq0} |\{i \in T \text{ s.t. } r_i \leq t < d_i\}|$，即单个时间 $t$ 上重叠作业时间窗口的最大数量。Hanen 和 Munier Kordon 将此方法扩展到处理不同处理时间的情况，采用参数对 $(\mu, p_{max})$，其中 $p_{max} = \max_{i \in T} p_i$，该算法的时间复杂度为 $O(f(\mu, p_{max}) × n^4)$。他们还证明了以路径宽度为参数的 $P2|r_i, d_i|⋆$ 问题和以 $p_{max}$ 为参数的 $P|prec, r_i, d_i|⋆$ 问题是 para - NP 完全的，这意味着除非 $P = NP$，否则 $P|prec, r_i, d_i|⋆$ 问题以单个参数为参数时不存在 FPT 算法。 分支限界法常用于开发解决 NP 完全调度问题的高效算法。Demeulemeester 和 Herroelen 算法（简称 DH 算法）是解决此类问题最有效的分支限界法之一，但目前尚无该算法的最坏情况复杂度分析。 研究证明，DH 算法基于树的探索方案可转化为状态图 $G$ 的构建，状态图 $G$ 的节点对应探索树的节点，其路径对应可行调度。同时，扩展了 DH 算法的分支定义以处理释放时间和截止时间，且不考虑边界技术。基于时间窗口结构提出了新的支配规则，证明了对于固定的参数 $\mu$ 和 $p_{max}$，状态图的状态数量与作业数量呈线性关系，且可通过固定参数可处理算法在 $O(h(\mu, p_{max}) × n^3)$ 时间内构建。实验表明，状态图生成的实际时间复杂度也强烈依赖于路径宽度 $\mu$，即使不使用边界技术，对于参数值较小的情况，状态图也能完全生成。 #### 2. 状态图 $G$ 的定义 此部分证明了所考虑调度问题实例的可行活动调度集可由无环状态图 $G$ 的最大路径表示。 ##### 2.1 基本定义和状态 - **活动和半活动调度**：可行调度若满足没有作业能在不改变其他作业开始时间的情况下左移一个时间单位（或提前调度），则称为半活动（或活动）调度。 - **部分可行调度**：设 $V \subseteq T$，$G_V = (V, E)$ 是 $G$ 限制在作业集 $V$ 上的优先级子图。部分可行调度是作业子集 $V$ 的可行调度，需遵循优先级图 $G_V = (V, E)$ 以及初始问题的所有约束（释放时间、截止时间和机器限制）。 - **状态**：状态 $v$ 是一个四元组 $v = (V, t, P, M)$，其中 $V \subseteq T$ 是作业集，$t \in N$ 是日期，$P \subseteq V$，$M \in N^{|P|}$ 是一个按 $P$ 索引的向量。存在作业 $V$ 的部分可行调度 $s$ 满足： 1. 每个作业 $i \in V \setminus P$ 在时间 $t$ 之前完成，即 $s(i) + p_i < t$。 2. 每个作业 $i \in P$ 在时间 $t$ 之前开始，并在时间 $M_i \geq t$ 完成，即 $s(i) = M_i -