一、概念
下料:有若幹規格的原材料,要切割成一批若幹規格的零件,确定一種切割方式,使得原材料用料最少、産生的廢料最少。
一維下料:上面提到的規格,可以包含很多屬性,比如:長度、寬度、厚度等等。所謂一維下料,隻關注其中一種屬性,而其它屬性被認為全部相同,這樣便大大降低了下料問題的處理難度。本文研究的一維下料,以長度作為優化目标。
二、術語定義
原料:用于切割的原材料,長度不定。
零件:從原料中切割下來的短料。
廢料:一根原料被使用後,剩餘長度無法再用于生産任意零件。一般定義為門檻值。
餘料:一個原料被使用後,剩餘材料仍然可以在後續生産中進行零件切割。
三、問題描述
現有N段長度不等的原料(當然,也可以全部長度相等或者其中一部分長度相等),現需要切割為M段長度不等的零件,生成一種切割方案,使産生的廢料最少(門檻值)、若必須要産生餘料應使餘料大于指定長度(門檻值)以便餘料再利用。
四、解決方案
1)窮舉法
當原料和零件數量很小時,窮舉法可以對所有切割方案進行窮舉周遊,尋找最優解。但是如果原料和零件數量達到一定量後,窮舉法時間複雜度成指數級增長,計算機無法算出結果。這裡給一些定量的概念,比如從零件的角度窮舉,M=20時,窮舉數量級為1,048,576,M=30時,窮舉數量級為1,073,741,824。即時間複雜度為O(2^M),隐藏零件數量到達20以上時,就變成了無法完成的任務。
2)遺傳算法
百度搜尋“一維下料 遺傳算法”,會得到非常多的相關論文搜尋結果。遺傳算法以進化論為依據,當種群進化若幹代後,便會得到一個相對精英的種群。将一維下料問題轉化為遺傳算法模型如下:
a)染色體:a1,a2,a3......am,表示第m個零件在第am根原料上截取;
b)種群初始化:初始化x個可行染色體種群
c)交叉算子:按交叉機率,對染色體進行兩兩交叉,注意不要交叉出無效染色體
d)變異算子:按變異機率,對染色體中的基因進行剔除并變異,注意不要變異出無效染色體
e)選擇算子:采用錦标賽算法或輪盤賭算法,對優秀染色體進行選擇
f)适應度函數:根據優化目标設計适應度函數,一般從使用率、廢料率角度設計
遺傳算法能對下料方案有一定程度的優化,但是優化不明顯,或許是哪個算子設計不合理、或者參數沒有調到合适的值。(注:相關的論文中,結果資料非常優秀,但本人無法調出那麼優秀的方案,是以對有些論文報懷疑态度)。
3)動态規劃
一維下料的核心,其實可以對接背包問題,而動态規劃實際上是一種解背包問題的其中一種算法。看了幾個論文資料,算法沒看太懂,暫沒時間做實驗,不做評價。
4)自研算法
涉及到商業上的問題,不便多說,但整體思路是模拟人工的操作。一般一個勞工,拿到一組原料和一組零件規格後,隻要給足夠的時間,總能設計出一些比較優秀的方案,而此算法正是模拟這個過程。
五、總結
算法的東西,需要深入研究,但是不能一味的陷進去,有時候換個思路,可能得到意想不到的效果。大道至簡才是精髓。
最後,放上一個測試連結,有興趣的歡迎交流:http://106.53.17.139:8088/demo/
下面貼一組資料:
方案1:
餘 0,排樣規則:2234=2234
餘 37,排樣規則:2676=2639
餘 12,排樣規則:2777=2765
餘 38,排樣規則:2964=2926
餘 1,排樣規則:3062=1518+1543
餘 16,排樣規則:3134=3118
餘 2,排樣規則:3472=3470
餘 8,排樣規則:3513=3505
餘 7,排樣規則:3574=1690+1877
餘 14,排樣規則:3577=1947+1616
餘 8,排樣規則:3972=1747+2217
餘 8,排樣規則:3996=3988
餘 3,排樣規則:4064=2028+2033
餘 3,排樣規則:4212=2567+1642
餘 0,排樣規則:4496=2759+1737
餘 2,排樣規則:4541=2183+2356
餘 0,排樣規則:4550=2632+1918
餘 0,排樣規則:4765=2918+1847
餘 1,排樣規則:4850=4849
餘 6,排樣規則:4902=2714+2182
餘 5,排樣規則:5869=3076+2788
餘 3,排樣規則:5972=3654+2315
餘 1,排樣規則:6135=3249+2885
餘 0,排樣規則:6209=3794+2415
餘 0,排樣規則:7807=3170+2390+2247
餘 2,排樣規則:8567=4698+3867
餘 1,排樣規則:8904=5174+3729
餘 1,排樣規則:9975=2390+2552+2751+2281
餘 0,排樣規則:10729=3757+3195+3777
餘 1,排樣規則:11176=4688+4019+2468
餘 0,排樣規則:11338=5213+3756+2369
餘 2,排樣規則:11561=3520+4546+3493
餘 0,排樣規則:11571=2290+4000+5281
餘 2,排樣規則:12140=3862+4399+2084+1793
餘 0,排樣規則:12613=5157+5391+2065
餘 1,排樣規則:13086=4737+5052+3296
餘 0,排樣規則:13423=4653+4372+4398
餘 2,排樣規則:13461=4713+4271+4475
餘 2,排樣規則:14717=3222+4870+4678+1945
餘 0,排樣規則:14836=4096+5550+5190
餘 0,排樣規則:15015=5023+2527+5312+2153
餘 0,排樣規則:15155=3852+5336+3706+2261
餘 0,排樣規則:15196=5079+2919+4830+2368
餘 0,排樣規則:15330=4031+2751+5726+2822
餘 1,排樣規則:15440=3417+5634+3687+2701
餘 1,排樣規則:15480=2890+4757+5090+2742
餘 0,排樣規則:15688=4129+4214+3227+4118
餘 1,排樣規則:15733=3609+5587+3739+2797
餘 1,排樣規則:15825=4925+5485+5414
餘 0,排樣規則:16118=5373+5581+5164
餘 2,排樣規則:16525=3363+4639+5489+3032
餘 1,排樣規則:16676=5686+5425+5564
餘 2,排樣規則:16719=5783+3481+4413+3040
餘 7,排樣規則:16736=3907+5722+3463+3637
餘 3,排樣規則:16764=5686+5473+5602
餘 3854,排樣規則:16793=4223+4454+4262
餘 3506,排樣規則:20185=5451+5705+5523
方案2:
餘 0,排樣規則:2234=2234
餘 37,排樣規則:2676=2639
餘 12,排樣規則:2777=2765
餘 38,排樣規則:2964=2926
餘 1,排樣規則:3062=1543+1518
餘 16,排樣規則:3134=3118
餘 2,排樣規則:3472=3470
餘 8,排樣規則:3513=3505
餘 7,排樣規則:3574=1877+1690
餘 14,排樣規則:3577=1947+1616
餘 8,排樣規則:3972=2217+1747
餘 8,排樣規則:3996=3988
餘 3,排樣規則:4064=2033+2028
餘 3,排樣規則:4212=2567+1642
餘 0,排樣規則:4496=2759+1737
餘 2,排樣規則:4541=2356+2183
餘 0,排樣規則:4550=2632+1918
餘 0,排樣規則:4765=1847+2918
餘 1,排樣規則:4850=4849
餘 7,排樣規則:4902=2742+2153
餘 0,排樣規則:5869=3687+2182
餘 0,排樣規則:5972=3907+2065
餘 1,排樣規則:6135=3249+2885
餘 0,排樣規則:6209=3794+2415
餘 0,排樣規則:7807=2822+3040+1945
餘 2,排樣規則:8567=5489+3076
餘 1,排樣規則:8904=2701+4118+2084
餘 0,排樣規則:9975=3296+4398+2281
餘 1,排樣規則:10729=5164+5564
餘 0,排樣規則:11176=3739+5190+2247
餘 3,排樣規則:11338=5312+2369+3654
餘 0,排樣規則:11561=3757+5336+2468
餘 0,排樣規則:11571=5550+2315+3706
餘 0,排樣規則:12140=4096+5783+2261
餘 1,排樣規則:12613=2890+5722+4000
餘 1,排樣規則:13086=3170+3195+3493+3227
餘 0,排樣規則:13423=4546+3862+1793+3222
餘 2,排樣規則:13461=2390+3756+5023+2290
餘 0,排樣規則:14717=4757+4475+5485
餘 0,排樣規則:14836=5686+5373+3777
餘 1,排樣規則:15015=4372+5523+2368+2751
餘 1,排樣規則:15155=4870+3481+4413+2390
餘 0,排樣規則:15196=5414+2527+4223+3032
餘 0,排樣規則:15330=5634+5425+4271
餘 0,排樣規則:15440=3609+3867+5213+2751
餘 1,排樣規則:15480=4688+2788+5451+2552
餘 0,排樣規則:15688=4214+3520+5157+2797
餘 3,排樣規則:15733=5726+4830+5174
餘 0,排樣規則:15825=3463+4262+4737+3363
餘 2,排樣規則:16118=2714+4713+5052+3637
餘 9,排樣規則:16525=3729+4019+4639+4129
餘 1,排樣規則:16676=5686+3417+4653+2919
餘 36,排樣規則:16719=5587+5705+5391
餘 0,排樣規則:16736=4399+3852+4454+4031
餘 3565,排樣規則:17866=4678+4698+4925
餘 3508,排樣規則:18958=5281+5090+5079
餘 3529,排樣規則:20185=5473+5602+5581
方案3:
餘 0,排樣規則:2234=2234
餘 37,排樣規則:2676=2639
餘 12,排樣規則:2777=2765
餘 38,排樣規則:2964=2926
餘 1,排樣規則:3062=1543+1518
餘 16,排樣規則:3134=3118
餘 2,排樣規則:3472=3470
餘 8,排樣規則:3513=3505
餘 7,排樣規則:3574=1690+1877
餘 14,排樣規則:3577=1947+1616
餘 8,排樣規則:3972=2217+1747
餘 8,排樣規則:3996=3988
餘 3,排樣規則:4064=2028+2033
餘 3,排樣規則:4212=2567+1642
餘 0,排樣規則:4496=2759+1737
餘 2,排樣規則:4541=2183+2356
餘 0,排樣規則:4550=2632+1918
餘 0,排樣規則:4765=2918+1847
餘 1,排樣規則:4850=4849
餘 6,排樣規則:4902=2714+2182
餘 5,排樣規則:5869=3076+2788
餘 0,排樣規則:5972=3907+2065
餘 2,排樣規則:6135=2281+3852
餘 0,排樣規則:6209=3794+2415
餘 1,排樣規則:7807=5722+2084
餘 3,排樣規則:8567=4372+2247+1945
餘 2,排樣規則:8904=4688+4214
餘 0,排樣規則:9975=5336+4639
餘 0,排樣規則:10729=5473+3463+1793
餘 0,排樣規則:11176=3654+2390+2390+2742
餘 0,排樣規則:11338=2797+2751+3637+2153
餘 1,排樣規則:11561=4653+3040+3867
餘 0,排樣規則:11571=4413+3296+3862
餘 0,排樣規則:12140=4096+5783+2261
餘 0,排樣規則:12613=2701+4129+3493+2290
餘 0,排樣規則:13086=5581+5190+2315
餘 0,排樣規則:13423=5425+2919+5079
餘 0,排樣規則:13461=4925+4830+3706
餘 0,排樣規則:14717=2527+5164+3417+3609
餘 0,排樣規則:14836=5414+4031+5391
餘 0,排樣規則:15015=4000+3777+4870+2368
餘 0,排樣規則:15155=2890+5634+4262+2369
餘 0,排樣規則:15196=5489+3729+3227+2751
餘 0,排樣規則:15330=5686+5373+4271
餘 0,排樣規則:15440=5213+3249+3756+3222
餘 2,排樣規則:15480=5281+5174+5023
餘 3,排樣規則:15688=3363+3757+4019+4546
餘 0,排樣規則:15733=5485+4698+5550
餘 1,排樣規則:15825=2552+3195+4223+3032+2822
餘 1,排樣規則:16118=5564+2468+4398+3687
餘 0,排樣規則:16525=3520+5157+4678+3170
餘 3,排樣規則:16676=3739+5312+4737+2885
餘 7,排樣規則:16719=5523+5602+5587
餘 25,排樣規則:16736=3481+4713+4399+4118
餘 32,排樣規則:16914=5705+5451+5726
餘 3549,排樣規則:17235=4454+4475+4757
餘 3664,排樣規則:19492=5052+5090+5686
方案4:
餘 0,排樣規則:2234=2234
餘 37,排樣規則:2676=2639
餘 12,排樣規則:2777=2765
餘 38,排樣規則:2964=2926
餘 1,排樣規則:3062=1518+1543
餘 16,排樣規則:3134=3118
餘 2,排樣規則:3472=3470
餘 8,排樣規則:3513=3505
餘 7,排樣規則:3574=1877+1690
餘 14,排樣規則:3577=1947+1616
餘 8,排樣規則:3972=2217+1747
餘 8,排樣規則:3996=3988
餘 3,排樣規則:4064=2033+2028
餘 3,排樣規則:4212=2567+1642
餘 0,排樣規則:4496=2759+1737
餘 2,排樣規則:4541=2183+2356
餘 0,排樣規則:4550=2632+1918
餘 0,排樣規則:4765=2918+1847
餘 1,排樣規則:4850=4849
餘 7,排樣規則:4902=2742+2153
餘 7,排樣規則:5869=3493+2369
餘 0,排樣規則:5972=3907+2065
餘 1,排樣規則:6135=3249+2885
餘 2,排樣規則:6209=4262+1945
餘 1,排樣規則:7807=5722+2084
餘 0,排樣規則:8567=2714+3463+2390
餘 0,排樣規則:8904=4830+2281+1793
餘 1,排樣規則:9975=5079+2527+2368
餘 1,排樣規則:10729=3032+5281+2415
餘 0,排樣規則:11176=4475+4454+2247
餘 0,排樣規則:11338=4678+4399+2261
餘 0,排樣規則:11561=4223+4870+2468
餘 0,排樣規則:11571=3867+5414+2290
餘 0,排樣規則:12140=4096+2822+2182+3040
餘 0,排樣規則:12613=4688+5373+2552
餘 0,排樣規則:13086=5190+5581+2315
餘 2,排樣規則:13423=4757+4546+4118
餘 0,排樣規則:13461=5023+2890+2797+2751
餘 0,排樣規則:14717=4653+3520+3756+2788
餘 0,排樣規則:14836=3363+3170+5602+2701
餘 0,排樣規則:15015=3739+3729+5157+2390
餘 0,排樣規則:15155=3227+5523+3654+2751
餘 1,排樣規則:15196=4019+4129+3852+3195
餘 2,排樣規則:15330=5052+3417+3637+3222
餘 0,排樣規則:15440=5312+4737+5391
餘 1,排樣規則:15480=5634+4372+5473
餘 0,排樣規則:15688=4639+3706+3481+3862
餘 0,排樣規則:15733=2919+4031+5174+3609
餘 1,排樣規則:15825=4925+5213+5686
餘 5,排樣規則:16118=3296+3687+5336+3794
餘 4,排樣規則:16525=5705+5090+5726
餘 0,排樣規則:16676=5425+3076+4398+3777
餘 0,排樣規則:16719=5783+5485+5451
餘 10,排樣規則:16736=4698+3757+4271+4000
餘 2,排樣規則:16764=5489+5686+5587
餘 3574,排樣規則:16914=4413+4214+4713
餘 3513,排樣規則:19791=5550+5564+5164
方案5:
餘 0,排樣規則:2234=2234
餘 37,排樣規則:2676=2639
餘 12,排樣規則:2777=2765
餘 38,排樣規則:2964=2926
餘 1,排樣規則:3062=1518+1543
餘 16,排樣規則:3134=3118
餘 2,排樣規則:3472=3470
餘 8,排樣規則:3513=3505
餘 7,排樣規則:3574=1877+1690
餘 14,排樣規則:3577=1947+1616
餘 8,排樣規則:3972=2217+1747
餘 8,排樣規則:3996=3988
餘 3,排樣規則:4064=2033+2028
餘 3,排樣規則:4212=2567+1642
餘 0,排樣規則:4496=2759+1737
餘 4,排樣規則:4541=2290+2247
餘 0,排樣規則:4550=2632+1918
餘 0,排樣規則:4765=1847+2918
餘 1,排樣規則:4850=4849
餘 5,排樣規則:4902=2714+2183
餘 7,排樣規則:5869=3493+2369
餘 0,排樣規則:5972=3907+2065
餘 1,排樣規則:6135=3249+2885
餘 0,排樣規則:6209=2415+3794
餘 0,排樣規則:7807=5451+2356
餘 3,排樣規則:8567=3729+2751+2084
餘 0,排樣規則:8904=4000+2751+2153
餘 1,排樣規則:9975=4372+5602
餘 0,排樣規則:10729=4223+4713+1793
餘 0,排樣規則:11176=3687+5174+2315
餘 0,排樣規則:11338=3227+5079+3032
餘 1,排樣規則:11561=2919+2182+2822+3637
餘 0,排樣規則:11571=2261+2281+4639+2390
餘 0,排樣規則:12140=5373+4399+2368
餘 2,排樣規則:12613=3481+3739+5391
餘 1,排樣規則:13086=4262+3076+2552+3195
餘 2,排樣規則:13423=4737+4031+4653
餘 0,排樣規則:13461=4925+4830+3706
餘 0,排樣規則:14717=3862+5686+2468+2701
餘 0,排樣規則:14836=3363+3756+5190+2527
餘 0,排樣規則:15015=5634+4019+3417+1945
餘 0,排樣規則:15155=4698+3654+4413+2390
餘 0,排樣規則:15196=3463+5425+3520+2788
餘 0,排樣規則:15330=4678+3040+4870+2742
餘 0,排樣規則:15440=5023+4398+3222+2797
餘 4,排樣規則:15480=3852+2890+5564+3170
餘 6,排樣規則:15688=4454+5705+5523
餘 0,排樣規則:15733=4096+4271+3609+3757
餘 1,排樣規則:15825=5722+5414+4688
餘 0,排樣規則:16118=5485+5581+5052
餘 6,排樣規則:16525=3867+3777+4757+4118
餘 3,排樣規則:16676=5164+5726+5783
餘 10,排樣規則:16719=5550+5473+5686
餘 7,排樣規則:16736=4214+3296+5090+4129
餘 3537,排樣規則:17715=5157+4475+4546
餘 3509,排樣規則:19492=5281+5213+5489
餘 3533,排樣規則:19768=5336+5312+5587
方案6:
餘 0,排樣規則:2234=2234
餘 37,排樣規則:2676=2639
餘 12,排樣規則:2777=2765
餘 38,排樣規則:2964=2926
餘 1,排樣規則:3062=1518+1543
餘 16,排樣規則:3134=3118
餘 2,排樣規則:3472=3470
餘 8,排樣規則:3513=3505
餘 7,排樣規則:3574=1877+1690
餘 14,排樣規則:3577=1947+1616
餘 8,排樣規則:3972=2217+1747
餘 8,排樣規則:3996=3988
餘 3,排樣規則:4064=2033+2028
餘 3,排樣規則:4212=2567+1642
餘 0,排樣規則:4496=2759+1737
餘 2,排樣規則:4541=2183+2356
餘 0,排樣規則:4550=2632+1918
餘 0,排樣規則:4765=2918+1847
餘 1,排樣規則:4850=4849
餘 6,排樣規則:4902=2369+2527
餘 0,排樣規則:5869=3687+2182
餘 0,排樣規則:5972=3907+2065
餘 1,排樣規則:6135=3249+2885
餘 0,排樣規則:6209=3794+2415
餘 1,排樣規則:7807=5722+2084
餘 0,排樣規則:8567=3227+2552+2788
餘 1,排樣規則:8904=5174+3729
餘 1,排樣規則:9975=3417+3481+3076
餘 0,排樣規則:10729=4688+4096+1945
餘 0,排樣規則:11176=2797+5157+3222
餘 0,排樣規則:11338=5485+2390+3463
餘 1,排樣規則:11561=4118+5052+2390
餘 0,排樣規則:11571=2290+4737+2751+1793
餘 0,排樣規則:12140=3852+5587+2701
餘 0,排樣規則:12613=5391+2822+2247+2153
餘 0,排樣規則:13086=4454+3609+5023
餘 0,排樣規則:13423=3637+5373+4413
餘 0,排樣規則:13461=5213+3706+2281+2261
餘 0,排樣規則:14717=2890+3654+5705+2468
餘 0,排樣規則:14836=2919+4129+5473+2315
餘 1,排樣規則:15015=4372+2751+5523+2368
餘 1,排樣規則:15155=5489+5451+4214
餘 1,排樣規則:15196=3862+4271+3195+3867
餘 0,排樣規則:15330=4698+3520+4398+2714
餘 2,排樣規則:15440=4031+5079+3296+3032
餘 3,排樣規則:15480=4653+5634+5190
餘 1,排樣規則:15688=4475+3757+4713+2742
餘 1,排樣規則:15733=4870+5550+5312
餘 2,排樣規則:15825=5564+4678+5581
餘 0,排樣規則:16118=5602+4830+5686
餘 0,排樣規則:16525=3756+5090+4639+3040
餘 2,排樣規則:16676=4000+5281+4223+3170
餘 5,排樣規則:16719=4019+5425+3777+3493
餘 36,排樣規則:16736=3739+5336+4262+3363
餘 91,排樣規則:16764=5726+5164+5783
餘 3533,排樣規則:17235=4546+4399+4757
餘 3548,排樣規則:19573=4925+5414+5686