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 回答