多个列表的排列

Question

我需要将工人安排到特定轮班的工作岗位。工人们对他们希望从事的工作设定了优先顺序。工作时间最少的工人优先获得工作机会。只有一名工人可以从事某项特定工作。

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

例如，下面是 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] 包含第二个工人偏好列表，依此类推。在此示例中，第一个工作人员选择了工作 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. 你的工人根据“谁先选择”进行排序
2. 时，偏好会按降序排列，并且
3. 每个工人应该只分配一个任务

，那么我认为工作分配算法应该可以以类似 O( n2 log(n))) 使用两个游标和已分配的作业列表。

是否还有您未说明的其他解决方案优化要求？：例如，

1. 您需要找到为最少的工人分配作业的解决方案没有任何偏好。或
2. 所有分配的工作的偏好等级总和应是数学上可能的最低值。

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

如果您所说的“有效解决方案”是指所有工人都从其偏好列表中获得工作的任何工作分配，那么我会质疑您的算法作为现实世界轮班工作分配问题的答案的适用性。你常常会以找不到解决方案而告终。

Answer 2

假设严格遵守资历/优先级（我知道我公司的每小时职位发布对资历严格），你可以简化事情：

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
}

现在，如果你没有严格的遵守政策，那么你正在考虑一个优化问题，并且问题是，您是否允许较高优先级的个人获得较低优先级的工作代码？

大多数优化算法并不具有与轮班工人相同的“公平”概念。

Answer 3

如果您在将员工分配给某个职位时将其从列表中删除，则后续的职位选择将会更快。另一种看待它的方法是遍历员工列表一次，对于每个员工，遍历他们的工作偏好并将他们分配给他们偏好列表中的第一个空缺职位。这样您只需查看每个员工一次。