8

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

职位：职位名称，具有每周周一和周三等规则。
类别：一组职位
组：另一组职位。同一组中的职位不能在同一天
分配成员：在给定日期分配到职位的用户。

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

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

4

3 回答 3

6

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

每个成员都获得一个分配的值。该值是一个 n 位的 ASCII 数字（为方便起见，您可以使用 8 位），在 n 个位置处填充零。之后，您附加名称。您还可以为每个成员添加可用职位

所以（n = 5）：

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

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

准备：

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

为特定日期分配的位置被映射（使用 SplObjectStorage）：

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

地图只包含当天必须分配的位置。之后

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

分配：

  • 您选择要分配的职位
  • 获取可以填补职位的成员列表
  • 从列表中删除可用成员并将它们放入 PriorityQueue
  • 通过从 PriorityQueue 中的 extract() 分配位置（正确分配是自动完成的）。分配的每个成员的值都会增加一（因此，如果您在这里工作，则减少和增加会达到水平）。如果您在这里并且由于某种原因没有被分配到某个职位，您将受到一个小罚分。如果你不在这里，你会受到两个惩罚。
  • 完成后，将剩余成员再次放入列表，清空PQueue，继续下一个任务。

注意事项：

  • 你必须小心，一个职位总是有足够的人。
于 2010-01-02T15:10:45.320 回答
1

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

我建议做的是找到一种将这些信息存储到一组表中的方法，然后计算出什么 sql 查询可以为您提供所需的答案。很多时候，用 sql 做起来比用过程语言做起来简单得多。

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

于 2009-12-19T12:09:45.323 回答
0

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

类别：一组职位——在该类别中分配一个职位的成员不能有另一个职位吗？

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

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

从数据结构的角度来看，将成员放在一个链表中——每个成员都必须有一个额外的 [position, day] 列表，他们最终被分配。然后，对于每个职位，都有一个对可以填补该职位的成员的引用列表。将类别实现为另一个位置的参考列表，以了解它所在的类别。

实际分配：有一个日计数器 = 0，并遍历位置。对于每个位置 P，遍历可以填充它的成员。在以下情况下，成员 M 可以填补该职位：

  • 他担任 P2 的任何职位都不与 P 共享一个类别。
  • 他用 day = daycounter 填充 P2 的任何位置都不与 P 共享一个组。

如果他可以填补该职位，则将 [position, day] 对添加到成员中，并将成员的节点移动到列表的 END （这就是为什么需要引用 - 所有引用仍然有效，即使节点移动）。这可确保“跳过”的成员获得最高优先级，而未到达的成员则获得次高优先级。

一旦一个职位被填满，就转到下一个职位。如果该职位与已经分配的职位共享一个组，请跳过它，遍历所有职位，直到您可以在第 1 天分配尽可能多的职位。然后，增加日期计数器并在第 2 天重复。这应该会给您所有工作的最大分配（不确定最大）。

提示：当将成员移动到成员列表的末尾时，为了避免遍历列表，请保持对末尾的引用——对于下一个位置，无论如何都需要从头开始，所以没有意义通过整个东西。

于 2010-01-02T17:16:29.177 回答