基于列生成发来解决工人分配的鲁棒分配为题及其算法研究（2）

郑梦莉

摘要：本文主要利用列生成算法来解决鲁棒分配问题。我们需要找到一种合理分配工人在不同岗位的方法。这个问题仿照一个线性问题来解决。我们寻找一个启发式算法，通过解决各个子问题来找到解决问题的模型。我们先用线性问题研究在一个岗位上的最大缺勤人数。

然后我们用贪婪启发式来解决多个工作岗位的鲁棒问题，并把这部分用java语言编辑并且运用CPLEX软件优化。

最后，多个工作岗位分配的鲁棒问题借助于整数线性问题建模。我们希望最终可以完成整个问题的建模。

关键词：鲁棒优化，列生成算法，贪婪启发式，java，CPLEX

1二分图中的完全耦合分析

在这个章节里，我们会给出几个定义，和一些对二分图中的完全耦合分析的结果。

1.1鲁棒问题

重新回忆一下RAP问题，鲁棒性的分配问题（Robust Assignment Problem，RAP）是为了来找出最大可缺勤人数。也就是在工作岗位和工人之间有一个一一对应的关系。

一个鲁棒性的分配问题可以模型化为一个二分图G（U ∪V，E），在这个图形中，U集合的元素对应了每个工作时间段，集合V对应了工作员工。如果V集合中的一个员工v在U集合的某一工作时间u工作，那么U和V之间就产生了一条线段uv，而k就是可以接受的最大缺勤数。而我们鲁棒性分配问题的目的，是为了使k最大化。

根据定理2：如果一个两部分组成的图形G（U∪V，E），当且仅当|NG（U'）| ≥ |U'|+k，图形G对于U是k-完全耦合。我们可以给出一个线性整数问题，来计算G中的最大k。

如果x是一个非0即1的数字，定义为：

那么，鲁棒性分配问题，就可以模型化为：

限制条件（1）指出，如果u是U'集合中的一个元素，那么u所代表的员工一次性只能选择一个工作岗位。限制条件（2）确保了u至少是一个子集的元素。在[Laroche et al.，2013]中指出并证明，我们可以在有限的时间内很容易的解决这个问题，甚至是针对于很多个时间点工作岗位，以及成千上万的员工。

1.2二分图中完全耦合分布的定义

我们回忆一下RAPm问题，多个岗位上的鲁棒性分配问题（RAPm）是在多个岗位上分配工人的问题。也就是说在每个岗位上可以允许的最大缺勤人数。

如果有一个多岗位上的鲁棒分析问题，我们把每个员工看作一个节点，并且我们把员工这些节点的集合命名为V。另外，对于每一个时间点，我们也给出一些节点的集合，命名为Ui（i是1...m的整数）。这个集合的元素代表了每个时间点需要的最少员工数。我们标记为U = ∪i∈1，...，mUi。

最后，对于每一个员工v ∈ V和每一个时间点i ∈ {1， ...， m}，我们确定了一条两个节点之间的线段uiv。如果员工v可以在ui时间点工作，那么他们之间就有一条属于集合E的线段。也就是说，E是线段uiv的集合。

下面的文章中，我们把RAPm多个岗位上的鲁棒分配问题标记为G（U ∪ V， E）。那么G（U ∪ V， E）就是一個二分图，U = {U1， ...， Um}是集合U的一部分。我们称V中的一种分配为V'= {V1， V2， ...， Vm}，当且仅当对于所有的i ∈ {1， ...， m}，子图形Hi = G[Ui ∪ Vi] （？i ∈ {1， ..， m}） 是k完全耦合，V'是k完全耦合（k-MCC）。

我们把最大可能k标记为kmax，也就是说对于所有的i ∈ {1， ...， m}，Hi都是k完全耦合。在二分图中的鲁棒完全耦合问题（PCCRB）就是考虑如何找出一个V集合的分配方法，来给出一个最大数k，以满足所有的子图形Hi = G[Ui ∪ Vi]是k完全耦合。

例子： 我们用下面的图形来考虑一个RAPm多个岗位上的鲁棒性分配问题。

图片1：多个岗位上的鲁棒性分配问题图型

对于图片1中的多个岗位上的鲁棒性分配问题，我们最优化的解决办法在下图2中给出。

图片2：图片1多个岗位上的鲁棒性分配问题解决办法

重新考虑，对于子图形H1 = G[U1∪V1]，我们可以删除任意一个节点v ∈ V1，剩下的U1仍旧满足是一个完全耦合图形。所以，H1是一个1-完全耦合图形。对于子图形H2，我们可以删除任意一个节点v ∈ V2，剩下的U2仍旧满足是一个完全耦合图形。所以，H2是一个1-完全偶和图形。

所以，在图形G中，V = {V1， V2}是一个1-完全耦合图形。

1.3紧密的整数线性问题

如果G是一个二分图并U = {U1， ..， Um}是这个图形的组合。我们重新考虑PCCRB问题的目的，就是为了找出一个G图形的分配方法V = {V1， ..， Vm}，能够使得G图形的每一个子图形都是一个k-完全耦合。在下面的文章中，我们把G图形所有Ui ∪ Vi的子图形标记为Hi。

限制条件（4）确保每个V集合内的元素v，仅出现在一个分配方案V中。限制条件（5）确保了在每一个时间节点，定理2的正确性：如果一个两部分组成的图形G（U∪V，E），当且仅当|NG（U'）| ≥ |U'|+k，图形G对于U是k-完全耦合。

参考文献（Reference）

[1] Sakarovitch， M. （1984）. Optimisation combinatoire： Programmation discrte （Vol. 2）. Editions Hermann.

[2] Hall，P.： A Contribution to the Theory of Groups of Prime-Power Order.Proceedings of the London Mathematical Society， 29-07， （1934）

[3] Hall， T. （1938）. Sur l'approximation polynomiale des fonctions continues d'une variable reelle. Neuvieme Congrrs des Mathemticiens Scandianaves， 367-369.

[4] Bipartite Matching Vertex Interdiction Problem. S.Martin， Z.Roka， F.Marchetti， P.Larocheendprint