多級下料問題的建模（有出處）695--中英文翻譯

1、<p><b>　　多級下料問題的建模</b></p><p><b>　　摘要</b></p><p>　　在多級下料問題（CSP）的切割過程是分布在幾個連續(xù)的階段。每一個階段除了最后一個生產(chǎn)中間產(chǎn)品。中間產(chǎn)品清單可給予或任意。我們的目標(biāo)是盡量減少材料總量減少了產(chǎn)成品庫存足以滿足采取客戶的需求。如果中間的大小，給出了列生成技術(shù)可以應(yīng)用

2、到多級切割問題。如果中間的大小也得不到那么另一個方面是增加了問題的復(fù)雜性。我們建議對于這種情況，動態(tài)生成兩行（中間大?。┖土械奶貏e程序模式）。我們把這種為行和列的生成方法。該方法使用一個輔助問題嵌入修訂后的單純形算法框架。這是一個非線性背包問題，可以有效解決。與此相反對列代方法開發(fā)的技術(shù)不能保證最優(yōu)解。然而，結(jié)果計算實驗是非常有前途，并證明該方法是一種寶貴的工具除了為多級CSP的建模和求解。 2002年Elsevier科學(xué)B.

3、訴保留所有權(quán)利。</p><p>　　關(guān)鍵詞：線性規(guī)劃;多級料問題;大規(guī)模優(yōu)化，行和列代</p><p><b>　　1簡介</b></p><p>　　一維下料問題（CSP）的推廣具有重要的現(xiàn)實時，切削過程是分布在幾個連續(xù)的階段。這不僅包括多級CSP的切割模式和他們的活動，而且中間產(chǎn)品和生產(chǎn)它們的數(shù)量每一個階段除了最后的切割工藝之一，并在每

4、一個階段的切割過程消耗除第一一。這些中間產(chǎn)品削減生產(chǎn)規(guī)模較小的中間或成品尺寸。中間產(chǎn)品產(chǎn)量和在切割過程的輸入。這種問題發(fā)生在幾乎每一個行業(yè)，一個典型的CSP的發(fā)生：紙張，薄膜，皮革，鋼鐵等雖然本文的結(jié)果同樣適用于任何行業(yè)，多級切割需要為宗旨的地方，學(xué)科領(lǐng)域說明，我們將使用的術(shù)語在造紙行業(yè)所接受。特別是，我們會將向作為其寬度幾何定義的產(chǎn)品推出。軋輥直徑，展開紙的總長度，紙卡尺不適合目前的調(diào)查有關(guān)。 圖。 1說明了三個階

5、段的切削過程。在這個例子中三種類型的股票中一滾，S2和S3是用于生產(chǎn)九成品卷（的F1 - F9鍵）類型。有趣的是，股票輥能提供任何階段的進(jìn)程。在這里，中一去的第一階段，S2的進(jìn)入到第二和S3去了三分之一。相反，成品輥可以生產(chǎn)在任何階段。三種類型的中間輥為I1，I2和I3被切斷前兩個階段。顯然，我們可能會看到股票種類，中間產(chǎn)品的擴(kuò)散，即使削減實際問題階段。</p><p>　　是一個重載多級字，特別是在運(yùn)

6、籌學(xué)和CSP領(lǐng)域。吉爾摩和戈莫里[7]指的是二維CSP的切割沿第一條解決了，然后通過切割帶自己的跨越，作為一個多階段的問題。在我們的情況下，所有削減都是沿（縱向）和問題是一維的CSP。 Dyckhoff[3]提出的多級為所謂的一切模型切割多級。一切模型是一個極端的例子不是一個常見的，眾所周知的情況下一階段的問題，無限的削減。有趣的是注意到，這些一切和多切模式只是同一個問題的兩個不同的配方，而在現(xiàn)實世界的情況下，一期CSP是往往

7、是多級CSP的放寬。一階段放寬提供了一個合理的下界原來的多級CSP的。</p><p>　　幾位研究人員襲擊了多級的CSP。哈斯勒[9]提出了一個以兩階段問題絡(luò)筒機(jī)在第一階段，在第二條生產(chǎn)復(fù)卷。他探索的方法與模式唱片代要么事先或在單純使用迭代列生成技術(shù)。他代表在成品卷筒和檢查方面絡(luò)筒機(jī)模式模式是否可以被分解成一中間輥組合合法。如果這樣的組合是允許的，該模式被接納對問題的矩陣。雖然這種方法是可行的，它有一些缺點。它

8、潛在的，包括不同中間輥數(shù)量龐大，并確定是否可以分割的格局是一復(fù)雜的裝箱問題。此外，這種方法并不容易切削加工規(guī)模更以上兩個階段。</p><p>　　費(fèi)雷拉和其他[4]也探討兩階段的問題，他們稱之為兩階段問題。筆者改編哈斯勒的順序啟發(fā)式程序[8]，最初為一典型的開發(fā)總警司，在兩個階段的切削過程。在每一個連續(xù)的過程步驟，他們正試圖尋找一套''好''中間輥保證了第一階段和第二好的模式的良

9、好格局。如果在第一階段的模式被接受，在成品卷筒上殘留的問題是更新，減少了下令由模式及其活動定義的金額數(shù)量。顯然，這類似于啟發(fā)式為解決一兩個階段的CSP手工操作。與此啟發(fā)式的主要困難是產(chǎn)生一組良好的中間輥。</p><p>　　卡瓦略和羅德里格斯[1]按照線性規(guī)劃的方法。他們的問題，但是，是受一個技術(shù)限制，完成了一個卷筒，寬度應(yīng)包括每一個中間輥。的限制允許預(yù)定義一個可能的中間輥名單。筆者重新初始LP問題成唱片中提

10、出的問題方面，成品輥中間輥的條款。阿列生成與常規(guī)的輔助問題背包技術(shù)被應(yīng)用。</p><p>　　一個的中間輥智能一代的想法[10]出現(xiàn)時，兩個階段的系統(tǒng) -削薄和切割-進(jìn)行了研究。在本論文中，我們''''的思想結(jié)晶，并提出一行和列求解多級一維的CSP發(fā)電技術(shù)。該技術(shù)是一種列生成的精液技術(shù)的推廣建議的Gilmore和戈莫里[5,6]為一個典型的CSP解決，或在我們的符號，一個單級的C

11、SP。對于一個多級的問題，更復(fù)雜輔助問題可能會導(dǎo)致列進(jìn)入基礎(chǔ)上的候選人，連同組合行相應(yīng)的新的中間輥。我們擴(kuò)大在LP矩陣行和列。一個有限單純形算法的迭代次數(shù)，導(dǎo)致要么最優(yōu)或接近最優(yōu)的解決方案。在接下來的章節(jié)中，我們將制訂兩個階段的CSP兩種基本模式，目前行andcolumn代方法，然后分析計算實驗。結(jié)果有些從作者的論文借來的[12]。</p><p>　　2模型的中間輥定列表</p><p>

12、;<b>　　有三種輥尺寸名單：</b></p><p>　　?列出股票的大小。?列出的中間尺寸。?列出成品尺寸。</p><p>　　請看圖。 2（一），這表明輥之間的關(guān)系，這三種類型。股票體積可用金額是眾所周知的。股票的大小可能會被消耗在切削過程的每一個階段，可切成中間或成品卷筒。中間輥的輸入和輸出。該中間輥技術(shù)的限制非常嚴(yán)格：每卷的大小所消耗的總?cè)?/p>

13、數(shù)不能超過生產(chǎn)量。理想情況下應(yīng)該有一個總的平衡，否則，有些過度無人認(rèn)領(lǐng)的''''中間輥數(shù)量應(yīng)該去庫存在倉庫里，如果有存儲空間可用。但是，這是另一種材料的浪費(fèi)之間的折衷與相關(guān)的成本和倉儲問題成本，這超出了目前的調(diào)查范圍。因此，我們認(rèn)為我們正在考慮開放與不等式約束的問題，我們認(rèn)為浪費(fèi)無人認(rèn)領(lǐng)的中間輥。對于成品輥擁有一支管理有序的數(shù)量應(yīng)得到滿足。</p><p>　　在這里，我們考慮一項

14、股票輥寬度為兩階段的CSP將在第一階段切成幾個（圖2（b））中間輥。產(chǎn)成品輥在第二階段削減中間卷。我們假設(shè)一個中間輥寬度出來的第一階段，將第二個滿足最低最高限制。每一個中間輥寬度也應(yīng)包括一個最小邊將在第二階段修整。</p><p>　　讓W(xué)和Y是成品，中間輥寬度載體，分別為。的切削模式第一階段和第二階段為代表的A11和A22號矩陣分別。為了彌補(bǔ)一個完整的唱片我們定義另一個矩陣矩陣A12往，顯示兩者之間的關(guān)系。每一

15、列連接的J矩陣的A12矢量，其中只有一個非零元素鈥樷€1鈥欌€出現(xiàn)在我的位置相對應(yīng)的中間輥我認(rèn)為應(yīng)削減根據(jù)裁剪定義列矩陣A22座因子。 我們可以制訂一個多級CSP的線性規(guī)劃模型：</p><p>　　在這里，向量x1和x2是圖案活動的第一和第二個階段，分別為B是向量 要求對成品輥目標(biāo)函數(shù)（1）盡量減少所用的股票，是由長期1Tx1定義成雙數(shù)。約束（2）保證</p><p>　　中

16、間輥在第二階段A12x2消費(fèi)應(yīng)不超過其在生產(chǎn)A11x1第一階段，的B卷?客戶需求應(yīng)該得到滿足。</p><p>　　請注意，整體矩陣具有特殊的結(jié)構(gòu)。有兩個對角塊A11和A22號代表兩個階段切割圖案，連接A12座，以及0塊在左下方角落。右手邊是由由0上的中間輥和載體的需求灣模型（1） - （3）一個兩階段的CSP唱片介紹，明確涉及中間輥。該矩陣可能已滿如果問題比較小。在這種情況下，對各個階段的所有模式可呈現(xiàn)在矩陣

17、。否則，是一個列選擇適當(dāng)?shù)募夹g(shù)在網(wǎng)上列生成。但在兩種情況下，我們是否提前產(chǎn)生的所有列，或使用列生成，在矩陣的行數(shù)保持不變，因為可能的中間大小的列表給出。</p><p><b>　　2.1雙重問題</b></p><p>　　在這里，向量U1和U2是雙變量向量對應(yīng)的中間輥和成品輥，分別。對偶問題（4） - （6）輔助導(dǎo)致兩個問題，應(yīng)該在解決類型的列選擇步驟，修訂后的單

18、純形算法。</p><p><b>　　2.2。列生成</b></p><p>　　在第一類的輔助問題，是關(guān)系到第一階段削減模式生成切削過程。中間輥列表保持不變。顯然，這種類型是與第一組問題的雙重約束（5），輔助問題在本質(zhì)上是相同的背包問題，因為我們在一個典型或一個階段的CSP。輔助問題可以表示為背包以下問題：在這里，U1是一個目標(biāo)函數(shù)的系數(shù)是主問題的雙變量的值向量;

19、Y是中間輥寬度載體; W0的是股票輥寬度和向量a是一個變量的向量。如果目標(biāo)函數(shù)值超過1.0，一個新列第一階段產(chǎn)生。這種情況緊跟從第一組的限制（5）可作為UT斯達(dá)康提交一答1161T。該為解向量進(jìn)入到矩陣答11列對第二類是輔助問題與成品輥切割產(chǎn)生的模式利用現(xiàn)有的中間輥。這種類型是與約束（5）第二組。對于每個中間輥系列YJ我們應(yīng)該解決以下背包問題：在這里，U2是目標(biāo)函數(shù)的系數(shù)是主對偶變量值的向量問題; w是一個成品尺寸的

20、載體;額敏是一項強(qiáng)制性的最低邊緣，eminP0;鷹擊是中間寬輥J和向量a是一個變量的向量。讓u1j是一個雙變量的值對應(yīng)于j的中間尺寸如果目標(biāo)函數(shù)價值超過u1j，一個新列第二階段產(chǎn)生。這種狀況緊跟從約束第二組（5）可作為UT斯達(dá)康提交2 A22號6 UT斯達(dá)康一答12。由于矩陣答12結(jié)構(gòu)，右邊歸</p><p>　　該解決方案作為載體進(jìn)入A22號為矩陣列。如果我們沒有中間輥中的不確定性，上述兩種

21、類型的背包-背包i和背包第二至足以解決問題最佳狀態(tài)。</p><p>　　3。模型未知的中間輥</p><p>　　如果中間輥是未知的，我們面臨更加復(fù)雜的局面。我們可以自由地選擇任何合適的從一個給定范圍內(nèi)的中間大小?[Ymin成員; yMax的]。由于每個中間輥和軋輥成品關(guān)聯(lián)用矩陣的唱片，在唱片的不確定性矩陣在兩個方向延伸行：列和行。出于這個原因，一列生成技術(shù)不能單獨解決這個問題

22、。另一方面，中間輥潛在的巨大數(shù)目可能產(chǎn)生的一切可能性預(yù)先排除。我們可以估計在現(xiàn)實生活中不同的中間輥潛力。讓頤，范圍為中間輥寬度。參數(shù)鏑是依賴于機(jī)器的，但通常頤800毫米。設(shè)d是至少幅寬的精度。通常情況下為 0.5毫米。因此，不同N =4輥這個公式給我們一個估計ñ1600。當(dāng)然，對于特殊情況的多級CSP的估計可能是少得多。雖然如此，全尺寸的LP矩陣往往是非常大的。</p><p>　　另一種說法，對先進(jìn)的

23、中間輥代的是一個業(yè)務(wù)問題。該在一次中間輥的多樣性減緩物質(zhì)流，復(fù)雜滾跟蹤任務(wù)，并提供切割作業(yè)少的靈活性。一家造紙廠總是傾向于用最少的操作一些不同中間輥尺寸。不用說，這將是非?？扇〉挠幸粋€聰明的辦法產(chǎn)生中間輥這可以做切割模式 -只在需要時。下一步，我們將目前的行和列的一代技術(shù)的兩個階段的問題（1） - （3）。</p><p><b>　　3.1。行與列代</b></p><

24、p>　　隨著背包一，二和背包，我們可能面臨的問題與第三類輔助同時產(chǎn)生新的中間輥和切割模式。在這里，我們應(yīng)該記住矩陣的唱片行目前的中間和成品卷。 （如果我們對股票的限制，我們輥將包括額外的行卷，以及股票。）的LP模式矩陣的列切進(jìn)入中間輥和中間輥到成品的股票名單。</p><p>　　在這里，我們正在努力適應(yīng)修正單純到一個任務(wù)，是不是它的典型。據(jù)了解，上每一步的修正單純一列正進(jìn)入更換的基礎(chǔ)和另一列是離

25、開的基礎(chǔ)。如果列在事先不知道，我們使用一列生成技術(shù)，擴(kuò)大了LP矩陣列方向。修訂后的單純沒有使我們有能力產(chǎn)生未知行?，F(xiàn)在的問題是如何能產(chǎn)生未知的中間輥使用修訂后的單純的步驟？</p><p>　　讓我們限制搜索生成中間輥不超過上一個新的中間輥修訂后的每一個單純的一步。因此，我們應(yīng)該生成矩陣的新的唱片行，并在非退化的情況下，矩陣的秩的唱片將有效地增加1。矩陣的基礎(chǔ)上，應(yīng)還可以擴(kuò)大一行和一列，因為只有一列葉片旋轉(zhuǎn)過程中

26、的基礎(chǔ)第一步，我們得出結(jié)論，兩列實際上應(yīng)該是在一個單一步驟生成。其中一應(yīng)添加到矩陣基礎(chǔ)上無條件地與其他人都不應(yīng)取代現(xiàn)有的一個旋轉(zhuǎn)的一步。</p><p>　　讓向量y為中間輥尺寸已經(jīng)在模型到目前為止，變量z是一個新的中間軋輥尺寸和V是一個相應(yīng)的對偶變量。我們面臨如下非線性整數(shù)規(guī)劃問題：</p><p>　　這里有兩個變量新列：列在第一階段和第二階段柱A22號答11，中間輥寬度z時，為新行V

27、雙變量，而軋輥一個新的中間數(shù)寬度在第一階段削減模式。請注意，約束（10）有一個平等的形式。作為解決背包三的結(jié)果，我們會找到一個新的中間輥尺寸，及兩所切割方式第一和第二階段，分別為。</p><p>　　從理論上說，上述規(guī)定的限制限制了我們的選擇產(chǎn)生中間輥。事實上，時可能出現(xiàn)的情況沒有新的存在只是一個涉及切割方式新的中間滾。至少有兩個新的中間輥應(yīng)列入一份關(guān)于第一階段削減模式。我們可以可以想象，這種情況更可能是在修正

28、單純的開始，當(dāng)初始設(shè)置中間輥是稀少。只要程序產(chǎn)生更多的中間輥，這種情況變得不太可能的。正如我們展示后，一次一個''''中間輥的限制是正當(dāng)?shù)膹V泛的現(xiàn)實世界中的CSP。</p><p>　　3.2。在經(jīng)修訂單純形算法的修改后的列選擇</p><p>　　讓我們證明了以下命題一。</p><p>　　命題1。設(shè)B是一個mm，非奇異矩陣，巴將

29、其擴(kuò)展加入一行，并形成一列如下所示：其中A是一個向量維數(shù)m，0是一個零鈥檚維向量米然后，逆矩陣B1一存在，并且被定義為證明。這是不難驗證巴布1一錄I，其中I是單位矩陣。修改后的列的修正單純形算法的選擇步驟如下：第1步。 i.如果解決背包的功能最優(yōu)值超過1.0，解答11是一列進(jìn)入修訂后的單純形算法的基礎(chǔ)旋轉(zhuǎn)步。否則，進(jìn)入下一步驟。第2步。二，解決背包為每個現(xiàn)有的中間輥系列YJ，強(qiáng)¼1。 。 。的

30、K.如果最優(yōu)值問題?超過u1j然后解決A22號是一列進(jìn)入修訂后的旋轉(zhuǎn)步的基礎(chǔ)單純形算法。否則，進(jìn)入下一步驟。第3步。解決背包三。如果功能最優(yōu)值超過1.0，我們應(yīng)</p><p>　　?擴(kuò)大一行和一列的基礎(chǔ)矩陣，?選擇一列作為進(jìn)入修訂后的單純形算法的基礎(chǔ)上旋轉(zhuǎn)步其他列</p><p><b>　　第二階段削減模式。</b></p><p>　

31、　矩陣的基礎(chǔ)上擴(kuò)大根據(jù)（14），其中B是迄今為止發(fā)現(xiàn)的基礎(chǔ)矩陣，A是一個新的添加的列。擴(kuò)大的逆矩陣保留當(dāng)前的逆矩陣的子矩陣B 1和它是適當(dāng)微升零點在該行第1A和B列中所示（15）元素。</p><p>　　如果背包第三最優(yōu)解不超過1.0，和松弛變量的減少成本非負(fù)數(shù)，那么當(dāng)前的解決方案是最佳的。列選擇看起來更比一代的經(jīng)典案列復(fù)雜。其實二2和3個額外的步驟是參與?，F(xiàn)在，我們調(diào)查的輔助問題本身。</p>

32、<p>　　3.3。背包問題的非線性</p><p>　　雖然前兩個輔助問題類型- 背負(fù)土地出人附著物背包II類是傳統(tǒng)的和同時涵蓋了文學(xué)（見[11]，或[2]），第三類背包第三需要專項調(diào)查。背包III是一個有許多額外的限制（7）非線性背包- （13）。非線性度是由兩個條款規(guī)定：在目標(biāo)函數(shù)中弗吉尼亞州（7）和約束（8）雜。</p><p>　　3.4。字典算法在背包問題<

33、;/p><p>　　所有問題的參數(shù)功能界別;一，保函，目標(biāo)函數(shù)系數(shù)和單約束參數(shù)，假設(shè)是積極的。該字典算法中提出了Chvatal由Gilmore和戈莫里[6] [2]符號如下： 第1步。安排的項目比率依序為：錄一其中m為載體維度。不失一般性，我們可以假設(shè)為C1 = a1Pc2= a2P中成藥=我。初始化索引變量的分支，鉀錄0，函數(shù)f的客觀錄零紀(jì)錄的價值，以及工作參數(shù)該算法的一個背包鈥布列斯特錄

34、其余（空缺）B部分（您不能跟蹤這方面的工作在原來的文件參數(shù)，但它不可避免地出現(xiàn)，一旦你開始編碼的算法。） 第2步。查找當(dāng)前分支的最有前途的延伸。</p><p>　　第3步。是一個改進(jìn)方案獲得？計算出的價值目標(biāo)函數(shù)f¼CTX和比較的交易記錄。</p><p>　　第4步?；厮莸较乱粋€分支。</p><p>　　第5步。是值得探討的分支？該分行潛力估

35、計由一個上限背包尾巴的功能。</p><p>　　這是一個基本的字典算法。對于背包III0，第2步是通過檢查補(bǔ)充在雙面約束的有效性（19）。如果檢查失敗轉(zhuǎn)到步驟4。</p><p>　　3.5。找到一個好的初始解</p><p>　　這是可取的開始，一個可行的方案接近最優(yōu)?；厥酌}2段，我們的結(jié)論是中間輥的初步名單應(yīng)至少包括Ymin成員，因為它可能無法提交由成品

36、輥寬度的線性組合。此外，為了提供一個溫暖的開始''''我們產(chǎn)生一初步清單使用以下過程中間輥。</p><p><b>　　4。一個樣本問題</b></p><p>　　假設(shè)有四個要削減成品卷。兩臺機(jī)器進(jìn)行兩個階段的連續(xù)切割：第一臺機(jī)器切成中間輥輥股票，而第二個削減到了中間輥成品卷。輸入數(shù)據(jù)見表1和2。首先，我們將產(chǎn)生一個初步的解決方

37、案。讓我們限制了中間輥的初步清單一個強(qiáng)制性輥：Ymin成員¼¼日圓1200毫米。因此，我們有一個在第一階段生產(chǎn)1200毫米模式四輥和第二階段的模式，每完成滾動。初始矩陣基礎(chǔ)上突出顯示于表3。目標(biāo)函數(shù)值是60.777。</p><p>　　表4顯示了解決問題的動力。有趣的是，如何跟蹤算法生成新列（模式）和（中間大?。┬滦?。問題是開始出現(xiàn)在初始矩陣大膽的框架。然后圖案9和第10列生成過程中產(chǎn)生

38、的步驟。下一步中間1900毫米大小的生成以及兩個新模式：模式11和模式12。然后，算法利用新的規(guī)模優(yōu)勢，并產(chǎn)生13-16新列。然后，一個新的中間尺寸1690 mm的生成以及兩個新模式，17和18，等等。</p><p>　　該算法發(fā)現(xiàn)換句話說與36套最佳解決方案的第一階段，36個股票輥有序需要削減量。我們怎樣才能證明最優(yōu)？我們可以通過計算一個下界允許所有成品輥要削減在第一階段直接。輕松的問題的最佳解決方

39、案，這是一個單級CSP的，也是36套。這是值得注意的解決方案是一種退化，因為只有六非零解的基本變量在9個元素的基礎(chǔ)。其基本模式是突出于表4。中間有四個1200，1390，1710和1900毫米軋輥的最佳解決方案。下一步，我們將展示如何提高業(yè)務(wù)質(zhì)量的解決方案。</p><p><b>　　5。減少中間輥</b></p><p>　　照此計算，一個中等大小的不同數(shù)量最

40、少的時間表是最可取的。該情況類似的模式在單階段問題減少。為解決這種情況的精確算法問題仍在等待來自運(yùn)籌社會的關(guān)注。現(xiàn)在是什么我們擁有一，該行為后試圖反復(fù)優(yōu)化分析，以取代一中間輥很少啟發(fā)式另外一個是已經(jīng)在溶液中，或以取代現(xiàn)有的兩個新的中間輥，或三個現(xiàn)有的兩個新的等中間輥在這里，我們演示了如何''二對一的''改建工程。讓我們看看我們剛才調(diào)查的樣本。在該解決方案有四個中間輥：1200，1390，1710和190

41、0毫米。在圖譜第一階段，我們可以看到，對1390卷和1710毫米22只外觀模式，都有因子1卷。讓我們嘗試下列替代：根據(jù)（23），我們將定義一個新的中間輥尺寸一五五〇毫米¼þ1710 mmÞð1390毫米= 2。因此，22模式將有一個例外，幾乎完整的：不是一139017時10毫米的外觀我們會得到兩個一五五零毫米亮相?，F(xiàn)在，我們也應(yīng)該轉(zhuǎn)向第二階段的模式與1390毫米和1710毫米卷。這些模式

42、是23和25。請注意，這兩個有一集的模式相同數(shù)目- 22?，F(xiàn)在我們可以用一種模式取代這兩種模式一五五零毫米¼þ50毫米320毫米þ2 þ500毫米340毫米44套。所</p><p><b>　　6。實驗</b></p><p>　　在實驗期間，我們追求的主要目標(biāo)是：?確定是否每次一個規(guī)則中間輥提供了一個體面的解決

43、方案的質(zhì)量，?估計有多少中間尺寸的解決方案，并?估計的熱情開始生效。</p><p>　　我們實現(xiàn)了兩個擴(kuò)展與修改單純形算法：列生成方法，行和列的生成方法使用Microsoft Visual C++。我們已經(jīng)制定了發(fā)生器隨機(jī)兩階段的問題。此外，我們跑了每個修剪消除了第二個問題松弛通過允許所有成品切割輥要削減在第一階段直接的階段。松弛的問題解決了常規(guī)列生成技術(shù)。</p><p>　　找到

44、的解決辦法按行和列代幾乎完全符合其定義的下限和50的訂單。隨機(jī)生成的具體參數(shù)列于表6。我們計算了的差距，其中f是功能價值，而F是美國東部時間的估計問題的最優(yōu)值的功能。在一個隨機(jī)生成的問題，1000樣品的最大差距為11.1％。它已經(jīng)達(dá)成只有兩個實例，并與三個訂單都是小問題。只有八個實例有超過0.5％的差距。因此，只有在少數(shù)情況下是最優(yōu)的解決方案問題</p><p>　　在解決中間輥數(shù)量不是單調(diào)函數(shù)的orders.W

45、hen數(shù)訂單的數(shù)量少它增加一些微薄的價值和深遠(yuǎn)的某一點后啟動下降。對于大規(guī)模問題的解決方案的不同，大小數(shù)都趨于中間是一個非常小。這種現(xiàn)象的最好解釋如下：隨著訂單數(shù)量的增長，第二階段的模式就變得如此多樣，只有少數(shù)中級尺寸必須提供高效率的第二階段削減。第一階段是保證切割效率高選擇中間有良好的尺寸合適的股票大小。例如，在許多情況下，只有兩個中間為五千毫米股票已經(jīng)生成尺寸大?。?585和一八三零毫米提供一個完美的第一階段格局：2 一五

46、八五毫米þ一八三零毫米。當(dāng)然，問題可能有一個大數(shù)目的中間解決方案卷筒但發(fā)展的方法的優(yōu)點是它可以產(chǎn)生一些解決方案。</p><p>　　3。表現(xiàn)也證明是可擴(kuò)展性。當(dāng)問題規(guī)模相對較小它具有顯著增長。迭代的次數(shù)的增多，如Oðm2Þ，其中m是成品尺寸數(shù)量。但經(jīng)過某一點，正如我們以上，生長穩(wěn)定。4。不料，熱啟動表現(xiàn)不佳。此外，雖然是一個有價值的熱啟動相對較小的問題，此外，它推動下表現(xiàn)為，凡在

47、大的問題，最后只一些中間輥的使用。正如我們所料，數(shù)據(jù)粒度或數(shù)據(jù)的準(zhǔn)確性影響的表現(xiàn)。允許所有寬度，四舍五入至整數(shù)，而不是維持毫米小到半毫米的精度，提高性能相當(dāng)。</p><p><b>　　7結(jié)論</b></p><p>　　切割過程跨越幾個階段帶來了另一個層面的CSP，使它更難因此更具挑戰(zhàn)性。充足的造型多級CSP的結(jié)果兩種模型類型：一一個給定的中間尺寸，并與其他未知的

48、中間尺寸。這些模型互補(bǔ)的，都應(yīng)該實行商業(yè)軟件解決多級總警司。目前的結(jié)果，特別是優(yōu)雅的行和列生成技術(shù)，是非常有前途為有效解決大型多級模型。實驗證明了計算程序的效率其解決方案和高品質(zhì)。盡管我們已經(jīng)證明在兩個階段的情況下，CSP的技術(shù)，它可適應(yīng)于一般情況下一個多級的CSP。</p><p><b>　　致謝</b></p><p>　　筆者要感謝克里斯倫尼克，兩個匿名的寶貴

49、意見和裁判建議，大大提高了紙張。</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] J.M.V.卡瓦略A.J.G.羅德里格斯線性規(guī)劃為基礎(chǔ)的方法，分兩個階段料問題，歐洲雜志運(yùn)籌學(xué)84（3）（1995）580-589。[2]五Chvatal，線性規(guī)劃，弗里曼，紐約，1983年。[3]閣下Dyckhoff，兩個主要模型之間橋梁的下料配

50、方，工藝，紙張的研討會生產(chǎn)管理在佩奇，匈牙利，九月6-9，1988，第40-51。[4] J.S.費(fèi)雷拉，肌肉萎縮癥內(nèi)韋斯，??P.F.卡斯特羅，分兩個階段滾切問題，歐洲運(yùn)籌學(xué)44（2）2003（1990）185-196。[5] P.C.吉爾摩R.E.戈莫里，線性規(guī)劃的方法來削減庫存問題，運(yùn)籌學(xué)8（1961）849 -859。[6] P.C.吉爾摩R.E.戈莫里，線性規(guī)劃的方法來削減庫存的問題。第2部