基于列生成發來解決工人分配的魯棒分配為題及其算法研究（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