如何将离散时间资源调度转化为问题？
How to formulate discrete-time resource scheduling into problem?
我是线性规划的新手，正在尝试围绕我要解决的问题开发 ILP 模型。
我的问题类似于机器资源调度问题。我有一组二进制变量来表示具有离散时间网格的机器的配对组合。作业 A 需要 1 小时，作业 B 需要 1 小时 15 分钟，因此时间网格应该以 15 分钟为间隔。因此作业 A 将使用 4 个时间单位，而作业 B 将使用 5 个时间单位。
我很难弄清楚如何表达约束，以便在将作业分配给机器时，它占用的单位在时间变量中是连续的。是否有示例说明如何对此约束建模？如果有帮助，我正在使用 PuLP。
谢谢！
您想实施约束：
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 重复此约束。
稍微好一点的版本是：
x(t+1)+...+x(t+n-1) >= (n-1)*(x(t)-x(t-1))
此约束还有一个分解版本，可能有助于提高性能（取决于求解器：一些求解器可以自动执行此分解）。
在计划期的开始和结束时，事情会变得有趣。例如。机器开始于 t=-1.
更新：
另一种方法是将作业的 "start" 限制为 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
我是线性规划的新手，正在尝试围绕我要解决的问题开发 ILP 模型。
我的问题类似于机器资源调度问题。我有一组二进制变量来表示具有离散时间网格的机器的配对组合。作业 A 需要 1 小时，作业 B 需要 1 小时 15 分钟，因此时间网格应该以 15 分钟为间隔。因此作业 A 将使用 4 个时间单位，而作业 B 将使用 5 个时间单位。
我很难弄清楚如何表达约束，以便在将作业分配给机器时，它占用的单位在时间变量中是连续的。是否有示例说明如何对此约束建模？如果有帮助，我正在使用 PuLP。
谢谢！
您想实施约束：
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重复此约束。稍微好一点的版本是：
x(t+1)+...+x(t+n-1) >= (n-1)*(x(t)-x(t-1))此约束还有一个分解版本，可能有助于提高性能（取决于求解器：一些求解器可以自动执行此分解）。
在计划期的开始和结束时，事情会变得有趣。例如。机器开始于
t=-1.
更新：
另一种方法是将作业的 "start" 限制为 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