python - 根据订单、模具优化组合和打印数量

Question

我写作是因为我有一个离散的优化问题需要解决，而且我认为可能已经有一些理论结果，甚至是 Python 中实现它的库（例如来自 Google 的 OR-Tool）。

问题如下：我有使用不同模具打印的不同对象。你可以把物体想象成小士兵或其他任何东西。每种物体都有不同的模具。我总共有 3 台不同的打印机，其中 2 台可以（同时）使用 8 个模具，1 台可以使用 10 个模具。当不同对象的订单到达时，我必须打印所有对象以尽量减少打印数量。还有一个侧面约束，很重要，但不必直接进入问题的理论表述：每次换模具，都会有巨大的印刷材料损耗。因此，尽量减少模具更换次数甚至比尽量减少打印次数更重要（换句话说，最好打印比所需相同对象更多的次数，

这是一个可能有助于理解的示例：

• 订单：
  • 对象 A：80
  • 对象 B：95
  • 对象 C：101
  • ……
  • 对象 Z：71
• 模具：
  • 答：1
  • 乙：2
  • C: 3
  • ……
  • Z：1
• 可用的打印机（他们处理的模具数量）：
  • P1：8
  • P2：8
  • P3 10

注意：打印机总是需要装满模具。

我想了一个简单的算法来解决单个打印机的问题，利用每个对象的顺序/模具数量的比率，但我相信有更好的方法，甚至可以同时考虑多个“打印机”。在某种意义上，它类似于装箱问题，但它更复杂一些，条件更多。

Answer 1

我对此的想法如下。如果安装到打印机上的任何蜕皮（但不是全部）超过了订购的对象数量，则打印（部分）浪费。如果安装到同一台打印机的蜕皮的订购对象数量不相等，则会发生这种情况。

因此，优化的第一步是构建具有相似数量的有序对象的 8 或 10 个蜕皮组。让我们首先保持简单，只考虑 8 组，忘记第三台打印机。浪费打印的总和是每组中最大订单数和最小订单数之间的差值之和。

我们可以通过在可用的蜕皮中拆分订单数量（如果不止一个）来优化这个数字。为简单起见，让我们暂时忘记我们也可以通过在不同的设置中再次使用相同的蜕皮来拆分数字。这为每种类型的蜕皮提供了 M-1 的自由度，我们可以使用它来最大限度地减少浪费的打印数量（M 是可用的蜕皮数量）。

这远不是一个完整的解决方案，但可能是一个起点。