algorithm - 最小浪费打印作业分组算法？

Question

我在一家出版社工作，我正在设置我们的一台打印机以进行“联合”，换句话说，同时打印多个活件。鉴于不同的打印作业可能有不同的数量，并且一次可能需要考虑 1 到 20 个作业，问题将是确定将哪些作业组合在一起以最大程度地减少浪费(来自较小的叠印的浪费 -给定集合中的工作数量)。

鉴于以下稳定数据:

1. 所有工作在空间大小方面都是平等的——不考虑在纸上的位置。
2. 有三个“ channel ”，这意味着可以同时打印三个作业。
3. 理想情况下，每个车道都有一份工作。部分问题是尽量减少每个作业运行的 channel 数。
4. 如有必要，可以在两条车道上运行一个作业，在第三个车道上运行第二个作业。
5. 一组给定工作的“分组”浪费(假设它们的数量为 x、y 和 z)将是最高数字减去两个较低数字。因此，如果 x 是较大的数字，则分组浪费将为 (x - y) + (x - z)。否则，打印作业 Y 和 Z(超过它们的数量)直到数量 X 时都会产生浪费。分组废物将是给定集合的限定词，这意味着它不能超过一定数量，否则作业将只需单独打印即可。

所以问题是:如何根据 1) 三个相似数量或 2) 两个数量，其中一个数量大约是另一个数量的两倍，从任何给定数量的工作中确定哪些工作组被组合在一起，并且以最小化各种集合中的总分组浪费为目标。

(编辑)数量信息:典型的作业数量可以是 150 到 350 外语版，或 500 到 1000 版英文版。此数据可用于为算法设置一些场景。例如，假设您有 5 份工作:

1000、500、500、450、250

通过查看它，我可以看到几个答案。显然 (1000/500/500) 效率不高，因为你会有 1000 的分组浪费。(500/500/450) 更好，因为你会浪费 50，但是你运行 (1000) 和 ( 250)独自一人。但您也可以在两条车道上以 1000 跑 (1000/500)，在两条车道上以 500 跑 (500/250)，然后单独跑 (450)。

就 channel 最小化与浪费的权衡而言，我们可以说任何超过 200 的分组浪费都过多。

(结束编辑)

...不用说，挺麻烦的。 (对我来说。)

我是一名技术水平一般的程序员，但我对算法不太熟悉，也没有充分研究该领域的数学。我正在 I/P 编写一种简单地尝试所有选项的蛮力程序，忽略任何似乎有过多分组浪费的选项树。但是，我不禁希望有一种更简单、更有效的方法。

我查看了各种网站，试图从总体上了解更多关于算法的信息，并且一直在努力研究符号系统，但进展缓慢。不幸的是，维基百科关于这个主题的文章非常相互依赖，很难找到一个“in”。我唯一能够真正找到的东西似乎是我需要的粗略算法类型的定义:从一维的角度来说，“独占距离聚类”。

我确实看过这个网站上似乎被普遍引用的算法，即 Bin Packing 算法，但我无法确切地看到它如何解决我的问题。

Answer 1

这似乎类似于运筹学中经典的“削减库存”问题。对于正式的数学处理尝试 http://en.wikipedia.org/wiki/Cutting_stock_problem

我使用 Robert W. Haessler(管理科学，88 年 12 月)的论文“Selection and Design of Heuristic Procedures for Solving Roll Trim Problems”中的延迟列生成技术编写了下料问题的解决方案。我测试了一百卷没有问题。了解如何从第一次迭代中获取残差，并使用它们为下一次迭代制作新方程非常有趣。看看您是否能拿到这篇论文，因为作者讨论了更接近您的问题的变体。

如果您掌握了可行的技术，我建议您使用功能强大的线性代数求解器，而不是重新发明轮子。虽然单纯形法很容易为分数解编写代码，但您在这里处理的问题更难 - 这是一个混合整数问题。对于使用例如现代 C 混合整数求解器 (MIP)。分支和绑定(bind)，我推荐使用 Java/python 绑定(bind) lp_solve .

当我写这篇文章时，我找到了 this NEOS guide page有用。在线求解器看起来已经失效(对我来说它返回 perl 代码而不是执行它)。还有一些背景信息。

编辑 - 一些注意事项:我将总结您的问题与下料问题之间的区别:1) 下料具有不可分割的输入长度。您可以通过多次运行问题来模拟您的可分问题，将作业分解为 1.0、{0.5、0.5} 倍的原始长度。2)你的“打印运行长度”映射到部分长度3)选择大的库存长度