algorithm - worker 调度算法

Question

问题

这是我要解决的问题的本质。我们有工作人员在周末固定时间在托儿所照顾 child 。一个周末有 16 个不同的时段可以填补。因此，对于一个有 4 周的月份，有 64 个空位需要填补。我们最多有 30 名保育员(尽管我们需要更多。有人喜欢 child 吗？)。

编辑:每个时隙都是离散的——它们不重叠。

目前每个月都有一个人制定托儿所时间表。每个月根据每个人的喜好制定这个时间表是一项复杂且耗时的任务。考虑到这个问题后，我心想，“一定有更好的方法!”

算法

我注意到问题本质上是一个 bipartite graph . marriage problem也是一个二分图，您可以使用像 Edmonds's matching algorithm 这样的匹配算法来求解它.

但这假设一个节点集中的每个节点只匹配另一个节点集中的一个节点。在我的例子中，每个保育员只能工作一个时间段。由于我们人手严重不足，那行不通!一群人将不得不每月工作两次以填补所有的时间空缺。

这似乎意味着这更像是经典的“医院/居民问题”。它与婚姻问题的不同之处在于，“女性”可以接受多个“男性”的“求婚”(例如，一家医院可以接收多名居民)。就我而言，一名保育员可以占用多个时间段。

现在怎么办？

哇哦!

现在我已经完成了设置....有没有人知道任何解释或显示这种算法的好链接？有没有更好的方法来解决这个问题？我是不是想多了？我在谷歌上搜索了“住院医师算法”并找到了研究生论文。啊!我以 CS 学位毕业并参加了 AI 类(class)……但那是 6 年前的事了。 救命!

感谢任何建议!!

Answer 1

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

• 医院有最大容纳量并且会安排住户(最需要到最不想要)。
• 居民将订购医院。
• 不可能有其他限制。

在您的例子中，医院是工作人员，居民是插槽。

• slots 可以为 worker 排序(也许你更喜欢在早上进行实验......)。
• 工作人员可以订购插槽。
• 但您不能有其他限制，例如:“我早上工作，我不想在同一天晚上工作”。

如果这对你没问题，那么你必须有以下可能性:

• 您想使员工受益:“面向医院的案例”。

  您将尝试将工作人员分配到他们喜欢的位置。

• 您想利用插槽:“面向居民的案例”

  每个插槽都会有他们喜欢的 worker 。

我去年不得不编写代码，这是代码。

/* 
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]中的排名:r在h的偏好列表中的位置

就这些。

// 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。

医院不必对每个人进行排名，也可以对少于其能力的人进行排名。