作业调度问题

Question

我正在开发一个应用程序，在该应用程序中，我需要按轮换计划自动为成员安排作业。我不太擅长解释规则，所以这里有一些数据可以帮助你：

职位:职位头衔，有诸如周一和周三这样的规则。

类别:一组位置

分组:另一组位置。同一组中的职位不能在同一天分配

成员:在给定日期分配到职位的用户。

对于当月的每个日期，成员都会被分配到职位(均按升序排列)。如果一个成员被分配到一个类别中的位置，下一次出现同一类别中的位置时，将按字母顺序(或列表的开头)分配下一个成员，例如。

成员: M1，M2，M3，M4

C1类别职位: P1、P2、P3

P1职位成员: M1，M2，M3，M4

P2职位成员: M1，M2，M3

P2职位成员: M1，M3，M4

如果为P1分配了M1，如果接下来是P2，则将分配M2。引入了一个额外的复杂性层，如果接下来是P3，则会分配M3。系统必须跟踪M2被“跳过”的事实，并且如果可用，则分配M2 next，然后分配M4 next，或者等到它到达M2可用的位置(当有许多“跳过的”成员时，这变得额外复杂)。

如果某个成员表示他在该日期将不可用，他也将被跳过。系统需要将跳过的成员放在优先级上，当他们出现时以某种方式识别他们，然后跳到列表中的下一个逻辑人员。由于日期冲突，跳过也适用于组。

我已经有了一个临时的、混乱的解决方案，尽管我在其中有很多注释来解释每个步骤，但我不再理解它了。它的弱点是在处理跳过的成员方面。

如果你打算对此进行编码，你会怎么做？我是用PHP实现的，但伪代码也可以。

Answer 1

我的解决方案是:您需要一个PriorityQueue (在PHP中可以在SplPriorityQueue下找到它)。PriorityQueue为您提供具有降序优先级的元素(按值排序，最小的值具有最高的优先级)。

每个成员都会得到一个赋值。该值是一个n位的ASCII数字(为方便起见，您可以使用8位)，由0到n位填充。在此之后，您可以附加名称。您还可以为每个成员添加可用的职位

So (n=5)：

• M1 value: 99999Albert P1，P2，P3
• M2 value: 99999Susi P1，P2
• M3 value: 99999Bob P1，P3

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

准备工作：

晴朗的一天。您正在检索指定日期的已分配职位和类别。每个成员都被加载到一个长列表中。没有出现在工作中的每个成员都不会被加载，但会将其值减少负2。Bob不在这里，因此它的新值为99997Bob。这意味着下次将自动选择Bob。所有其他成员的值都会减1。

为特定日期指定的位置映射(使用SplObjectStorage)：

P1->M1、M2、M3、M4等P2->等。

地图只包含今天必须分配的位置。在

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

分配：

通过从position

• Remove () PriorityQueue中提取(自动完成正确的分配)，您可以选择要分配的位置，并获取可填充可用成员列表的成员列表，并将它们放入
  • 位置。每个被分配的成员的值将增加1(所以如果你在这里工作，那么减少和增加的级别就会消失)。如果你在这里，因为任何原因没有被分配到一个职位，你会得到一分的小惩罚。如果你不在这里，你将受到两分的惩罚。
  • 完成后，再次将剩余的成员放在列表中，清除PQueue并继续下一次赋值。

注意事项：

• 你必须小心，一个职位总是有足够的人。

Answer 2

uff。我没有遵循你的描述，但在类似的情况下，我曾使用sql来解决这类问题。如果您使用的是php，我猜您有可用的sql。

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

例如，对于跳过的部分，您可能会有一个列来记录上次分配某人的时间，然后按该列排序(这样您就可以选择很长时间未分配的人员)。或者，您可以将跳过的次数作为一列并按其排序。

Answer 3

我所理解的是有'm‘个成员和'n’个位置。

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

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

最后，一个职位有一个可以填补它的成员列表。

从数据结构的角度来看，将成员放在一个链表中--每个成员都必须有一个额外的位置列表，这是他们最终被分配的日子。然后，对于每个职位，有一个可以填补该职位的成员的引用列表。将类别实现为职位的另一个引用列表，说明该职位所在的类别。

实际的赋值:有一个day counter = 0，并迭代位置。对于每个位置P，遍历可以填充它的成员。如果满足以下条件，则成员M可以填补该职位：

• 他填充的任何职位P2不与P.
• 任何他填充了P2 = daycounter的职位不与P.

共享组

如果他可以填补职位，位置，日期对被添加到成员，并且成员的节点被移动到列表的末尾(这就是为什么引用是必要的--所有的引用仍然有效，即使节点移动了)。这确保了“跳过”的成员具有最高优先级，而未联系到的成员则具有次高优先级。

一旦一个职位被填补，就转到下一个职位。如果该职位与已分配的职位共享一个组，则跳过它，遍历所有职位，直到您可以在第1天分配尽可能多的职位。然后，递增day计数器并重复第2天。这将为所有作业提供最大分配(不确定最大)。

提示:将成员移动到成员列表的末尾时，为了避免必须遍历列表，请保留对末尾的引用--对于下一个位置，无论如何都需要从头开始，所以没有必要遍历整个列表。