工人调度算法

Question

问题

这是我想要解决的问题的本质.在周末,我们有工人在托儿所照顾孩子.一个周末有16个不同的插槽可供填写.因此,对于为期4周的月份,有64个插槽可供填充.我们最多有30名托儿所工人(虽然我们需要更多.像孩子一样的人？).

编辑:每个时段都是离散的 - 它们不重叠.

目前有一个人每个月都会提出托儿所时间表.每个月根据每个人的喜好制定这个时间表是一项复杂而耗时的任务.在考虑了这个问题后,我心想,"必须有一个更好的方法!"

算法

我注意到问题基本上是一个二分图.在婚姻问题也是一个二分图,您可以通过使用像匹配算法解决埃德蒙兹的匹配算法.

但是这假设一个节点集中的每个节点仅匹配另一个节点集中的一个节点.就我而言,每个托儿所工作者只能工作一个时间段.由于我们严重缺乏人手,这是行不通的!一群人每个月必须工作两次才能填满所有时间段.

这似乎意味着这更像是经典的"医院/居民问题".它与婚姻问题的不同之处在于,"女性"可以接受来自不止一个"男人"的"建议"(例如,医院可以接纳多个居民).在我的情况下,托儿所工人可以占用多个时间段.

现在怎么办？

呼!

现在我已经完成了设置....有没有人知道任何解释或显示这种算法的好链接？有没有更好的方法来解决这个问题？我在想它吗？我做了一个谷歌搜索"医院居民算法",并找到了研究生的论文.尔加!我毕业于CS学位并参加了AI课程......但那是6年前的事了.救命!

Aaaaany建议表示赞赏!!

Answer 1

“医院/居民问题”确实可以解决，但这取决于你的限制：

\n\n

\n
• 医院有最大容量，并将命令住院医师（最想要的到不太想要的）。
\n
• 居民将订购医院。
\n
• 不可能有其他限制。
\n

\n\n

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

\n\n

\n
• 老虎机可以命令工人（也许你更喜欢在早上进行实验......）。
\n
• 工人可以订购槽位。
\n
• 但你不能有其他限制，例如：“我早上工作，我不想当天晚上工作”。
\n

\n\n

如果这对你来说没问题，那么你就有可能：

\n\n

\n

• 您想为工人提供优势：“以医院为导向的案例”。

  \n\n

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

\n

• 您想要优势槽位：“面向居民的案例”

  \n\n

  每个槽位都会有自己喜欢的工人。

\n

\n\n

我去年必须编码它，这是代码。

\n\n

/* \nRO : needed for Resident-Oriented version\nHO : needed for Hospital-Oriented version\n*/\nconst int MAX_R = 1000;\nconst int MAX_H = 1000;\nconst int INF = 1000*1000*1000;\n

\n\n

您需要填写输入变量。\n一切都很简单：

\n\n

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

\n\n

就这样。

\n\n

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

\n\n

下面不用碰。

\n\n

// Internal data\nint RankWorst[MAX_H];   // Rank of the worst r taken by h\n/*RO*/int BestH[MAX_R];       // Indice of the best h in R_pref the r can get\n/*HO*/int BestR[MAX_H];       // Indice of the best r in H_pref the h can get\nint Size[MAX_H];        // Number of residents taken by h\n\n// Output data\nint M[MAX_R];\n\nvoid stable_hospitals_RO()\n{\n    for(int h = 0 ; h < H ; h++)\n      RankWorst[h] = H_pref[h].size()-1;\n    fill_n(BestH, R, 0);\n    fill_n(Size, H,0);\n    fill_n(M,R,INF);\n    for (int i = 0; i < R; i++)\n        for (int r = i; r >= 0;)\n        {\n        if(BestH[r] == int(R_pref[r].size()))\n            break;\n            const int h = R_pref[r][BestH[r]++];\n            if(Size[h]++ < C[h])\n            {\n                M[r] = h;\n                break;\n            }\n            int WorstR = H_pref[h][RankWorst[h]];\n            while(WorstR == INF || M[WorstR] != h) // Compute the worst\n                WorstR = H_pref[h][--RankWorst[h]];\n            if(H_rank[h][r] < RankWorst[h])        // Ranked better that worst\n            {\n                M[r] = h;\n                M[r = WorstR] = INF;    // We have eliminate it, he need to put it somewhere\n            }\n        }\n}\nvoid stable_hospitals_HO()\n{\n    fill_n(BestR, H, 0);\n    fill_n(Size, H,0);\n    fill_n(M,R,INF);\n    vector<int> SH;\n    for (int h = 0; h < H; h++)\n        SH.push_back(h);\n    while(!SH.empty())\n    {\n        int h = SH.back();\n        if(Size[h] == C[h] || BestR[h] == int(H_pref[h].size())) // Full or no r available\n        {\n            SH.pop_back();\n            break;\n        }\n    const int r = H_pref[h][BestR[h]++];\n    // r is unassigned or prefer h to current hospital\n        if(M[r] == INF || R_rank[r][h] < R_rank[r][M[r]]) \n        {\n            if(++Size[h] == C[h]) // Will be full\n                SH.pop_back();\n            if(M[r] != INF) // Delete from M[r]\n            {\n                Size[M[r]]--;\n                SH.push_back(M[r]);\n            }\n            M[r] = h;\n        }\n    }\n}\n

\n\n

用于展示如何从首选项建立排名的示例。\n（在这种情况下，首选项列表位于标准输入上）。

\n\n

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

\n\n

举个例子：\n医院 1 至 3、6 r\xc3\xa9sidents。

\n\n

H_首选项：

\n\n

\n
• 1 -> 2 5 6 1（优先选择 2 然后 5 然后 6 然后 1）
\n
• 2 -> 4 2 1 6 3 5
\n
• 3 -> 1 2
\n

\n\n

R_偏好：

\n\n

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

\n\n

H_等级：

\n\n

\n
• 1 -> 4 1 INF INF 2 3 （1 位于 H_pref[1] 中的位置 4，3 不存在）
\n
• 2 -> 3 2 5 1 6 4
\n
• 3 -> 1 2 INF INF INF INF
\n

\n\n

R_rank 类似。

\n\n

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

\n