具有多个列表的排列

我需要将工人置于某个班次的工作中。工作人员对他们希望工作的工作设置了优先顺序。工作时间最少的工人在工作中获得第一选择。只有一名工人可以从事某项工作。具有多个列表的排列

我试图通过创建锯齿阵列来解决这个问题。该阵列由最小时间的工人排序。每个子数组都是特定的工人偏好列表。数组中的数字是作业代码。然后我生成排列，直到我得到一个有效的解决方案。

例如，下面列出了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

具有多个列表的排列

回答

相关问题