外文翻譯--多級(jí)下料問(wèn)題的建模 中文版

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

30、K.如果最優(yōu)值問(wèn)題?超過(guò)u1j然后解決A22號(hào)是一列進(jìn)入修訂后的旋轉(zhuǎn)步的基礎(chǔ)單純形算法。否則，進(jìn)入下一步驟。第3步。解決背包三。如果功能最優(yōu)值超過(guò)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是一個(gè)新的添加的列。擴(kuò)大的逆矩陣保留當(dāng)前的逆矩陣的子矩陣B 1和它是適當(dāng)微升零點(diǎn)在該行第1A和B列中所示（15）元素。</p><p>　　如果背包第三最優(yōu)解不超過(guò)1.0，和松弛變量的減少成本非負(fù)數(shù)，那么當(dāng)前的解決方案是最佳的。列選擇看起來(lái)更比一代的經(jīng)典案列復(fù)雜。其實(shí)二2和3個(gè)額外的步驟是參與?，F(xiàn)在，我們調(diào)查的輔助問(wèn)題本身。</p>

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

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

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

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

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

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

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

39、案，這是一個(gè)單級(jí)CSP的，也是36套。這是值得注意的解決方案是一種退化，因?yàn)橹挥辛橇憬獾幕咀兞吭?個(gè)元素的基礎(chǔ)。其基本模式是突出于表4。中間有四個(gè)1200，1390，1710和1900毫米軋輥的最佳解決方案。下一步，我們將展示如何提高業(yè)務(wù)質(zhì)量的解決方案。</p><p><b>　　5。減少中間輥</b></p><p>　　照此計(jì)算，一個(gè)中等大小的不同數(shù)量最

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

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

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

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

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

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

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

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

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

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

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