如何将离散时间资源调度问题转化为问题？

Question

我对线性规划很陌生，并试图围绕我想要解决的一个问题开发一个ILP模型。

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

我很难理解如何表达约束，这样当任务被分配给机器时，它所占用的单元在时间变量中是顺序的。有关于如何建模此约束的示例吗？如果有帮助的话，我正在使用PuLP。

谢谢!

Answer 1

您希望实现约束：

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

备注：

对于每个稍微好一些的t.

• A，您需要重复这个约束的

1. 是：

x(t+1)+...+x(t+n-1) >= >=也是该约束的一个分类版本，它可能有助于性能(取决于求解者:一些求解者可以这样做)，automatically).

• Things可能在规划周期的开始和结束时变得有趣。在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