Jasper 记录生活，也记录思考

数学

调度问题

“一个任务有m个子任务，每个任务完成时间不等，系统最高可以进行n个并发处理，如何通过编排处理顺序，使得任务完成时间尽可能的短。” 这个问题是我在上班时处理数据时遇到的，当时处理数据我开了200并发，其中任务大概有400个，其中399个很快就解决了，但是剩下的一个很大，下载的时间超过了其他任务的总和，我就在想如果把大的任务放到早的时候开始处理，尽可能的增加并发的时间，可以缩短整个任务的总和时间，为了把这个速度处理到最优，我开始问ai关于这个问题的最优算法，发现这个问题很深，且目前人们并没有找到一个算法可以在多项式时间内，找到最优排布。感觉很有意思，学到了很多，此笔记为记录对这个问题的学习。

问题定义

  • 输入：m 个任务，处理时长 $p_1, \dots, p_m$；n 台并行机器（并发位）
  • 目标：最小化完工时间（makespan）$C = \max_k L_k$，其中 $L_k$ = 机器 k 的负载 这里的负载是指的一个机器的总运行时间。

首先明确，最小时间是肯定存在的，我们需要遍历m和n的所有组合，然后取最快的时间就行了，这样的组合数为$n^m$种，每种的时间计算的复杂度为O（m），总的复杂度为O（$mn^m$） O（m）解析：首先我们确定每种排布时间，先要算每个机器的负载，再对负载进行比较，每个机器的负载要进行m-n次加法，比较要进行n-1次，总的操作为m-1次，复杂度取首项。（比较操作等价于相减看符号）

然后我的想法是让长的任务，尽可能早的运行。这在算法领域被称为贪心算法，对于调度问题，被称为LPT算法 规则：任何机器空出来 → 立刻从剩余任务中挑最长的开始。 开工时启动最长的 n 个；此后”空位即补最长”，任务耗尽前零空闲

首先我要举一个反例来证明这不是最优排布： 5个任务[10,10,8,7,7],两台机器 按照LPT的排序，A机器处理[10,8,7],B机器处理[10,7]，时长为25。 最优排法是A处理[10,10],B机器处理[8,7,7]，时长为22。 一些补充：最优排布运行时间是有下界的，当所有机器一直同时运转到刚好结束就是最快的，所以这个任务的下界21，但由于任务是离散的，所以不一定有一个排布可以让机器刚好结束。每种排布的差异时间就是有机器多空闲的时间。

既然不是最优排布，我们接下来要思考它能多接近最优排布。 这个关系在1969年被Graham证明：$C_{LPT} \le \left(\frac{4}{3} - \frac{1}{3n}\right) OPT$，$C_{LPT}$是LPT时间，OPT为最优时间 可以看出，LPT最多也就比OPT多1/3，这是很好的算法， 接下来给出证明： 设定：n 台相同机器，m 个任务，时长 $p_1 \ge p_2 \ge \cdots \ge p_m$（按 LPT 安排顺序编号）。OPT 表示最优完工时间。

第 0 步：不妨设”任务 m 最后完成” 若最后完成的不是任务 m，就从实例中删掉任务 m：

  • 任务 m 是 LPT 最后一个考虑的，删掉它不改变其余任务的分配 ⟹ $C_{\text{LPT}}$ 不变
  • 少一个任务，最优解面对的实例更容易 ⟹ $OPT$ 不变或变小 把新的最后完成的任务当成m，证明这个更紧的不等式，原不等式自动成立，所以只需证明m最后完成的情况。 — 第 1 步：关键不等式 设任务 m 在时刻 $S$ 开始（它是最后完成的，$C_{\text{LPT}} = S + p_m$）。 LPT 把任务 m 分给了当时负载最小的机器，因此在时刻 S，所有 n 台机器的负载都 ≥ S。 时刻 S 各机器已分配的任务互不相交、且不含任务 m，所以总工作量满足： \(n \cdot S + p_m \le \sum_{i=1}^{m} p_i\) 而任何排布的完工时间 ≥ 平均负载：$\sum p_i \le n \cdot OPT$ （OPT可以完成所有任务，OPT时间n个机器一起运行肯定可以完成所有任务）。联立： \(S \le OPT - \frac{p_m}{n}\)

代入完工时间： \(C_{\text{LPT}} = S + p_m \le OPT + p_m\left(1 - \frac{1}{n}\right) \quad (\star)\)

第 2 步：情形一（$p_m \le OPT/3$）——直接得证（最小的任务是“小任务”） 代入 $(\star)$： \(C_{\text{LPT}} \le OPT + \frac{OPT}{3}\left(1 - \frac{1}{n}\right) = \left(\frac{4}{3} - \frac{1}{3n}\right)OPT \quad\) —

第 3 步：情形二（$p_m > OPT/3$）（最小的任务是“大任务”） 前提注意：任务 m 是最小的，所以所有任务都 > OPT/3。 用反证法：假设 $C_{\text{LPT}} > OPT$，即 \(S > OPT - p_m \quad (\ast)\) 步骤 A：证明OPT 的装填限制m ≤ 2n OPT 的每台机器负载 ≤ OPT，装 3 个每个都 > OPT/3 的任务必然超载。所以OPT 每台机器至多装 2 个任务。 LPT情况的证明 事实 1：时刻 S 之前，每台机器恰好有 1~2 个任务 至少1个：若某机器为空，则最闲机器负载为 0，S = 0，从而 $C_{\text{LPT}} = p_m \le OPT$（任务 m 在任何排法中都要跑完 $p_m$），与假设 $(\ast)$ 矛盾。 （不可能有一台机器从没有跑过，如果这样只有一轮，那LPT=OPT）

至多 2 个：反设某机器 X 装了 3 个任务 $x_1 \ge x_2 \ge x_3$（每个 > OPT/3）。设 i = 恰好装 1 个任务的机器数。 从 LPT 侧数 i（X 有 3 个，其余非单任务机至少 2 个；已分配任务数 = m − 1）： \(m - 1 \ge i + 2(n - i - 1) + 3 \implies i \ge 2n - m + 2 \quad (\heartsuit)\)

从 OPT 侧数 i：单任务机上的任务 ℓ 满足 $\ell \ge S > OPT - p_m$（它是”最闲时刻”的负载之一）。若 ℓ 在 OPT 中与任何任务同机： 「这里的单任务机指的是在LPT中到S时刻，只有一个任务l的机器」 \(\ell + (\text{任何任务} \ge p_m) \ge S + p_m > OPT \quad \text{超载}\) 所以 i 个”长任务”在 OPT 中各自独占一机。OPT 剩 n − i 台机器要装其余 m − i 个任务（每个 > OPT/3，每台至多 2 个）： \(m - i \le 2(n - i) \implies i \le 2n - m \quad (\spadesuit)\) $(\heartsuit)$ 与 $(\spadesuit)$ 矛盾（下界比上界大 2）。因此假设错误，所以$C_{\text{LPT}} <= OPT$，因为OPT是最优，所以$C_{\text{LPT}} = OPT$ 综上，得证 证明界是紧的例子（等号能取到）： 对每个 n，实例”n 台机器、2n+1 个任务：3 个时长为 n，n+1~2n−1 各 2 个”使 LPT 达到比值 $4/3 - 1/3n$ 精确取等——界不能改进。

  • OPT = 3n：三个 n 捆一机，其余首尾配对 $(n{+}i)+(2n{-}i) = 3n$
  • LPT = 4n−1：三个 n 各落一台负载 2n−1 的机器
  • 该实例中 $p_m = n = OPT/3$，恰好位于情形一的边界

对于证明分类的分析： 证明分类其实是讨论的两种情况，大任务情况和小任务情况，大任务情况下，OPT处理最快的机器也至多运行二轮，在这种情况下，LPT的排布会达到最优。小任务情况下，所有机器同时运行的时间比较长，此时最后一轮空闲机器所产生的误差相对比较小，不等式也能成立。 我们可以认为看每个任务的平均最优处理任务数是m/n。当这个数字小于2时可以看作小任务，大于2时作为大任务，这个数字越大，误差越小。所以这个算法的危险区，是当数字介于中间大小，此时LPT的算法性能优化不足，且相对误差比较大。

实操可以进行的补充： 从证明可以看出，当$p_m > OPT/3$时，OPT=LPT，在实操中我们可以根据这个判断LPT是否达到最优排布，但我们是不知道OPT大小的，但我们知道LPT大于等于OPT，所以当，$p_m>=LPT/3$时，我们可以确定我们的LPT算法已经达成最优排布。 {等号情况的补充说明：当$p_m=LPT/3$，假设LPT不等于OPT，则有OPT小于LPT，则有$p_m>OPT/3$,推出LPT=OPT，矛盾，所以假设不成立。所以可以取等。}

LPT算法复杂度解析： LPT（最长处理时间优先）是并行机器调度的经典贪心算法，核心分为排序+作业分配两个串行阶段，总时间复杂度为： \(\boldsymbol{O(n \log n + n \log m)}\)

  • $n$：作业总数
  • $m$：并行机器总数

  • 当 $m \ll n$ 时，总复杂度可近似为 $O(n \log n)$

    一、排序阶段：为什么是 $O(n \log n)$ 核心思想：分治排序 工业界通用的高效排序（归并排序、快速排序、堆排序）均基于分治策略：

  • 拆分：将 $n$ 个元素的数组逐层对半拆分，直到每个子数组仅含1个元素（天然有序）；
  • 合并：从底层开始，逐层将两个有序小数组合并为一个有序大数组，最终得到完整有序序列。 复杂度推导
  • 层数：完整拆分共需约 $\log_2 n$ 层。若 $n$ 不是2的整数次幂，层数向上取整（例如 $(n=9)$ 时共4层，对应 $\log_2 9 \approx 3.17$）。
  • 每层操作量：每一层的所有合并操作，会将全部 $n$ 个元素各遍历处理一次（比较大小、搬运元素），总操作量与 $n$ 成正比，即每层复杂度为 $O(n)$。
  • 总复杂度：总操作量 = 层数 × 每层操作量 ≈ $n \times \log n$，因此时间复杂度为 $O(n \log n)$。 具体是这么做的 假设两个有序列表a=[1,3]和b=[2,5]，空列表[]。下面用a代表有序列表a的长度大小，b同理。 1和2比较，取小的到空列表，3和2比较，取小，3和5比较取小，最后一个5直接拿出放到最后。 一共进行a+b-1次比较，a+b次移动，共2（a+b）-1次操作。可以理解为a+b=n 所以单层操作，2n-1次操作，一共有$[\log_2 n]+1$层。所以一共有$（2n-1）([\log_2 n]+1)$次操作。 复杂度为O（$n\log_2n$）,实际算法实现可以用双指针。 二、分配阶段：堆优化为什么是 $O(n \log m)$

作业分配的核心需求：每次从 $m$ 台机器中快速找到当前总负载最小的机器，分配作业后更新负载。 使用最小堆（优先队列可将朴素遍历的 $O(n \cdot m)$ 优化至 $O(n \log m)$，是量级上的性能飞跃。 最小堆基础

  • 本质：满足「父节点值 ≤ 所有子节点值」的完全二叉树，因此堆顶（根节点）永远是全局最小值。
  • 存储：用一维数组紧凑存储，通过下标可直接计算父子节点位置。
  • 高度特性：$m$ 个节点的完全二叉树，高度约为 $\log_2 m$；节点数每翻倍，高度仅增加1层，这是对数复杂度的根源。 两大核心维护操作： 最小堆的所有结构调整都遵循「单路径移动」原则：每次只沿一条父子路径交换元素，不会遍历整棵树。 （1）上浮调整（插入元素时使用）
  • 触发场景：新元素追加到堆末尾后，向上调整以恢复堆性质。
  • 操作逻辑：新元素从最底层叶子节点开始，逐层与父节点比较；若比父节点小则交换位置，直到满足堆性质或到达堆顶。
  • 单步操作：每层仅与1个父节点做1次比较。
  • 复杂度：最坏情况从底部走到顶部，步数等于堆高度，即 $O(\log m)$。 （2）下沉调整（删除堆顶时使用）
  • 触发场景：删除堆顶后，用最后一个元素填补堆顶空位，向下调整以恢复堆性质。
  • 操作逻辑：从堆顶开始，逐层与左右两个子节点比较；若当前节点不是三者中的最小值，则与最小的子节点交换，直到满足堆性质或到达叶子层。
  • 单步操作：每层与2个子节点做2次比较，仅为常数级差异。
  • 复杂度：最坏情况从顶部走到底部，步数等于堆高度，即 $O(\log m)$。

关键说明：下沉单次循环多1次比较，但只是常数倍差异，大O表示法中会忽略常数系数，因此上浮、下沉的时间量级完全一致，均为 $O(\log m)$。{下沉比上浮多一倍操作，实际为2logm次操作}

标准单轮分配流程：

每分配1个作业，对应完整的「取-改-插」三步：

  1. 取出堆顶最小值，把列表最后数字提到堆顶 → 下沉调整恢复堆结构：$O(\log m)$
  2. 加上当前作业的处理时间：纯加法运算 $(O(1))$（量级可忽略）
  3. 新负载插回堆末尾 → 上浮调整恢复堆结构：$O(\log m)$

单轮分配总复杂度为 $O(\log m)$，共分配 $n$ 个作业，因此分配阶段总复杂度为 $O(n \log m)$。 「堆储存每台机器的当前总负载。」

LPT专属的常数优化方案 虽然无法从逻辑上完全消除向下调整，但针对LPT「删顶+插新严格成对出现」的特性，可以实现常数级别的性能优化，且不改变时间复杂度的量级。 最优常数优化：替换堆顶 + 单次下沉 这是LPT场景下的理论最优实现，相比通用堆流程常数开销直接减半：

  1. 直接读取堆顶最小值（无需删除、无需补位）
  2. 计算新负载 = 最小值 + 当前作业处理时间
  3. 用新负载直接覆盖堆顶的旧值
  4. 从堆顶开始做一次下沉调整，恢复堆性质

优化原理：省去了“用末尾元素补堆顶”和“插入后上浮”两步，仅保留一次必要的下沉调整，总比较次数从约 $3\log_2 m$ 降至约 $2\log_2 m$。

工程层面的可选的额外优化

  • 先定位后交换：先一路向下找到元素的最终位置，再一次性移动元素，比较次数不变，但交换次数从 $\log m$ 次减少到1次，适合大元素场景。
  • 四叉堆实现：将二叉堆替换为四叉堆，堆高度变为 $\log_4 m$，虽然每层比较次数增加，但总比较次数更少，且内存缓存命中率更高，是工业界常用优化手段。
  • 利用作业顺序特性：LPT作业按从大到小分配，越往后作业增量越小，下沉的平均步数少于最坏情况的 $\log m$，实际运行常数低于理论值。 以上所有优化均为常数级性能提升，不会改变 $O(n \log m)$ 的时间量级。对于绝大多数工程场景，直接使用标准库的优先队列即可满足需求，无需额外做常数级优化。

堆的列表实现：下标为 i 的节点：

  • 左子节点下标：2i + 1
  • 右子节点下标：2i + 2
  • 父节点下标：$\lfloor (i-1)/2 \rfloor$，符号是向下取整 列表：[0, 4, 2, 3]的二叉树长下面这样。 
         0
   /   \
 4       2
/
3

    这样

综合上面几步，LPT算法的复杂度为$O(\boldsymbol{n \log nm})$。

LPT是半在线算法，任务以此到达，当任务到达时才知道任务大小。 下面给出半在线算法的相关证明： 1.机器数n=2的情况下LPT半在线算法是最优算法的证明 最优算法定义：在最坏情况下，t（算法）/t（OPT） 最小 第一步：证明2机器情况下，任何算法大于等于7/6 OPT 构造这样一组任务[3,3,2,2,2]（这个构造就是LPT，n为2的紧情况） 对手先发[3,3]，如果算法放同一台，立刻结束，则OPT为3，此算法时间为6，比为2， 如果算法放两台机器，继续发[2,2,2],此时OPT为[3,3],[2,2,2],时间为6，算法负载则至少为7，3+2+2.比值为7/6. 在这个构造下，任何算法，最好也只能做到7/6。 为什么能随时停止：因为任务是陆续到达的，对于同一个算法，我们可以把在不替换顺序的情况下，处理是一样的，既然一样，我们就可以随时停止，然后把任务切换成停止的切片任务。

第二步：在n等于2的情况下，LPT的最坏情况是7/6OPT，上下界闭合，所以LPT是最好算法。

机器数n大于等于3情况下的最优算法下界证明：

模型：3 台机器，任务不增到达、即时不可反悔分配，对手可在任意前缀后收手。目标：证明没有算法能保证竞争比 < c。 设任务列表为下面，x是自由参数 \(S(x)=\big(x,\;x,\;1-x,\;1-x,\;\tfrac13,\;\tfrac13,\;\tfrac13\big)\) 递减性要求 $x \ge 1-x \ge \tfrac13$，即 x ∈ [1/2, 2/3]。除此之外 x 完全自由——证明的最后一步就是让对手把 x 调到最优。 第一步：发前三个任务 x, x, 1−x 前缀最优值：OPT(x,x) = x，OPT(x,x,1−x) = x（3个占3台机器，取最大数x）。

  • 若两个 x 同机：对手收手。时间 ≥ 2x，比值 = 2x/x = 2 （发两个就收手）
  • 若 x 与 1−x 同机：对手收手。该机负载恰为 x+(1−x) = 1，比值 = 1/x。

在 x ∈ [1/2, 2/3] 上，1/x ≥ 3/2。所以任何想活得比 3/2 好的算法都必须把三个任务分放三台机器 第二步：第四个任务 1−x 只有三台机器且都已被占，1−x 只有两类放法。 情形 A：与某个 x 同机 → 对手收手 该机负载 = x + (1−x) = 1。此时只有四个任务 {x, x, 1−x, 1−x}： OPT = 2(1−x)。 证明：任意划分必有某台机器装 ≥ 2 个任务，而任意两个任务之和 ≥ 两个最小任务之和 = 2(1−x)；另一方面划分 {1−x, 1−x}、{x}、{x} 合法且达到此值。

\[\text{比值} 为 \frac{1}{2(1-x)} \;=:\; f_1(x)\]

情形 B：与第三个任务（1−x）同机 → 对手续发 1/3, 1/3, 1/3 该机负载 2(1−x)。全序列的最优值： OPT = 1。证明：总量 = 2x + 2(1−x) + 3·(1/3) = 3，故 OPT ≥ 3/3 = 1 ；划分 {x, 1−x}、{x, 1−x}、{1/3, 1/3, 1/3} 达到 1。 算法放三个 1/3 时：

  • B1：某个 1/3 落到负载 2(1−x) 的机器上 ⇒ 比例为 \(2(1-x)+\frac13 = \frac73 - 2x \;=:\; f_2(x)\)
  • B2：三个 1/3 全部分到两台 x 机器上 ⇒ 抽屉原理，某台至少分到两个 ⇒ 比例为 \(x + \frac23 \;=:\; g(x)\)

\(\text{此情形比值} \;\ge\; \min\big(f_2(x),\, g(x)\big)\) 第三步：找到x 综合所有分支，对手在牌型 S(x) 下的保证值是 \(R(x) = \min\big(\underbrace{1/x}_{\text{第一步}},\; \underbrace{f_1(x)}_{\text{情形A}},\; \underbrace{f_2(x)}_{\text{B1}},\; \underbrace{g(x)}_{\text{B2}}\big)\) 我们需要求R（x）的最大值，找到最为难算法的x 在 [1/2, 2/3] 上：f₁ 从 1 升到 3/2（递增），f₂ 从 4/3 降到 1（递减），g 从 7/6 升到 4/3（递增），1/x ≥ 3/2 始终在上方（非约束）。R(x) 的最大值在 f₁ 与 f₂ 的交点： \(\frac{1}{2-2x} = \frac73 - 2x \;\Longleftrightarrow\; (2-2x)\Big(\frac73-2x\Big)=1 \;\Longleftrightarrow\; 12x^2 - 26x + 11 = 0\) \(x = \frac{26 \pm \sqrt{676-528}}{24} = \frac{13 \pm \sqrt{37}}{12}\) 两根中只有 $x^* = \dfrac{13-\sqrt{37}}{12} \approx 0.5764$ 落在合法区间 [1/2, 2/3]（另一根舍去）。代回： \(c = f_2(x^*) = \frac73 - 2\cdot\frac{13-\sqrt{37}}{12} = \frac{14-(13-\sqrt37)}{6} = \boxed{\frac{1+\sqrt{37}}{6} \approx 1.18046}\) 第四步：验证所有非约束分支都高于 c

  • 递减性：x* ≈ 0.5764 ≥ 1−x* ≈ 0.4236 ≥ 1/3 ✓；
  • 第一步威胁：1/x* = 12/(13−√37) = (13+√37)/11 ≈ 1.7348 > c ✓；
  • 抽屉支线：g(x) − c = (x + 2/3) − c = (19 − 3√37)/12 > 0，因为 19² = 361 > 333 = (3√37)² ✓；
  • c 的方程形式：由 1/(2−2x) = c 及 x = (7−3c)/6，得 2−2x* = (3c−1)/3，即 3/(3c−1) = c，整理为 3c² − c − 3 = 0 ✓。 在牌型 S(x*) 下，算法的每一步都被逼入比值 ≥ c 的分支——任何算法的竞争比都 ≥ (1+√37)/6。 调度问题的竞争比示意 这里并不是说m=3时的最好算法竞争比是(1+√37)/6，而是说所有算法最好竞争比也不会超过这个数，但是否真有算法达到这个最好情况还不确定。 证明m大于等于3时的下界为(1+√37)/6

证明：若 m 台机器有 OPT=1 的递减对抗实例保证比值 ≥ c，则 m+1 台也有。

我们手上有一套在 m 台机器上折磨算法的”剧本”（递减序列 J + 对手策略 S），保证算法最多做到 c。现在想造一套在 m+1 台机器上同样保证 c 的剧本。

只要在序列最前面插一个大小为 G ≈ 0.847 的任务。 四个初始条件：

不变量 解释
(I1) OPT_m(J) ≤ 1 老实例的最优解不超过 1（时间单位已归一化）
(I2) 最小任务 = 1/3，最大任务 ≤ G J 里没有太小的任务，也没有比 G 大的任务
(I3) 每个停止点，算法负载 ≥ 1 老剧本每次收手时，算法至少堆到了 1
(I4) 每个停止点 L ≥ c·OPT 老剧本本身保证比值 ≥ c

三、关键数字 \(G = \frac{\sqrt{37}-1}{6} \approx 0.847, \qquad c = \frac{1+\sqrt{37}}{6} \approx 1.1805, \qquad \frac13 \approx 0.333\) 三个关系记住就行：

  • G + 1/3 = c（所以 G = c − 1/3）
  • c·G = 1（所以 G = 1/c）——这是 c 的方程 3c² − c − 3 = 0 的改写 结合1和2式子就能得到G。G的大小是从这里来的
  • 1/3 < G < 1 拿 SSW 的 m=3 实例当具体例子，全程跟着它走： \(J = (0.576,\ 0.576,\ 0.424,\ 0.424,\ 0.333,\ 0.333,\ 0.333)，\ OPT_3 = 1\) 插入后： \(J' = (\underbrace{0.847}_{G},\ 0.576,\ 0.576,\ 0.424,\ 0.424,\ 0.333,\ 0.333,\ 0.333)，\ 4\ 台机器\) — 四、对手的新策略 S′

先把 G 发出去。然后盯着 G 那台机器：

  • 规则 α：算法敢往 G 的机器上堆任何任务，立刻停止。
  • 规则 β：算法一直不敢碰那台机器，那就让 G 白白占掉一台机器，剩下 m 台机器上把老剧本 S 原样重演一遍。

算法只有这两种活法，只要分别证明两种方法都≥ c。

五、情形 α：算法敢碰 G 的机器——为什么立刻死 假设某一刻，算法把任务 q 放到了 G 那台机器上。 q 是 J 里的任务，由工具 (I2)，J 里最小的任务也有 1/3，所以 \(\text{负载} \ge G + q \ge G + \frac13 = \underbrace{(c-\frac13)}_{G} + \frac13 = c\) 第二步：此刻的 OPT 是多少？ 此刻只打出了 J′ 的一部分任务。两个事实：

  • 整个 J′ 的 OPT 都不超过 1：把 G 单独放一台，J 按最优放进其余 m 台，makespan ≤ max(G, OPT_m(J)) ≤ max(0.847, 1) = 1；
  • 打得越少的任务集，OPT 只会更小。

所以此刻 OPT ≤ 1。 第三步：比值。 \(\text{比值} = \frac{\text{负载}}{\text{OPT}} \ge \frac{c}{1} = c。\)

而且负载 ≥ c > 1，顺手把 (I3′) 也验了。

六、情形 β：算法不碰 G 算法始终绕开 G 的机器。于是 J 的全部任务被塞进了其余 m 台机器——局面和原来的 m 机器博弈一模一样，对手照老剧本 S 打，在 S 的某个停止点收手。设收手时：

  • 算法在这 m 台上的 makespan 为 L（老剧本保证 L ≥ 1 且 L ≥ c·OPT_m(P)）；
  • P 是 J 的某个前缀。 要证的是：在新博弈里，算法的总比值 ≥ c。逐个拆解： (a) 算法的总 makespan = L 总 makespan 是 m+1 台机器里的最大负载：G 那台是 G ≈ 0.847，其余 m 台最大是 L。由工具 (I3)，L ≥ 1 > G，所以 \(\text{总 makespan} = \max(G, L) = L。\) (b) 新 OPT 会涨，但涨不过 G 现在的前缀是 {G} ∪ P，多了个 G，OPT 可能比 OPT_m(P) 大。但它大不了多少——把 G 单独放一台、P 放进 m 台，得到 \(OPT_{m+1}(\{G\}\cup P) \le \max(G,\ OPT_m(P))。\) 新 OPT 被两个数里的较大者封住：要么是 G，要么是老 OPT。 （其实这里的OPT就是OPT（m），G小于1） (c) 两个下界合并，刚好压住新 OPT 我们手里关于 L 有两张牌：
牌 来源
L ≥ c·OPT_m(P) 工具 (I4)，老剧本的保证
L ≥ 1 = c·G 工具 (I3) + 关键恒等式 cG = 1

\(L \ge \max(cG,\ c\cdot OPT_m(P)) = c\cdot \underbrace{\max(G,\ OPT_m(P))}_{\ge\ 新OPT，见(b)} \ge c\cdot OPT_{m+1}(\{G\}\cup P)\) 除以新 OPT：比值 ≥ c

七、无限迭代 新剧本 (J′, S′) 满足

  • (I1′) OPT ≤ 1 ✓（第五步第一步）
  • (I2′) 最小任务还是 1/3（G > 1/3），最大任务变成 G ✓
  • (I3′) 情形 α 收手负载 ≥ c > 1；情形 β 收手负载 = L ≥ 1 ✓
  • (I4′) 两种情形都 ≥ c ✓

——和引理的输入条件一字不差，于是可以把它再喂回引理：m=3 → m=4 → m=5 → …。配合 SSW 基例，所有 m ≥ 3 下界 c 证完。

另一种统一构造证明的方法： 统一显式构造的人工证明 定理：设 c = (1+√37)/6，r = (2+√37)/11 ≈ 0.7348，s = (1+r)/3 = (13+√37)/33 ≈ 0.5783。对任意 m ≥ 4，对抗序列 \(S_m = (\underbrace{1,\dots,1}_{m-1},\ \underbrace{r,\dots,r}_{m-1},\ \underbrace{s,\dots,s}_{m-1})\) 保证任何确定性算法的竞争比 ≥ c。

  1. 前缀 OPT 引理

在对手可能收手的所有前缀上，OPT 只有三个值（已数值核验 m=4,5,6 全部吻合）：

前缀 OPT
$(1^j)，j ≤ m−1；(1^{m−1}, r)$ 1
$(1^{m−1}, r²)$ 2r
$(1^{m−1}, r^j)，j ≥ 3；(1^{m−1}, r^{m−1}, s^k)$，k ≤ 3 1+r

证明要点：

  • 前两个：任务数 ≤ m，各自独占 ✓。
  • 2r：{r,r} 一台 + 其余独占达到 2r（2r > 1）；下界：m+1 个任务 m 台机器必有配对，最便宜的配对就是 {r,r} = 2r（{1,r} = 1+r、{1,1} = 2 都更贵）✓。
  • 1+r（含带 s 的情形）：上界 {1,r}×j + 其余独占（带 s 时：k 个 s 全放第 m 台，ks ≤ 3s = 1+r，恒等式三在此用第一次）。下界用反证：若所有机器负载 < 1+r，则 {1,1}、{1,r}、三 r 同机全被禁（都 ≥ 1+r），于是 m−1 个 1 必须独占 m−1 台，而 ≥ 3 个 r 每台至多 2 个、至少再占 2 台，合计 ≥ m+1 台 > m 台，矛盾；s 也救不了场（{r,r,s} 和 {1,s,s} 都超线，s 只能挂单机上，改变不了计数）。
  1. 对手策略（三阶段）

阶段一：m−1 个 1 两个 1 同机（负载 2）→ 立即收手：OPT = 1，比值 2 > c ✓。 此后被迫：1 分占 m−1 台，剩一台空机 M*。 阶段二：m−1 个 r

  • r₁ 上 1-机器（1+r）→ 收手：OPT = 1，比值 1+r ≈ 1.7348 > c ✓。被迫：r₁ → M*。
  • r₂ 上 1-机器（1+r）→ 收手：OPT = 2r，比值 (1+r)/(2r) = c（恰等） ✓。被迫：r₂ → M*（2r）。
  • r₃ 及以后：OPT 已涨到 1+r，收手线启动（≥ 2r+s 即收手）：
    • 上 M* → ≥ 3r：比值 ≥ 3r/(1+r) = (√37−1)/4 ≈ 1.2707 > c ✓；
    • 上已含 r 的机器 → ≥ 1+2r：比值 ≥ (1+2r)/(1+r) = (11+√37)/12 ≈ 1.4236 > c ✓；
    • 上空的 1-机器 → 1+r：唯一安全，继续。 被迫格局：M* = 2r；m−3 台机器 = 1+r；恰好剩 2 台负载为 1 的机器。 阶段三：s 决胜 收手线仍是 2r+s。算法对 s 的放法只有四类机器可选：
s 放到 新负载 收手比值
M*（2r） 2r+s = c（方程二，恰等）✓
1+r 机器 1+r+s 1 + s/(1+r) = 4/3 > c（恒等式三）✓
空 1-机器 1+s ≈ 1.5783 不触线——唯一安全位
1+s 机器 1+2s (21−√37)/12 ≈ 1.2431 > c ✓

s₁、s₂ 被迫占掉仅有的两台安全机器；第 3 个 s 到达时全场无安全位——对手收手，比值 ≥ c。m−1 ≥ 3 保证 s₃ 存在（这正是 m ≥ 4 的地方）。

CKK算法，目前最好的半在线算法，m=3时，到达下界，证明为最优算法。 下面给出做法： LPT 是”无脑贪心”：每个任务都放当前最空的机器。 CKK 的发现是：只要手里有一个”OPT 至少有多大”的下界 L，就可以给每台机器设一个天花板 c·L——只要全程没机器超过天花板，比值就自动 ≤ c（因为 L ≤ OPT，所以负载 ≤ c·L ≤ c·OPT）。整个 A3 就是”维护下界 + 天花板下填装”。 A3 的三步（m = 3，c = (1+√37)/6 ≈ 1.1805） 第 1 步：前三个任务 p₁, p₂, p₃ 直接分放三台机器 M₁, M₂, M₃。 （只有三个任务时 OPT = p₁，分放零风险。） 第 2 步：第 4 个任务到达时，算一个 OPT 下界 \(L_0 := \max\{p_1,\ p_3 + p_4\}\) 为什么这是下界：OPT ≥ p₁（最大任务总得放某处）；OPT ≥ p₃+p₄（4 个任务塞进 3 台机器，必有一台装两个，而任何一对的和 ≥ 最小两个之和 p₃+p₄）。 然后做全算法唯一的关键决策：

  • 情形一：p₁+p₄ ≤ c·L₀——”最大任务还吃得下 p₄”。把 p₄ 放到 M₁（和 p₁ 同机！负载 p₁+p₄ 仍在天花板下），p₅ 放 M₂，之后所有任务无脑放最空机器。
  • 情形二：p₁+p₄ > c·L₀——”放 M₁ 会爆”。把 p₄ 放到 M₃（和最小的 p₃ 同机，负载 p₃+p₄ ≤ L₀，永远安全）。 第 3 步（情形二的后续）：用更锋利的下界替换 L₀： \(L := \max\{L_0,\ \min\{p_2+p_5,\ p_3+p_4\},\ \dots\}\) （min 那一项来自”5 个任务 3 台机器”的鸽子笼推理：OPT 至少等于某对任务的和，而具体是哪对可以看 p₅ 到了之后收窄。）之后的每个任务：放进”装完仍不超天花板 c·L 的机器中最满的那台”；若所有机器都装不下，才放最空的机器。

CKK算法在m大于等于4的情况下，证明出上界为5/4。在大于4的情况，超过LPT模型，在等于4的情况，和LPT模型一致。这是目前已证明的最优半在线模型。

音乐
星空封面

星空

Jasper

0:000:00