并行机器上的固定顺序调度

### 并行机器上的固定顺序调度 #### 1. 引言 在许多物流和服务应用中，存在一个看似简单却极具挑战性的调度问题。给定一系列作业和一组机器，需要将作业逐个分配到机器上，且每台机器要保持作业的原始顺序，即遵循先进先出（FIFO）原则。每个作业有处理时间 $p_j$ 和权重 $w_j$，目标是最小化加权完成时间的总和，其中作业 $j$ 的完成时间是同一机器上先于 $j$（包括 $j$ 本身）的所有作业的总处理时间。 这个问题与排队论中的任务分配问题相关，不同之处在于排队论中的作业是随时间随机到达的。该问题可以看作是在完全了解处理时间的情况下，将单个队列中的作业最优地分配到 $m$ 个服务器队列中，本质上是将一个队列拆分为 $m$ 个队列。而将 $m$ 个队列合并为一个队列的反向问题，是经典的单机调度问题，可通过贪心选择总权重与总处理时间之比最大的作业前缀来高效解决。 在调度文献中，固定顺序调度问题可视为具有序列相关设置时间的调度问题的特殊情况。对于该问题，在线版本（即在知道序列中的下一个作业之前就需要分配当前作业）不存在常数竞争比的算法。 #### 2. 问题定义、符号表示和 NP 难性 有一组相同的机器 $M = \{1, \ldots, m\}$，每台机器一次只能处理一个作业，以及一个全序的作业集 $J = \{1, \ldots, n\}$，每个作业 $j \in J$ 有权重 $w_j \in N$ 和处理时间 $p_j \in N$。定义作业 $j$ 的 Smith 比率 $s_j := \frac{w_j}{p_j}$。 可行调度 $\mu : J \to M$ 为每个作业 $j$ 分配一台机器 $\mu(j)$。调度 $\mu$ 的成本是加权完成时间的总和： $\Gamma(\mu) = \sum_{k \in J} \sum_{j \in J: j \leq k, \mu(j) = \mu(k)} p_j \cdot w_k$ 目标是最小化调度的成本。记最优成本为 $opt$，$\sigma_{\mu} : J \to N$ 为将每个作业映射到其在调度 $\mu$ 下的完成时间的函数，定义偏序 $\prec$ 为：$j \prec k$ 当且仅当 $j < k$ 且 $s_j \leq s_k$。 不允许 $p_j = 0$，这是为了确保 Smith 比率 $\frac{w_j}{p_j}$ 始终有定义，但结果可轻松扩展到允许处理时间为零的作业的情况。最小化加权完成时间总和且无排序约束的问题是经典的强 NP 难问题，该结果也适用于固定顺序调度。 #### 3. 最优解的结构性质 ##### 3.1 单位处理时间 假设所有作业的处理时间相等，不妨设为 1。此时，$j \prec k$ 表示 $j < k$ 且 $w_j \leq w_k$。假设调度是阶梯形的，即对于作业的每个前缀 $1, \ldots, k$，分配到每台机器的作业数量随机器索引单调递减。 定义 1：如果对于每个作业 $k$，$\mu(k) = |\{j < k : \sigma_{\mu}(j) = \sigma_{\mu}(k)\}| + 1$，则调度 $\mu$ 是阶梯形的。 任何调度都可以转换为阶梯形调度而不改变任何作业的完成时间。 定义 2：如果对于每个 $j \prec k$，都有 $\mu(j) \leq \mu(k)$，则调度 $\mu$ 是 Smith 单调的。 引理 1：对于单位处理时间，存在一个最优调度是 Smith 单调且阶梯形的。 证明思路：定义势函数 $\sum_{j \in J} \mu(j)j$，假设 $\mu$ 是在最优且阶梯形的调度中使该势函数最大的解。若 $\mu$ 不是 Smith 单调的，则存在违反 Smith 单调性的紧对 $j \prec k$。通过交换 $j$ 和 $k$ 的机器分配，可以得到一个势函数更高但成本不增加的调度。若新调度不是阶梯形的，对作业进行排序可解决此问题，且不会改变完成时间，这与原调度的选择矛盾。 ##### 3.2 一般处理时间 对于一般处理时间，可能不存在最优的 Smith 单调调度，但可以在目标函数上损失一个常数因子的情况下施加这种结构。 给定一般问题的实例 $I$，通过将每个作业 $j \in J$ 替换为一组 $p_j$ 个连续的作业 $U(j) = \{j_1, \ldots, j_{p_j}\}$，每个作业的处理时间为 1，权重为 $\frac{w_j}{p_j}$，得到单位处理时间的实例 $I_{unit}$。设 $J_{unit}$ 是 $I_{unit}$ 的作业集，$opt_{unit}$ 是 $I_{unit}$ 的最优成本。 引理 2：$opt_{unit} \leq opt - \sum_{j \in J} \frac{1}{2}(p_j - 1)w_j$ 引理 3：$I$ 的最优 Smith 单调调度的成本至多为 $opt_{unit} + \sum_{j \in J}(p_j -