下料問題的解法

下料問題的解法有交貨時間限制的大規(guī)模實用下料問題PAGEPAGE4有交貨時間限制的大規(guī)模實用下料問題朱珠,王輝,張志敏指導老師：魯習文(華東理工大學理學院數(shù)學系,上海200237)摘要：本文討論了有交貨時間限制的大規(guī)模單一原材料下料問題。對于一維下料問題，本文提出一種新的算法：DP貪婪算法。在一維的基礎上建立了二維的求解模型，運用降維思想結合一維的DP貪婪算法，給出解決該模型的算法。數(shù)值計算結果表明該算法對大規(guī)模下料問題是有效的。關鍵詞：下料問題，DP，貪婪算法1、問題描述單一原材料下料問題.設這種原材料呈長方形，長度為,寬度為，現(xiàn)在需要將一批這種長方形原料分割成種規(guī)格的零件,所有零件的厚度均與原材料一致，但長度和寬度分別為，其中。種零件的需求量分別為。下料時，零件的邊必須分別和原材料的邊平行。這類問題在工程上通常簡稱為二維下料問題。特別當所有零件的寬度均與原材料相等，即，則問題稱為一維下料問題。一個好的下料方案是在生產(chǎn)能力容許的條件下，借助模型假設中假設(3)：增加一種下料方式大致相當于使原材料總損耗增加。故可將雙目標轉化為單目標：由于每天下料的數(shù)量受到企業(yè)生產(chǎn)能力的限制，假設在天內各種下料方式的下料總根數(shù)分別為,,…,，零件的需求數(shù)量為，第種下料方式下料一次產(chǎn)生的零件的個數(shù)為。設是要求在天內完成的零件集合，則必須滿足：即天內需要完成的零件必須在前根原材料的切割中得到。根據(jù)上述分析，得到有時間限制的一維單一下料問題模型：s.t.其中：第種下料方式前天內下料總根數(shù)，：交貨時間均等于的零件集合2.3模型求解對于該問題，因為可能的下料方式將隨需要的零件種類數(shù)量成指數(shù)級增長，所以它是一個NP－Hard問題。這樣對于大多數(shù)問題，一般方法無法得到最優(yōu)結果或無法及時得到最優(yōu)結果。因此對于大規(guī)模的一維下料問題，我們給出了結合動態(tài)規(guī)劃和貪婪算法的新算法，稱之為DP貪婪算法。基本思想是：對模型計算時，不用先得到一定數(shù)量的下料方案，而是在選取下料方案時就以數(shù)學模型中的目標和約束條件為基礎來進行尋找。為了保證盡量節(jié)省材料，應該盡量將比較大的零件先進行處理，并同時輔以長度小的零件，以保證單個原料的利用率盡量大。因此對每一個零件按照其長度大小依次給定處理順序的權值。為了保證時間的要求，有要求的零件應該盡量優(yōu)先處理，對每一個零件按時間緊迫度t依次給定一個處理順序的權值。兩者的結合將作為每一個零件動態(tài)規(guī)劃初始權值。在決定了處理順序后，首先利用貪婪思想，選取當前尚沒有得到的零件集合中權值最大的一個進行處理。調用動態(tài)規(guī)劃方法，得到一種下料方式，此方法里含有當前的零件，在得到此下料方式后，先盡可能按照此方式進行處理，以盡量減少下料方式數(shù)，然后再應用貪婪思想。依次類推，直到得到所有的零件。這樣我們將得到一種下料方案。如果此方案滿足約束要求則停止處理，否則對權值進行調整，如果結果不能滿足時間緊迫度的限制，則將優(yōu)先權值步長直接調節(jié)到理論上限，隨后通過二分查找的方法進行選擇，如果材料利用率過低，則參照以上方法進行調節(jié)。而后重復上述過程，直到得到合理結果。算法描述：1.局部最優(yōu)//計算當前單根利用率最大值，并得到一組可行下料方案FORI=1TO工件總種類數(shù) FORJ=原材料總長度DOWNTO0 IF在J的位置已經(jīng)有解 FORK=第I件工件中未切割的數(shù)量DOWNTO1 當前長度=J+第I件工件的長度*K IF當前長度位置尚未得到解THEN保存當前解 ELSE對兩個解進行比較選取較優(yōu)解FORI=材料長度DOWNTO1 IF當前長度有解存在THEN返回解全局貪婪對所有需要的零件進行處理FORI=1TO工件種類總數(shù) WHILE如果當前種類還有剩余(按照權值大小依次處理)DO 利用上述局部最優(yōu)處理選取一種至少含有當前種類一根的最優(yōu)解 累加計算結果更新數(shù)據(jù)表格反復調整調整權值IF得到全局的解法不合理IF不能按時完成零件按規(guī)則加大優(yōu)先權值ELSE浪費過于大按規(guī)則加大長度權值調用上述全局貪婪3、二維下料問題二維情況下，假設在矩形原料切割時采用正交切割，切割時的鋸縫可以是直的也可以是彎的；不允許零件旋轉；而且切割所引起的鋸縫損耗忽略不計。3.1模型建立假設共有種不同下料方式，第種下料方式下料的總塊數(shù)記為，并記第種下料方式產(chǎn)生零件的個數(shù)記為(如果某零件（）滿足，則（）)，記第種下料方式下料一次產(chǎn)生的余料（即料頭）為。二維單一原材料下料模型的建模思想與一維單一原材料下料模型類似。得到如下有交貨時間限制的二維下料問題的數(shù)學模型：s.t.3．3模型求解目前，解有交貨時間限制的二維下料問題的常用方法是啟發(fā)式算法，但是這種方法在大規(guī)模的下料問題中并不能將問題的規(guī)模降到一個合理的范圍。對于大規(guī)模的二維下料問題，本文給出新的求解方法。先利用降維思想將二維下料問題化為兩個一維下料問題，對每一個一維下料問題，再使用本文一維下料問題的DP貪婪算法進行計算，再將兩者的結果結合起來，得到最終的結果。本文采用的降維思想為：第一步，先考慮長度（或寬度）這一維(以下采用先考慮寬度為例進行說明)，將寬度相同的零件歸為一類，對每一類,假設各自存在與該類等寬與原母板等長的母板。這樣，每一類零件寬度與各自的母板寬度相等，這就轉化為一維下料問題。故可借助一維下料模型的算法解出原母板在長度維上的切割方式。這種方式找到的是長度維上的局部近似最優(yōu)。第二步，考慮寬度（或長度）這一維。由上一步，我們可以得到每一寬度各自所需的母板根數(shù)，可將每一類寬度視為一維切割中一個零件的長度，將每一類所需的根數(shù)作為零件的下料任務，原母板的寬度作為現(xiàn)在一維切割原料的長，這樣又得到一個一維下料問題，同樣借助一維下料模型的解法來獲得局部近似最優(yōu)解。經(jīng)過上述兩步后，二維下料問題就轉化為了兩個一維下料問題，在借助一維下料問題的求解算法得到兩個局部最優(yōu)解后，可以通過兩者的結合得到最終解。算法的基本思想是：首先比較長的種類和寬的種類，從中選取種類比較少的一個作為第一次降維考慮的基礎(在不影響一般性的前提下，以下假設寬度種類較少來進行描述)。按照寬度對所有零件進行分類，然后假設已經(jīng)有各種寬度的模板足夠多，而模板的長和原材料的長相等。這樣在接下來的切割過程中將不考慮跨度問題，這樣將完全變?yōu)橐痪S下料問題。為了得到更優(yōu)的解應該優(yōu)先處理寬度最寬的一類，所以依據(jù)寬度給定每一類零件一個權值。同時要考慮到交貨時間的要求，交貨時間比較短的零件應該優(yōu)先處理，所以依據(jù)交貨時間給定每一類零件一個權值，兩者的結合作為處理順序的權值。在接下來的處理中，應該選取當前未處理集合中權值最大一類寬度的零件借助一維下料算法進行處理，以得到需要此類寬度模板的數(shù)量。為了提高原材料利用率，當一類寬度零件處理完畢后，如果有一些余料，將采用動態(tài)規(guī)劃方法，在利用率高的要求下將其它寬度的零件盡量用這些余料來獲得，直到剩下的余料不能再被使用為止。重復這個過程，可以得到每一類寬度的模板需要多少數(shù)目，同時得到一種下料方案。接下來，將每一種寬度作為一維下料問題中零件的規(guī)格，而每一類寬度需要的數(shù)目就是一維下料問題中零件的數(shù)量要求，而此次一維下料問題的原材料長度是二維下料問題中原材料的寬度，對于這個一維下料問題借助上文的算法對其進行處理，得到一種下料方案。將第一次得到的一維下料方案和第二次得到的一維下料方案按順序進行組合，即得到這個問題的下料方案。而第二次一維下料問題所需要的原材料個數(shù)就是在二維下料問題中所需要原材料塊數(shù)。算法描述：比較所有零件每一維的類別數(shù)對所有零件以其中類別數(shù)最少的一維為主進行排序WHILE能取出一個等長（寬）分組(按照權值順序)取出其中一個等長（寬）分組在該分組內調用一維算法計算一組可行解綜合所有解，在另一維上得到一組滿足第一問的原始數(shù)據(jù)調用一維算法得到一維下料方案將兩次得到的下料方案進行組合，得到二維下料方案IF下料方案不能滿足時間限制THEN 調整權值重新計算，重新調用算法進行計算4、結果與討論我們用TC編寫了本文算法的程序，并將給定的實例代入程序進行了計算。對一維模型，經(jīng)計算使用800根原料可以得到所有所需的零件，只超出最優(yōu)量3根，廢料總長度為7232mm,共使用58種下料方式，原材料的利用率r＝。對二維模型，經(jīng)計算使用451塊原料可以得到所有所需的零件，比最優(yōu)用量超出3塊，廢料總面積為7232，共使用了66種下料方式，材料利用率r＝。圖1給出其中一種下料方式332538393939332538393939圖1二維時給定實例的一種下料方式從原材料的利用率，可以看出原材料得到較為充分的利用，這也說明模型和求解算法是十分有效和理想的。又因為算法設計時考慮了普遍的情況，所以算法在解決大多數(shù)實際下料問題，特別是大規(guī)模下料問題時是切實有效的。5、模型應用下料問題的本質是要在浪費最小的情況下，達到生產(chǎn)要求。在理論上，這類問題都可以用此模型求解。比如，我們對一維下料問題的求解可以推廣到背包問題，對二維下料問題的求解可以推廣到工具裝箱問題。在解決二維下料問題中，我們設計了一種降維的方法，此方法具有通用性。因此對于任意維的下料問題、裝箱問題或類似的其他問題都可以用本文中的模型和方法來處理。相對于其它的非全局搜索算法，我們的算法具有以下優(yōu)點：在規(guī)模較大的情況下，兼顧了計算速度和結果的質量，而且規(guī)模越大，算法得出的結果和目標結果越接近；相比其它剪枝的搜索方法，在時間允許的情況下，進行了自適應的調整，使結果盡可能滿足可行性條件下的最優(yōu)；相比直接在二維進行DP的算法，本算法的限制很