跳至內容

單機調度

維基百科,自由的百科全書

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

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

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

變體

[編輯]

最小化加工周期問題在多機調動中經常被當成目標函數,但在單機調度中意義不大。在單機調度中,我們經常選擇一些其他的目標函數進行研究:[2]

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

參考文獻

[編輯]
  1. ^ Eugene L. Lawler, Jan Karel Lenstra, Alexander H. G. Rinnooy Kan, David B. Shmoys. Chapter 9 Sequencing and scheduling: Algorithms and complexity. Handbooks in Operations Research and Management Science. 1993-01-01, 4: 445–522 [2022-02-23]. ISSN 0927-0507. doi:10.1016/S0927-0507(05)80189-6. (原始內容存檔於2022-02-23) (英語). 
  2. ^ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 Grinshpoun, Tal. Subjects in Scheduling. www.youtube.com. 2020 [2021-09-12]. (原始內容存檔於2022-03-03). 
  3. ^ Knapsack-like scheduling problems, the Moore-Hodgson algorithm and the ‘tower of sets’ property. Mathematical and Computer Modelling. 1994-07-01, 20 (2): 91–106 [2022-03-03]. ISSN 0895-7177. doi:10.1016/0895-7177(94)90209-7可免費查閱. (原始內容存檔於2022-03-11) (英語). 
  4. ^ Sahni, Sartaj K. Algorithms for Scheduling Independent Tasks. Journal of the ACM. 1976-01-01, 23 (1): 116–127. ISSN 0004-5411. doi:10.1145/321921.321934.