外文翻译--最小化模式下料问题科林麦克迪尔米德 中文版

1 离散应用数学 离散应用数学 98(1999) 121-130 最小化模式下料问题 科林麦克迪尔米德 统计 部门 ，牛津大学，南 公园路一号 ，牛津 大学 OX1 3TG，英国收稿 于 1997 年10 月 21日，接受 于 1999 年 2月 8日 摘 要 在切割存量模式最小化问题，我们希望，以满足尽可能少巨型卷轴卷轴切割各种客户的需求，并进一步减少使用不同的切削模式的数量。我们专注于特殊情况，其中任何两个客户卷轴到一个巨型合适，但没有三事：这个案件的兴趣，部分是因为它是最简单的情况是不平凡的，部分是因为它在实践中可能会出现当一个 尝试一个解决方案，以改善迭代。 我们发现，该模式最小化问题是强 NP 难的，即使在这种特殊情况下，当inding 最低废液的基本问题是微不足道的。 我们的分析主要论点集中在 均衡 的子集，并提出了涉及亚均衡的启发式搜索方法的方法。 1999 Elsevier 科学 BV 公司保留所有权利。 关键词： 下料，切割模式 ；分区 ； NP 难 ；动态规划 2 1 简介 有些材料如纸，可制造性 巨无霸 卷，这是后来成为更窄辊切，以满足客户的需求。为了减少浪费，应选择切割方式，以尽可能少的使用客机（见 4,7,8）。 因此，下料问 题已基本输入一个正整数 j，不同的正整数 r1的 ,., Rn和 D1的 ,.,正整数的 DN，以及需要的任务是，以尽可能客机的宽度 j的数为满足客户的卷筒宽度里迪需求对每个 i = 1 ,.,，全 这是其中的经典 OR问题之一。 它包含了强烈的 NP -完全问题三分区： 因此即使巨幅大小 J外面有一层氮、多项式满足每个客户的卷轴大小国际扶轮扶轮 J / 4 J / 2 -看 6,p。 224。因此我们不能指望在合理时间内总是能找到最优解等问题的。 每一次不同的客户卷轴模式是被削减，在切 割机的刀需要重新设置。甲由Cn中 Goulimis 并在第 29届欧洲与产业调查研究组 1996 年 3 月有关如何找到办法来解决上述料问题，这进一步减少了用于切割不同模式的数量问题 - 见1,2,9 。 一般情况下这当然是变得越来越难 。为了探讨扩展问题雪上加霜，我们在这里考虑一个特殊的案件中，尽量减少对客机（减少废物），数量基本问题是微不足道的。 最小化格局 ： 输入： D1的正整数 ；的 DN。 任务：在切割存量问题，即要求 I 型迪卷轴是，任何两个卷轴到一个巨型做它，但没有三，工业最低废液，进一步减少了使用不同模式的数量。 这种特殊的情况是非常有限的部分原因是因为它似乎是最简单的情况是完全不平凡的，部分是因为它可能会在实践中产生的，当一个一个解决方案试图改善迭代的兴趣 。 例如，如果对目前使用的一些模式集合同意的大型卷轴和 difer小卷轴而已，它在任何两个小卷轴左边的大型卷轴的宽度，那么当我们试图重新分配小我们面临的正是这种卷轴的特殊情况 16。 我们调查模式是否最小化问题还很难在这个特殊的情况，并简要考虑办法找到好的解决办法。 很明显，所需要的客机数量最少的是我的 di / 2，圆了总需求的一半，它是微不足道的一个相应的最低工 业废液。但是，它是多么容易跻身工业废物最小的解决方案，一个能最大限度地降低使用的模式的数量，？对于这个问题的变体在没有三个客户卷轴它变成珍宝，但也有一些对可能不是，它是在 1表明，问题是强 NP -难问题。下面的定理加强这种不利的结果。 定理 1： 这个问题最小化模式是强 NP -难问题。 3 对上述问题的理解关键是一个 平衡的一个子集 的概念。 给定一个家庭 d =(d1,dn)的非负整数 ,表示 x(d)的 在任何解决方案中使用最少的废物模式的最小数量。 还有 ,另一个平衡的非空的子集 1,n ,如果它能够被分割成两个集 合A和 B,tA di = 5ieB di。因此 ,如果 di = 0 然后单独设置 i是平衡的。让 v(d)是最大的数字的平衡子集两两相互无 关的。 引理 1： 如果 J2i di 是偶数 ,然后 x(d)= n - v(d)。 如果 i di 是奇数，令 x(d) = i(d),其中 d1 从 D获得通过增加一个额外的统筹的 DN +1 = 1。 我们将在下一节中证明这个引理。 当与一个模式最小化所面临的问题，我们领导的定理 1 和引理 1以上考虑启发式方法 inding 亚群平衡的好包装。不幸的是 NP -完全甚至 是 测试，如果一个家庭中的 正整数格 a1,.,an有一个平衡的一个子集。 这就是问题称为弱分区是大卫约翰逊的 NP 完全列 10，其中四分之三的 NP 完全独立的证据被引用，最早在13。 我们希望工业亚群的平衡好包装，但我们知道这是很难工业最佳包装，的确是很难平衡的工业任何一个子集。自然启发式的方法是反复寻找和删除一个平衡的一个子集，最好是小的。其中寻求一个平衡的一个子集的方法是使用diferencing，这里我们再次取代其 diference 绝对值两个数字 - 参见5,12,15,17。这种方法目前正在调查中最小的格 局 16中。另一种方法是使用一个还算快速算法，保证工业均衡的子集或子集的最小平衡：我们会看到，我们可以使用一个简单的动态规划方法来测试，如果有一个平衡的子集，均衡和 IND一个最小的子集如果有一个，在伪多项式时间。最小的模式启发式方法更普遍的情况下在降低库存的问题被认为是 1,2,9,11。 该论文的其余部分计划如下。在下一节中，我们建立的模式之间的平衡亚群的数量和包装的关系。接下来，我们证明我们的主要结果，这个问题最小化模式是强 NP -难问题。在此之后，我们认为 briely 如何寻找平衡的子集， 并 inally我们做一些总结性发言。 4 2 模式，学位和平衡套 在这一节中，我们将证明引理 1，其中涉及的图案编号，包亚群平衡 英格斯。最小化的问题可以改写格局在图上。一个模式，涉及卷轴 I型和 J型卷筒之间将对应顶点顶点 vi和 vj 的边缘。我们将让我们的图，包含在任何顶点循环但不包含多个边缘。 给定一个图 G =（ V， E）对集 V = v1， .， v2的顶点，连同非负整数重量的边缘 E，我们的家庭 W 时，顶点加权第六度过度的重量与我们六边 事件的总和与任何循环，计数两次。给定一个向量 d =（ d1. dn） 的正整数，我们呼吁 d如果每个顶点 Vi 有两人加权程度地代表公克 WA 网络。考虑以下问题。 学位 ： 输入：积极 intergers d1. 甚至与 dn。 任务：工业用尽可能少的边缘一个代表网络。 给定一个 d 组 =（ d1 . dn）的正整数，甚至与我二，有一个度之间的解决方案和模式 MINIMI SATION 这些自然的对应，特别是最小的边数前者的可能等于 （ d）项。 引理 1： 假设 di是偶数。 设 G w是任何代表工作，并考虑为 G的 K 个节点集 K 表的组成部分。这当然必须有至少 k - 1条边，如果它有这个数目，因此 是对 K 树，那么三分之二的顶点着色表明， K 是平衡的。因此，在 G 的边数至少有 n 减去若干套组成部分的平衡。因此（ D） Jsn - 的 v（ d）。 为了证明反向不等式，考虑任何 V1.Vn（ Ki： i I），其中一个最不均衡。我们将证明，有代表 怨恨网络 G， W 使得图 G有组件（ Gi： I i）如已设立文基顶点，这些组件是这样，如果文是平衡的，然后是一树基如果没有则Gi是一加一树循环。这将完成该引理的证明。 考虑平衡集 K，其中分区 A U S 使得 YieA= igBdi国际能源署。我们必须表明，有对 T边缘 E对 K和非负权重，我们一树 T，使得对于每一个节点 v K 时，对事件边的权重之和等于的 dv（其中双回路数）。我们使用 K|表感应。如果 A或 B 是空的，结果是微不足道的，因为我们必须为每个 V 光那假设 A和 B都是非空的 dv = 0。选择任何一个和 b 阿 B和不失一般性假设大 分贝。减少大的分贝。现在 K 表 B的是平衡的，我们可以感应工业适当的加权树。然后加入与体重分贝边缘抗体。 最后，考虑一个集 K这是不均衡的，但就是这样，相应的要求和是偶数。如 5 上所述，我们可以随时更换了使用成本的一个边缘的 diference 两 个要求。因此，我们能满足所有，但一用边缘形成一个对 K树需求，然后添加一个循环结束的组成部分。 6 3 最小化模式是强 NP -难 在本节中，我们证明定理 1，这个问题最小化模式是强 NP -难问题。总结三（或舒尔三）是三，这样的两个之和等于第三个不同的整数集合。下面的问题可以得到更充分的描述，总结成独特的整数分区的三倍作为。 总结三元 输入： S1. S3n 不同的正整数。 问：能否输入三元分割成总结？ 这个问题类似于数值匹配与目标款项，加里和 Johnson 6，第 224，但额外的（令人惊讶的麻烦），条件是涉及的人数必须是不同的。 引理 2： 问题总结三元是强 NP -完全的。 本节的大部分将用于证明上述引理，但首先，让我们看到，它会产生定理 1。 证明定理 1（假设引理 2） ： 我们给一个总结，学位 strightforward 三倍，多项式时间减少。考虑一个总结三元上述实例。以 =作为学位实例（ 2s1 .2s 3n）。由于硅是不同的正整数，也有规模不小于 3套平衡。因此，（ dHence 由引理 1，第十章 x（ d） 2n与 x（ d）为 2n =当且仅如果 s1 . .s3n可分为总结三倍 现在考虑的问题总结三倍，这显然是在 NP。我们将证明它是强 NP -通过给从 NP -完全问题限制 X3C 减少完成，下述，总结每个三元组在 O（ n3）的。 限制 X3C： 输入：一组第三季度的 X元素和一个三元组集合 C在十，这样每个 X的 元素完全相同 3 三元载。问：可以划分为三元 X是在 C？ 引理 3： 限制 X3C 问题是 NP完全的 。 证明 据了解，这个问题是 NP 完全问题，如果每个元素被限制在最多 3 三倍，而不是正好 3 - 见加里和 Johnson 6，第 221。这是很容易对注册整洁 的实例 X， 使每个元素恰好是 3 的三倍。 很明显，我们能坚持，每个元素在 2或 3 的三倍。我们可以在分区中的元素正好两个三元组分为三个区块的大小。对于每个块 x， Y， Z，添加新的元素三个 x， y， z及 x， y， z， x， y， z， x1， y， z， x1， y， z。调用新的实例 X， C的。显然，每个 X的元素是完全相同三三元在 C；和 X 可以被划分在 C到三倍，如果有仅当 X可以被划分为三元在 C。 引理 2： 考虑一个实例 X， C的限制 X3C，其中 | X = = CI=3q。 7 季度全令 Y = X x 1 ,., 7。我们将建设一个 扩大 在 Y D 的收集，包含三元使得 X可分为三元在 C分区，当且仅当 y可划分为 D中三元，接着我们将构造一个实例（秒（ y）的：你们的 Y 总结三倍，其中每个尺寸 S（ y）的异 O（ n2），），这样的总结恰恰三倍对应的三元组在 D 形成一个二分图 G =（ C， X， E）的顶点 C 部及 X 和顶点窄隙室和 X GX的相邻（即边发射 GE）的正是由于当 x 吨 G 中的每个顶点度是三，我们可以在多项式时间内找到一个合适的 3 边染色 ： E - 1,2,3。现在，我们每个元素x GX 的分割成三份（ x， 1），（ x， 2）和（ x， 3）。鉴于一特里普尔 T = x， y，z气相色谱，令 T是三重 T= （ x， KTx），（ y， （ Ty），（ z， （ Tz） 观察，在三 T的分子具有不同的第一坐标（ X），以及独特的第二个坐标（必须是 1,2,3），而 C=（ T： TG）分区集 X x 1,2,3。 接着，每个 X光霞，让 Fx 的是集合组成的四个三元 （ x， 1），（ x， 4），（ x， 5） ， （ x， 3），（ x， 4）， （ x， 5） ， （ x， 2），（ x， 6），（ x，7） 和 （ x， 3），（ x， 6），（ x， 7） 。设 D是由碳的收集与所有的 X 十，因此 D包含在集合在一起 Fx 的三元 | | +4 | x |= 5n 的三倍。 如果某些子集合 的 D 是 Y的分区，然后对每个 x G X 的时候，恰恰的要素之一（ x， 1），（ x， 2），（ x， 3）不包括由三元组在 D东经外汇，因此必须由在 D东经企业所得税三倍以下方便，这包括 X可以被划分在 C到三倍，当且仅当 y划分可分为三元在 D这样就完成了施工红外警戒的一部分。 下一步，我们将看到如何分配尺寸 S（ y）对每个元素 y 戈瑞以便在 Y元素的总结三元正是在 D的三元组，我们将使用一个界定差不多的 K -明智的独立随机变量的家庭小样本空间。 设 1 = 3 log2 n+10，令 t = 2n1，令 k = 91，让 8 = 2。有 Q的一个子集 0,1，大小 2（ 1 + 0（ 1） K的：如果一个点的合作 =（ ro1 .,cot）是随机挑选的统一 Q，则 ,., cot）的是 8距离的 K -明智的独立，见 3。今后这类一套 Q可以（明确）在多项式时间建成北界 。 给定一个点合作宾馆，对每个 i = 1 ,., 2n 个，让 $ = $（ co）是非负， teger 二进制扩展 coy。当一个点 co=（ co1,., cot）的采收有限公司。 从Q随机均匀，然后 S1.,.S2n是随机变量，以价值观在 0,1 ,., N - 1 个，其中 N = 2Z，它们具有以下属性。对于任何集成电路与 IC1 .2n 与 0| 11 69，和任何集合 0,1 ,., N - 我们： I I） G E） - |E| /NI/| 61 / 2：现在，我们可以定义元素的大小为我们总结三元原审（年）。为清楚起见，我们将写的（ X， 1），而不是秒（ X， 1）等。给定一个采样点的合作宾馆，对每个 i = 8 1 ,., n 我们设 S（ xi， 1） = 2S2i - 1（ co） + 2N 个和 S（ xi， 2） = 2S2i（ m） + 2N。设 x G X，假设使（ x， 3）是在三 T Cwhere T 公司还包含（ X， 1）和（ x ，2）。然后我们设 S（ x， 3） =s（ x， 1） + s（ x， 2）（ 4N）。这个定义的（ x， i）为每个 X G X 和 iG1,2,3。现在，对于每个 x G X 的，设 S（ x， 4） =（ s（ x， 1） +s（ x， 3） / 2s（ x， 5） =（ - S的（ x， 1） + S（ x）， 1） / 2s（ x， 6） =（ d（ x， 2） +s（ x， 3） / 2 和 S（ x， 7） =（ - S（ x， 2） +s（ x， 3）/ 2。现在我们已经定义了一个正整数的大小为每个 Y 戈瑞的（ y）和 D中的每个三是始终总结。 让 BCQ 公司是 坏 的情形，或者因为你们的价值之（ y）的失败是不同的，或一些较 D 组其他三是总结。我们将表明， P（ B）“ 1。它会跟有一个采样点的合作 Q b，和我们能找到这样一个由穷举搜索多项式时间点。这将完成该引理的证明。 为了证明 P（ B）“ 1，它足以让我们假设随机变量的 S1， S2n正是 9 明智的每个独立的均匀分布于 0， 1， N - 1，然后，以证明 P（ B）“ 1 / 2。观察，从 s 的定义（ y）的，为每个 Y 有一个向量 a（ y）的 e - 1， 0， 1， 2 2n个，大小为支持最多 3，使得 s（ y）的，保险业监督（ y）的 ；是一个常数（即不依赖于合作）。 让 y1和 y2是 Y 的不同元素，让 a=a(y1) a(y2)。这是很容易看到， a 是一个非零整数大小为支持最多 6 个载体，并有一个常数 c 使得 s（ y1） =s（ y2）的当且仅当易 =角但是，这最后事件的概率至多为 1 /全因此，概率为你们的价值之（ y）的并不都是最明显的是在 2N6 同样，对于 我们可能会说不需要的三倍。让日 y1， y2 和 y3 的是不同的元素，形成一个不考虑在 D事件的 s（ y1） +s（ y2） =s（ y3）。设 a =a（ y1） +a（ y2）=s（ y3）。然后，一个有规模的支持最多 9，并有一个常数 c 使得 s（ y1） +s（ y2）=s（ y3）当且仅当易 =角我们断言向量 a是非零。然后，它将按照三倍的概率并不一定是在 D总结至多（ ） 3 6 ；，因此 P（ B） 6（ 72i0nfn）“ 1 / 2，根据需要。 它仍然只是建立上述索赔。对于每一个元素 y =（ x i） e ，让 n1（ y） = x和 7i2（ y） = i，记 Yia（ y） i 的由 c（ y）。假设 a = 0 时：我们必须获得矛盾。请注意：第一，如果 7i2（ y） = 3，那么 r（ y） = 4。因此，既不氮气，也不 7i2（ y2）的可以等于 3，因为我们不是让 Yiai“ 4 - ff（ y3） 0。 现在假设氮气（ y2）的 1,2，这是 ff（ y1） = 2。那么 C（ Y2）的必须是1或 2。我们认为这两种情况。 （一） 首先假设的 c（ y2） = 1。然后， cr（ y3） = 3。现在 a（ y1的只有 9 一个非零统筹 2， a（ y2）的有 -1,1,1 和 a（ y3）有 1,1,1。然后的 n1（ y1） = n1（ y2） = n1 （ y2）和特里普尔 T =（ y1 y2 y3） isinD，矛盾。 （二） 现在假设 r（ y2） = 2。然后， r（ y2） = 4。现在 a（ y1有一个 2，（ y2）的有 1个 2 和 a（ y3）有 2,2。同样的三重性 T D，一个矛盾。 现在我们已经表明， n2（ y1）的 e 1,2,3，同样 y2。因此，这两个 n2（ y1）和7i2（ y2）在 4， 5,6,7。因此 ff（ y1）和 cr（ y2）的 are1or3， cr（ y2） is2 或4。 首先假设 ff（ y1） = C（ y2） = 1，所以 C（ y3） = 2。然 后两个 a（ y1）和 a（ y2）的有非零统筹 -1 1 1 和 a（ y3）有 2。但接下来 a（ y1）和 a（ y2）的必须具有相同的支持。接下去的 n1（ y1） = n1（ y2），这是不可能的。不失一般性，我们现在可以假设 ff（ y1） = 1 和“ r（ y2） = 3。然后， r（ y1） = 4，和 a（ y1）的有非零协调 -1,1,1， a（ y1）有 1,1,1，和 a（ y3）有 2， 2。然后，我们再一次工业 a（ y1）和 a（ y2）的必须具有相同的支持，等的 n1（ y1） = n1（ y2） = 1（ y3）。但现在，三 T是在 D，一对矛盾。 10 4 寻找平衡的子集 这是一个 NP 完全测试，如果一个家庭中格 A1 ,., 可持续的竞争整数的POS 机一有一个平衡的一个子集，但我们仍然可能希望为亚群平衡的格局中搜索到最小某些启发式方法。在本节中，我们看到，一个简单的基于动态规划的方法就能解决的伪多项式时间等问题。 红外警戒看到我们如何测试，如果有一个平衡的一个子集，如果这样工业之一（另外两个最小相应的总和）在 O（ 5 iai）的步骤。之后，我们将看到如何找到一个平衡的最小的子集，在 O（ n2J iai）的步骤。这不是 明显的，这些算法将在一个最小化的启发式方法具有更好的模式。 让 s0=5 0 / 2。对于每个 S = 0,1 ,., S0 的，而且每个 j = 0,1 ,., n，设集 f（ s， j）为 T。 如果有一个相应和 S子集，让集 f（ s， j）的平等 F， 否则。则 f（ 0， j）的每个 j = T 为 = 0,1 ,., n，且集 F（ S， 0） =每次的 F = 1 ,., S0 的。我们可以计算所有的值集 f（ 0， j）在反过来，在 O（ 1）每个值的步骤，如下所示。 为 s = 1 ,.,对于 j = 1 . n s0 f（ s， j） f（ s， j - 1） V f（ s - aj， j - 1）。 （如果 s 0，我们解释集 f（ s， j） a s F） 如果在上述复发，这是从来没有的情况是，在右边两个术语是 T，那么就没有平衡的一个子集。但假设这种情况确实存在，而且我们第一次见面是在 s0和j0。那么有两种不同的亚群的相应和 A 和 B（一 j0和一个不包含）。此外 A 和 B必须是不相交的，由 s0的极小。很明显，我们可以发现这样集合 A和 B 很快，他们的联盟是需要平衡的设置。 现在假设我们希望工业一个最小的平衡，如果有一子。我们描述动态规划的需要 O（ n2J iai）的步骤为基础的方法。 和以前一样，让 s0= iai / 2。对于每个 s = 0,1 ,.,s0的，而且每个 J型， K和 K = 0,1 ,., 6 ， 让集 f（ s， j， k）为 T，如果有一个大小最多 K 表的一个子集与对应和 s，让集 f（ s， j， k），否则等于 F。然后再次发生 f（ s， j， k） =f（ s， j - 1， k） V f（ s - flj， j - 1， k - 1） 再加上适当的边界条件，使我们能够确定的所有值在 O集 f（ s， j， k） O（ 1） 每个值的步骤。 11 对于每个 S = 1， s0的是让作为一个子集最小尺寸 1， n的相应和 S 如果有这样的一个子集，让为 as= 0，如果不是 ；，让旅馆是第二小的尺寸一个子集 1 . n s 如果至少有两个这样的子集，让 bs= 0，如果没有。我们已经看到，我们可以计算出所有值集 f（ s， j， k） inO（ n2s0）步骤。从这些值集 f（ s， j， k），我们可以计算出在相同的约束，因为所有的价值和 BS，内容如下。 要计算的，注意，如果 f = 0 的（ s， N组， n） = F 和如果没有则因为是最小的 k，使得集 f（ s， n， k） =T 现在假设 as= 0，考虑如何计算学士学位。 请注意，如果集 f（ s， j， k） = T 接着我们可以找到一个子集 1， j大小至多 k与相应和 S透过回溯复发。我们也可以说，如果有多个这样的子集检查，如果再发生在右侧，如果过了相应的集 f（ s， n， n）（我们知道的是 T）这两个术语吨有一个独特的解决方案，然后 bs= 0。否则， bs是最 K，使得相应的 f（ s， n， k）有一个以上的解决方案。 如果 bs当时的不可能有平衡的一个子集 0。假设现在至少有一个非零值学士学位，并设 T是一个值之比达到最小为 + BS 上旅馆所有的 S = 0。让我们在与Bt是每个 T 和相应的金额，这样独特的套 装 | AT= | 转 Bt =胜。 （我们可以找到这样集快。）以下的索赔将完成我们的证明。 索赔：该套在与 Bt 是不相交的，并在 u =转 Bt CT 是最小的平衡设置 证明索赔 ： 假设在满足不同的集合和 Bt。记的在 Bt 基因的总和美国那么这也是转 Bt和在。但现在金 +不 at+bt= | Ct|。 12 5 结束语 我们已经看到，即使是在削减库存问题非常有限的情况下，它是强 NP -难，尽量减少使用不同模式的数量，因此，我们不能期望能够解决伪多项式时间等问题，即使。关键的概念，是一个平衡的子集，我们被带往亚群平衡的考虑包装启发式，从而考虑寻求这种子集 NP难问题。 13 6 如需进一步阅读 以下参考，也是读者所关心的： 14。 14 致 谢 我非常感谢其他参与 在红外警戒中 讨论 的研究组成员 。 15 参考文献 1 C. Aldridge, J. Chapman, R. Gower, R. Leese, C. McDiarmid, M. Shepherd, H. Tuenter, H. Wilson, A.Zinober, Pattern Reduction in Paper Cutting, Report of the 29th European Study Group with Industry,University of Oxford, March 1996. 2 J.M. Allwood, C.N. Goulimis, Reducing the number of patterns in the 1-dimensional cutting stockproblem, Internal Report of Control Section, Electrical Engineering Department, Imperial College, 1988. 3 N. Alon, O. Goldreich, J. Hastad, R. Peralta, Simple constructions of almost k-wise independent randomvariables, Random Structures and Algorithms 3 (1992) 289-304. 4 V. Chvatal, Linear Programming, Freeman, San Francisco, 1983, pp. 195-212. 5 E.G. Coffman, G.S. Lueker, Probabilistic Analysis of Packing and Partitioning Algorithms, Wiley, New York, 1991. 6 M.R. Garey, D.S. Johnson, Computers and Intractability, Freeman, San Francisco, 1979. 7 P.C. Gilmore, R.E. Gomory, A linear programming approach to the cutting-stock problem, Oper. Res. 9 (1961) 849-859. 8 P.C. Gilmore, R.E. Gomory, A linear pr