工人排班算法

Question

问题

我想要解决的问题本质如下：我们有工人在周末的一定时间内照顾幼儿。一个周末有16个不同的时段需要填充。因此，一个4周的月份有64个时间段需要填充。我们最多有30个托儿所工作人员（虽然我们需要更多人，有没有人喜欢孩子？）。

编辑：每个时间段是离散的 - 它们不重叠。

目前有一个人每个月制定托儿所的时间表。每个月制定这个时间表是一个复杂而耗时的任务，需要考虑到每个人的偏好。考虑了这个问题后，我心想，“肯定有更好的办法！”

算法

我注意到这个问题本质上是一个二分图。 婚姻问题也是一个二分图，你可以使用匹配算法（例如Edmonds's matching algorithm）来解决。

但这假设每个节点在一个节点集中只匹配另一个节点集中的一个节点。在我的情况下，每个托儿所工作人员只会工作一个时间段。由于我们严重缺乏工作人员，这种方法行不通！一些人必须要每月工作两次以填补所有时间段。

这似乎意味着这更像是经典的“医院/住户问题”。它与婚姻问题不同之处在于，“女性”可以接受多个“男性”的“求婚”（例如，一家医院可以接受多个住户）。在我的情况下，一个托儿所工作人员可以选择多个时间段。

现在怎么办？

呼!

现在，我已经完成设置......有人知道任何好的链接可以解释或展示这种算法吗？有更好的方法来解决这个问题吗？我是不是想太多了？我在谷歌搜索“医院住院医师算法”，找到了研究生论文。啊！我拥有计算机科学学位并且上过AI课程......但那是6年前的事情。求助！任何建议都会受到赞赏！

- JonH

---

听起来这对我来说就像是 http://en.wikipedia.org/wiki/Assignment_problem，即使对于足够小的 n（例如64），O(x^n) 的暴力解法也是可行的。 - msw

单个周末的时间段是否重叠？ - Svante

据我理解，这是一个64x30的矩阵，其中包含1/0值 - 1表示工人可以填充时间段。目标是在每个|s|>0的情况下最小化|n|向量的最大值。 - HamoriZ

@msw - 暴力破解是否意味着遍历所有可能的分配，找到匹配项，并选择具有最多分配的那个？ @Svante - 编辑了描述，不，它们不重叠。 - JonH

Answer 1

“医院/居民问题”确实可行，但这取决于您的限制条件：

- 医院有最大容量，并将按照需求程度来排序居民。 - 居民将排序医院。 - 没有其他可能的约束条件。

在您的情况下，医院是工人，而居民是插槽。

- 插槽可以订购工人（也许您更喜欢在早上有经验的工人...）。 - 工人可以订购插槽。 - 但是您不能有其他约束条件，例如：“我早上已经工作了，我不想在同一天晚上再次工作”。

如果这对您来说没问题，那么您有两种可能性：

- 您想优先考虑工人：“以医院为导向的情况”。 您将尝试将工人分配到他们首选的插槽。 - 您想优先考虑插槽：“以居民为导向的情况”。 每个插槽都有他们首选的工人。

我去年不得不编写它，以下是代码。

/* 
RO : needed for Resident-Oriented version
HO : needed for Hospital-Oriented version
*/
const int MAX_R = 1000;
const int MAX_H = 1000;
const int INF = 1000*1000*1000;

您需要填写输入变量。

• R_pref和H_pref是居民/医院的偏好列表
• H_rank[h][r]是r在H_pref[h]中的排名：即h的偏好列表中r的位置

就是这样。

// Input data
int R, H;                   // Number of Residents/Hospitals
int C[MAX_H];               // Capacity of hospitals
vector<int> R_pref[MAX_R], H_pref[MAX_H]; // Preferences : adjency lists
/*RO*/int H_rank[MAX_H][MAX_R];   // Rank : rank of r in H_pref[h]
/*HO*/int R_rank[MAX_R][MAX_H];   // Rank : rank of h in R_pref[r]

无需在下面进行操作。

// Internal data
int RankWorst[MAX_H];   // Rank of the worst r taken by h
/*RO*/int BestH[MAX_R];       // Indice of the best h in R_pref the r can get
/*HO*/int BestR[MAX_H];       // Indice of the best r in H_pref the h can get
int Size[MAX_H];        // Number of residents taken by h

// Output data
int M[MAX_R];

void stable_hospitals_RO()
{
    for(int h = 0 ; h < H ; h++)
      RankWorst[h] = H_pref[h].size()-1;
    fill_n(BestH, R, 0);
    fill_n(Size, H,0);
    fill_n(M,R,INF);
    for (int i = 0; i < R; i++)
        for (int r = i; r >= 0;)
        {
        if(BestH[r] == int(R_pref[r].size()))
            break;
            const int h = R_pref[r][BestH[r]++];
            if(Size[h]++ < C[h])
            {
                M[r] = h;
                break;
            }
            int WorstR = H_pref[h][RankWorst[h]];
            while(WorstR == INF || M[WorstR] != h) // Compute the worst
                WorstR = H_pref[h][--RankWorst[h]];
            if(H_rank[h][r] < RankWorst[h])        // Ranked better that worst
            {
                M[r] = h;
                M[r = WorstR] = INF;    // We have eliminate it, he need to put it somewhere
            }
        }
}
void stable_hospitals_HO()
{
    fill_n(BestR, H, 0);
    fill_n(Size, H,0);
    fill_n(M,R,INF);
    vector<int> SH;
    for (int h = 0; h < H; h++)
        SH.push_back(h);
    while(!SH.empty())
    {
        int h = SH.back();
        if(Size[h] == C[h] || BestR[h] == int(H_pref[h].size())) // Full or no r available
        {
            SH.pop_back();
            break;
        }
    const int r = H_pref[h][BestR[h]++];
    // r is unassigned or prefer h to current hospital
        if(M[r] == INF || R_rank[r][h] < R_rank[r][M[r]]) 
        {
            if(++Size[h] == C[h]) // Will be full
                SH.pop_back();
            if(M[r] != INF) // Delete from M[r]
            {
                Size[M[r]]--;
                SH.push_back(M[r]);
            }
            M[r] = h;
        }
    }
}

以下是一个示例，展示如何通过偏好列表来构建排名。（在该示例中，偏好列表存在于标准输入中。）

int main()
{
    scanf("%d%d",&R,&H);
    int num;
    // put inf

    for(int r = 0 ; r < R ; r++)
    {
        scanf("%d",&num);
        R_pref[r].resize(num);
        for(int h = 0 ; h < num ; h++)
        {
            scanf("%d",&R_pref[r][h]);
            R_rank[r][R_pref[r][h]] = h;
        }
    }
    for(int h = 0 ; h < H ; h++)
    {
        scanf("%d",&C[h]);
        scanf("%d",&num);
        H_pref[h].resize(num);
        for(int r = 0 ; r < num ; r++)
        {
            scanf("%d",&H_pref[h][r]);
            H_rank[h][H_pref[h][r]] = r;
        }
    } 
    stable_hospitals_RO();
    printf("\n\n\n\n");
    stable_hospitals_HO();
    return 0;
}

举个例子：

医院1到3，6名居民。

H_pref：

• 1 -> 2 5 6 1（偏爱2然后是5、6、1）
• 2 -> 4 2 1 6 3 5
• 3 -> 1 2

R_pref：

• 1 -> 1 2 3
• 2 -> 3 1
• 3 -> 2 1
• 4 -> 1 3 2
• 5 -> 3 2 1
• 6 -> 3

H_rank：

• 1 -> 4 1 INF INF 2 3（1在H_pref[1]中排名第4位，3不在其中）
• 2 -> 3 2 5 1 6 4
• 3 -> 1 2 INF INF INF INF

R_rank同理。

医院不必为每个人排名，也可以比其容量更少的人排名。

- Loïc Février

---

不错！我认为我的限制将符合这些规则。我会选择“以医院为导向的情况”。有几个关于代码的问题。1）1000是从哪里来的？为了对数组的大小进行上限控制吗？2）您如何将R_pref和H_pref向量用作多维向量？看起来您正在将它们创建为具有一个索引的向量，但稍后您却像R_pref[x][y]一样调用它们。3）我该如何提取匹配的数据？也就是说，医院及其分配的居民？如果这些问题中有任何一个很明显，请原谅我 - 我已经做了一段时间的Java / C＃，而我的C ++有点生疏！ - JonH

1. 1000是我正在处理的问题的上限（没有动态分配：当你必须在编程竞赛中重新编码它时，更快、更安全），只需使用任何你想要的（但一定要足够大）。
2. 每个R_pref[i]都是一个向量。
3. 在“int M”（输出数据）中，你可以找到每个居民匹配的医院。

如果你在使用它时遇到问题，请发布你的数据链接（并解释它的组织方式），我会构建程序。 - Loïc Février

明白了！我正在创建一个应用程序进行测试，但是一个示例输入将会非常有帮助。假设朱迪在医院列表中的索引为h=1，可以在星期六晚上7点工作，这在住院医生列表中表示为r=4。她有3个可用的时间段可以工作，在这些时间段中，这是她最喜欢的（另外两个不太喜欢的可能是...比如按顺序是r=1和r=6）。我该如何设置H_pref和R_rank来反映这一点呢？ - JonH

我已经添加了例子并修改了主函数。它是旧版本的代码，在我使用vector<int>之前。现在我需要在插入数据之前先调整它们的大小。 - Loïc Février

非常确定这就是我要找的答案 - +1 为深入解释！我现在明白如何格式化数据了。我的最后一个问题是：对于时间段或居民，谁在哪里工作并不重要。因此，当涉及到居民时，我没有任何真正的偏好。我假设算法对于居民的0个偏好无法正确工作？ - JonH

如果某个居民（时间段）没有给医院（工作者）排名，那么他将永远不会被分配到任何一个医院。您可以使用随机排序或总是相同的排序方式。例如，先为那些不介意工作两次的人排名（他们更有可能被选择两次）。别忘了为每个工作者添加最大容量：在您的情况下，2或3应该足够。 - Loïc Février

Answer 2

如果有人遇到类似的问题，这是我采用的解决方案：

最终我使用了回溯搜索算法来解决约束满足问题。它只是执行普通的回溯搜索，但在遍历树时检查所有约束是否得到满足。以下是伪代码：

function BACKTRACKING-SEARCH(csp) returns a solution, or failure
     return BACKTRACK({ }, csp)

function BACKTRACK(assignment, csp) returns a solution, or failure
     if assignment is complete then return assignment
     var = SELECT-UNASSIGNED-VARIABLE(csp)
     for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do
        if value is consistent with assignment then
           add {var = value} to assignment
           result = BACKTRACK(assignment, csp)
           if result != failure then
              return result
           remove {var = value} 
     return failure

变量是时间段。分配给变量的可能值是工人。变量及其实际分配的组合是树中的节点。因此，搜索空间是所有可能的时间段和工人的组合。约束条件会从搜索空间中剪枝节点。

约束可以是工人的可用性。因此，如果将时间段A分配给工人X，但X无法在时间段A工作，则该节点将被判定为不一致。

我解决了一个特定时间段被分配多个工人的问题，方法是将每个时间段/工人组合视为它自己的时间段。因此，如果儿童托儿所有2名工人需要填补，我将其视为两个单独的时间段来填补，每个时间段都分配了自己的工人。这样每个变量只分配一个值。这使得算法更简单。

感谢您帮助将此问题缩小到可解决的范围。

- JonH