基于多線程求解一維下料問(wèn)題的遞歸算法.pdf

1、下料問(wèn)題廣泛應(yīng)用于國(guó)民經(jīng)濟(jì)的許多行業(yè),如何提高原材料利用率,降低成本,簡(jiǎn)化切割工藝,是各企業(yè)關(guān)注的焦點(diǎn)。一維下料問(wèn)題是指在下料時(shí)只需要考慮一個(gè)方向的尺寸,因此又被稱為線材下料問(wèn)題。“堆”是指在下料過(guò)程中用來(lái)存放各種毛坯的容器,處于打開狀態(tài)的堆稱為“開堆”。下料過(guò)程的不同時(shí)刻,開堆數(shù)可能不同,其最大值稱為最大開堆數(shù)。因下料場(chǎng)地面積一定,(最大)開堆數(shù)往往會(huì)受到限制。
　　 本文研究的是一種長(zhǎng)度線材上的下料問(wèn)題。提出采用遞歸精確算法

2、約束一個(gè)排樣方式中所含毛坯種數(shù),以減少(最大)開堆數(shù)和簡(jiǎn)化切割工藝。此外,針對(duì)遞歸技術(shù)是精確算法,計(jì)算時(shí)間較長(zhǎng)的缺陷,先后運(yùn)用上界法和多線程技術(shù)對(duì)遞歸算法進(jìn)行改進(jìn),有效減少運(yùn)算時(shí)間。同時(shí),保證較高的材料利用率,并實(shí)現(xiàn)一維下料系統(tǒng)。通過(guò)實(shí)驗(yàn)數(shù)據(jù)測(cè)試,證實(shí)本文算法的正確性和有效性。本文所做主要工作如下:
　　 首先,針對(duì)本文的研究?jī)?nèi)容,建立當(dāng)前最好排樣方式的計(jì)算模型,采用遞歸技術(shù)求解基于該模型的背包問(wèn)題,生成線材中所含毛坯總價(jià)值最大

3、的當(dāng)前最好排樣方式。接著,先后運(yùn)用上界法、多線程技術(shù)對(duì)遞歸算法進(jìn)行改進(jìn),并利用同步函數(shù)實(shí)現(xiàn)當(dāng)前最好排樣方式的更新。
　　 然后,將一維下料問(wèn)題的線性整數(shù)規(guī)劃模型松弛得到線性規(guī)劃模型,將生成的最好排樣方式與線性規(guī)劃結(jié)合,利用延遲列生成法求得線性規(guī)劃問(wèn)題的最優(yōu)解,并采取適當(dāng)?shù)姆椒ㄈ≌?得到一維下料問(wèn)題的近似最優(yōu)解。
　　 最后,在基于多線程遞歸算法的基礎(chǔ)上開發(fā)一維下料系統(tǒng),提供人性化的輸入輸出界面,能夠滿足用戶訂制的需求。實(shí)