6.1 随机调度的基本概念

离线调度

TODO:

在线调度

在线调度（On-Line scheduling）指任务的处理时长未知的调度。对于 $1|r_j| \sum C_j$ 调度模型而言:

• 单机调度时，给定 $n$ 个任务，其处理时间分别为 $C1, …, Cn$，其被调度时刻为 $r1, …, rn$
• 是一个 NP-hard 问题
• 如果所有任务的调度时刻相同，则可以使用 SPT（最短处理时间优先, shortest processing time first）策略解决此问题
• SPT 是一个在线调度算法（每当单机空闲时，处理一个具有最短处理时间的任务）。
• 定理：对于 $1|r_j|\sum C_j$ 的 SPT-算法具有常数竞争率
• 可以更好吗？最好是什么程度？下界：竞争率至少为 2

竞争分析

• 一个在线算法具有 $\rho$-竞争率，如果他的目标值不超过 $\rho$ 乘以所有实例的最优在线值
• 竞争率与在线设置的近似值有关
• 一个允许随机化的在线算法（允许随机选择）则竞争分析使用期望值来进行计算

$\alpha$-调度器

调度算法：

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;

• 对于固定的 $\alpha$, $\alpha$-调度器是一个确定性算法
• 对于 $\alpha$ = 1, $\alpha$-调度器的竞争率为 2
• 其他 $\alpha$ 值具有更高的竞争率
• 定理: 任何随机在线 $\alpha$-调度器算法具有竞争率 $e / (e-1) \simeq 1.582$，其中 $\alpha$ 根据概率密度函数 $f(\alpha) = \frac{ e^\alpha }{ e - 1 }$ 进行选择
• 定理: Any randomized on-line algorithm for problem $1|r_j| \sum C_j$ 问题的任何随机化在线算法竞争率至少为 $e/(e-1)$ 。