OI-wiki 单机任务调度问题（Job Order）：邻项交换微扰法与 Livshits–Kladov 定理全解

OI-wiki 单机任务调度问题Job Order邻项交换微扰法与 Livshits–Kladov 定理全解【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本文围绕 OI-wiki 杂项板块的「在一台机器上规划任务」问题见 docs/misc/job-order.md其在站点导航中的条目位于 mkdocs.yml系统讲解单机调度中以最小代价顺序执行任务的经典模型从问题形式化定义出发推导线性、指数、相同单增三类代价函数下的最优排列策略并最终给出完整刻画该问题可排序性的 Livshits–Kladov 定理。读完本文你将掌握邻项交换微扰这一排序类贪心问题的核心分析工具并能独立完成此类题目的排序比较器设计。问题定义你有 $n$ 个任务要求找到一个代价最小的顺序来执行它们。第 $i$ 个任务花费的时间是 $t_i$而第 $i$ 个任务等待 $t$ 的时间会花费 $f_i(t)$ 的代价。形式化地说给出 $n$ 个函数 $f_i$ 和 $n$ 个数 $t_i$求一个排列 $p$最小化$$ F(p)\sum_{i1}^nf_{p_i}\left(\sum_{j1}^{i-1}t_{p_j}\right) $$也就是说第 $i$ 个被执行的任务 $p_i$ 的代价只取决于它开始执行前所有已执行任务耗时的总和即它等待的时间。这个模型对应真实场景中一台机器机器串行处理、每个工件加工时间固定、完成/延迟代价随等待时间增长的经典单机调度问题与 Johnson 问题单机版本同源。问题的核心难点在于$n$ 个任务的排列共有 $n!$ 种直接枚举不可行。但如果代价函数具有某种可交换性我们就能通过邻项交换判断任意相邻两项的先后次序从而把整个问题归约为一次排序。线性代价函数首先考虑所有函数都是线性函数的情形即$$ f_i(x)c_ixd_i $$其中 $c_i$ 是非负整数。显然常数项 $d_i$ 与执行顺序无关可以事先把它们全部加起来因此函数就转化为 $f_i(x)c_ix$ 的形式代价只与单位等待时间的惩罚系数 $c_i$ 和等待时间成正比。邻项交换分析考虑两个排列 $p$ 和 $p$其中 $p$ 是把 $p$ 的第 $i$ 个位置上的数和第 $i1$ 个位置上的数交换得到的排列。则$$ \begin{aligned} F(p)-F(p)c_{pi}\sum{j1}^{i-1}t_{pj}c{p{i1}}\sum{j1}^{i}t_{pj} -\left(c{p_i}\sum_{j1}^{i-1}t_{p_j}c_{p_{i1}}\sum_{j1}^{i}t_{p_j}\right)\ c_{p_i}t_{p_{i1}}-c_{p_{i1}}t_{p_i} \end{aligned} $$推导的关键在于交换相邻两项只影响这两项各自的等待时间它们之前任务的累计时间 $\sum_{j1}^{i-1}t_{p_j}$ 不变之后任务的累计时间也不变因此总代价差只由这两项的 $c,t$ 决定。当 $c_{p_i}t_{p_{i1}}-c_{p_{i1}}t_{p_i}0$ 时交换后 $F(p)F(p)$即 $p_i$ 排在 $p_{i1}$ 前面是更劣的选择应该交换。排序规则于是我们使用如果 $c_{p_i}t_{p_{i1}}-c_{p_{i1}}t_{p_i}0$ 就交换的策略做一次排序即可。把判别式写成$$ \dfrac{c_{p_i}}{t_{p_i}}\dfrac{c_{p_{i1}}}{t_{p_{i1}}} $$的形式就可以理解为将排列按 $\dfrac{c_i}{t_i}$升序排序。注意这里有一个经典的实现陷阱当 $t_i0$ 时 $\dfrac{c_i}{t_i}$ 会出现除零。实际写排序比较器时应当使用交叉相乘的整数形式c[a] * t[b] c[b] * t[a]即把 $b$ 排在 $a$ 前面更优作为比较函数既避免浮点误差也避免除零。这本质上是分数比较的标准技巧与 OI-wiki 中分数规划相关讨论见 docs/misc/frac-programming.md中处理比率比较的思路一致。方法论提炼处理这个问题我们的思路是考虑微扰后的变换情况贪心地选取最优解假设当前已有一个最优排列任意取相邻两项交换这两项计算目标函数的变化量若交换使答案变优则说明当前次序错误由任意相邻两项都无需交换推出全局最优的排序比较器。这种邻项交换微扰法是证明按某关键字排序即得最优类贪心的通用框架其成立依赖目标函数对排列的交换满足可传递的比较关系。指数代价函数考虑代价函数的形式为$$ f_i(x)c_i\mathrm{e}^{ax} $$其中 $c_i\ge 0,a0$。沿用之前的思路考虑将第 $i$ 和第 $i1$ 个位置上的数交换引起的代价变化。设这两项之前的总等待时间为 $T$则交换前的贡献为$$ c_{p_i}\mathrm{e}^{aT}c_{p_{i1}}\mathrm{e}^{a(Tt_{p_i})} $$交换后的贡献为$$ c_{p_{i1}}\mathrm{e}^{aT}c_{p_i}\mathrm{e}^{a(Tt_{p_{i1}})} $$若交换更优后者更小即$$ c_{p_{i1}}(1-\mathrm{e}^{at_{p_i}})c_{p_i}(1-\mathrm{e}^{at_{p_{i1}}}) $$注意到 $a0$ 且 $t_i0$ 时 $1-\mathrm{e}^{at_i}0$整理即得交换更优当且仅当$$ \dfrac{1-\mathrm{e}^{at_{p_i}}}{c_{p_i}}\dfrac{1-\mathrm{e}^{at_{p_{i1}}}}{c_{p_{i1}}} $$最终得到的算法是将排列按照$$ \dfrac{1-\mathrm{e}^{at_i}}{c_i} $$升序排序。实现时同样建议使用交叉相乘规避浮点问题指数部分可用std::exp计算。相同的单增函数考虑所有 $f_i(x)$ 都是同一个单增函数 $\phi(x)$ 的情形。此时每个任务的惩罚曲线完全一致只有等待时间 $t_i$ 不同。那么显然等待时间短的任务越早执行其后的每个任务都能少等一段时间因此将排列按照 $t_i$升序排序即可。这是一个非常直觉化的结论也可以用邻项交换立即验证若相邻两项 $t_{p_i}t_{p_{i1}}$交换后第 $i1$ 项少等 $t_{p_i}-t_{p_{i1}}$第 $i$ 项多等同样长度而 $\phi$ 单增交换一定不劣。Livshits–Kladov 定理前文的三类代价函数看似各有各的排序规则但它们并非孤立的特例——Livshits–Kladov 定理指出这些情况恰好是单机调度问题可被简单排序求解的全部情形。Livshits–Kladov 定理问题的最优解可以通过简单排序在 $O(n\log n)$ 时间内求出当且仅当代价函数是以下三种情况之一线性函数$f_i(t) c_it d_i$其中 $c_i\ge 0$指数函数$f_i(t) c_i \mathrm{e}^{a t} d_i$其中 $c_i,a0$相同的单增函数$f_i(t) \phi(t)$其中 $\phi(t)$ 是一个单增函数。定理是在假设代价函数**足够平滑存在三阶导数**的条件下证明的。直观理解前两类函数保证了任意两项的交换判据只依赖两项自身参数线性情形依赖 $\dfrac{c_i}{t_i}$指数情形依赖 $\dfrac{1-\mathrm{e}^{at_i}}{c_i}$且该判据构成全序因此可以排序第三类则直接退化为按 $t_i$ 排序。一旦代价函数形变超出这三类例如不同任务拥有形状各异的凸函数邻项交换的判据就可能不再传递简单排序无法保证全局最优需要转向动态规划、费用流等其他手段。小结代价函数形式排序关键字复杂度线性$f_i(x)c_ixd_i$$c_i\ge 0$$\dfrac{c_i}{t_i}$ 升序$O(n\log n)$指数$f_i(x)c_i\mathrm{e}^{ax}$$c_i\ge 0,a0$$\dfrac{1-\mathrm{e}^{at_i}}{c_i}$ 升序$O(n\log n)$相同单增$f_i(x)\phi(x)$单增$t_i$ 升序$O(n\log n)$核心要点回顾**微扰法邻项交换**是此类排序贪心问题的万能起点固定其余任务只交换相邻两项并计算代价差线性情形应使用交叉相乘的整数比较器c[a] * t[b] c[b] * t[a]排序避免浮点误差与除零当且仅当代价函数属于 Livshits–Kladov 定理给出的三类时问题可以在 $O(n\log n)$ 内通过简单排序解决识别可排序性是解题关键题目给出的代价函数若不在三类之内不要贸然设计排序贪心。本文内容主体来自 OI-wiki 的 docs/misc/job-order.md该页面在杂项板块的定位见 docs/misc/index.md其站点导航配置见 mkdocs.yml。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考