0

我是线性规划的新手，并试图围绕我要解决的问题开发 ILP 模型。

我的问题类似于机器资源调度问题。我有一组二进制变量来表示具有离散时间网格的机器的配对组合。作业 A 需要 1 小时，作业 B 需要 1 小时 15 分钟，因此时间网格应该以 15 分钟为间隔。因此，作业 A 将使用 4 个时间单位，而作业 B 将使用 5 个时间单位。

我很难弄清楚如何表达一个约束，这样当一个作业被分配给一台机器时，它占据的单位在时间变量中是连续的。有没有一个如何建模这个约束的例子？如果有帮助，我正在使用纸浆。

谢谢！

4

1 回答 1

0

您要实现约束：

x(t-1) = 0 and x(t) = 1 ==> x(t)+...+x(t+n-1) = n

一种方法是：

x(t)+...+x(t+n-1) >= n*(x(t)-x(t-1))

笔记：

  1. 您需要为每个t.

  2. 稍微好一点的版本是：

    x(t+1)+...+x(t+n-1) >= (n-1)*(x(t)-x(t-1))

  3. 此约束还有一个分解版本可能有助于提高性能（取决于求解器：一些求解器可以自动执行此分解）。

  4. 在计划期的开始和结束时，事情可能会变得有趣。例如机器开始于t=-1.

更新：

一种不同的方法是将工作的“开始”限制为 1。即只允许组合

 x(j,t-1) = 0 and x(j,t) = 1

对于给定的工作 j。这可以用类似的方式处理：

 start(j,t) >= x(j,t)-x(j,t-1)
 sum(t, start(j,t)) <= 1
 0 <= start(j,t) <= 1
于 2020-02-05T09:00:39.020 回答