作业调度问题
我正在开发一个应用程序，我需要按轮换时间表自动为成员安排工作。我不太擅长解释规则，所以这里有一些数据可以提供帮助：
职位：职位名称，规则包括每周周一和周三。
类别：一组位置
组：另一组位置。同一组的职位不能在同一天分配
成员：在给定日期分配到职位的用户。
对于该月的每个日期，成员都会被分配到职位（均按升序排列）。如果将成员分配到一个类别中的某个位置，则下次出现同一类别中的位置时，将按字母顺序（或列表的开头）分配下一个成员，例如。
成员：M1、M2、M3、M4
C1 类职位：P1、P2、P3
P1 位置的成员：M1、M2、M3、M4
P2 位置的成员：M1、M2、M3
位置 P2 的成员：M1、M3、M4
如果将 M1 分配给 P1，如果接下来是 P2，则将分配 M2。引入了额外的复杂性层，如果接下来出现 P3，则分配 M3。系统必须跟踪 M2 被“跳过”的事实，并在可用的情况下分配下一个 M2，然后分配下一个 M4，或者等到它到达 M2 可用的位置（当有许多“跳过”时，这会变得更加复杂） ' 成员）。
如果会员表示他在该日期无法出席，该会员也将被跳过。系统需要优先考虑跳过的成员，在他们出现时以某种方式识别他们，然后跳转到列表中的下一个逻辑人员。由于日期冲突，跳过也适用于团体。
我已经有了一个临时[而且混乱]的解决方案，尽管我有很多评论解释了每个步骤，但我不再理解它。它的弱点在于处理跳过的成员。
如果你要编写这个代码，你会怎么做？我正在 PHP 中实现这个，但伪代码也可以工作。
I'm working on an application where I need to automatically schedule jobs for members on a rotating schedule. I'm not very good at explaining rules, so here's some data to help out:
Positions: A job title, with rules such as Mondays and Wednesdays weekly.
Categories: A set of positions
Groups: Another set of positions. Positions in the same group cannot be assigned on the same day
Members: Users assigned to positions on a given date.
For each date in the month, members are assigned to positions (both in ascending order). If a member is assigned to a position in one category, the next time a position in the same category comes up, the next member alphabetically (or the beginning of the list) gets assigned eg.
Members: M1, M2, M3, M4
Positions in Category C1: P1, P2, P3
Members in Position P1: M1, M2, M3, M4
Members in Position P2: M1, M2, M3
Members in Position P2: M1, M3, M4
If M1 is assigned for P1, if P2 comes next, M2 will be assigned. An additional layer of complexity is introduced where if P3 comes next instead, M3 gets assigned. The system has to keep track of the fact that M2 was 'skipped' and assign M2 next if available, then assign M4 next, or wait until it gets to a position where M2 is available (this becomes additionally complex when there are many 'skipped' members).
A member will also be skipped if he has indicated he won't be available on that date. The system needs to place priority on skipped members, somehow identify them when they come up and then jump to the next logical person in the list. Skipping also applies to groups due to date clashes.
I already have a temporary [and messy] solution which I no longer understand even though I have a lot of comments in it explaining each step. Its weaknesses are in dealing with the skipped members.
If you were going to code this how would you go about it? I'm implementing this in PHP but pseudocode would work as well.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
嗯。我不明白你的描述，但在类似的情况下我已经使用sql来解决此类问题。如果你使用的是 php，我猜你有可用的 sql。
我建议做的是找到一种方法将这些信息存储到一组表中，然后计算出什么 sql 查询可以为您提供所需的答案。通常，使用 sql 比使用过程语言要简单得多。
例如，对于跳过的部分，您可能有一个列记录上次分配某人的时间，然后按该列排序（以便您选择长时间未分配的人员）。或者，您可以将跳过的次数作为一列并按其排序。
uff. i don't follow you description, but in similar situations i have used sql to solve this kind of problem. if you are using php i guess you have sql available.
what i would suggest doing is finding a way of storing this information into a set of tables and then working out what sql query gives you the answer you want. quite often it's a lot simpler to do in sql than it is in a procedural language.
for the skipped part, for example, you might have a column which records when someone was last assigned, and then order by that (so that you select the person who has not been assigned for a long time). alternatively, you could have the number of times skipped as a column and order by that.
我的理解是有“m”个成员和“n”个职位。
类别：一组职位——在该类别中被分配一个职位的成员不能拥有另一个职位吗？
组：一组职位——同一组中的职位必须在不同日期分配。
最后一件事，一个职位有一个可以填补该职位的成员列表。
从数据结构的角度来看，将成员放入一个链接列表中 - 每个成员都必须有一个最终分配的[职位，日期]的附加列表。然后，对于每个职位，都有一个可以填补该职位的成员的参考列表。将类别实现为职位所属类别的另一个参考列表。
实际分配：让日计数器 = 0，并迭代职位。对于每个位置 P，迭代可以填充它的成员。成员 M 可以填补该职位，如果：
如果他可以填补该职位， [position, day] 对被添加到成员中，并且成员的节点被移动到列表的末尾（这就是为什么需要引用 - 即使节点移动，所有引用仍然有效）。这可确保“跳过”的成员获得最高优先级，而未到达的成员则获得次高优先级。
一旦一个职位被填补，就转到下一个职位。如果该职位与已分配的职位共享一个组，请跳过它，迭代所有职位，直到您可以在第一天分配尽可能多的职位。然后，增加天数计数器并重复第 2 天。这应该给您所有作业的最大分配（不确定最大分配）。
提示：将成员移动到成员列表的末尾时，为了避免遍历列表，请保留对末尾的引用 - 对于下一个位置，无论如何都需要从头开始，因此没有必要遍历列表整个事情。
What I understand is there are 'm' members and 'n' positions.
Category: a group of positions -- a member who is assigned one position in the category can't have another?
Group: a group of positions -- positions in the same group must be assigned on different days.
Last thing, a Position has a list of members who can fill it.
Looking at this from a data-structure point of view, put the members in a linked list -- each member has to have an additional list of [position, day] that they are finally assigned. Then, for each position, have a list of references to the members that can fill that position. Implement categories as another list of references for a position as to which categories it is in.
The actual assignment: have a day counter = 0, and iterate through the positions. For each position P, iterate through the members that can fill it. A member M can fill the position if:
If he can fill the position, the [position, day] pair is added to the member, and the member's node is moved to the END of the list (this is why references are necessary -- all the references are still valid even though the node moved). This ensures that the 'skipped' members are given highest priority, and the members who weren't reached were given next highest priority.
Once a position is filled, go to the next position. If the position shares a group with a position already assigned, skip it, iterating through all the positions until you can assign as many positions as you can on day 1. Then, increment the day counter and repeat for day 2. This should give you a maximal assignment (not sure about maximum) for all the jobs.
Tip: when moving a member to the end of the member list, to prevent having to traverse the list, keep a reference to the end -- for the next position, you need to start from the beginning anyway, so there's no point going through the whole thing.
我的解决方案：
您需要一个 PriorityQueue（在 PHP 中可以在 SplPriorityQueue 下找到）。 PriorityQueue 为您提供具有降序优先级的元素（按值排序，最小的
值具有最高优先级）。
每个成员都会获得一个分配的值。该值是一个 n 位 ASCII 数字（为了方便起见，您可以使用 8 位数字），用零填充到 n 个位置。之后你追加
名字。您还可以向每个成员添加可用职位
So (n=5)：
这样可以轻松按优先级和名称对成员进行排序。
准备工作：
一个阳光明媚的日子。您正在检索给定日期分配的职位和类别。每个成员都被列在一个长长的名单上。每个没有上班的成员都不会被加载，但他的价值会减少-2。 Bob 不在这里，因此它的新值变为 99997Bob。这意味着下次将自动选择 Bob。
所有其他成员的价值都会减少负一。
映射为特定日期分配的位置（使用 SplObjectStorage）：
P1->M1、M2、M3、M4 等。
P2-> 地图仅
包含当天必须分配的位置。
过滤后
：
您必须查找组并删除地图上当天无法分配的任何位置。您的组描述有点不清楚。
分配：
自动）。每个被分配的成员的价值都会增加
一（因此，如果您在这里工作，则减少和增加会趋于平稳）。
如果您在这里并且由于某种原因没有被分配到某个职位，您将获得
小罚一分。如果你不在这里，你会被扣两分。
继续下一个作业。
注意事项：
My solution:
You need a PriorityQueue (which is available in PHP under SplPriorityQueue). The PriorityQueue gives you elements with descending priority (sorted by values, the smallest
value has the highest priority).
Each member gets an assigned value. This value is an ASCII number with n digits (you could use 8 digits for convenience), filled up with zeroes to n positions. After that you append
the name. You also add to each member the available positions
So (n=5):
This makes it easy to sort members by priority and name.
Preparation:
A sunny day. You are retrieving the assigned positions and a category for a given day. Each member is loaded on a long list. Each member who is not showing up on work is not loaded, but gets his value decreased by minus two. Bob is not here, so its new value gets 99997Bob. This means that Bob will be selected automatically the next time.
All other members get their value decreased by minus one.
The positions assigned for a specific Day are mapped (use SplObjectStorage):
P1->M1,M2,M3,M4 etc.
P2-> etc.
The map contains only the positions which must be assigned this day.
After the
Filter:
You must look up the groups and delete any positions on the map which cannot be assigned this day. Your group description is a bit unclear.
Assign:
automaticially). Each member which is assigned will gets its value increased by
one (So the decrease and increase levels out if you are here and working).
If you are here and not assigned to a position for whatever reason, you get
a small penalty of one. If you not here, you get a penalty of two.
continue with the next assignment.
Caveats: