一维下料（线材排样）软件

aoe1981

一把小刀闯天下 发表于 2018-3-29 20:28
122楼的数据，使用随机数瞎掰了一个，每次结果好像都是157，用时5min左右，参与一下而已。

一把宝刀震天下！！！

aoe1981

三坛老窖 发表于 2018-3-29 23:19
首先表示祝贺！我给出的几组测试数据，单从用料根数来说，都已经被你追平了。
其次表示敬佩！测试一组数 ...

　　“真心希望你能找到解决一维下料问题的、比我这个更好的方法，进而获得1503、1873的方案。”

　　我是个半路出家的人，真心没有能力做此奢望，倒是可以肯定的是，这个问题要歇一歇了……

　　看砸锁者，更证实这世界高人太多……鄙愚仰视啊

　　老窖此款软件从本论坛来看，无疑将是一维下料问题的终结帖，至少我这样认为。

wangvvei

虽然我没用到过三坛老窖的软件，但是如果真的有他所说的那样效率的话，那真是厉害了。

aman1516

三坛老窖 发表于 2018-3-20 16:04
可能那一刻是吉时，第一次默认参数，获得155-24的方案，第二次调整了M、P参数，获得155-23，第三次再调整 ...

程序的包装部分有时的确比核心部分还麻烦，这类应用有个最实用的功能希望能完善下：下料尺寸及数量未必是汇总好的数据，而是多个订单共用同一原材 料的下料数据明细，如多加一列，对应每个尺寸数量是属于哪个订单号，那么问题来了，能否优化开料后，什对每个"工单"的“模式号”，自动生成每根尺寸材料属于那个订单号的列表清单吗？
详见附件： Sch_64_76-39-151.rar (1.03 MB, 下载次数: 53)

2018-5-5 00:05 上传

点击文件名下载附件

QD72

高手，我这里有个下料问题看你的软件能实现吗？  原材料长度市场可以采购到6米7米8米9米10米11米12米，零件长度为0.01米到12米中的任意长度（具体到工程确定长度和数量），长短搭配出料。限制条件：一根原材料（6米或7米或8米或9米或10米或11米或12米）最多出四种零件，数量不限制。根据零件搭配选择原材料长度进行购买。

xsteelnet

我要购买  微信：15000004823

香川群子

aoe1981 发表于 2018-3-20 15:19
　　终于跑出了一个155－29：
　　

我跑出了更好的结果:155根-21方案，耗时48.49秒

项目	方案	剩余	方案: 33规格 / 714根  (理想最少 = 152)
21	155	1817256	明细: 数量*规格 =  1860000(97.702%)
4	12	12000	1*2583+1*2559+1*2394+2*2232
4	12	12000	2*2600+1*2307+1*2261+1*2232
4	12	12000	2*2559+1*2311+1*2294+1*2277
4	12	12000	1*3114+1*3091+1*3048+1*2747
5	12	12000	1*2559+1*2485+1*2347+1*2336+1*2273
5	6	12000	1*2639+1*2559+1*2294+1*2277+1*2231
4	3	11997	1*2639+1*2600+1*2294+2*2232
4	15	11996	2*2559+1*2307+1*2294+1*2277
4	12	11991	1*2626+1*2438+2*2316+1*2295
4	9	11991	1*2600+1*2474+2*2320+1*2277
3	6	11981	1*3126+2*2970+1*2915
2	2	11978	3*3126+1*2600
2	1	11869	2*2474+3*2307
1	9	11660	4*2915
1	3	11528	4*2882
1	3	11308	4*2827
1	3	11192	4*2798
1	3	10660	4*2665
1	18	10556	4*2639
2	1	10517	3*2639+1*2600
2	1	10274	3*2600+1*2474

aoe1981

香川群子 发表于 2018-8-17 15:35
我跑出了更好的结果:155根-21方案，耗时48.49秒

也是随机算法吗?不过，您一般较少用随机算法的……

香川群子

aoe1981 发表于 2018-8-18 08:24
也是随机算法吗?不过，您一般较少用随机算法的……

我的算法，还是贪婪算法。
即，以余量最小、重复次数最多的组合作为优先组合解。


不过，之前对随机次数的控制是错误的，随机乱序次数越多，结果反而更差了。
（乱序程度较大时、较难得到贪婪的最优解）

所以，这次对随机次数做了限制，即，在一个组合方案中，并没必要做很多的随机测试。
但是，我增加了对精度误差（余量在一定范围内，视作同等优秀）的有效控制，
这样，在较多的随机测试以后，就容易得到较为平衡的组合解。
请注意，这里的随机次数，是从头开始的随机组合计算，并不是一个组合解中的随机次数。

总之，大致算法没变。

思路是：
一、找到一组解
1. 按照从大到小的顺序凑出余量小于最小需求规格的一个组合；
2. 用字典记录这个组合，并记录其余量r和该组合可重复次数t；
3. 遍历所有剩余需求规格，得到很多组合，更新最小余量r和可重复次数t
4. 随机乱序1-5次，然后重复1-3步骤，得到最小余量r和可重复次数t最大的最优组合
这样就得到了第一组最优解，记录着组解，并按最大可重复次数核减需求规格和数量
二、以剩余需求规格和数量，重复步骤一，直到所有需求都被组合完成。
这样就得到了一个包含很多组合的解决方案，记录这个方案的组合项目数、原料根数、原料规格*根数的总量


三、自动调整最小余量的分级档位，重复上述步骤，得到很多种不同的方案，
记录最优的方案，即原料利用率最高（需求规格*数量/原料规格*根数的百分比）
此时一般说原料总根数也最少。（多规格时，根数可能就不是最少）
且方案的项目总数最少。


四、在上述基础上，继续从头开始计算（相当于自动多次按下按钮）
以便在多次计算后得到最优解。

哈哈。
这样的算法，一般说可以得到原料利用率较高，且切割项目总数（组合数）较少的方案，
但是，如有特殊情况下，项目数稍多，但原料利用率更高的组合，就较难计算出来，或者根本就不可能算出来啦。

三坛老窖

香川群子 发表于 2018-8-18 19:22
我的算法，还是贪婪算法。
即，以余量最小、重复次数最多的组合作为优先组合解。

你的这个算法思路，总体上来说，与我的算法思路是一样的。就是通过随机，求取一个较好的下料组合（即下料模式），按该组合的最大可重复次数扣除需求量，继续求取下一个下料组合，直到所有需求都等于0。
按这个思路求解整体下料方案，我觉得你的这个最小余量的分级档位，似乎没有意义，不知你是基于什么考虑，需要用到它？在具体的过程中又是如何定义（计算）它的呢？