# 6.1 隨機調度的基本概念 ## 離線調度 TODO: ## 在線調度 在線調度（On-Line scheduling）指任務的處理時長未知的調度。對于1|rj|∑Cj1|rj|∑Cj調度模型而言: * 單機調度時，給定nn個任務，其處理時間分別為C1,…,CnC1,…,Cn，其被調度時刻為r1,…,rnr1,…,rn * 是一個 NP-hard 問題 * 如果所有任務的調度時刻相同，則可以使用 SPT（最短處理時間有限, shortest processing time first）策略解決此問題 * SPT 是一個在線調度算法（每當單機空閑時，處理一個具有最短處理時間的任務）。 * 定理：對于1|rj|∑Cj1|rj|∑Cj的 SPT-算法具有常數競爭率 * 可以更好嗎？最好是什么程度？下界：競爭率至少為 2 ### 競爭分析 * 一個在線算法具有ρρ\-競爭率，如果他的目標值不超過ρρ乘以所有實例的最優在線值 * 競爭率與在線設置的近似值有關 * 一個允許隨機化的在線算法（允許隨機選擇）則競爭分析使用期望值來進行計算 ### αα\-調度器 調度算法： ~~~ 1. L: list of tasks for which in the optimal preemptive schedule an alpha fraction has already been scheduled at the current time; initially L = {}; 2. proceed in time whereby the preemptive schedule is updated 3. If alpha fraction of task j is finished in preemptive schedule Then 4. add j at the end of L; 5. If machine gets idle Then 6. schedule first job of L or if L is empty proceed in time; ~~~ * 對于固定的αα,αα\-調度器是一個確定性算法 * 對于αα\= 1,αα\-調度器的競爭率為 2 * 其他αα值具有更高的競爭率 * 定理: 任何隨機在線αα\-調度器算法具有競爭率e/(e?1)?1.582e/(e?1)?1.582，其中αα根據概率密度函數f(α)\=eαe?1f(α)\=eαe?1進行選擇 * 定理: Any randomized on-line algorithm for problem1|rj|∑Cj1|rj|∑Cj問題的任何隨機化在線算法競爭率至少為e/(e?1)e/(e?1)。