作业调度问题

Question

我正在研究一个应用程序，我需要按照轮流计划自动为成员安排作业。我不是很擅长解释规则，所以这里有一些数据可以帮助您：

职位：职位名称，每周一星期三和星期三。
类别：一组职位
分组：另一组职位。
成员：在指定日期分配给职位的用户。

对于本月中的每个日期，成员被分配到职位（均按升序排列）。如果一个成员被分配到一个类别中的一个位置，下一次出现同一类别中的一个位置时，下一个成员按字母顺序（或列表的开始）被赋值，例如。

成员：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中实现这一点，但伪代码也可以。

Answer 1

我的解决方案： 您需要一个PriorityQueue（在SplPriorityQueue下可在PHP中使用）。 PriorityQueue为您提供优先级降低的元素（按值排序，最小的 值具有最高优先级）。

每个成员都获得一个指定的值。这个值是一个有n位数字的ASCII码（为了方便你可以使用8位数字），用零填充到n个位置。之后，您追加 的名称。您还可以添加到每个成员可用位置

所以，（N = 5）：

• M1值：99999Albert P1，P2，P3
• M2值：99999Susi P1，P2
• M3值：99999Bob P1，P3

这使得按优先级和名称对成员进行排序变得容易。

准备：

一个阳光灿烂的日子。您正在检索给定日期的指定位置和类别。每个成员都加载在一个长列表中。没有出现在工作中的每个成员都没有加载，但是他的价值减少了两分之一。鲍勃不在这里，所以它的新值得到99997Bob。这意味着Bob将在下次自动选择。 所有其他成员的价值减去一。

分配给一个特定日的位置被映射（使用SplObjectStorage）：

P1-> M1，M2，M3，M4等 P2->等

的地图仅包含位置必须在今天进行分配。 之后

筛选器： 您必须查找组并删除地图上今天无法分配的任何位置。你的小组描述有点不清楚。

分配：

• 您选择的位置来分配成员，可以填补该职位从列表
• 删除现有成员
• 获取列表，并把它们放到时Queue
• 指定位置通过从PriorityQueue中提取（）（正确分配自动完成 ）。被分配的每个成员的价值都会增加 （因此，如果你在这里工作，减少和增加水平）。 如果您在这里，并且因为任何原因未被分配到某个职位，您将得到一个小罚1。如果你不在这里，你会得到两罚。
• 完成后，再次将其余成员放在列表中，清除PQueue并继续下一项作业。

注意事项：

• 你必须小心，总是有足够多的人的位置。

Answer 2

uff。我不遵循你的描述，但在类似的情况下，我用SQL来解决这类问题。如果你使用的PHP我猜你有SQL可用。

我会建议做的是找到一种方法，将这些信息存储到一组表中，然后找出sql查询为您提供的答案。通常在sql中比在过程语言中更简单。

对于跳过的部分，例如，您可能有一列记录了上次分配人员的时间，然后按此顺序进行排序（以便您可以选择长时间未分配的人员）。或者，您可以将跳过的次数作为列和顺序。

Answer 3

我的理解是有'm'个成员和'n'个职位。

类别：一组职位 - 在该类别中被分配了一个职位的成员不能拥有另一个职位？

组：一组职位 - 同一组中的职位必须在不同的日期分配。

最后一件事，一个职位有一个成员谁可以填写它的列表。

从数据结构的角度来看待这个问题，把成员放在一个链表中 - 每个成员必须有一个附加的[position，day]列表，他们最终被分配。然后，对于每个职位，都有一份可以填写该职位的成员的参考列表。将类别作为另一个引用列表来实现它所处的类别。

实际分配：有一个计数器= 0，并遍历位置。对于每个位置P，遍历可以填充它的成员。成员M可填补，如果位置：

• 的任何位置，他填补了P2不P.
• 他充满了一天P2的任何位置共享类别= daycounter不共用一组P.

如果他可以填写该位置，则[位置，日期]对被添加到该成员，并且该成员的节点被移动到列表的结尾（这就是为什么引用是必要的 - 所有即使节点移动，引用仍然有效）。这确保了“跳过”成员被赋予最高优先级，并且未被到达的成员被赋予次优先级。

一旦一个位置被填满，转到下一个位置。如果头寸与已分配的头寸共享一组，则跳过该头寸，遍历所有头寸，直到您可以在第1天分配尽可能多的头寸。然后，增加日计数并重复第2天。这应该会给您所有工作的最大分配（不确定最大值）。提示：将成员移动到成员列表的末尾时，为了避免必须遍历列表，请保留对结束的引用 - 对于下一个位置，无论如何都需要从头开始，所以有没有一点经历整个事情。