调度应用中的约束图变换

我强烈建议你看看 Mozart Oz ,如果您的问题 只处理整数。oz对有限域有很好的支持 约束规范、推理和优化。以你为例 通常您会执行以下操作:

1. 以声明方式指定约束。在这方面,你会 指定所有变量及其域(如v1:1 100,表示 v1变量可以取1-100范围内的值。一些变量 可能直接有值,比如v1:99。此外,您还可以指定 变量的所有约束。

2. 向系统询问解决方案:满足以下条件的任何解决方案 约束或最优解。然后你会显示这个 用户界面上的解决方案。

3. 假设用户更改了变量的值,可能是 任务的时间。现在您可以转到步骤1将问题发布到 盎司求解器。这次,解决问题很可能不需要 和之前一样多的时间,因为所有的变量都已经被实例化了。

   可能是用户选择了不一致的值。在那 case,解算器返回空值。然后,您可以将ui带到前面的 解决方案。

如果奥兹适合你的需要,而且你喜欢这门语言,那么你可能想 将约束求解器编写为侦听套接字的服务器。这种方式, 你可以把约束解算器和其他代码分开, 包括用户界面。

希望这有帮助。

出于以下几个原因,我将投票赞成约束编程:

1)如果没有满足您的限制的时间表,CP会很快告诉您

2)看起来你想给你的用户一个可行的解决方案,但是 允许他们操纵作业以改进解决方案。CP也擅长这个。

3)MILP方法通常很复杂,很难制定,你必须人为地创建一个目标函数。

4)CP并不难学,特别是对有经验的程序员来说——它实际上来自计算机科学界,而不是像我这样的操作研究人员。

祝你好运。

您可以更改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

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