一種節省原材料的一維下料方法

2023-07-28 18:49:01 2

專利名稱：：一種節省原材料的一維下料方法
技術領域：
：本發明屬於計算機應用
技術領域：
，涉及一種在生產過程中使原材料得到充分利用的分析方法。
背景技術：
：隨著全球資源的日益匱乏，人們對資源利用問題的研究越來越重視。最大限度地節約原材料，提高原材料利用率成為工業生產中提高效益的一個重要手段，下料問題(CuttingStockProblem,CSP)就是其中之一。下料問題是針對某種資源的利用，研究怎樣能夠在滿足客觀條件和可以接受的時間下，通過優化排樣得到最優解或近似理論最優解，從而最大限度的利用該資源。通過尋找出一種最優的下料方案，可以節省原材料消耗，降低生產成本，間接的為企業創造了經濟效益。在機械、造紙、服裝、木材等多種行業，下料問題都有著廣泛的實際應用。因此，開展對下料問題的研究具有重要意義和工程應用價值。下料問題根據維數的不同分為一維下料、二維下料和高維下料問題。通常解決一維下料問題有兩種方法一類是基於求解線性整數規劃模型的方法；另一類是基於啟發式算法的方法。標準一維下料問題(StandardOne-DimensionalCuttingStockProblem,S1D-CSP)描述為設某企業存有某種長度為L的原材料，現客戶需要數量為di(i=1，2，…，n)，長度分別為li(i二1，2，…，n)的該型原材料。企業的目標是完成客戶訂貨，並使得消耗的原材料數量最少或切邊損失(Trimloss)最少。S1D-CSP由前蘇聯經濟學家Kantorovich於1939年提出。他採用基於求解線性整數規劃模型的方法，並給出了一維下料問題第一個線性整數規劃的模型，該模型如下《minZh/=1，2,..,"》,x,J化A;=l，2,...,《ykG{0，1}k=1，2，…，KXik^0整數i=l，2，...，n;k=l，2，…，K式中yk=1表示第k根原材料已經被切割；yk=0表示第k根原材料未使用；Xik為整數，表示從第k根原材料上切割下第i種訂貨材料的數量；K表示完成切割任務需要的原材料根數的上界。1961年，Gilmore&Gomory給出了一個基於切割方案導向的模型，巧妙利用所給出的推遲列生成法求得了該問題的近似最優解，使得求解大型一維CSP成為可能。Gilmore&Gomory的模型如下min(c^+C2X2+…+cnxn)ai!x!+ai2X2+…+ainxn>diXi>0i=1，2，…，n式中n為切割方式；Ci為第i=1，2，…，n的費用；Xi為第i=1，2，…，n為第j種切割方式切下第i種訂貨材料的數量，a".是整數。該模型的成功之處在於(1)模型能夠簡單的對一維CSP進行求解。由於該模型產生的切割方式很多，即使在m不是很大時也能提供將近數百萬種切割方式；(2)模型在開始迭代之初不必給出切割方式；(3)在解決背包問題時，採用ad-hoc方法與動態規劃相結合，使得模型可以求解原材料長度相差不大的一維CSP。目前這種求解大型一維CSP的方法是在原材料使用時採用之前最重要的分析方法，但是，其存在一些難以克服的困難(1)模型求到的解不是整數；(2)求得的最後解的切割方式較多，使得在實際生產中需要多次調整切割機器；(3)容易導致訂貨任務不能完成或超額完成；(4)單純形方法僅在需要產生新的切割方式時才產生進基列(推遲列生成Delayedcolumngeneration)，計算量不大；(5)每種切割方式的費用難以計算，模型中往往採用原材料的價格來替代，導致生產成本上升。
發明內容本發明的目的是針對現有解決一維下料問題的方法存在的問題，為使生產過程中原材料能夠得到充分利用，使企業在生產過程中能夠最大限度地激昂地原材料消耗，降低生產成本，提出一種節省原材料的一維下料方法。假設在生產過程中，需要a種原材料山，12，…，la，其中，Mi=1，2，，a)表示原材料的權值(如長度、價格、形狀等)。每種原材料的數量不限(或限制)。現要求將這些原材料拼接或剪裁成長度為L、數量為m的管道(稱為結果管材)，並滿足下述要求1、每條管道上有n個區間LpL2，…，L。，在Li(i=1，2，…，n)內不允許拼接原材料，即，不允許存在接口；2、要求剪裁原材料li(i=1，2，，a)的次數及焊接數越少越好，即切口數及接口數儘量少；3、給a種原材料賦以不同的權值。在原材料的數量有限的條件下，先使用權值高的原材料，並按權值的大小排序為1"12，，la;4根據用戶對管道數量m需求，採用將m分成k個類組，k的值由用戶設定。要求同一類組內的管道使用相同的拼接方法，而不同類組的管道則使用不同的拼接方法；5、設定長度閾值I^與R2，&〈R2，並且原材料lp12，…，la的長度li(仍用12，…，L表示)均大於R2。當li(i二l，2，…，a)被剪裁後的剩餘料長r'i大於R2(或小於R》時，稱其為餘料(或廢料)。要求產生的廢料越少越好，從而提高剪裁率。7剪裁率formulaseeoriginaldocumentpage8其中L〃表示管組集合，L'為已使用的原材料集合，A為餘料集合；或者要求mmS。，A天為廢料集合；。e^6、設原材料使用率為aj，即限制原材料lj的使用數量。用L表示管道的長，用l"l2，…，la表示原材料lpl2，…，la的傳值(如原材料的長度、價值等)。L、lji=1，2，…，a)均為整數(如果L是有理數或無理數，則將L轉化為整數或者取近似值之後轉化為整數。對原材料傳值li(i=1，2，…，a)亦作同樣處理，且L>12》">la。a.當L是li的整數倍也是li—p1^的整數倍時，選取m，x/,.的li拼接管道L，使接口數與切口數達到最小。條件是(max/,的/,)x(max/,的/,的數目Pwi:(1)b.當L是li的整數倍但不是l卜p的整數倍時，用li拼接管道L，使切口數達到最小。條件是liX(li的數目)^mL(2)c.當L是HJ勺整數倍但不是U勺整數倍(lw〉li〉lH)時，用li拼接管道L，使切口數達到最小，條件同式(2)。d.當L既不是li的整數倍也不是li—plw的整數倍，即，Lmodli^0(i=1，2，…，a)時，採用下述方法拼接L=a'J,a'2l2+...+a'ala+r0其中a;=0,1,2，"'，^，a,丄_a汄一a2/2-----;a2=0,1,2,…,a2，a2丄一a乂5￡170，1，2，a—1。選取r。=0或者使minr。對應的拼接c採取上述拼接方法能夠滿足條件2、3、5，為滿足條件l，設接口處為點a'山，1=1，2，…，a，a'i=l，2，…，ai，L上的區間LnL2，…，k是給定的。判定區間Lj(j=1，2，…，n)是否包含點a'Ji，或者點a'山是否位於區間Lj內(i=1，2，…，a;j二l，2，…，n)。如果點a'山位於區間L/內，則採用變換構成L的li及r。的順序，或逐次更換構成L的li的方法。i附如果將m分成D組，每組有故下式成立時根管道，由於同一組中管道採用相同的拼接方法，8formulaseeoriginaldocumentpage9選取原材料l'i共計n'i根，剪裁併填補L的最後一段。例如formulaseeoriginaldocumentpage9=2.5時，選取l'i=IO的原材料IO根，每根原材料I'i均被切成4等份，每份長2.5，用它們填補40根管道的最後一段。這樣處理，就不會產生餘料。如果式(3)或者式(4)不成立，則選擇使formulaseeoriginaldocumentpage9成立的l'i、n'i與n〃i，從而使產生的餘料達到最少。之後，根據上述分析，在實際生產中對原材料進行裁剪切割等具體操作。有益效果本發明提出的解決一維下料問題的方法，能在多約束條件下(包括約束條件不確定的情況下)求解一維下料問題。通過採用非數值計算的方式，選擇出最優的剪裁、拼接方法，求得最優解，使得在實際生產過程中最大限度的利用了原材料，節約了資源，降低了企業生產成本。圖1為本發明具體實施方式中步驟10的示例圖2為本發明具體實施方式的實施例示意圖。具體實施例方式下面通過本發明方法的具體實施方式及實施例對本發明作詳細說明。首先將未剪裁過的原材料拼接成數量為m、長度為L的結果管材，使結果管材的剩餘部分的長度小於原材料的長度；之後，利用最優的剪裁方法剪裁原材料，使用這些被剪裁的原材料拼接結果管材的剩餘部分。最後，檢查約束條件1是否被滿足，如果不滿足，則作適當調整。由於每個不同的實例，其結果管材所分類(組)以及算法執行中原材料集合的規模、內容等都是不確定的，需要技術方案能應對這些不確定約束，並且能求得最優解，即剪裁率最高的下料方案。參數設定如下1、原材料長度lp12，，la;2、原材料數量rvn2，...，na;3、原材料長度按優先級排序L>12>>la;4、原材料使用率、，a2，，aa;5、不可拼接區間LnL2，…，L"6、結果材料分組數D;7、各組管道根數ivm2，…，niD;8、各組管道長度L、L2，…，L、9、最大類(組)數max工i=3;10、廢料閾值R。11、餘料閾值尺2。步驟l:首先進行類(組)數初始化，即Ii—1，i=1，2，…，D。之後，依據用戶設定的原材料使用率=1，2，…，a)，計算可供使用的原材料根數。因為對於給定的a種原材料(分別有na根)，並非均會使用，也就是說，需要修改原材料集合。步驟2:處理Li《lj，i=1，2，…，D;j二l，2，…，a。當Li=lj時，取lj作為匸；當Ui2)a(丄'";《)上式中，第一個式子r^in(卜,.i;-"乂l)表示進行總長度控制，要求總長度差值最小化；第二個式子(^in((—Z、)v"—￡、)>^)表示進行單根長度限制，要求單根長度差值最小化或單根長度差值大於R2;第三個式子L、'j.n〃j=lAii表示兩種長度總值，要求兩種長度總值相等。上述三個式子同時成立，便保證了所選取的n'j根原材料l'j，每根1'j剪裁成n〃j等份(每份長Li)，能最優的構成mi根結果管材L、步驟3:對類(組)進行劃分。當mi二nj時，將lj歸為一組，然後拼接其它原材料；當A>2nii時，使用根1」的組不進行分類或分組，多餘的1」可以歸入該組，也可以歸入其它組；當mi<nj<2nii時，將nj等分，並歸入同一類(組)，再將其它原材料歸入另一類(組)，即第i組管道分成兩個類(組)進行拼接(Ii=2)。以上述劃分方案為基礎，若有新的劃分類(組)的方法，並且能提高剪裁率，那麼可以將新方法編入步驟2。對於不同的實例，其類(組)的劃分是不同的，這表明該方法適用於某些不確定約束條件，並具有學習、自我完善的能力。步驟4:計算n/，r/，為步驟5提供部分數據準備，並確定步驟5至步驟8的循環次數D'。其中，D'由兩部分組成D與,1^(/'—U其中D由用戶設定，而Ii已由步驟l和步驟3產生。步驟5:a+l個"邏輯或"表達式表示a+l個並列情況，前a個情況分別顯示由單種原材料進行拼接，而第a+l個情況則顯示由多種原材料(兩種至a種)進行拼接4:^^，，…，h根(Ae{0,l，.1})62根(62e{0,l，.,一一1})6。根(~e(O,l,...，a—l})並且|^"'<(~+1)/,+:，/"=1,2，...,"其中bk及bj由o丄…，a-丄中取值。該步驟按給定的原材料長度優先級進行拼接，優先級高的原材料總是優先用完。實際應用中，a值為一個不大的常數，故第a+l個情況所包含的項數不會出現過多，完成該情況的計算所需時間和空間也不會太多。步驟6:從原材料集合中刪去已使用的原材料。由於步驟5是用整根原材料進行拼接，使拼接之後的長度等於或接近結果管材的長度。每執行步驟5—次，就要使用一批原材料進行拼接，因而原材料集合必須修改。步驟7:計算結果管材長度與拼接長度之差。每次執行步驟5，均處理一個類(組)的拼接，而且拼接之後的長度不超過結果管材的長度。多數情況下，為小於結果管材的長度，因而計算結果管材長度與拼接長度之差就成為必不可少的工作。步驟7中的r〃jk便是所要求的差值，等號右側有a+l個式子，它們之間具有邏輯或關係，並且與步驟5中的計算是對應的。步驟8:改變循環控制變量k的值，k的終值為D'。在初始設定輸入時，由於只給定了組數D的值，經過步驟3的計算，某些組中的類(組)數Ii可能會發生改變，因而步驟4中要計算類(組)的總數，即D'。這樣，每執行一次步驟5至步驟8的循環，便完成一個類(組)的拼接及r〃jk的計算並修改原材料集合一次。步驟9:為快速並最優的從剩餘原材料集合R中選取管材拼接Lk的最後一段，需要將修改後的原材料集合R中的原材料按長度遞增序排列，並且按數量遞減序列^:《^2,…,^進行排列。首先考慮r〃/，從R中選取最短的原材料，然後選取次最短的原材料，最後選取最長的原材料。對每種原材料均用步驟10方法執行，從中選取最優的剪裁及拼接方案，以解決Lk最後一段的拼接問題，同時修改R;其次考慮r〃/，重複上述過程；最後考慮《D'，重複上述過程。步驟10:該步是解決Lk最後一段拼接問題的關鍵。具有邏輯"或"關係的三個表達式從3個不同方面控制從剩餘原材料集合R中選取原材料1'j共計n'jk根，每根l'j剪成n〃jk等份，用這些段拼接nii根Lk的最後一段，從而獲得最優的剪裁、拼接方案。下面舉一個例子設R={5.5，6.5，8}，r「1=2,附,=30,ni=5，n2=6，n3=10，如圖1所示，執行步驟10，選1'」=13，共計8根，即!1'3=8。每根13剪成等長的4段，每段長度為2，n〃3=4。實際上，將前7根中的每一根13等分為4段，最後一根13剪成長度11為2、2、4的子段，將長度為2的4*7+2=30根子段拼接L1的最後一段。步驟11:R修改為:R={4，5.5，6.5，8}，=1，n2=5，n3=6，n4=2，即從R中刪去已使用的原材料。k—k+l，用步驟10方法繼續拼接L2，…，LD'的最後一段。採用下述方法計算各種拼接的剪裁率設已計算C(比如0=10)種拼接(對於某確定的Lk，比如L1)的剪裁率，並按遞減序排列Pl，P2，…，Pc，計算第C+l種拼接(仍對Lk)的剪裁率PC+1。如果Pc+1PA(Pc+1P"則將Pc+1作為序列的第1個元素，刪去Pc。步驟12:對於Pl，p2，"、Pe所對應的拼接，從P工對應的拼接開始檢查設拼接點為a'jlj，如果區間LpL2，…，Ln均不含拼接點a'jlj，或者a'山不落入區間LnL2，，k，貝UP:對應的拼接Lk為所求輸出；否貝U，LpL2，…，Lc,^均不含拼接點a'j—ALc,含拼接點a'jlj，則將a'j—Jj與a'jlj之間管材lj進行更換，S卩(兩種調整方法)(1)將lj與Lik最後一段管材進行交換。這時，Lik的長度沒有改變，剩餘原料集R也不變；(2)從剩餘原料集R中選取1'，用l'取代lj。這時，Lik的長度改變了，計算r〃'j，並更換Lik的最後一段並修改R。步驟13:如果調整成功，即1^丄2，…，Ln均不含拼接點，則輸出Lk及拼接順序；否則，k，L2，…，Lc,均不含拼接點a'jljALc,+1含拼接點a',山，則採用步驟11中方法處理(對於相同的i)。步驟14:如果調整成功，即1^丄2，…，Ln均不含拼接點，則輸出Lk及拼接順序；否則，重複步驟13，直至L"L2，…，Ln內均不含拼接點；否則，i—i+l，重複步驟12至步驟14(檢查、調整Pl，P2，…，Pc對應的拼接)。k由1至D'，逐次檢查L、L2，…，L。'，k是外循環變量，i是內循環變量，i二1，2，…，C。步驟15:結果線材長度之和￡力^已使用原材料長度之和。等號成立時，P=100%。由於餘料可用再次被利用，故餘料長度應為計算P公式中分子部分。執行步驟11時，對每次外循環都要進行C次內循環，每次內循環計算1次剪裁率，共計要計算D'C次剪裁率，並從中選取最優解。根據上述計算，能夠得到由原材料長度=1，2，…，a)組成的結果管材Li(i=1，2，…，D)的序列。根據該序列能夠得出每根結果管材由哪些原材料組成，組成的順序如何，以及每根已用原材料的去處。實施例輸入L=10m，12=8.3m，13=7.lm，14=6.8m。=212，n2=32，n3=16，n4=8。aj=1。lj具有相同的優先級。D=4，=m2=m3=m4=32，L1=20.6122m，L2=20.4177m，L3=20.2233m，L4=18.2785m。maxli=3。不可拼接區間12tableseeoriginaldocumentpage13R丄=0.2，R2=0.5。輸出L=I2=I4=1，I3=2，拼接結果如圖2所示。結果材料總長2545.0144m，餘料長6.2916m，原料總長2553.6m。剪裁率p=，;，6=99.91%，接口數224個。2553.權利要求一種節省原材料的一維下料方法，其特徵在於用L表示管道的長，用l1，l2，…，la表示原材料l1，l2，…，la的傳值，L、li(i＝1，2，…，a)均為整數，如果L是有理數或無理數，則將L轉化為整數或者取近似值之後轉化為整數，對原材料傳值li(i＝1，2，…，a)亦作同樣處理，且l1＞l2＞…＞la；a.當L是li的整數倍也是li-1、li+1的整數倍時，選取的li拼接管道L，使接口數與切口數達到最小，條件是b.當L是li的整數倍但不是li-1、li+1的整數倍時，用li拼接管道L，使切口數達到最小，條件是li×(li的數目)≥mL(2)c.當L是li、li-1的整數倍但不是li+1的整數倍(li+1＞li＞li-1)時，用li拼接管道L，使切口數達到最小，條件同式(2)；d.當L既不是li的整數倍也不是li-1、li+1的整數倍，即，Lmodli≠0(i＝1，2，…，a)時，採用下述方法拼接L＝a′1l1+a′2l2+…+a′ala+r0其中a′1＝0，1，2，…，a1，a′2＝0，1，2，…，a2，a′a＝0，1，2，…，aa，選取r0＝0或者使minr0對應的拼接；為滿足條件1，設接口處為點a′ili，i＝1，2，…，a，a′i＝1，2，…，ai，L上的區間L1，L2，…，Ln是給定的，判定區間Lj(j＝1，2，…，n)是否包含點a′ili，或者點a′ili是否位於區間Lj內(i＝1，2，…，a；j＝1，2，…，n)，如果點a′ili位於區間Lj′內，則採用變換構成L的li及r0的順序，或逐次更換構成L的lj的方法；如果將m分成D組，每組有根管道，由於同一組中管道採用相同的拼接方法，故下式成立時或者選取原材料l′i共計n′i根，剪裁併填補L的最後一段；如果式(3)或者式(4)不成立，則選擇使或者成立的l′i、n′i與n″i。F2008102270391C0000011.tif,F2008102270391C0000012.tif,F2008102270391C0000013.tif,F2008102270391C0000014.tif,F2008102270391C0000015.tif,F2008102270391C0000016.tif,F2008102270391C0000017.tif,F2008102270391C0000021.tif,F2008102270391C0000022.tif,F2008102270391C0000023.tif2，，a)均為整數，如果L是有理數或無理數，則將L轉化為整數或者取近似值之後轉化為整數，對原材料傳值li(i=1，2，…，a)亦作同樣處理，且^>12>.">la;a.當L是li的整數倍也是l卜p的整數倍時，選取m，x(的l拼接管道L，使接口數與切口數達到最小，條件是(max/,的/,)x(max/,的/,的數目)》附Z(1)b.當L是l的整數倍但不是1卜p的整數倍時，用li拼接管道L，使切口數達到最小，條件是liX(li的數目)>mL(2)c.當L是li、l卜工的整數倍但不是1L，使切口數達到最小，條件同式(2);d.當L既不是I,的整數倍也不是lia)時，採用下述方法拼接formulaseeoriginaldocumentpage0的整數倍>li>l卜》時，用li拼接管道的整數倍，即，Lmodli#O(iformulaseeoriginaldocumentpage2，選取r。=0或者使minr。對應的拼接；為滿足條件l，設接口處為點a'山，1=1，2，…，a，a'·1^丄2，…，Ln是給定的，判定區間Lj(j=1，2，·1，2，…，ai，L上的區間-，n)是否包含點a'ili，或者點a'是否位於區間Lj內(i=1，2，…，a;j二l，2，…，n)，如果點a'山位於區間一內，則採用變換構成L的li及r。的順序，或逐次更換構成L的lj的方法；附如果將m分成D組，每組有式成立時formulaseeoriginaldocumentpage2根管道，由於同一組中管道採用相同的拼接方法，故下formulaseeoriginaldocumentpage2選取原材料l'i共計n'i根，剪裁併填補L的最後一段；如果式(3)或者式(4)不成立，則選擇使formulaseeoriginaldocumentpage2formulaseeoriginaldocumentpage32.如權利要求所述的一種節省原材料的一維下料方法，其特徵在於約束條件如下(1)、每條管道上有n個區間L"L2，…，Ln，在Li(i=1，2，…，n)內不允許拼接原材料，即，不允許存在接口；(2)、要求剪裁原材料li(i=1，2，，a)的次數及焊接數越少越好，即切口數及接口數儘量少；(3)、給a種原材料賦以不同的權值，在原材料的數量有限的條件下，先使用權值高的原材料，並按權值的大小排序為1"12，，la;(4)根據用戶對管道數量m需求，採用將m分成k個類組，k的值由用戶設定，要求同一類組內的管道使用相同的拼接方法，而不同類組的管道則使用不同的拼接方法；(5)、設定長度閾值&與R2，&12>(4)原材料使用率c^，a2，，aa;(5)不可拼接區間LpL2，…，L"(6)結果材料分組數D;(7)各組管道根數!vm2，…，niD;(8)各組管道長度L、L2，…，L、(9)最大類數maxIi=3;(10)廢料閾值&;(11)餘料閾值I^;'>1。由lj(j二l，2，…，a)組成Li(i=1，2，…，D)的序列；步驟1:首先進行類數初始化，即Ii—l，i=1，2，…，D，之後，依據用戶設定的原材料使用率aji=1，2，…，a)，計算可供使用的原材料根數；步驟2:處理Li《lj，i=1，2，…，D;j二l，2，…，a，當Li=lj時，取lj作為Li;當匸<lj時，用lj剪裁L、並要求滿足下述條件formulaseeoriginaldocumentpage4上式中，第一個式子mjn(h丄'-";/;l)表示進行總長度控制，要求總長度差值最小化；第二個式子(m^((-力";)v(/;-力";.)>及2)表示進行單根長度限制，要求單根長度差值最小化或單根長度差值大於R2;第三個式子j.n〃j=lAii表示兩種長度總值，要求兩種長度總值相等；步驟3:對類進行劃分；當mi=nj時，將lj歸為一組，然後拼接其它原材料；當nj>2!!^時，使用mi根lj的組不進行分類或分組，多餘的lj可以歸入該組，也可以歸入其它組；當Hi,<nj<2nii時，將nj等分，並歸入同一類，再將其它原材料歸入另一類，即第i組管道分成兩個類進行拼接(Ii=2);步驟4:計算n/，r/，為步驟5提供部分數據準備，並確定步驟5至步驟8的循環次數D'，其中，D'由兩部分組成D與,-f(/'—1}其中D由用戶設定，而Ii已由步驟l和步驟3產生；步驟5:a+l個"邏輯或"表達式表示a+1個並列情況，前a個情況分別顯示由單種原材料進行拼接，而第a+1個情況則顯示由兩種至a種原材料進行拼接formulaseeoriginaldocumentpage4、根(he{0，l，..1})62根(62e{0,l，..、0—1})並且1>丄^丄'<(~+1";+t^^=1,2,'B。根(6。e(0,l,…,a-1))'"其中bk及bj由O，l，…，a-l中取值；步驟6:從原材料集合中刪去已使用的原材料；步驟7:計算結果管材長度與拼接長度之差；每次執行步驟5，均處理一個類的拼接，而且拼接之後的長度不超過結果管材的長度；多數情況下，為小於結果管材的長度，因而計算結果管材長度與拼接長度之差就成為必不可少的工作；步驟7中的r〃jk便是所要求的差值，等號右側有a+l個式子，它們之間具有邏輯或關係，並且與步5中的計算是對應的；步驟8:改變循環控制變量k的值，k的終值為D';步驟9:將修改後的原材料集合R中的原材料按長度遞增序排列，並且按數量遞減序列，r〃，d'進行排列；首先考慮r〃/，從R中選取最短的原材料，然後選取次最短的原材料，最後選取最長的原材料，對每種原材料均用步驟10方法執行，從中選取最優的剪裁及拼接方案，以解決Lk最後一段的拼接問題，同時修改R;其次考慮r〃/，重複上述過程；最後考慮r〃/'，重複上述過程；步驟10:具有邏輯"或"關係的三個表達式從3個不同方面控制從剩餘原材料集合R中選取原材料l'j共計n'jk根，每根l'j剪成n〃jk等份，用這些段拼接mi根Lk的最後一段；步驟11:R修改為R={4，5.5，6.5，8}，ni=l，n2=5，n3=6，n4=2，即從R中刪去已使用的原材料；k—k+l，用步驟10方法繼續拼接L2，…，LD'的最後一段；採用下述方法計算各種拼接的剪裁率設已計算C種拼接的剪裁率，並按遞減序排列Pl，p2，…，Pc，計算第C+l種拼接的剪裁率Pc+1;如果pc+1pA(pc+1pp則將pc+1作為序列的第1個元素，刪去pc;步驟12:對於PpP2，…，Pe所對應的拼接，從Pi對應的拼接開始檢查設拼接點為a'jlj，如果區間k，L2，…，Ln均不含拼接點a'jlj，或者a'山不落入區間LnL2，，k，貝UP:對應的拼接Lk為所求輸出；否則，L15L2，，Lc,^均不含拼接點a'j—ALc,含拼接點a'jlj，則將a'j-Jj與a'jlj之間管材lj進行更換，即(1)將lj與最後一段管材進行交換；(2)從剩餘原料集R中選取l'，用l'取代，計算r〃',並更換1^的最後一段並修改R;步驟13:如果調整成功，即k，L2，…，Ln均不含拼接點，則輸出Lk及拼接順序；否則，LpLy…，W均不含拼接點a'jljALc,M含拼接點a'j+1lj，對於相同的i，則採用步11中方法處理；步驟14:如果調整成功，即L15L2，…，Ln均不含拼接點，則輸出Lk及拼接順序；否則，重複步13，直至LpL2，…，Ln內均不含拼接點；否則，i—i+l，重複步12至步14;k由l至D'，逐次檢查L、L2，…，LD'，k是外循環變量，i是內循環變量，i二1，2，…，C;步驟i5:結果線材長度之和y《《已使用原材料長度之和Z^"，等號成立時，p=;執行步驟11時，對每次外循環都要進行c次內循環，每次內循環計算1次剪裁率，共計要計算D'C次剪裁率，並從中選取最優解。4.如權利要求3所述的一種節省原材料的一維下料方法，其特徵在於以上步驟3中的劃分方案為基礎，若有新的劃分類的方法，並且能提高剪裁率，那麼可以將新方法編入步2。全文摘要本發明涉及一種節省原材料的一維下料方法。該方法能在約束條件不確定的環境下求得一維下料問題的最優解，從而最大限度地提高原材料利用率，降低廢料的產生。本發明方法的具體內容為首先將不剪裁的原材料拼接成數量為m、長度為L的結果管材，使結果管材的剩餘部分的長度小於原材料的長度；其次利用最優的剪裁方法剪裁原材料，使用這些被剪裁的原材料拼接結果管材的剩餘部分。最後，檢查約束條件1是否被滿足，如果不滿足，則作適當調整。本發明利用非數值計算的思想，能用於眾多約束條件，包括有些約束條件是不確定的情況下一維下料問題的求解，通過巧妙的比較，選擇出最優的剪裁、拼接方法，求得最優解，由此實現原材料最大利用。文檔編號G06Q10/00GK101739606SQ200810227039公開日2010年6月16日申請日期2008年11月19日優先權日2008年11月19日發明者付夢印,周培德,王美玲,黃源水申請人:北京理工大學