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

三坛老窖

aoe1981 发表于 2018-3-15 20:42
　　哈哈，老窖，我终于跑出了1874的结果，虽然时间长一些，但不在乎，我使用的是零件数、综合长度比重震荡 ...

好，很好！你再琢磨下去，我的软件就得给你比下去了。

看你能否找到1873、1503的。

你没有将模式的最大可重复次数参与震荡，当筛选目标为总成本时，对有些数据而言，可能会少一种调整手段。

aoe1981

三坛老窖 发表于 2018-3-16 20:09
好，很好！你再琢磨下去，我的软件就得给你比下去了。

看你能否找到1873、1503的。

　　“比下去”基本是不可能的，您的出发点是应用，我的出发点多少是出于数字游戏，所以我从一开始就没有考虑“成本”，什么不同批次的原材价格不同，模式切换的成本等等……基本上没这个动力……
　　至于“最大可重复次数”，虽然受前面所说论文启发，可以得到了，但效率却低了太多太多。原因是当零件不太小时，由于“重排零件数组”这个子程序调用次数增加（因为一种规格零件选一次后不能再选下次，故而删除），远远大于零件选择提速的效果，效率更是差得令人难以忍受，故而早都放弃了。如果要再钻一钻的话，估计得用新的技巧重写了，也未可知。现在实在没多大冲动了……
　　这一次也是偶尔的测试成功，我前前后后都做了20个小版本了，失败累积出来的吧。现在的状况也只是可以得到更进一步的结果了，而不是像之前漫长的时间里只停留于1876、799、59而毫无进展。这点是欣慰的……但距离“达到”您的水平还是很远很远，上面1874至少跑了1000多秒，1875倒是易得一些……
　　这次真是可以丢开一段时间了……在没有新的思想时，反复瞎撞、测试对比真是低级又无聊，做着做着好像只是为了安慰自己。呵呵……

aoe1981

三坛老窖 发表于 2018-3-16 20:09
好，很好！你再琢磨下去，我的软件就得给你比下去了。

看你能否找到1873、1503的。

目前我所做的忽然出现了一个奇怪的现象：就是如果追求更优解的话，更加依赖于贪婪次数的提高。如果50种零件规格的话，对比优化一个下料组合的次数设置到200次时，1、2百方案就可以出1875、1505这样的结果……多次测试总感觉更依赖贪婪次数的提高了，这也导致效率惨不忍睹。
　　那组200规格的超大数据，我设置贪婪次数1000，生成一个方案用时17秒，就可以达到99.99％，跑多了没敢等，1个方案的话连震荡机会都不给。我感觉在小规模数据时，与您的差距不是太大，但大规模数据时差距简直是呈平方扩大……尤其我对模式数的收敛控制并不好，因为我在一开始是忽略这个目标的，直到粗粗地读了许多免费的早期论文时才注意到，但也没在意。因为我只是在做数字游戏，不期实用的。

　　使事情发生转机的正是一组小规模数据：

1664	32		6000
1599	96		最优解194
1552	160		193已突破
1409	16
1352	384
802	112
660	64

　　我早都追帖193－7模式的结果了，但忽然在我后来一个得意版本中再测试时，居然连193都出不来，才引起我对参数震荡范围的调整，要不我会沉浸在那个1876、799、58－10的“得意版本”中的。
　　这组193的数据也不可小觑，用您的软件的默认参数时也跑不出来，只有把m吧调大就出来了……这是大概的契机。
　　刚刚用您的默认参数测试时，又嗖嗖地出来了……奇怪……

　　　　下图就是一个例证：高贪婪值、低方案数：
　　

　　
　　我感觉您的软件不会有如此高的贪婪值，速度快，但是有时生成1个方案结果也是很优秀的。佩服！！！

三坛老窖

aoe1981 发表于 2018-3-16 20:53
目前我所做的忽然出现了一个奇怪的现象：就是如果追求更优解的话，更加依赖于贪婪次数的提高。如果50种零 ...

你的贪婪次数，即我的最佳模式设定值，在我的程序中，这个值是这样使用的：
当前生成的模式指标优于之前的最优值时，计数器清零，否则计数器+1，其思想是连续生成n个（设定值）模式，找不到更优的了，则承认该模式为最佳。
还有就是当前的模式指标，与已经加入方案的前一个最佳模式的指标作比较，如果指标值优于前一个最佳模式，则直接接受当前的模式为最佳模式。
这就是一些提速的小技巧，你可试试。

aoe1981

三坛老窖 发表于 2018-3-17 15:05
你的贪婪次数，即我的最佳模式设定值，在我的程序中，这个值是这样使用的：
当前生成的模式指标优于之前 ...

　　老窖，我用了您的技巧，提速是有的，但解的质量在我的程序中有所下降，如果提高连续探测步长值，则质量上了，效率又反不如初。盖因我的程序总体思路总是依赖于高贪婪次数的缘故吧，竟如邯郸学步。以后再试。

　　您有功夫了试试以下两组数据：
　　1.来源于香川：
　　http://club.excelhome.net/forum. ... 256&pid=8508651

序号	零件长度	需求量/个
1	1250mm	1
2	1240mm	1
3	1127mm	1
4	1117mm	1
5	1107mm	1
6	1100mm	13
7	1097mm	1
8	1090mm	13
9	1077mm	1
10	1067mm	1
11	1057mm	5
12	1050mm	10
13	1047mm	14
14	1040mm	10
15	1037mm	11
16	1000mm	2
17	990mm	2
18	817mm	2
19	807mm	6
20	797mm	5
21	787mm	2

序号	原料长度	库存量/根
1	6400mm	20
2	6000mm	20
3	5500mm	20
4	5000mm	20

切口宽度

0mm

　　香川大侠在这组数据上独步古今啊：105900－8模式
　　我用您的跑了40000方案得到105900－9模式，使用默认参数，时间较之香川自然不占优。但您的软件在应对各类数据时，适应性、效率、解的质量综合起来都是最优的，我给您打99分，留1分激励您持续进步。
　　我的则差得远，最佳106000。
　　其实这组数据和我之前发的一组数据类型一样，您通过调整原材不同的库存量，也可以逼近更优解，不算新鲜。

　　2.我改造的数据：

6900	3
8900	5
6350	15
6000	9
3000	13
1000	8
2650	7
5500	5
6500	2
3500	3

1000	12	1000
6000	10	6000
9000	10	9000
12000	16	12000

　　切口0
　　这组数据您见过，当时搭配不完，现在可以了。
　　期待您调试出来的结果。

三坛老窖

源自香侠的这组数据，用我改进后的代码，可以获取105900-8的方案：

三坛老窖

你改造的这组数据，用原来的代码，获取的结果如下：

三坛老窖

aoe1981 发表于 2018-3-18 11:23
　　老窖，我用了您的技巧，提速是有的，但解的质量在我的程序中有所下降，如果提高连续探测步长值，则质 ...

如果100分是点击一下秒出绝对最优方案，则给我的软件打99分，显然是高了许多。

你给出的这两组数据，让我发现了这个算法目前存在的一个不好解决的问题：
香侠的这组数据，如果用改进前的代码，即按棒料可用量随机选取下一支用于下料的棒料，则得不到105900-8的最优方案，而你改造的这组数据，如果用我改进后的代码，即从可用棒料中选取最合适的那支棒料用于下料，则会发生可用棒料不够的情况。

目前能想到的，只有在参数【投料规则】中增加一个选项，让用户来选择了。
像那个T参数一样，这个参数的设定，也缺乏依据，只能试着看，这无疑是一个缺陷。

aoe1981

三坛老窖 发表于 2018-3-18 15:36
如果100分是点击一下秒出绝对最优方案，则给我的软件打99分，显然是高了许多。

你给出的这两组数据， ...

我没记错的话，我改造的那组数据，您把您改造前的代码的参数m,p调大到20试试，效果就好了……

三坛老窖

aoe1981 发表于 2018-3-18 17:58
我没记错的话，我改造的那组数据，您把您改造前的代码的参数m,p调大到20试试，效果就好了……

m、p调到20，得到的最优方案是34200-11，利用率从之前的94.57%提高的96.78 %，从指标上看是比之前的要好，但看用料情况，1000的原料没有用上，实际上应该不如之前的方案好。