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

Question

我在一家出版社工作,我正在设置我们的一台"帮派"印刷机,换句话说,同时印刷多个工作.鉴于不同的打印作业可以有不同的数量,并且一次可能需要考虑1到20个作业,问题在于确定将哪些作业组合在一起以最大限度地减少浪费(来自过度打印的废物在较小的情况下 - 给定集合中的数量作业,即).

鉴于以下稳定数据:

1. 所有工作在空间大小方面都是相同的 - 纸上的位置没有考虑在内.
2. 有三个"通道",意味着可以同时打印三个作业.
3. 理想情况下,每条车道都有一项工作.部分问题是最小化每个作业运行的通道数.
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)单独.但是你也可以在两条车道(500/250)上运行(1000/500),在两条车道上运行500,然后单独运行(450).

在车道最小化与浪费的权衡方面,我们可以说任何超过200的分组浪费都是过度的.

(结束编辑)

......不用说,这是一个很大的问题.(为了我.)

我是一名技术熟练的程序员,但我对算法并不熟悉,而且我对该领域的数学还没有充分研究.我是I/P写的一种蛮力程序,它只是尝试所有选项,忽略了任何似乎有过多分组浪费的选项树.但是,我不禁希望有一种更简单,更有效的方法.

我已经查看了各种网站,试图找到更多关于算法的信息,并且一直在通过符号系统,但它进展缓慢.不幸的是,维基百科关于这个主题的文章非常依赖于交叉,很难找到"in".我唯一能够真正找到的东西似乎是我需要的粗略算法类型的定义:"独家距离聚类",一维地说.

我确实看过这个网站上普遍提到的算法,Bin Packing one,但是我无法确切地看到它如何解决我的问题.

Answer 1

如果我理解这个问题（我不确定我理解），那么解决方案可能很简单，例如在所有三个通道中打印作业 1，然后在所有三个通道中打印作业 2，然后在所有三个通道中打印作业 3。

最坏的情况是每个作业额外打印两张纸。

我可以想到这不是最佳的情况（例如，三份工作，每份四张纸需要六页而不是四页），但它的开发可能比 Bin Packing 解决方案（这是 NP 完全的）要简单得多；随着时间的推移，三个车道中的每一个都代表垃圾箱。）