一维嵌套算法

将一维长度嵌套到预定义库存长度的有效算法是什么?

• 5 x 2米
• 5 x 4米

这些可以从10米长的钢筋上切割下来。

此外,如何将多个库存长度合并到算法中?

---

我有一点时间来研究这个问题,所以我要写下我是如何解决它的。我希望这对某人有用。我不确定这样回答我自己的问题是否合适。如果更合适,主持人可以将此更改为答案。

the cutting stock problem

"Calculating a cutting list with the least amount of off cut waste" .

好的,继续解决问题。

• 原料:将被切成小块的一段材料
• 切割:从库存中切割的材料长度。可从同一块坯料上进行多次切割
• 废料:所有切割完成后留在一块料中的材料长度。

解决这个问题主要有三个阶段,

1. 确定所有可能的切割组合

第一步

对于N个切割,有2^N-1个独特的切割组合。这些组合可以表示为二进制真值表。

其中A、B、C是唯一切割;

A B C | Combination
-------------------
0 0 0 | None
0 0 1 | C
0 1 0 | B
0 1 1 | BC
1 0 0 | A
1 0 1 | AC
1 1 0 | AB
1 1 1 | ABC

带有一些位运算符的for循环可用于快速创建每个切割组合的分组。

对于较大的N值,这可能会非常耗时。

A B B | Combination
-------------------
0 0 0 | None
0 0 1 | B
0 1 0 | B (same as previous)
0 1 1 | BB
1 0 0 | A
1 0 1 | AB
1 1 0 | AB (same as previous)
1 1 1 | ABB

我能够利用这种冗余来减少计算组合的时间。我将重复的切割组合在一起,并计算出该组的唯一组合。然后,我将此组合列表附加到第二个组中的每个唯一组合,以创建一个新组。

A A | Combination
-------------------
0 1 | A 
1 1 | AA

把这个组叫做X。

将X附加到B的唯一实例,

B B X | Combination
-------------------
0 0 1 | A 
      | AA
0 1 0 | B
0 1 1 | BA
      | BAA
1 1 0 | BB 
1 1 1 | BBA
      | BBAA

把这群人叫做Y。

将Y附加到C的唯一实例,

C Y | Combination
-----------------
0 1 | A 
    | AA
    | B
    | BA
    | BAA
    | BB 
    | BBA
    | BBAA 
1 0 | C
1 1 | CA 
    | CAA
    | CB
    | CBA
    | CBAA
    | CBB 
    | CBBA
    | CBBAA 

此示例生成17个唯一组合,而不是31个(2^5-1)。节省了将近一半的钱。

一旦确定了所有组合,就应该检查其是否适合库存。

步骤2

该步骤的目的是将步骤1中确定的切割组合映射到可用的库存尺寸。

这是一个相对简单的过程。 对于每个切割组合,

   calculate the sum of all cut lengths.
   for each item of stock, 
        if the sum of cuts is less than stock length,
            store  stock, cut combination and waste in a data structure.
            Add this structure to a list of some sort.

这将生成有效嵌套切割组合的列表。

步骤3

在一个理想的世界里,我们会计算所有的可能性并选择最好的一个。对于任何一组非平凡的切割,计算它们都需要花费很长时间。我们只需要满足于非最优解。

我选择了一种方法来寻找一个浪费最少的巢穴。它将重复这一过程,直到所有的削减都被考虑在内。

• nestList:步骤2中生成的嵌套列表。这是从最低的废物分类到最高的废物。

pick nest from nestList with the least waste
  if EVERY cut in the nest is contained in cutList
     remove cuts from cutList
     copy this nest into the finalList
  if some cuts in nest not in cutList
      remove this nest from nestList             
repeat until cutlist is empty

使用这种方法,我成功地获得了一些典型测试数据约2-4%的总浪费。希望我能在某个时候重新考虑这个问题,并尝试实现 Delayed column generation 算法。这将产生更好的结果。

大卫