單機調度

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

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

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

變體

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

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