在一台機器上規劃任務

你有 \(n\) 個任務，要求你找到一個代價最小的的順序執行他們。第 \(i\) 個任務花費的時間是 \(t_i\)，而第 \(i\) 個任務等待 \(t\) 的時間會花費 \(f_i(t)\) 的代價。

形式化地説，給出 \(n\) 個函數 \(f_i\) 和 \(n\) 個數 \(t_i\)，求一個排列 \(p\)，最小化

\[ F(p)=\sum_{i=1}^nf_{p_i}\left(\sum_{j=1}^{i-1}t_{p_j}\right) \]

特殊的代價函數

線性代價函數

首先我們考慮所有的函數是線性的函數，即 \(f_i(x)=c_ix+d_i\)，其中 \(c_i\) 是非負整數。顯然我們可以事先把常數項加起來，因此函數就轉化為了 \(f_i(x)=c_ix\) 的形式。

考慮兩個排列 \(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} -\left(c_{p_i}\sum_{j=1}^{i-1}t_{p_j}+c_{p_{i+1}}\sum_{j=1}^{i}t_{p_j}\right)\\ &=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\) 就交換的策略做一下排序就可以了。寫成 \(\dfrac{c_{p_i}}{t_{p_i}}>\dfrac{c_{p_{i+1}}}{t_{p_{i+1}}}\) 的形式，就可以理解為將排列按 \(\dfrac{c_i}{t_i}\) 升序排序。

處理這個問題，我們的思路是考慮微擾後的變換情況，貪心地選取最優解。

指數代價函數

考慮代價函數的形式為 \(f_i(x)=c_i\mathrm{e}^{ax}\)，其中 \(c_i\ge 0,a>0\)。

我們沿用之前的思路，考慮將 \(i\) 和 \(i+1\) 的位置上的數交換引起的代價變化。最終得到的算法是將排列按照 \(\dfrac{1-\mathrm{e}^{at_i}}{c_i}\) 升序排序。

相同的單增函數

我們考慮所有的 \(f_i(x)\) 是同一個單增函數。那麼顯然我們將排列按照 \(t_i\) 升序排序即可。

Livshits–Kladov 定理

Livshits–Kladov 定理成立，當且僅當代價函數是以下三種情況：

線性函數：\(f_i(t) = c_it + d_i\)，其中 \(c_i\ge 0\)；
指數函數：\(f_i(t) = c_i \mathrm{e}^{a t} + d_i\)，其中 \(c_i,a>0\)；
相同的單增函數：\(f_i(t) = \phi(t)\)，其中 \(\phi(t)\) 是一個單增函數。

定理是在假設代價函數足夠平滑（存在三階導數）的條件下證明的。在這三種情況下，問題的最優解可以通過簡單的排序在 \(O(n\log n)\) 的時間內解決。

本頁面主要譯自博文 Задача Джонсона с одним станком 與其英文翻譯版 Scheduling jobs on one machine。其中俄文版版權協議為 Public Domain + Leave a Link；英文版版權協議為 CC-BY-SA 4.0。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用