在一台机器上规划任务

你有 $n$ 个任务，要求你找到一个代价最小的的顺序执行他们。第 $i$ 个任务花费的时间是 $t_{i}$ ，而第 $i$ 个任务等待 $t$ 的时间会花费 $f_{i} (t)$ 的代价。

形式化地说，给出 $n$ 个函数 $f_{i}$ 和 $n$ 个数 $t_{i}$ ，求一个排列 $p$ ，最小化

F (p) = \sum_{i = 1}^{n} f_{p_{i}} (\sum_{j = 1}^{i - 1} t_{p_{j}})

特殊的代价函数

线性代价函数

首先我们考虑所有的函数是线性的函数，即 $f_{i} (x) = c_{i} x + d_{i}$ ，其中 $c_{i}$ 是非负整数。显然我们可以事先把常数项加起来，因此函数就转化为了 $f_{i} (x) = c_{i} x$ 的形式。

考虑两个排列 $p$ 和 $p^{'}$ ，其中 $p^{'}$ 是把 $p$ 的第 $i$ 个位置上的数和 $i + 1$ 个位置上的数交换得到的排列。则

\begin{aligned} F (p^{'}) - F (p) & = c_{p_{i}^{'}} \sum_{j = 1}^{i - 1} t_{p_{j}^{'}} + c_{p_{i + 1}^{'}} \sum_{j = 1}^{i} t_{p_{j}^{'}} - (c_{p_{i}} \sum_{j = 1}^{i - 1} t_{p_{j}} + c_{p_{i + 1}} \sum_{j = 1}^{i} t_{p_{j}}) \\ = c_{p_{i}} t_{p_{i + 1}} - c_{p_{i + 1}} t_{p_{i}} \end{aligned}

于是我们使用如果 $c_{p_{i}} t_{p_{i + 1}} - c_{p_{i + 1}} t_{p_{i}} > 0$ 就交换的策略做一下排序就可以了。写成 $\frac{c_{p_{i}}}{t_{p_{i}}} > \frac{c_{p_{i + 1}}}{t_{p_{i + 1}}}$ 的形式，就可以理解为将排列按 $\frac{c_{i}}{t_{i}}$ 升序排序。

处理这个问题，我们的思路是考虑微扰后的变换情况，贪心地选取最优解。

指数代价函数

考虑代价函数的形式为 $f_{i} (x) = c_{i} e^{a x}$ ，其中 $c_{i} \geq 0, a > 0$ 。

我们沿用之前的思路，考虑将 $i$ 和 $i + 1$ 的位置上的数交换引起的代价变化。最终得到的算法是将排列按照 $\frac{1 - e^{a t_{i}}}{c_{i}}$ 升序排序。

相同的单增函数

我们考虑所有的 $f_{i} (x)$ 是同一个单增函数。那么显然我们将排列按照 $t_{i}$ 升序排序即可。

Livshits–Kladov 定理

Livshits–Kladov 定理成立，当且仅当代价函数是以下三种情况：

线性函数： $f_{i} (t) = c_{i} t + d_{i}$ ，其中 $c_{i} \geq 0$ ；
指数函数： $f_{i} (t) = c_{i} e^{a t} + d_{i}$ ，其中 $c_{i}, a > 0$ ；
相同的单增函数： $f_{i} (t) = ϕ (t)$ ，其中 $ϕ (t)$ 是一个单增函数。

定理是在假设代价函数足够平滑（存在三阶导数）的条件下证明的。在这三种情况下，问题的最优解可以通过简单的排序在 $O (n \log n)$ 的时间内解决。

本页面主要译自博文 Задача Джонсона с одним станком 与其英文翻译版 Scheduling jobs on one machine。其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0。

本页面最近更新：2023/6/27 13:39:08，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Enter-tainer, ouuan, sshwy, Tiphereth-A
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用