7

我正在开发一个交互式作业调度应用程序。给定一组具有相应容量/可用性配置文件的资源,一组要在这些资源上执行的作业,以及一组确定作业顺序和作业的最早/最晚开始/结束时间的约束,我想让用户手动移动周围的工作。本质上,我希望用户能够“抓住”工作网络的一个节点并及时向前/向后拖动而不违反任何约束。

该图显示了一个简单的示例配置。最后的三角形作业表示所有作业的最晚完成时间,作业之间的连接线对作业施加顺序,灰色/绿色条表示资源可用性和负载。

您可以拖动任何作业来压缩计划。请注意,由于容量配置文件不同,作业的长度会发生变化。

我已经实现了一个有点工作的临时算法。但是,仍然存在失败并违反某些约束的情况。然而,由于工作车间调度是一个研究得很好的领域,有很多算法和启发式方法可以找到一般 NP-hard 问题的最佳(或相当好的)解决方案 - 我认为解决方案应该存在于我更容易的子集。我研究了约束编程主题,甚至研究了基于物理的解决方案(通过静态关节连接的刚体),但到目前为止找不到任何合适的东西。对我有任何指示/提示/提示/搜索关键字吗?

4

4 回答 4

1

出于以下几个原因,我会投票支持约束规划:

1) CP 会很快告诉您是否没有满足您的限制的时间表

2)您似乎希望为您的用户提供一个可行的解决方案,但允许他们操纵工作以改进解决方案。这点CP也不错。

3) MILP 方法通常复杂且难以制定,您必须人为地创建目标函数。

4) CP 并不难学,尤其是对于有经验的程序员来说——它确实更多地来自计算机科学界,而不是运筹学研究人员(比如我)。

祝你好运。

于 2010-02-02T16:32:42.947 回答
1

如果您的问题仅涉及整数,我强烈建议您查看Mozart Oz 。Oz 对有限域约束规范、推理和优化具有出色的支持。在您的情况下,您通常会执行以下操作:

  1. 以声明的方式指定您的约束。在此,您将指定所有变量及其域(例如 V1:1#100,表示 V1 变量可以取 1--100 范围内的值)。一些变量可能直接具有值,例如 V1: 99。此外,您将指定变量的所有约束。

  2. 向系统寻求解决方案:满足约束的任何解决方案或最优解决方案。然后,您将在 UI 上显示此解决方案。

  3. 假设用户更改了变量的值,可能是任务的开始时间。现在您可以转到步骤 1 将问题发布到 Oz 求解器。这一次,解决问题很可能不会像以前那样花费太多时间,因为所有变量都已经实例化了。

    可能是用户选择了不一致的值。在这种情况下,求解器返回 null。然后,您可以将 UI 带到较早的解决方案。

如果 Oz 适合您的需要并且您喜欢该语言,那么您可能想要编写一个约束求解器作为侦听套接字的服务器。这样,您可以将约束求解器与其他代码(包括 UI)分开。

希望这可以帮助。

于 2009-12-31T10:23:24.007 回答
0

您是否考虑过使用整数线性规划引擎(如 lp_solve)?它非常适合调度应用程序。

于 2010-01-26T16:55:49.630 回答
0

您可能可以更改 Waltz 约束传播算法以处理不断变化的约束,从而快速确定给定解决方案是否有效。我没有提到手,但这可能会为您指明正确的方向: http ://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYF-41C30BN-5&_user=809099&_rdoc=1&_fmt=&_orig=search&_sort= d&_docanchor=&view=c&_searchStrId=1102030809&_rerunOrigin=google&_acct=C000043939&_version=1&_urlVersion=0&_userid=809099&md5=696143716f0d363581a1805b34ae32d9

于 2009-11-20T10:56:15.780 回答