调度中的加权事件图：扩展、归一化与周期性调度

### 调度中的加权事件图：扩展、归一化与周期性调度 #### 1. 加权事件图的扩展与最小扩展 在调度问题中，加权事件图（WEG）的扩展是一个重要概念。当满足一定条件时，WEG 可以进行扩展，转化为非加权的定时事件图，且能精确模拟相同的优先级关系。 - **扩展条件**：对于强连通的标记 WEG，若存在向量 $(N_1, \ldots, N_n) \in N^{*n}$，使得每个位置 $p = (t_i, t_j)$ 能按照特定引理被替换为 $t_i$ 和 $t_j$ 的 $N_i$ 和 $N_j$ 个副本之间的非加权位置，即 $\frac{N_i}{v(p)} = \frac{N_j}{u(p)}$，则该 WEG 是可扩展的。 - **最小扩展**：存在一个最小向量 $N^{\star} = (N^{\star}_1, \ldots, N^{\star}_n) \in N^{*n}$，使得所有满足扩展条件的向量 $N$ 都与 $N^{\star}$ 成比例，即 $N = \lambda \cdot N^{\star}$，其中 $\lambda \in N^{*}$。与 $N^{\star}$ 相关联的标记事件图就是该 WEG 的最小扩展。 例如，对于一个标记 WEG，其系统 $\Sigma(G)$ 为： \[ \Sigma(G) = \begin{cases} \frac{N_2}{5} = \frac{N_3}{2}\\ \frac{N_3}{1} = \frac{N_4}{3}\\ \frac{N_2}{5} = \frac{N_4}{6}\\ \frac{N_1}{3} = \frac{N_2}{1}\\ \frac{N_4}{2} = \frac{N_1}{5} \end{cases} \] 其最小整数解为 $N^{\star} = (15, 5, 2, 6)$。 下面通过一个表格总结扩展相关的关键信息： | 概念 | 定义 | 条件 | | ---- | ---- | ---- | | 可扩展性 | 存在向量 $(N_1, \ldots, N_n) \in N^{*n}$，使位置可替换 | $\frac{N_i}{v(p)} = \frac{N_j}{u(p)}$ | | 最小扩展 | 存在最小向量 $N^{\star}$，其他解与 $N^{\star}$ 成比例 | $N = \lambda \cdot N^{\star}, \lambda \in N^{*}$ | #### 2. 扩展与归一化的关系 强连通的 WEG 可扩展性和可归一化性是等价的，并且存在 $K \in N^{*}$，使得对于任意 $t_i \in T$，有 $Z_i \cdot N_i = K$。 - **可扩展性推出可归一化性**：若 WEG 可扩展，存在向量 $N = (N_1, \ldots, N_n) \in N^{*n}$ 满足 $\frac{N_i}{v(p)} = \frac{N_j}{u(p)}$。定义 $M$ 为 $N_1, \ldots, N_n$ 的最小公倍数，对于每个位置 $p = (t_i, t_j)$，设置 $\gamma_p = \frac{M}{N_i \cdot u(p)} = \frac{M}{N_j \cdot v(p)}$，则可证明该 WEG 可归一化。 - **可归一化性推出可扩展性**：若 WEG 可归一化，对于每个位置 $p = (t_i, t_j)$，有 $v(p) = Z_j$ 和 $u(p) = Z_i$。定义 $M$ 为 $Z_i$ 的最小公倍数，对于任意 $t_i \in T$，设置 $N_i = \frac{M}{Z_i}$，则可证明该 WEG 可扩展。 #### 3. 周期性调度 周期性调度在实际应用中具有重要意义，许多作者为了便于实现调度，常常考虑周期性调度。 - **周期性调度的定义**：一个调度 $\sigma$ 是周期性的，如果每个转换 $t_i \in T$ 都有一个周期 $w_{\sigma}^i$，使得对于所有 $k \geq 1$，有 $S_{\sigma}^{<t_i,k>} = s_{\sigma}^i + (k -