mixed-integer-programming - 使用 Time Windows 进行一维装箱

Question

嗨 StackOverflow 专家！

我有一个 1D Bin 包装满意度问题（即给出了 bin 的数量并且不需要最小化）。我认为这个问题非常简单，可以在这里找到 MIP 公式：https ://medium.com/swlh/exploring-the-bin-packing-problem-f54a93ebdbe5

但是，如果要打包的块有 Time Windows 怎么办？示例：假设每个 bin 的高度在 70 到 100 之间。一些块有一个打开的 TimeWindow，这意味着它们可能位于任何位置（在任何 bin 中）。但是如果一个 5 大的块的 TimeWindow 等于例如 [50,60]，则块的开始必须位于 50 或更高，而块的结束必须位于 60 或更早。（即，如果位置 0 位于容器顶部，位置 100 位于容器底部，则块必须位于 100 高的容器中点的正下方）。

垃圾箱的（整数）大小约为 50-100，块的大小约为 2-25，TimeWindows 通常为 6-100 大。

因此，问题不再只是为每个块找到最佳 bin，而是将每个块定位在其分配的 bin 内。

应该是个有趣的问题！任何人都有好的 MIP 配方？:-)

标签： mixed-integer-programming

Answer 1

这可以建模为并行机器上的调度问题。让我们介绍一些符号：

• 让J是作业集（块）和M机器集（箱）
• r_j并且d_j将是工作j时间窗口的开始和结束（r表示发布日期，d表示截止日期）
• c_jm是在机器上处理工作的成本，以及j在机器上处理所需的时间。mp_jmjm
• x_jm一个二进制变量，如果作业j分配给机器m，则为 1，否则为 0
• y_ij另一个变量是 1 如果作业i并且j分配给同一台机器，作业在作业i之前j；0 否则
• s_j和的开始和结束时间的e_j连续变量j，分别

有了这个，根据 Sadykov 和 Wolsey [SW]，以下是一个众所周知的 MIP 公式：

目标函数最小化总处理成本（目标函数可以更改为另一种东西，因为 OP 只想解决可满足性），而约束表示：

1. 每个作业都分配给一台独特的机器。
2. 关联作业的开始和完成时间。
3. 确保 if y_ij = 1， ie在同一台机器i之前j和由同一台机器处理，然后处理j必须在结束之后i开始。这里，U是一个足够大的常数，可以设置为例如U = max_j d_j - min_j r_j。
4. 5. 是否尊重时间窗口。
5. 逻辑约束；最多一个，i并且j可以在另一个之前处理
6. 保证如果i和j被分配给m，那么一个必须在另一个之前被处理。
7. 如果作业i和j被分配到不同的机器，那么y_ij = 0和y_ji = 0。
8. 10. 限制变量域。

上面的参考资料包括几个不等式来收紧模型，以及一个计算基准比较和结合模型与约束编程。

编辑：在 OP 的情况下，所有箱子都是平等的，因此我们可以简化模型以考虑相同的机器（就每个作业的独特成本c_j和处理时间而言p_j，与机器无关）。

---

[SW] Sadykov, R. 和 Wolsey, LA (2006)。整数规划和约束规划在解决具有截止日期和发布日期的多机分配调度问题。INFORMS计算杂志，18 (2), 209-217。可在 ResearchGate 上在线获取。