有效的排课算法 [英] Effective Timetabling Algorithm

问题描述

我找到了一份工作，我一直要求做涉及编写一个程序来确定不同的人有工作在某一天。

I've got a job that I've been asked to do which involves writing a program to determine where various people are to work on a given day.

例如该输入可以是：
4-6pm，站点A
1-2pm，站点B
9-11am和放大器; 2-4pm站点A

For example the input may be:
4-6pm, Site A
1-2pm, Site B
9-11am & 2-4pm Site A

从本质上可以有很多的网站，人们可以在多个块的工作。我得到了这样的问题已经解决了所以以前的，而不是重新发明轮子，我希望有人可以点我的一个很好的解决方案方向的感觉。

Essentially there can be many sites and people can work during multiple blocks. I get the feeling that this kind of problem has been solved long ago so rather than reinventing the wheel I was hoping somebody could point me in the direction of an elegant solution.

编辑：阅读类似的问题，我得到这个问题可能是NP完全的感觉。我并不需要最有效的解决方案只适用，是合理的正常的东西。

Reading similar questions I get the feeling that the problem may be NP complete. I don't need the most efficient solution only something that works and is reasonably ok.

编辑2：为了澄清，输出应该是与人的时间表分配，这样的差距（情况下没有人工作），是尽可能小

Edit 2: To clarify, the output should be a timetable with people allocated such that gaps (instances where nobody is working) is as small as possible.

推荐答案

看起来你试图解决一个问题，其中有相当专门的软件应用程序。如果你的问题是足够小，你可以尝试做一个强力的方法是这样的：

Looks like you are trying to solve a problem for which there are quite specialized software applications. If your problem is small enough, you could try to do a brute force approach like this:

• 在确定问题的粒度。例如。如果这是一个学校的时间表，你的粒度可以是1小时。
• 请实例为每个时隙的粒度划分。因此，对站点B将有一个实例（1-2pm），对于大小会有很多情况下（4-5pm，5-6pm，9-10am，10-11am，...）。
• 请情况下，所有你要分配的人
• 然后反复地一个人分配到空闲时隙采取所有的约束条件考虑在内（如节日，午休，只能够做一件事的时候，每个站点的人最多，...），直到：
  • 您有一个有效的解决方案（精细，打印出来并退出应用程序）
  • 您输入的情况下，你仍然需要把人，但没有有效的时间段了。然后原路返回（撤消最后一个动作，并试图寻找它的替代）。
  • Determine the granularity of your problem. E.g. if this is for a school time table, your granularity can be 1 hour.
  • Make instances for every time slot divided by the granularity. So for Site B there will be one instance (1-2pm), for size A there will be many instances (4-5pm, 5-6pm, 9-10am, 10-11am, ...).
  • Make instances for all the persons you want to assign
  • Then iteratively assign a person to a free time slot taking all of your constraints into account (like holiday, lunch break, only being able to do one thing at a time, maximum number of people per site, ...) until:
    • you have a valid solution (fine, print it out and exit the application)
    • you enter a situation where you still need to place persons but there is no valid time slot anymore. Then backtrack (undo the last action and try to find an alternative for it).

    如果你的问题不是太大，你会发现在合理的时间内解决。

    If your problem is not too big you could find a solution in reasonable time.

    不过，如果问题开始变大了，找更专业的软件。事情要寻找的基于约束的优化和约束规划。

    However, if the problem starts to get big, look for more specialized software. Things to look for are "constraint based optimization" and "constraint programming".

    例如。 Eclipse的工具是一个开源的约束编程环境。你可以找到 http://eclipseclp.org/examples/index.html 的一些例子。一个很好的例子，你可以发现还有就是SEND + MORE =钱的问题。在这个问题您有以下公式：

    E.g. the ECLIPSe tool is an open-source constraint programming environment. You can find some examples on http://eclipseclp.org/examples/index.html. One nice example you can find there is the SEND+MORE=MONEY problem. In this problem you have the following equation:

        S E N D
    +   M O R E
    -----------
    = M O N E Y
    

    替换每一个字母一个数字，使之和是正确的。 这也说明，虽然可以解决这个蛮力，还有更聪明的方法来解决这个问题（见 http://eclipseclp.org/examples/sendmore.pl.txt ）。

    Replace every letter by a digit so that the sum is correct. This also illustrates that although you can solve this brute-force, there are more intelligent ways to solve this (see http://eclipseclp.org/examples/sendmore.pl.txt).

    这篇关于有效的排课算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！