平行机调度问题-负载均衡问题

问题定义

平行机调度问题（负载均衡问题）：记机器数量为 $m$ ，工件数量为 $n$ ，$x_{ij}$ 表示第 $j$ 个工件是否安排在机器 $i$ 上，$P_{ij}$ 表示第 $j$ 个工件在机器 $i$ 上的负载。求完成所有工件需要的最少负载 $T$ 。整数规划为：

\[ \begin{align*} \min \ &T\\\\ \sum_{j=1}^nP_{ij}x_{ij}\le T,&\ i=1,...,m\\\\ \sum_{i=1}^mx_{ij}= 1,&\ j=1,...,n\\\\ x_{ij} =& \{0,1\} \end{align*} \]

直接将整数规划转化为线性规划的结果并不好：
如： $m$ 个机器，⼀个工件,其⻓度为 $m$ 则整数规划的解为，这个工件放到⼀个机器上， $T=m$；⽽线性规划的解为：拆分工件到 $m$ 个机器，$ T=1$。线性规划给出的下界太松。

参数修剪的线性规划

得到初始的负载 $T_0$ ：可以将所有工件放到⼀个机器上或者⽤ greedy 算法将每个工件放到最⼩的机器，满足 $T_0\le \sum_{i,j} P_{ij}\le mn P_\max$
从 $T_0$ 开始对 $T$ 进行二分查找：若$P_{ij} > T$，则加入 $x_{ij} = 0$ 的约束【这个约束的含义是：当第 $j$ 个工件在第 $i$ 个机器上的负载大于总负载时，第 $j$ 个工件不可能放在第 $i$ 个机器上工作，从而去除一些整数规划中不可能成立的解】。等价的，定义 $S_T = \{(i,j),\vert p_{ij}\le T\}$ ，加入新约束：$x_{ij}\ge 0,\quad (i,j)\in S_T$, 再解线性规划判断 $T$ 是否有可⾏解【用解线性规划两阶段法的第一阶段即可】：
- 若有可行解：对 $T$ ⼆分变⼩后继续迭代
- 若没有可行解：对 $T$ ⼆分变⼤后继续迭代
二分查找的复杂度为 $\log n$ ，由于 $T_0\le mn P_\max$，只需查找 $\log m + \log n + \log P_\max$ 次即可。得到的 $T^*$ 构成了整数规划问题的下界: $T^*\le T_{OPT}$ 。

接下来，可以得到一个负载 $T\le 2T^*$ 的整数解，从而得到一个近似比为 2 的近似算法。

Rounding 算法

构造二分图 $G=(J,M,E)$，左边表示 $m$ 台机器，右边表示 $n$ 个工件。$x_{ij} >0$ 则在机器 $i$ 和工件 $j$ 之间有⼀条边。

考虑二分图连通的情况：如果不连通，则对各连通分量分别进行算法，可以得到结果【证明见下】。

先考虑只分配到一个机器的工件 $x_{ij} = 1$，将那个工件 $j$ 分配给机器 $i$ ，并删除工件 $j$ 的点与 $(i,j)$ 这条边。二分图的连通性不变。
图中只剩下在 $T^*$ 中分配到多个机器上的工件，考虑度为 1 的机器 $i$, 假设唯⼀连的边为 $(i,j)$ ，那么就将整个工件 $j$ 分配给机器 $i$ 然后去掉机器 $i$, 工件 $j$ 以及 $j$ 连的所有边。二分图连通性不变。
剩下的图只能有偶环，可以得到一个完美匹配：⼀个工件匹配到⼀台机器

这样，每台机器除了分配到的完整工件外，最多分配到⼀个原解中拆分到包括自身在内的多个机器的工件。而根据 $T^*$ 的求法，拆分的工件在自身的负载一定小于等于 $T^*$ 。因此，每台机器的总负载最多为 $2T^*$ 。

证明

记可行解 $x$ 为 $T^*$ 中的极点的解，$x$ 对应的二分图为 $G=(J,M,E)$

$LP(T)$ 问题的极点中最多有 $n+m$ 个非零变量

分析问题$LP(T)$ ：

\[ \begin{align*} \sum_{j=1}^nP_{ij}x_{ij}\le T,\ i=1,...,m\\\\ \sum_{i=1}^mx_{ij}= 1,\ j=1,...,n\\\\ x_{ij}\ge 0,\quad (i,j)\in S_T \end{align*} \]

有 $r = \vert S_T\vert$ 个变量。可行解 $x$ 是问题的极点，当且仅当有至少 $r$ 个线性独立约束取等号【在 $r$ 维线性空间中， $r$ 个线性无关的方程才能确定一个点】。则在第三种约束中，至少有 $r-(n+m)$ 个约束取等号。因此，$LP(T)$ 问题的极值点最多有 $n+m$ 个非零变量。

$x$ 中最多有 $m$ 个工件被拆开

记 $x$ 为 $T^*$ 中的极点，在 $x$ 中，$n$ 个工件有 $n_1$ 个工件没有拆分 [对应 1 个非零变量]， $n_2$ 个工件拆分到不同机器上 [对应 2 个及以上非零变量]。由于最多有 $n+m$ 个非零变量，有：

\[ \begin{cases} n_1+2n_2\le m+n \\\\ n = n_1+n_2 \end{cases} \Rightarrow n_2\le m \]

图 $G=(J,M,E)$ 是伪森林 (pseudo-forest)

伪树 (pseudo-tree)：一个连通图中，边的数量少于等于顶点的数量，则成图为伪树。也就是树或者树加上一条边。一棵伪树中最多只有一个环
伪森林 (pseudo-forest)：图中每个连通分量都是伪树，则称它是伪森林

考虑 $G$ 中的连通分量 $G_c$ 。将 $LP(T)$ 和 $x$ 限制在 $G_c$ 中的机器和工件上，得到新的问题与极点 $LP_c(T)$ 和 $x_c$ 。令 $x_\bar{c}$ 代表 $x$ 的其余部分。则，$x_c$ 必须是 $LP_c(T)$ 的极点: 否则，$x_c$ 是 $LP_c(T)$ 的两个可行解的凸组合。两个可行解分别与 $x_\bar{c}$ 一起构成 $LP(T)$ 的可行解。则 $x$ 是 $LP(T)$ 的两个可行解的凸组合，矛盾。