New results in two identical machines scheduling with agreement graphs

收录于 TCS 2019 的一篇文章，基于许可图的独立双机流水安排问题的一些新进展。

问题模型

有 \(n\) 个任务，第 \(i\) 个任务需要的时间是 \(p_i\) 。

一共有两台机器，每个任务都需要被连续地安排到某一个机器上完成。

将任务抽象成点，给定一个许可图，两个任务有边则可以分别在两个机器上同时执行。

求一个安排方案，最小化最后一个被做完的任务完成时间。

现有结论：

• 许可图是树的情况下，此问题是 NP-Hard 的
• 许可图是毛毛虫的情况下，存在 \(\mathcal{O}(n)\) 求最优解的方法

毛毛虫

毛毛虫是一种特殊的树，由一个核心路径和若干到路径距离为 \(1\) 的点构成。

Notation

Meaning	Notation
Processing time	\(p\)
Maximum weighted independent set of the agreement graph \(G\)	\(I_p(G)\)
Weight of \(I_p(G)\) (a lower bound on the optimal makespan)	\(\overline{I_p}(G) =\sum_{j\in I_p(G)} p_j\)
Set of neighbors of a job \(j\) (generalized for a subset \(J'\))	\(N(j)/N(J')\)
Set of leaves connected to job \(j\)	\(Lv(j)\)
Starting time of a job \(j\)	\(t_j\)
Minimum starting time of a subset \(J'\)	\(t_j(J')=\min_{k\in J'}\{t_k\}\)

Algorithm

见原文 [4.2] Caterpillar scheduling algorithm。

Polynomiality and Optimality Proof

为了简单描述，我们称在 MWIS 里的点为黑点，其余点为白点。

可以发现断掉白点之间的所有边后，这个新的图的性质是所有的边都是黑-白边。

Claim 1. 对于每个新的连通块 \(CAT_i\) ，其内的黑点集 \(S_i^*\) 仍然是 \(CAT_i\) 的 MWIS

假设存在其他的 MWIS \(I_p(CAT_i)\) 使得 \(\overline{I_p}(CAT_i) > \sum_{j\in S_i^*} p_j\) ，那么我们考虑将 \(CAT_i\) 这一部分的 MWIS 换成这个新的集合，其他部分的 MWIS 不变，那么还原回仍是原图的一个 IS，而这个新的 IS 比原来的 MWIS 权值还大，所以矛盾了。 \[ \sum_{j \in S^{\prime}} p_{j}=\overline{I_{p}}(C A T)-\sum_{j \in S_{i}^{*}} p_{j}+\overline{I_{p}}\left(C A T_{i}\right)>\overline{I_{p}}(C A T) \]

Claim 2. 对于每个新的连通块 \(CAT_i\) 的点集 \(J_i\) ，其内任何一个白点子集的点权和不会超过其邻居黑点的点权和

假设存在这样的一个白点集 \(W\) 满足 \(\sum_{j \in W} p_{j} > \sum_{j \in N(W)} p_{j}\) ，那么考虑将 \(S_i^*\) 换成 \(S'= (S_i^*\setminus N(W))\cup W\) ，易证\(S'\) 也是一个独立集，且比 \(S_i^*\) 权值和还要大，矛盾。 \[ \sum_{j \in S^{\prime}} p_{j}=\sum_{j \in S_{i}^{*}} p_{j}-\sum_{j \in N(W)} p_{j}+\sum_{j \in W} p_{j}>\sum_{j \in S_{i}^{*}} p_{j} \]

Claim 3. 对于任意白点 \(\beta\) ，其邻居黑点都会被连续地安排在第一个机器上

分类讨论一下，如果是叶子显然；如果不是叶子，假设链上的顺序是 \(\alpha-\beta-\gamma\) ，那么黑点顺序显然是 \(\alpha-(\beta\) 的叶子 \()-\gamma\)

Claim 4. 对于任意两个白点 \(\alpha,\beta\) ，如果他们被连续地安排在了某一个机器上，那么他们一定有公共邻居。

同样分类讨论 \(\alpha\) 和 \(\beta\) 的位置关系（分别是主干/叶子）即可。

Claim 5. 对于任意连续安排的白点集，其邻居一定是被连续安排在一个区间内的

前两条的自然结果，当然也需要第二条辅助理解一下，证明黑色一定是连续的。

---

Lemma 1. 每一个白点都会被安排在邻居对应的区间里

反证法，不符合的就两种情况：

1. \(t_\beta < t(N(\beta ))\) ：这种情况不存在，因为算法中每个黑点是连续安排的，如果出现该情况，这个白点会与非邻接的黑点重合，与许可图的要求相冲突。
2. \(t_\beta+p_\beta > t(N(\beta )) + \sum_{j\in N(\beta)} p_j\) ：这种情况不存在，考虑从 \(\beta\) 往前的第一个满足 \(t_\alpha=t_{N(\alpha)}\) 的任务 \(\alpha\) ，那么从 \(\alpha\) 到 \(\beta\) 这一段是连续安排的，由事实 \(5\) ，连续安排的白点集，其邻居一定是被连续安排在一个区间内的，因此白点的区间就是 \([t_\alpha,t_\alpha+\sum_{j\in[\alpha,\beta]} p_j]\) ，黑点的区间就是 \([t(N([\alpha,\beta])),t(N([\alpha,\beta])) + \sum_{j\in N([\alpha,\beta])} p_j]\) ; 又由事实 \(2\) ，对于 \(J_i\) 内任何一个白点子集，其点权和不会超过其邻居黑点的点权和，因此有 \(t_\alpha+\sum_{j\in[\alpha,\beta]} p_j \le \sum_{j\in N([\alpha,\beta])} p_j\) ，因此 \([\alpha, \beta]\) 这一段的白点终止时间不超过黑点，因此作为最后一个完成的白点 \(\beta\) ，有 \(t_\beta+p_\beta \le t(N(\beta )) + \sum_{j\in N(\beta)} p_j\)

Theorithm 2. 本算法求出的安排方案为最优解。

由引理 \(1\) ，每个 \(\sigma_i\) 所需要的时间就是其中黑点所需的时间，即 \(\overline{I_p}(CAT_i)\) ，因此总方案 \(\sigma\) 所需的时间 \(\sum_{i} \overline{I_p}(CAT_i) = \overline{I_p}(CAT)\) ，即答案下界。

总结

最后放一个 pdf 版的总结：