c# - 多个列表的排列

Question

我需要为给定的类次安排工作人员。 worker 们对他们希望从事的工作设定了偏好顺序。工时最少的 worker 在工作中获得第一优先权。只有一名 worker 可以从事一项特定的工作。

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

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

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] 包含第二个 worker 偏好列表，依此类推。在此示例中，第一个 worker 选择了工作 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。

我遇到的问题是性能。我尝试使用递归和非递归循环进行迭代，但性能很糟糕。我的想法是必须有一种不同的方法来解决问题，或者我可以购买已经这样做的图书馆。在此先感谢您的帮助。

Answer 1

当你有

1. 你的 worker 根据“谁先挑”排序
2. 偏好降序排列
3. 每个 worker 应该只分配一项任务

然后我认为作业分配算法应该可以使用两个游标和已分配作业的列表以类似 O(n2 log(n))) 的方式执行。

是否有您没有说明的其他解决方案优化要求？:例如

1. 您需要找到一种解决方案，让尽可能少的员工分配到他们根本没有偏好的工作。或
2. 所有分配工作的偏好等级总和应该是数学上可能的最低值。

如果是这样算法会更复杂。

如果您所说的有效解决方案是指所有工作人员都从他们的偏好列表中找到工作的任何工作分配，那么我会质疑您的算法作为现实世界轮类工作答案的适用性赋值问题。您经常会以没有解决方案而告终。