解决特定时间段的人员分配问题

Question

我正在尝试解决每个人的职责很少以及必须履行各种职责的日期的问题。 例如：

1. 约翰可以当老师和清洁工
2. 玛格丽特可以成为会计师和清洁工
3. 安德鲁可以成为一名会计师和教师

为此我有时间段：

1. 周六8:30我们需要两名老师和一名清洁工
2. 周日 10:00 我们需要一名会计师和一名老师 等等一个

我正在寻找一种可以在 C# 中实现的算法来满足这个要求。 我发现类似的问题描述称为

Maximum Flow Problem.

但我不认为它解决了我的问题。 有没有什么算法可以解决上述问题？

Answer 1

您只需要解决所构建的图的最大流。

从源到Pi为1，保证每个人都可以使用一次。 从 Job_j 到 Sink 的给定作业数量保证了该作业的使用次数不能超过该数量。每个人都通过权重为 1 的链接与他们可以完成的工作相关联。这样他们就可以为该工作做出贡献。但他们只能为个人工作做出贡献，因为他们从来源处收到了 1。