工人调度算法 [英] Worker Scheduling Algorithm
问题描述
问题
这里是我想解决的问题的本质。我们有工人照顾孩子在一个托儿所在设定的时间在周末。在一个周末有16个不同的插槽。所以对于一个4个月的月份有64个插槽。我们有最多30个苗圃工人（虽然我们需要更多，任何人喜欢孩子。）
编辑：每个时间段是离散的 - 它们不重叠。 / p>
目前有一个人每个月提出育儿时间表。这是一个复杂和耗时的任务，使每个人都喜欢这个日程安排。考虑到我自己想到的问题后，一定有更好的方法！
算法
我注意到，问题本质上是一个二分图。 婚姻问题也是一个二分图，您可以使用 Edmonds的匹配算法等匹配算法进行解析。
但这假设一个节点集中的每个节点只匹配另一个节点集中的一个节点。在我的情况下，每个苗圃工人只工作一个时间段。因为我们严重缺乏，这不会工作！一群人每个月要工作两次，填满所有的时间段。
这似乎意味着这更像是经典的医院/居民问题。它不同于婚姻问题，因为妇女可以接受来自一个以上男人的提议（例如，医院可以服用多个居民）。
现在是什么？
哇！
现在，我已经设置了方式....任何人知道任何好的链接，解释或显示这样的算法？有更好的方法去解决这个问题吗？我在想什么？我做了google搜索医院居民算法，并找到研究生的论文。 Gah！我毕业与CS学位，并采取了AI类...但是那是6年前。
- 医院有最大容量和
- 居民将订购医院。
- 没有其他限制。
在您的情况下，医院是工人，居民是插槽。
- 工人可以订购插槽。
- 但你可以没有其他限制，例如：我已经在早上工作，我不想在晚上的同一天工作。
<
如果这样就可以了：
-
每个广告位都有自己首选的工作人员。
我不得不去年编码，这里是代码。
/ *
RO：需要用于面向居民的版本
HO：需要面向医院的版本
* /
const int MAX_R = 1000;
const int MAX_H = 1000;
const int INF = 1000 * 1000 * 1000;
您需要填写输入变量。
一切都很简单：
- R_pref和H_pref是居民/医院的偏好列表
- H_rank [h] [r]是H_pref [h]中r的排名：h在偏好列表中的位置
$ b $
//输入数据
int R，H; //居民/医院数量
int C [MAX_H]; //医院容量
矢量< int> R_pref [MAX_R]，H_pref [MAX_H]; // Preferences：adjencies lists
/ * RO * / int H_rank [MAX_H] [MAX_R]; // Rank：r in H_pref [h]
/ * HO * / int R_rank [MAX_R] [MAX_H]; // Rank：rank of h in R_pref [r]
>
//内部数据
int RankWorst [MAX_H]; //由h
/ * RO * / int BestH [MAX_R]获取的最差r的排名// R_pref中的最佳h的索引r可以得到
/ * HO * / int BestR [MAX_H]; // H_pref中的最佳r的索引h可以得到
int Size [MAX_H]; //由h
创建的居民数量//输出数据
int M [MAX_R];
void stable_hospitals_RO（）
{
for（int h = 0; h
fill_n（BestH，R，0）;
fill_n（Size，H，0）
fill_n（M，R，INF）;
for（int i = 0; i
{
if ] == 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）//计算最差的
WorstR = H_pref [h] [ - RankWorst [h]];
if（H_rank [h] [r]< RankWorst [h]）//更好地排序最差
{
M [r] = h;
M [r = WorstR] = INF; //我们已经消除它，他需要把它放在某处
}
}
}
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
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] ++];如果（M [r] == INF || R_rank [r] [h]
{
if（++ Size [h] == C [h]）//将满
SH.pop_back（）;
if（M [r]！= INF）//从M中删除[r]
{
Size [M [r]] - ;
SH.push_back（M [r]）;
} b $ b M [r] = h;
}
}
}
使用示例从prefs建立排名。
（在这种情况下，偏好列表在stdin上）。
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
scanf（％d，& R_pref [r] [h]）;
R_rank [r] [R_pref [r] [h]] = h;
}
}
for（int h = 0; h
scanf（％d，& C [h] ）;
scanf（％d，& num）;
H_pref [h] .resize（num）;
for（int r = 0; r
scanf（％d，& H_pref [h] [r]）;
H_rank [h] [H_pref [h] [r]] = r;
}
}
stable_hospitals_RO（）;
printf（\\\
\\\
\\\
\\\
）;
stable_hospitals_HO（）;
return 0;
}
例如：
医院1至3,6名。
H_pref：
- 1 - > 2 5 6 1 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不是theree） / li>
- 2 - > 3 2 5 1 6 4
- 3 - > 1 2 INF INF INF INF
类似于R_rank。
医院不必对每个人排名，也可以排名少于他们的能力。 / p>
The Problem
Here's the essence of the problem I want to solve. We have workers taking care of children in a nursery for set times during the weekend. There's 16 different slots to fill in one weekend. So for a 4-week month there's 64 slots to fill. We have at max 30 nursery workers (though we need much more. anybody like kids?).
EDIT: Each time slot is discrete - they don't overlap.
Currently there's a person who comes up with the nursery schedule each month. It's a complex and time consuming task to make this schedule every month with everybody's preferences. After considering the problem I thought to myself, "There must be a better way!"
Algorithms
I notice that the problem is essentially a bipartite graph. The marriage problem is also a bipartite graph which you can solve by using a matching algorithm like Edmonds's matching algorithm.
But this assumes that each node in one node set matches just one node in the other node set. In my case, each nursery worker would work only one time slot. As we're seriously understaffed, that won't work! A bunch of people are going to have to work twice a month to fill up all the time slots.
Which seems to mean that this is more like the classic "hospitals/residents problem". It differs from the marriage problem in that the "women" can accept "proposals" from more than one "man" (e.g., a hospital can take multiple residents). In my case, a nursery worker can take more than one time slot.
What now?
Whew!
Now that I have the set up out of the way....does any one know of any good links that explain or show such an algorithm? Are there better ways to go about solving this? Am I over thinking it? I did a google search for "hospital residents algorithms" and found grad student papers. Gah! I graduated with a CS degree and took an AI class...but that was 6 years ago. Help!
Aaaaany advice is appreciated!!
The "hospitals/residents problem" could indeed work but it depends of your constraints :
- Hospital have a maximum capacity and will order the resident (most wanted to less wanted).
- Residents will order hospitals.
- No other constraints possible.
In your case the hospitals are workers and the residents are slots.
- Slots can order workers (maybe you prefer experimented ones in the morning...).
- Workers can order slots.
- But you can't have other constraints such as : "I've worked in the morning, I don't want to work the same day in the evening".
If that's ok for you then you have to possibilities :
you want to advantage workers : "hospital oriented case".
You will try to assign workers to their preferred slot(s).
you want to advantage slots : "resident oriented case"
Each slot will have their preferred workers.
I had to code it last year, here is the code.
/*
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;
You need to fill the input variables. Everything is straightforward :
- R_pref and H_pref are the list of preferences for residents/hospitals
- H_rank[h][r] is the rank of r in H_pref[h] : the position of r in the preference list of h
That's all.
// 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]
No need to touch below.
// 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;
}
}
}
Example of use to show how to build rank from prefs. (In that case the preference lists were on the stdin).
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;
}
On an example : Hospitals 1 to 3, 6 résidents.
H_pref :
- 1 -> 2 5 6 1 (prefers 2 then 5 then 6 then 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 is in position 4 in H_pref[1], 3 is not theree)
- 2 -> 3 2 5 1 6 4
- 3 -> 1 2 INF INF INF INF
Similar for R_rank.
Hospital don't have to rank everyone et can also rank less people than their capacity.
这篇关于工人调度算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
