跳转至

# 在一台机器上规划任务

你有 𝑛 n 个任务，要求你找到一个代价最小的的顺序执行他们．第 𝑖 i 个任务花费的时间是 𝑡 𝑖 t i，而第 𝑖 i 个任务等待 𝑡 t 的时间会花费 𝑓 𝑖(𝑡)f i(t) 的代价．

形式化地说，给出 𝑛 n 个函数 𝑓 𝑖 f i 和 𝑛 n 个数 𝑡 𝑖 t i，求一个排列 𝑝 p，最小化

𝐹(𝑝)=𝑛∑𝑖=1 𝑓 𝑝 𝑖(𝑖−1∑𝑗=1 𝑡 𝑝 𝑗)F(p)=∑i=1 n f p i(∑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 个位置上的数和 𝑖 +1 i+1 个位置上的数交换得到的排列．则

𝐹(𝑝′)−𝐹(𝑝)=𝑐 𝑝′𝑖 𝑖−1∑𝑗=1 𝑡 𝑝′𝑗+𝑐 𝑝′𝑖+1 𝑖∑𝑗=1 𝑡 𝑝′𝑗−(𝑐 𝑝 𝑖 𝑖−1∑𝑗=1 𝑡 𝑝 𝑗+𝑐 𝑝 𝑖+1 𝑖∑𝑗=1 𝑡 𝑝 𝑗)=𝑐 𝑝 𝑖 𝑡 𝑝 𝑖+1−𝑐 𝑝 𝑖+1 𝑡 𝑝 𝑖 F(p′)−F(p)=c p i′∑j=1 i−1 t p j′+c p i+1′∑j=1 i t p j′−(c p i∑j=1 i−1 t p j+c p i+1∑j=1 i t p j)=c p i t p i+1−c p i+1 t p i

于是我们使用如果 𝑐 𝑝 𝑖 𝑡 𝑝 𝑖+1 −𝑐 𝑝 𝑖+1 𝑡 𝑝 𝑖 >0 c p i t p i+1−c p i+1 t p i>0 就交换的策略做一下排序就可以了．写成 𝑐 𝑝 𝑖 𝑡 𝑝 𝑖 >𝑐 𝑝 𝑖+1 𝑡 𝑝 𝑖+1 c p i t p i>c p i+1 t p i+1 的形式，就可以理解为将排列按 𝑐 𝑖 𝑡 𝑖 c i t i 升序排序．

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

### 指数代价函数

考虑代价函数的形式为 𝑓 𝑖(𝑥) =𝑐 𝑖 e 𝑎 𝑥 f i(x)=c i e a x，其中 𝑐 𝑖 ≥0,𝑎 >0 c i≥0,a>0．

我们沿用之前的思路，考虑将 𝑖 i 和 𝑖 +1 i+1 的位置上的数交换引起的代价变化．最终得到的算法是将排列按照 1−e 𝑎 𝑡 𝑖 𝑐 𝑖 1−e a t i c i 升序排序．

### 相同的单增函数

我们考虑所有的 𝑓 𝑖(𝑥)f i(x) 是同一个单增函数．那么显然我们将排列按照 𝑡 𝑖 t i 升序排序即可．

## Livshits–Kladov 定理

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

- 线性函数：𝑓 𝑖(𝑡) =𝑐 𝑖 𝑡 +𝑑 𝑖 f i(t)=c i t+d i，其中 𝑐 𝑖 ≥0 c i≥0；
- 指数函数：𝑓 𝑖(𝑡) =𝑐 𝑖 e 𝑎 𝑡 +𝑑 𝑖 f i(t)=c i e a t+d i，其中 𝑐 𝑖,𝑎 >0 c i,a>0；
- 相同的单增函数：𝑓 𝑖(𝑡) =𝜙(𝑡)f i(t)=ϕ(t)，其中 𝜙(𝑡)ϕ(t) 是一个单增函数．

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

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

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