问题定义

平行机调度问题 （负载均衡问题）：记机器数量为 $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$。线性规划给出的下界太松。

参数修剪的线性规划

  1. 得到初始的负载 $T_0$ ：可以将所有工件放到⼀个机器上或者⽤ greedy 算法将每个工件放到 最⼩的机器，满足 $T_0\le \sum_{i,j} P_{ij}\le mn P_\max$
  2. 从 $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$ ⼆分变⼤后继续迭代
  3. 二分查找的复杂度为 $\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$ 之间有⼀条边。

image-20200210110511417

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

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

这样，每台机器除了分配到的完整工件外，最多分配到⼀个原解中拆分到包括自身在内的多个机器的工件。而根据 $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)$ 的两个可行解的凸组合，矛盾。

由于$LP(T)$ 问题的极点中最多有 $n+m$ 个非零变量，因此$LP_c(T)$ 的极点形成的二分图边数少于等于顶点数。 $G_c$ 是伪树。

将分配到一个机器的工件 ($x_{ij} = 1$) $j$ 分配给机器 $i$ ，并删除工件 $j$ 的点与 $(i,j)$ 这条边。设当前的图为 $H$ 【步骤1】

图 $H$ 有一个完美匹配

由于删除了相等数量的边和顶点，因此 $H$ 也是伪森林。

在 $H$ 中，工件的度至少为 2。因此， $H$ 的叶节点都是机器。接着进行步骤 2，将叶节点的机器匹配一个工件后删除机器，工件以及工件连着的所有边。此时，叶节点依然只能是机器，且图依然是伪森林。由于是二分图，最后只会剩下偶环【也有可能没有剩】。

对于偶环，可以找到一个完全匹配，将一个工件匹配到一个机器。

image-20200211114419859

图源：Vijay Vazirani, Approximation Algorithms, Chapter 17，Springer Verlag, 2001.

参考文献：