具有多個列表的排列

我需要將工人置於某個班次的工作中。工作人員對他們希望工作的工作設置了優先順序。工作時間最少的工人在工作中獲得第一選擇。只有一名工人可以從事某項工作。具有多個列表的排列

我試圖通過創建鋸齒陣列來解決這個問題。該陣列由最小時間的工人排序。每個子數組都是特定的工人偏好列表。數組中的數字是作業代碼。然後我生成排列，直到我得到一個有效的解決方案。

例如，下面列出了28名工人以及每位工人的工作偏好。

int[][] preference = { 
    new int[] {1,2,3,4,5,6,7,8,11,12,13,14,15}, 
    new int[] {2,4,5,6,7,8,11,12,13,14,15}, 
    new int[] {1,3,6,7,8,9,10,14,15,18,19,22,23,24,26,27,29,30,32,34,35,25,36}, 
    new int[] {4,5,12,13}, 
    new int[] {9,10,11,14,15,1,2,6}, 
    new int[] {9,10,11,14,2,6,18,19,27,29,30,31,32,35}, 
    new int[] {11,12,13,14,2,4,5,6}, 
    new int[] {12,13,4,5}, 
    new int[] {9,10,11,13,14,15,1,2,6,7,8,18,19,21,22,23,24,26,27,28,29,30,31,32,34,35,16,17,33,36}, 
    new int[] {1,2,9,10,11,14,15,18,19,30,31,32,35,37,33}, 
    new int[] {4,13,18,19,35}, 
    new int[] {18,19,35}, 
    new int[] {21,22,23,24,18,19}, 
    new int[] {22,23,24,25,18,19,16,17}, 
    new int[] {18,19,23,24,35}, 
    new int[] {18,19,23,24,35}, 
    new int[] {27,26,28,29,30,32,34,35,36}, 
    new int[] {27,26,30,32,34,35,36}, 
    new int[] {28,29,30,31,32,33,35}, 
    new int[] {28,29,30,31,32,33,26,35,36}, 
    new int[] {26,29,30,31,32,34,35,36}, 
    new int[] {28,29,31,32,33,26,35,36}, 
    new int[] {27,28,29,30,31,32,35,33,1,2,3,9,10,11,14,18,19,6,15}, 
    new int[] {34,35,36,26,27,31,32}, 
    new int[] {31,32,34,35,2,11,14,18,19,23,24,6,15,16,17,20}, 
    new int[] {37,29,30,31,32,35,33,36,2,9,10,11,14,18,19,23,24,6,15,16,17}, 
    new int[] {18,19,35}, 
    new int[] {18,19,35}, 
};

preference[0]包含第一個工人喜好列表。 prererence[1]包含第二個工作人員Perference列表，依此類推。在這個例子中，第一個工人已經選擇工作1,2,3,4,5,6,7,8,11,12,13,14,15。正確的解決方案是：1,2,3,4,9,10,11,12,14,15,13,18,21,22,23,24,27,26,28,29,30,31,32,34,6,37,19,35。

我遇到的問題是性能問題。我嘗試使用遞歸循環和非遞歸循環迭代，性能非常糟糕。我的想法是必須有一個不同的方法來解決這個問題，或者一個已經可以購買的圖書館。預先感謝您的幫助。

來源

2011-05-09 Larry

您可否詳細說明「然後我生成排列，直到我得到一個有效的解決方案。」？爲什麼不簡單地重新列出清單，併爲每個員工列出他們的第一個可用工作？解決方案的正確性標準是什麼？ – captncraig 2011-05-09 20:03:40

我假設兩名工人不能做同樣的工作，所以你必須計算出每個人對於「最喜歡的」工作選擇有多接近的最小總和 – BrokenGlass 2011-05-09 20:06:06

你的*正確*解決方案似乎很奇怪。誰的工作號碼是5？爲什麼在14和15之前選擇13？請您詳細說明所需的輸出，並提供更多關於迄今爲止所做的工作的信息（如CMP建議的） – 2011-05-09 20:14:57

當你有

你的員工按照「誰可以先拿」
的偏好按優先和
分類每個工人應該交由只有一個分配

然後我認爲工作分配算法應該可以使用兩個光標和一個已經分配的作業列表在O（n2 log（n））之類的東西中執行。

是否存在您未說明的其他解決方案優化要求？

您需要找到解決方案，儘可能少的工人分配他們沒有偏好的工作。或
所有分配作業的偏好等級的總和應該是數學上最低的。

如果這樣算法會更復雜。

如果你的意思的，所有的工人都從自己的喜好列表得到一個工作職位的任何分配有效的解決方案，那麼我會質疑你的算法的適用性的回答爲現實世界輪班工作分配問題。你經常會沒有解決方案。

來源

2011-05-09 20:53:39

如果您將員工從列表中刪除，因爲他們被分配到工作中，後續的工作選擇將會更快。另一種看待這種情況的方式是沿着員工名單走下去，並且讓每位員工順着他們的工作偏好，將他們分配到他們的偏好列表中的第一個開放工作。這樣你只能看到每個員工一次。

來源

2011-05-09 20:57:56

首選項的排序很重要，只是使用布爾將忽略它。工人0最想要工作1，工作要少15。 – Kris 2011-05-09 21:19:31

@Kris - 你是對的 - 我錯過了按照優先順序排列工作的部分。已應用編輯。 – 2011-05-09 21:38:54

假設嚴格遵守資歷/優先級（我知道在我的公司時薪招聘職位嚴格WRT工齡），你可以簡化事情：

var availableJobs = new List<int>(... jobs here ...); 
var usedJobs = HashSet<int>(); 
var selectedJobs = new Dictionary<int,int>(); // keyed by employee # 

for (int ww = 0; ww < preference.Count(); ++ww) 
{ 
    // this will throw an exception if strict ordering is unsolvable 
    try 
    { 
     // Remove the try...catch if job cannot be 0 and use FirstOrDefault 
     int job = preference[ww].First(jj => !usedJobs.Contains(jj)); 
     selectedJobs.Add(ww, job); 
     usedJobs.Add(job); 
    } 
    catch(InvalidOperationException ioe) 
    { 
     Console.WriteLine("Cannot allocate job code to worker: {0}", ww); 
     Console.WriteLine("No job preference matches."); 
     Console.WriteLine(" Job codes avaliable"); 
     Console.WriteLine(" -------------------"); 
     foreach (var jobCode in availableJobs.Except(usedJobs)) 
     { 
      Console.WriteLine("{0}", jobCode); 
     } 

     break; 
    } 
} 

if (selectedJobs.Count() == preference.Count()) 
{ 
    // jobs have been assigned per worker 
}

現在，如果你沒有嚴格遵守政策，那麼你正在尋找一個優化問題，問題就變成了你是否允許優先級更高的人獲得更低優先級的工作代碼？

大多數優化算法並沒有相同概念，即您的輪班員工可能擁有「公平」的概念。

來源

2011-05-09 22:45:34 user7116

具有多個列表的排列

回答

相關問題