基于订单、模具的版画组合与数量优化

Question

我写这篇文章是因为我有一个必须解决的离散优化问题，我认为在Python实现它时可能已经有一些理论结果，甚至是库(比如Google的or工具)。

问题是:我有不同的对象，使用不同的模具打印。你可以认为物体是小士兵或其他任何东西。每种物体都有不同的模具。总共，我有3台不同的打印机，其中2台可以同时使用8台模具，1台可以使用10台模具。当不同对象的订单到达时，我必须打印所有的对象，以尽量减少打印的数量。还有另一个方面--约束，这是非常重要的，但它不需要直接进入理论制定的问题:每次我改变模具，我就有一个巨大的损失印刷材料。因此，减少更换模具的数量甚至比减少打印的数量更重要(换句话说，如果我可以少修改一次模具，那么打印的次数要比要求的多一些更好)。

下面是一个可能有助于理解的例子：

• 命令：
  • 对象A: 80
  • 对象B: 95
  • 对象C: 101
  • …. 71

• 对象Z：

• 模具：
  • A: 1
  • B: 2
  • C: 3

  H 125…. 1

• Z.

• 可用打印机(它们处理的模具数量)：
  • P1: 8
  • P2: 8
  • P3 P2

注意:打印机总是需要充分装载模具。

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

Answer 1

我对此的想法如下。如果对安装在打印机上的任何molt (但不是全部)超过了预定的对象数量，则打印将被(部分)浪费。如果安装在同一台打印机上的蜕皮的有序对象数量不相等，则会发生这种情况。

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

我们可以通过将订单的数量分割到可用的蜕皮(如果不止一个)来优化这个数目。为了简单起见，让我们暂时忘记，我们也可以通过在不同的设置中再次使用相同的蜕皮来拆分这个数字。这给我们M-1自由度的每种类型的蜕皮，我们可以使用，以尽量减少浪费的打印(M是蜕皮的数目可用)。

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