多對多「廣義分配」問題

我遇到了一個特定問題。我必須安排5名員工在14天內工作。每個員工只能在14天內工作9天，每天必須安排3名員工。關鍵部分是每個員工在某一天工作都會有一定的懲罰。因此，如果他們當天無法工作，如果他們能夠工作，並且不介意其懲罰爲零，並且最後如果他們能夠但不希望其懲罰爲5，那麼他們的懲罰爲10。每個員工每天都有一個懲罰值矩陣。我試圖找到一種方法來寫出我的限制。（i，j）= A（i，j）* B（i，j），我想到了矩陣A（罰分矩陣）和矩陣B（調度矩陣）和矩陣C.如果A（i，j）等於0（員工不工作），則給定此設置，那麼將不考慮懲罰，反之亦然。多對多「廣義分配」問題

於是我可以說作爲我的約束：

A（1,1）+ A（1，M）+ A（1，n）的< = 9

和

甲（1,1）+ A（m，1）+ A（n，1）= 3

並且我最小化：C（1,1）+ C（m，m）+ C（n，n）

我這樣看待它的問題是試圖在優化算法中使用它。單純形算法應該能夠解決任何LP問題，但它可能是最慢的。我被卡住了，現在我確信我正在看着這個錯誤的方式。如果任何人都可以給我一個新的眼睛，並可能解釋爲什麼我看着這個錯誤的方式，我將不勝感激。

來源

2013-02-19 Mark

您是否因爲需要更快速度而卡住了？ – 2013-02-19 04:41:47

目前還不清楚你的問題是什麼。由於A（i，j）是二元變量，所以也不可能使用單純形法來解決這個問題。如果你的問題規模相當小，一個好的MIP求解器應該能夠達到足夠的容差。提供更多細節！ – raoulcousins 2013-02-19 06:41:43

此問題與[護士名冊競賽]非常相似（http://docs.jboss.org/drools/release/5.5.0.Final/drools-planner-docs/html_single/index.html#d0e1680）。如果你正在尋找一個開源的實現來複制，[這裏是一個（不是MIP，但是metaheuristics）]（https://github.com/droolsjbpm/drools-planner/tree/master/drools-planner-examples/src/main/java/org/drools/planner/examples/nurserostering/domain）（請參閱[本視頻]（http://www.youtube.com/watch?v=7nPagqJK3bs）中的操作） – 2013-02-19 10:01:35

我認爲你犯了一個模型錯誤，使得你的問題比它需要的更困難。

爲什麼你使用懲罰函數爲「能夠並且願意」，「能夠但不願意」和「無法」建模？難道你不是隻想盡量減少員工被分配一個員工能夠但不願意工作的時間段的次數嗎？（當然，沒有指定任何僱員插槽，他們無法工作？）

如果您修改問題就像我上面提出的，這可以被建模爲一個直接的最小成本流問題。您有一組員工的節點和一組時間段的節點。如果員工能夠處理該時段，則將員工連接到容量爲1的時段。如果員工願意繼續工作，那麼給它一個成本爲0，如果員工不願意繼續工作，則成本爲1。添加一個源和一個接收器;來源應該爲每位員工提供容量爲9（他們可以工作的天數）和零成本的優勢，而每個時間段應該具有容量爲3和零成本的水槽邊緣。

從頭開始編寫最小成本流程求解器相對比較簡單。

如果你想禁止兩個或兩個以上不願意的員工配備時間槽，我認爲你不能將問題建模爲一個整數程序。 GLPK是一個自由的線性和整數程序解算器。這不是最先進的技術，但它在很多問題上都能很好地工作。我懷疑它會在解決像你這樣的小規模實例時遇到麻煩。

來源

2013-02-19 18:58:22 tmyklebu

多對多「廣義分配」問題

回答

相關問題