是否有一种优化"制造商的时间表"的调度算法？

Question

您可能熟悉保罗格雷厄姆的论文,"制造者的时间表,经理的时间表".文章的关键在于,对于创意和技术专业人士来说,会议是对生产力的诅咒,因为他们倾向于导致"计划碎片化",将自由时间分解成太小而无法获得解决困难问题所需的焦点的块.

在我的公司中,我们通过最大限度地减少造成的中断数量已经看到了显着的好处,但是我们用来决定时间表的蛮力算法并不够复杂,无法很好地处理大群人.(*)

我正在寻找的是,如果有一个众所周知的算法可以最大限度地减少这种生产力中断,在一组N制造商和管理者中间.

在我们的模型中,

• 有N个人.
• 每个人p _我或者是制造商(的Mk)或管理器(镁).
• 每个人都有一个时间表小号_我.
• 每个人的日程安排都是H小时.
• 时间表由一系列非重叠间隔s _i = [ h ₁,...,h _j ]组成.
• 间隔是空闲的还是忙的.两个相邻的自由间隔相当于跨越两者的单个自由间隔.
• 每个人的生产率P是0到1之间的值.
  • 当空闲间隔的数量最小化时,制造商的生产率最大化.
  • 制造商的生产率等于1 /(最大[1,空闲间隔数]).
  • 当空闲时间的总长度最大化时,经理的生产力最大化,但他们喜欢会议之间的长时间而不是短暂休息.
  • 经理的生产率等于每个自由区间长度的平方和作为当天的比例.即,(h ₁/s _i)² +(h ₂/s _i)² + ...,其中每个间隔是自由间隔.
• 目标:最大化团队的总体生产力.

请注意,如果没有会议,制造商和经理都会体验到最佳的生产力.如果必须安排会议,那么制造商更喜欢会议背靠背,而管理人员并不关心会议的进展.请注意,因为所有中断都被视为对制造商同样有害,所以持续1秒的会议与持续3小时的会议如果划分可用空闲时间则没有区别.

问题是决定如何安排涉及N个人的任意数量的M个不同会议,其中给定会议中的每个人必须将繁忙间隔放入他们的日程中,使得它不与任何其他繁忙间隔重叠.对于每个会议M _t,忙碌间隔的开始时间对于所有各方必须相同.

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

---

(*)实际上这并不是一个真正的问题,因为我们很少同时与超过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幼儿园全年.