精读笔记

Problem Setting

论文实际解决的是 classical single-machine deadline selection 中一个很具体但有价值的问题：Lin-Wang 的 insertion-only SJF greedy 规则能否被直接高效实现，以及这个规则产生的所有解到底有什么组合结构。

真正困难点不在于判断一个固定集合是否 feasible，因为 EDF prefix inequalities 已经给出标准判据；困难在于 greedy pass 中要动态、反复地测试“当前接受集 + 一个候选任务”是否仍满足所有 deadline-prefix constraints。朴素检查每个 deadline prefix 会给 O(n^2)。

以前方法的卡点是表示层。Moore-Hodgson 用 deadline order 加删除最长任务，算法简单且经典，但不是 insertion-only SJF 语义；Zhao-Yuan 实现了同一类 SJF greedy，但维护 backward preemptive schedule 和 DD-interval family，复杂度证明依赖 amortized interval changes。本文要解决的关键矛盾是：SJF greedy 的选择逻辑很简单，但已有高效实现的状态表示并不简单。

Motivation

已有路线不够的地方不是渐近复杂度，而是机制透明度。Zhao-Yuan 已有 O(n log n)，所以本文不是在追求更快的大 O，而是在去掉 schedule-level 状态、preemption 表示和 amortized interval bookkeeping。

作者的核心观察是：insertion-only SJF greedy 在执行时根本不需要知道具体调度长什么样，只需要知道所有 deadline-prefix slack 是否非负。也就是说，实现层面不必维护 schedule；维护 prefix inequality 的最小 slack 就够了。

理论上的缺口则是：Lin-Wang / Zhao-Yuan 知道这个规则是 optimal 的，但“所有 tie-breaking 输出形成什么结构”并没有被完全暴露。本文把这个缺口推进到 prefix optimality、lex-first threshold characterization、tier matroid、laminar matroid 和 polymatroid rank。

Core Idea

核心思想是把调度问题从“构造一个可行调度”改写为“维护一组 deadline-prefix 容量约束”。每个 deadline 节点只需要两个聚合量：子树总 work 和子树内最小 local prefix slack。插入一个任务只会增加某个 deadline 及其右侧 prefix 的负载；如果根节点最小 slack 仍非负，则所有 prefix constraints 仍成立。这样，feasibility test 从 schedule manipulation 变成 balanced BST 上的局部聚合更新。

更深一层的思想是：SJF 顺序不是任意 greedy order，而是在逐步固定最短 processing times。它的 inductive bias 是“先占用短作业的可行容量”，因此每个 greedy prefix 都是同 cardinality 下 total execution 最小的 feasible set。equal-length tier 内没有长度优先级可用，剩余自由度正好由 deadline-prefix residual capacity 形成 nested constraints。这是本文和 prior 的本质区别：不是通过 schedule representation 证明 greedy 可执行，而是通过 prefix slack 和组合结构解释 greedy 为什么成立。

Method

第一，deadline-prefix slack 维护解决的是动态 feasibility test。需要它是因为每个候选任务是否可接受取决于所有不早于其 deadline 的 prefix gaps；核心变化是把 O(n) prefix scan 压缩成 root minimum slack 查询。

第二，augmented balanced BST 解决的是 worst-case 更新复杂度。每个 deadline key 聚合相同 deadline 的 work，节点维护 x = subtree work 和 y = subtree minimum local slack。旋转或插删后只需常数时间 recompute 节点聚合，因此每个 candidate 是 O(log n) 插入、O(1) root test、失败时 O(log n) 删除。这里没有 schedule reconstruction，也没有 interval amortization。

第三，exchange proof 解决的是 SJF greedy 的 optimality 归因。关键 lemma 表明，如果 greedy prefix 没被某个 execution-minimal feasible set 包含，可以交换进一个 greedy 任务并换出同长度任务，同时保持 feasibility 和 total execution minimality。这直接给出 prefix optimality：第 i 个 greedy prefix 等于 short(S,i)。

第四，tier orthogonality / nested matroid 解决的是 tie-breaking 的结构。较短 tier 固定后，某个 equal-length tier 内能选哪些任务只由 residual slack 的 chain constraints 决定，即 |Y cap D_k| <= b_k。这把 tie-breaking 影响限制在同长度层内，并说明所有 greedy outputs 是这些 tier matroids 的 direct-sum bases。

第五，flow-polymatroid 视角不是实现算法，而是把 prefix constraints 写成 cut constraints。max-flow value r_S(X) 是一个 polymatroid rank；对固定 lower-tier greedy set 做 contraction，可以恢复 tier nested matroid。这是结构解释，不是性能来源。

Key Insight / Why It Works

最核心的有效性来自一个很朴素但被用得很干净的事实：对于 1||sum U_j，feasibility 没有隐藏状态，完全由 EDF deadline-prefix inequalities 决定。因此只要能动态维护 minimum prefix slack，就已经维护了全部可行性信息。本文算法贡献的本质是 representation compression：从 schedule/interval representation 压缩到 deadline-keyed prefix aggregates。

SJF greedy 为什么能保证 optimality，关键不只是“短作业优先”这个口号，而是 exchange argument 中的长度守恒。若 greedy prefix 与某个同基数 execution-minimal feasible set 不一致，最早分歧的 greedy 任务可以换入，并通过选取 minimum-deadline 的待换出任务保证 prefix feasibility；由于原集合已是 total execution 最小，换入任务长度必须等于换出任务长度。这个等长结论非常关键：它把所有非确定性压缩到 equal-execution tiers。

我认为本文最实质的贡献有两个：一是 augmented slack BST 给出非常直接的 worst-case O(log n) candidate test；二是 tier orthogonality + nested matroid 把 SJF greedy 的 tie-breaking 空间说清楚。flow-polymatroid 视角更像结构统一语言，漂亮但对算法性能不是必要条件。

哪些部分可能只是 engineering：O(n log n) 不是新复杂度，且 red-black tree augmentation 是标准技巧；增益来自把要维护的量选对，而不是新的 data structure。哪些部分不是 scaling：没有数据、没有训练、没有 benchmark scaling；这里是纯组合算法与结构证明。所谓 generality 也有限，主要 generalize 在 arbitrary tie-breaking 和所有 greedy outputs 的刻画，而不是调度模型的外延扩展。

Relation To Prior Work

最接近的是三条线：Moore-Hodgson、Lin-Wang、Zhao-Yuan。Moore-Hodgson 是 classical optimal algorithm，但处理顺序是 deadline order，并允许删除已接受任务；它解决原问题，但不是本文关注的 insertion-only SJF rule。Lin-Wang 给出 SJF-greedy / critical-set optimality 条件，是本文规则来源。Zhao-Yuan 已经给出 O(n log n) 实现，并进一步支持 number-length tradeoff。

本文真正不同的是实现状态。Zhao-Yuan 把 feasibility 嵌入 backward preemptive schedule 的 interval family；本文把 feasibility 嵌入 prefix slack 的 augmented BST。两者渐近复杂度相同，但信息流完全不同：前者维护一种调度证据，后者只维护所有 deadline-prefix constraints 的最小余量。

看似新的部分中，balanced BST augmentation 本身是已有思想重组；flow network 也是 prefix constraints 的自然 cut formulation。实质创新在于把这些标准工具正好放在 SJF insertion-only greedy 上，并给出完整的 tie-breaking 输出结构：equal-length tier 是 nested matroid，整体是 laminar matroid，greedy outputs 是其 bases。这比单纯证明某个固定 tie-breaking optimal 更强。

Dataset / Evaluation

这不是实验型论文，没有 dataset、benchmark 或 empirical evaluation。主要 claim 是理论性质：正确性、O(n log n) worst-case 实现、lex-first characterization、matroid / polymatroid structure。这些 claim 由证明支撑即可。

如果把 Section 4 的实现简化视为工程 claim，文中没有真实实现、运行时间、常数因子或 memory comparison。它充分证明了 asymptotic worst-case bound 和状态复杂度更简单，但没有证明在实际 workload 上一定优于 DD-interval implementation。

evaluation 覆盖范围仅限理论模型：single machine、all tasks released at zero、nonpreemptive feasibility by EDF、comparison-based RAM、real-valued arithmetic constant time。它没有验证跨 scheduling variants 的泛化，也没有真实系统部署层面的 evidence。

Limitation

核心前提很强：所有任务在 time zero 可用，单机，目标是最大化 on-time task count，且 feasibility 可由 deadline-prefix inequalities 完全刻画。一旦有 release times、weighted tardiness、多机、precedence constraints 或 setup times，prefix slack 这个充分统计量大概率不再成立。

scalability 上限也明确：它把 greedy pass 做到 O(n log n)，但排序已经 O(n log n)，且没有突破已知渐近界。对很多实际变体，真正瓶颈可能不是此处的 prefix feasibility test。

结构结果的上限在于解释 greedy outputs，而不是给出全 feasible family 的 matroid。论文也明确说 feasible sets generally need not form a matroid；只有在 equal-length tier 条件化之后才出现 nested matroid。因此这个 matroid 结构不是原问题的全局可交换性，而是 SJF order 与 equal-length residual constraints 共同诱导出的局部结构。

文中未充分说明这些结构能否产生新的算法能力。例如 laminar matroid bases 精确等于 greedy outputs，但是否能用于更复杂 objective、枚举、sampling、sensitivity analysis，文中没有展开。flow-polymatroid 视角的增益来源也偏解释性；作为算法工具的新增价值不清。

Takeaway

• 1. 对这类 scheduling greedy，真正值得维护的不是 schedule，而是 feasibility certificate 的最小充分统计量；这里就是 deadline-prefix slack。
• 2. SJF greedy 的 optimality 不是一般 greedy miracle，而是“短作业优先 + execution-minimal exchange + equal-length tie freedom”的组合结果。
• 3. equal-length tier 是理解 tie-breaking 的正确粒度；一旦短 tier 固定，剩余选择变成 nested matroid，这个 insight 可迁移到其他按 weight/length 分层的 greedy 问题。
• 4. flow-polymatroid 提供了一个统一解释：prefix constraints 是 cut constraints，tier matroid 是 residual capacity contraction 后的 unit-tier 结构。

一句话总结

这篇论文把 Lin-Wang insertion-only SJF greedy 从一个需要复杂调度表示支撑的规则，重写成基于 deadline-prefix slack 的直接 O(n log n) 算法，并用 tier matroid / polymatroid 精确解释了它的 tie-breaking 结构。