在一台机器上规划任务

你有 个任务，要求你找到一个代价最小的的顺序执行他们。第 个任务花费的时间是 ，而第 个任务等待 的时间会花费 的代价。

形式化地说，给出 个函数 和 个数 ，求一个排列 ，最小化

特殊的代价函数

线性代价函数

首先我们考虑所有的函数是线性的函数，即 ，其中 是非负整数。显然我们可以事先把常数项加起来，因此函数就转化为了 的形式。

考虑两个排列 和 ，其中 是把 的第 个位置上的数和 个位置上的数交换得到的排列。则

于是我们使用如果 就交换的策略做一下排序就可以了。写成 的形式，就可以理解为将排列按 升序排序。

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

指数代价函数

考虑代价函数的形式为 ，其中 。

我们沿用之前的思路，考虑将 和 的位置上的数交换引起的代价变化。最终得到的算法是将排列按照 升序排序。

相同的单增函数

我们考虑所有的 是同一个单增函数。那么显然我们将排列按照 升序排序即可。

Livshits-Kladov 定理

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

• 线性函数：，其中 ；
• 指数函数：，其中 ；
• 相同的单增函数：，其中 是一个单增函数。

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

---

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