3

所以..最近有人要求我为他们制定时间表，我同意了。当我坐下来做这件事时，我意识到这比我想象的要难。这只是一个时间表，让 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

我猜这可行，但有点明显。问我的人想看看不同的选择。有没有更好的方法来执行此操作以查看更多内容而不仅仅是此选项？或者甚至有一个程序可以为你做到这一点？

4

3 回答 3

2

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

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

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

    遗传算法定义

    遗传算法教程

    带有 GA 的课程安排项目

也看看：一个类似的问题和另一个

于 2011-01-04T15:00:20.827 回答
1

蛮力是没有意义的。

使用Drools Planner、Choco、JGap、cpsolver 等框架为您解决。其中一些框架（包括 Drools Planner）允许您轻松切换优化算法并包含用于确定最适合您的问题的工具。

于 2011-12-20T17:07:37.060 回答
0

约束编程问题通常很复杂且难以编程。即使您的问题相当简单，您也可能需要下载一个工具来解决此问题。Gnu 线性编程工具包可能是最好的选择，它有一个求解器和一个你可以使用的建模语言。我写了一篇关于安排一次的很长的帖子。

于 2010-10-18T16:42:23.573 回答