在一台机器上规划任务

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

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

特殊的代价函数

线性代价函数

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

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

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

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

指数代价函数

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

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

相同的单增函数

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

Livshits-Kladov 定理

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

  • 线性函数:,其中
  • 指数函数:,其中
  • 相同的单增函数:,其中 是一个单增函数。

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


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