algorithm - 是否有针对 "maker' 的调度进行优化的调度算法”？

Question

您可能熟悉 Paul Graham 的文章， "Maker's Schedule, Manager's Schedule" 。这篇文章的症结在于，对于创意和技术专业人士来说， session 是生产力的诅咒，因为它们往往会导致“日程碎片化”，将空闲时间分成太小的 block ，无法获得解决难题所需的注意力。

在我的公司，我们已经看到通过最大限度地减少造成的中断量带来的显着好处，但我们用来决定日程安排的蛮力算法不够复杂，无法很好地处理大量人员的日程安排。 (*)

我正在寻找的是，在一组 N 创客和经理中，是否有任何众所周知的算法可以最大限度地减少这种生产力中断。

在我们的模型中，

• 有 N 个人。
• 每个人 p_i 要么是创客 (Mk) 要么是经理 (Mg).
• 每个人都有一个时间表s_i。
• 每个人的日程都是 H 小时。
• 时间表由一系列不重叠的时间间隔组成 s_i = [h₁, . .., h_j].
• 一个间隔要么是空闲，要么是忙碌。两个相邻的空闲区间等同于跨越两者的单个空闲区间。
• 每个人的生产力 P 是一个介于 0 和 1 之间的值。
  • 当空闲间隔的数量最少时，制造商的生产率就会最大化。
  • 创客的生产率等于 1/(max[1, 空闲间隔的数量])。
  • 当空闲时间的总长度最大化时，经理的工作效率会最大化，但他们更喜欢 session 之间的长时间，而不是短暂的休息。
  • 经理的工作效率等于每个空闲时间段长度的平方和占一天的比例。也就是说，(h₁/s_i)² + (h₂/s_i)² + ... ，其中每个间隔都是一个空闲间隔。
• 目标:最大限度地提高团队的总生产力。

请注意，如果没有 session ，则制造者和经理都会体验到最佳生产力。如果必须安排 session ，那么决策者更愿意连续召开 session ，而管理者则不关心 session 的地点。请注意，由于所有中断都被视为对创客同样有害，因此如果将可用空闲时间分段，则持续 1 秒的 session 和持续 3 小时的 session 没有区别。

问题是决定如何安排 M 个不同的 session ，涉及任意数量的 N 人，其中给定 session 中的每个人都必须安排一个忙 间隔进入他们的日程安排，这样它就不会与任何其他繁忙间隔重叠。对于每个 session M_t，所有各方的繁忙 间隔的开始时间必须相同。

是否存在解决此问题或类似问题的算法？我的第一个想法是，这看起来非常类似于碎片整理(最小化不同 block 的数量)，并且有很多关于它的算法。但是碎片整理与调度没有太大关系。想法？

---

(*) 实际上，这并不是真正的问题，因为我们很少同时与超过 5 个人开会，所以可能性很小。

Answer 1

可以通过使用遗传算法对此进行很好的近似。

编写一个函数来创建 1000 个样本随机时间表，随机分配制造商和管理者。

编写另一个函数(适应度函数)，为有问题的时间表分配缺点(同时工作的人，制造者不足，管理者不足，有人工作不够，有人工作太多)。

foreach schedule assign calculate fitness keeping a reference to the lowest scoring (best) schedule.

while (best schedule > minimum fitness value)
    foreach schedule s in population of schedules
        foreach time slot
           if (random < .5)
               choose value from best schedule
           else
               choose value from schedule s
           end if
       end foreach
       score schedule s with fitness function
    end foreach
end while

虽然这种方法不会产生最优调度并且有可能找到局部最小值。它总是会产生一个时间表，你总是可以为你不想看到的任何条件添加更多的健身功能约束。这种类型的算法可以处理许多不同类型的约束满足问题。

我个人使用类似的算法在我的笔记本电脑上安排了我全年的 Wifes Co-Op 学前类，大约需要两个小时。