有没有一种调度算法可以针对"创客时间表"进行优化？

Question

你可能熟悉保罗·格雷厄姆的文章“制造商时间表，经理时间表”。文章的核心观点是对于创意和技术专业人员来说，会议是影响生产力的大敌，因为它们往往导致“时间表碎片化”，将自由时间分成太小的块，难以获得解决困难问题所需的专注力。

在我们公司，通过最小化造成的干扰，我们已经看到了显著的好处，但我们使用的暴力算法不能很好地处理大规模人员的日程安排(*)

我正在寻找的是是否有任何众所周知的算法可以在一组N个制造商和经理中最小化这种生产力干扰。

在我们的模型中，

• 有N个人。
• 每个人p_i都是制造者(Mk)或经理(Mg)。
• 每个人都有一个日程安排s_i。
• 每个人的日程安排都长H小时。
• 一个日程安排包括一系列不重叠的时间段s_i=[h₁, ..., h_j]。
• 时间段可以是空闲的，也可以是忙碌的。两个相邻的空闲时间段等同于跨越两个时间段的单个空闲时间段。
• 每个人的生产力P是0到1之间的值。
  • 制造者的生产力在最小化空闲时间段数时达到最大值。
  • 制造者的生产力等于1 / (max[1，空闲时间段数])。
  • 经理的生产力在最大化空闲时间总长时达到最大值，但他们更喜欢会议之间的长时间间隔而不是短暂的休息。
  • 经理的生产力等于每个空闲时间段长度的比例的平方和。即，(h₁/s_i)² + (h₂/s_i)² + ... ，其中每个时间段都是空闲时间段。
• 目标：最大化团队的总生产力。

请注意，如果没有会议，制造商和经理都能够达到最佳生产力。如果必须安排会议，则制造商更喜欢会议连续进行，而经理则不在意会议的时间。请注意，由于所有干扰对制造商来说都同样有害，因此如果会议分割了可用的空闲时间，那么持续1秒或3小时的会议之间没有区别。

问题是如何决定如何安排涉及N个人的M个不同会议，每个参加会议的人必须将繁忙时间段放入他们的日程安排中，以使其不与任何其他繁忙时间段重叠。对于每个会议Mt，所有参与者的“繁忙”时间段的开始时间必须相同。

是否存在一种算法来解决这个问题或类似的问题？我的第一个想法是这看起来非常类似于碎片整理（最小化不同块的数量），并且有许多关于此的算法。但是碎片整理与调度没有太大关系。您有什么想法吗？

---

(*) 实际上，这并不是一个真正的问题，因为我们很少有一次性与超过5个人开会，因此可能性的范围很小。

- John Feminella

---

这是NP问题，因为它涉及组合计算（必须考虑所有会议时间的排列组合），但这并不意味着你不能编写一个不错的（可能是近似的）算法来解决它。 - Victor Liu

我认为那不完全是NP的定义... - Tim

问题没有明确说明什么是最佳结果：如果一种可能性是经理会面10个小时，制造商有10个空闲时间段，而另一种可能性是经理会面20个小时，制造商有5个空闲时间段，那么哪一个更好？其中一个对经理来说更好，另一个对制造商来说更好，而没有规则来权衡这些不同类型的价值。 - Charles Stewart

@CharlesStewart：我将该规则作为模型的参数留给用户，因为不同的公司会有不同的权衡。您可以假设存在一个函数对 [Mk(S), Mg(S)]，用于计算制造商或经理在特定时间表下的幸福感。 - John Feminella

约翰：为了避免高阶参数，最好不要只寻求一个最佳结果，而是找到帕累托最优日程表的前沿。这暗示了一个动态规划解决方案。通过寻求接近帕累托最优解的前沿，您可能能够将其精细化为合理的近似值。您还对解决此问题的其他方法感兴趣吗？ - Charles Stewart

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

虽然这种方法无法产生最优的计划，并且有可能找到局部最小值。但它总是能够产生一个计划，而您可以始终向适应函数添加更多约束条件以排除任何不想看到的情况。这种算法可以处理许多不同类型的约束满足问题。

我个人使用类似的算法，在我的笔记本电脑上大约两个小时就为妻子的合作幼儿园安排了整整一年的计划。

- Jeremy E

Answer 2

这个问题看起来足够难以为 NP，但我认为它可以做一些不错的近似。

特别是，我认为你可以通过 会议规模优化 来管理得相当好，其中你将最大的会议（以出席人数为标准，因为他们是你尝试不干扰的人）放置到最佳位置，然后再用较小的会议依次进行。为了打破同一长度的较小会议的平局，你可以按参加者的会议负荷加权（这样你就有机会在他们身上进行优化，而不会让他们的生活变得更糟）。

现在，你已经将问题分解为安排单个会议，因为任何已安排的会议都会有效地缩短一个人的日程安排。解决方案非常简单：最优解是与制定时间表的制造商的时间表边的最大数量对齐的解，这样每个人都可以在那个时间参加会议。你甚至可以用暴力方法在类似于 O((k+g)*k*n) 的时间内解决这个问题，其中 k 是制造商的数量，g 是经理的数量，n 是制造商时间表中典型的时间间隔数量。

唯一的问题是，如果这种直接的方法会导致无法满足的会议。在这种情况下，您可以将该会议的优先级提高一个或多个插槽，然后再尝试一次。

- Rex Kerr

Answer 3

尝试看看模拟退火算法。它类似于Jeremy E所描述的遗传算法，但不是随机生成起始日程集，而是从一些有效但非最优日程开始。其思想是通过随机调整一些会议时间来生成原始日程的某个“邻居”，然后在迭代之前进行适应度测试。

S' = Starting Schedule
S = S'    
while( Fitness( S ) < Minimum Fitness ) 
{
    NS = Neighbor( S )
    if( Fitness( NS ) > Fitness( F ) )
    {
         S = NS
    }
}
Return( S )

与其针对某个最低适应度水平进行测试，您也可以指定一组迭代次数，以便确定程序何时完成执行。

这种算法的问题在于最终结果往往看起来像起始状态，因此如果您想要在一天早些时候给大型会议（以制造商的大小为衡量标准）分配更高的权重，那么您可以这样做。

- ForeignCat

Answer 4

我记得使用A*搜索算法实现了与您的问题非常相似的东西。您很容易会找到几个算法的实现，但是为了将其应用于调度问题，您需要根据您的模型构建距离和启发式函数，并将连续时间分成块。

- gleb