algorithm - 制定时间表

Question

所以.. 最近有人要我为他们制定时间表，我同意了。当我坐下来做这件事时，我意识到这比我想象的要难。这只是一个时间表，白天或晚上轮类给 4 个人。

我想到了这样的事情:

for Monday to Saturday {
  for(i=0;i<people.length;i++){
    if (person[i].available()){
      person.worksDay()
      person is now not available.
    }
  }

  for(i=0;i<people.length;i++){
    if (person[i].available()){
      person[i].worksNight()
      person[i] is now not available.
    }
  }
}

因此，此算法背后的想法是，每一天，一个人都会被分配到白类或夜类。如果一个人不只是轮类工作并且他们不在假期，那么他们是有空的。它适用于周一至周六。正如您可能知道的那样，给定人员 A、B、C、D，分配将如下所示(如果没有人在度假):

Mon A B
Tue C D
Wed A B
Th  C D
Fri A B
Sat C D

我想这可行，但有点明显。问我的人想看到不同的选择。有没有更好的方法可以看到比这个选项更多的东西？或者甚至有一个程序可以为您执行此操作？

Answer 1

我认为你应该使用遗传算法，因为:

• 它最适合大型问题实例。
• 它以不准确的答案为代价降低了时间复杂度(不是最终最好的)
• 您可以通过调整未满足条件的适应度惩罚来轻松指定约束条件和偏好。
• 您可以指定程序执行的时间限制。

• 解决方案的质量取决于您打算花多少时间解决该程序。

  Genetic Algorithms Definition

  Genetic Algorithms Tutorial

  Class scheduling project with GA

另请参阅:a similar question和 another one