單機調度

單機調度也被稱為單資源調度，是計算機科學和運籌學中的一個最佳化問題。在這一問題中，我們有從 $J_{1}$ 到 $J_{n}$ 這 $n$ 個工作，每項工作所需處理時間都不盡相同。我們所需要做的便是將這些工作在機器上進行排程，使其目標函數（諸如吞吐量）實現最佳化。

單機調度問題是同機調度問題的特殊情況，而同機調度又是最優作業調度的特殊情況。許多常見的NP困難問題在單機調度問題中都可以在多項式時間內解決。^[1]^:10-20

在最優作業調度問題的標準三字段表示法中，單機變量在第一個字段中用1表示。例如 $1||\sum C_{j}$ 可以用來表示無約束的同機調度問題，其目標是最小化完成時間的總和。

變體[編輯]

最小化加工周期問題 $1||\sum C_{\max }$ 在多機調動中經常被當成目標函數，但在單機調度中意義不大。在單機調度中，我們經常選擇一些其他的目標函數進行研究：^[2]

$1||\sum C_{j}$ $1||\sum C_{j}$ 是最小化完工時間總和的問題，該問題可用最短處理時間優先（英語：Shortest Processing Time First，SPT）原則來解決，即優先解決處理時間短的任務。
- $1||\sum w_{j}C_{j}$ 是最小化加權完工時間總和的問題，該問題可用加權最短處理時間優先（英語：Weighted Shortest Processing Time First，WSPT）原則來解決，即優先解決權重和處理時間之比（ $p_{j}/w_{j}$ ）更大的任務。^[2]^{:lecture 1, part 2}
- $1|chains|\sum w_{j}C_{j}$ 是在具有任務順序限制的情況下最小化加權完工時間總和的問題，這類問題可以通過泛化的加權最短處理時間優先原則來解決。^[2]^{:lecture 1, part 3}
$1||L_{\max }$ $1||L_{\max }$ 是最小化最大延遲時間的問題，在這類問題中，每個工作 $j$ $j$ 都存在一個截止日期 $d_{j}$ $d_{j}$ ，如果在截止日期之後才完成任務，那麼就會產生一個延遲，延遲的定義是 $L_{j}:=C_{j}-d_{j}$ $L_{j}:=C_{j}-d_{j}$ 。這類問題可以用最早截止日期優先（英語：Earliest Due Date First，EDD）原則來解決，即優先解決 $d_{j}$ $d_{j}$ 靠前的任務。^[2]^{:lecture 2, part 2}
- $1|prec|h_{\max }$ 問題是 $1||L_{\max }$ 問題的泛化。這個問題允許對任務設定前後順序，並且允許對每個任務的延遲都設定一個成本函數 $h_{j}$ 。這一目標函數可以通過一種被稱為勞勒算法的貪心算法進行最小化。^[2]^{:lecture 2, part 1}
- $1|r_{j}|L_{\max }$ 問題也是 $1||L_{\max }$ 問題的泛化。這一問題允許對每一項任務設定推出時間 $r_{j}$ ，每項任務都不得在推出時間之前進行，這就導致了機器可能處於閒置狀態。這是一個NP難度的問題，但是可以採取分支定界算法進行優化。^[2]^{:lecture 2, part 3}
$1||\sum U_{j}$ $1||\sum U_{j}$ 是最小化遲到任務數量的問題，但是不考慮每個遲到任務的延遲。這一問題可以使用霍奇森-摩爾算法進行優化。^[3]^[2]^{:lecture 3, part 1}
- $1||\sum w_{j}U_{j}$ 是最小化加權後遲到任務數量的問題。這是一個NP難度的問題，因為在每個任務的截止時間都相等（ $1|d_{j}=d|\sum w_{j}U_{j}$ ）的特殊情況下，這一問題等價於背包問題。^[2]^{:lecture 3, part 2}
現假定在截止時間之前完成任務就能得到 $p_{j}$ 的收益，反之則無收益。問題的目標是最大化收益。這一問題屬於NP困難的問題，計算機科學家薩爾塔伊·薩尼找出了指數時間的準確算法和多項式時間的近似算法。^[4]