这是一个最小的封面问题吗？

Question

我有以下场景(对长度的初步道歉,但我希望尽可能具有描述性):

我收到了一份"食谱"(Ri)清单,必须按照提供的顺序完成,以完成给定的任务.每个配方都包含完成它所需的部件列表(Pj).配方通常需要最多3或4个部件,但可能需要多达16个.示例配方列表可能如下所示:

• R1 = {P1}
• R2 = {P4}
• R3 = {P2,P3,P4}
• R4 = {P1,P4}
• R5 = {P1,P2,P2} //注意,可能需要超过1个给定部分.(这里,P2)
• R6 = {P2,P3}
• R7 = {P3,P3}
• R8 = {P1} //请注意,食谱可能会在列表中重复出现.(与R1相同)

最长的列表可能包含几百个配方,但通常包含一些配方的多次重复,因此消除相同的配方通常会将列表减少到少于50个独特的配方.

我有一组机器(Mk),每个机器都已预先编程(这种情况发生一次,在列表处理开始之前),以生成一些(或所有)可用类型的部件.

履行过程的迭代发生如下:

• 列表中的下一个配方将显示给计算机组.
• 在每台机器上,选择其中一个可用程序来生成此配方所需的部件之一,或者,如果此配方不需要,则将其设置为"离线".
• 转动一个"曲柄",每个机器(没有"脱线")吐出一个部件.
• 将曲柄旋转一圈产生的零件组合起来就完成了配方.订单无关紧要,例如,履行配方{P1,P2,P3}与履行配方{P1,P3,P2}相同.

这些机器可以即时,并行运行,并且具有无限的原材料,因此没有资源或时间/调度限制.机器组的尺寸k必须至少等于最长配方中的元件数量,因此具有与上述配方长度大致相同的范围(通常为3-4,可能高达16).因此,在上面的例子中,k = 3(由R3和R5的大小决定)似乎是一个合理的选择.

手头的问题是如何对机器进行预编程,以便银行能够完成给定列表中的所有配方.机器库共享一个公共内存池,因此我正在寻找一种算法,该算法产生的编程配置可以消除(完全或尽可能多)机器之间的冗余,从而最大限度地减少总内存负载量.机器组大小k是灵活的,即,如果增加超过给定列表中最长配方长度的机器数量,则为列表产生更优化的解决方案(但保持硬限制为16),这很好.

目前,我认为这是一个单一的问题,即每个程序需要相同数量的内存,尽管我希望将来能够灵活地添加每个程序的权重.在上面的例子中,考虑到所有配方,P1最多出现一次,P2出现最多两次(在R5中),P3出现最多两次(在R7中),而P4最多出现一次,所以我理想地希望实现一个与此匹配的配置 - 只有一台配置为生成P1的计算机,两台配置为生成P2的计算机,两台配置为生成P3的计算机,以及一台配置为生成P4的计算机.上述示例的一个可能的最小配置,使用机器组大小k = 3,将是:

• M1被编程为产生P1或P3
• M2被编程为产生P2或P3
• M3被编程为产生P2或P4

由于这里没有任何车间类型的限制,我的直觉告诉我,这应该减少到集合覆盖问题 - 就像在设计数字系统时发现的最小的unate set-cover问题.但我似乎无法使我对这些算法的知识(通常是有限的)适应这种情况.有人可以确认或否认这种方法的可行性,在任何一种情况下,都指向一些有用的算法？我正在寻找可以集成到现有代码块中的东西,而不是像伯克利的Espresso那样预先打包的东西.

谢谢!

Answer 1

这让我想起了编译器中用于寄存器分配的图形着色问题。

步骤1：如果菜谱中重复了相同的部分，则重命名；例如，R5 = {P1, P2, P2'}

第 2 步：将所有部件插入到图中，并且同一配方中的部件之间有边

步骤 3：对图形进行着色，使两个连接的节点（部分）没有相同的颜色

颜色是制造零件的机器标识。

这是次优的，因为重命名的部件在其他配方中创建了错误的约束。您也许可以通过“合并”来解决此问题。参见布里格斯。