Question

我接受我所要求做的工作,其中涉及起草一项方案,以确定哪些人将在某一天工作。

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

基本上可以有许多地点,人们可以在多个区段工作。我感觉到,这种问题早就得到解决了,而不是重新发明了我所怀念的轮.,有些人希望我能够把我们引向一个棘手的解决办法。

Edit:阅读类似问题我感到这个问题可能已经解决。我不需要最高效的解决办法,而只有能够奏效并且能够合理地ok。

第2号:为了澄清,产出应当是一个时间表,配给人,因此差距(如果没有人工作的情况)尽可能小。

Answer 1

看像你那样试图解决一个非常专业化的软件应用问题。如果你的问题太小,你可以尝试采取像以下那样的淡化武力做法:

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).

如果你的问题不是太大,你就可以在合理的时间内找到解决办法。

然而,如果问题开始变得大,则寻找更多的专用软件。有待考虑的事项是“以制约为基础的优化”和“制约性方案拟订”。

例如,ECLIPSe工具是一种开放源的制约方案规划环境。 http://eclipseclp.org/examples/index.html 你可以发现的一个 example例子是SEND+MORE=MONEY。在这个问题上,你有以下平衡:

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

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).

友情链接