計算機與運籌學研究一種最佳切割方式的確定算法（有出處）703--中英文翻譯

1、<p>　　計算機與運籌學研究一種最佳切割方式的確定算法</p><p>　　席林，邁克爾喬治艾迪斯* 汽巴精化公司的CH - 1870 Monthey，瑞士 研究與技術(shù)中心 - 海拉斯，化工過程工程研究所，寶盒361 熱敏電阻57001，希臘塞薩洛尼基</p><p>　　摘要   本文提出了在確定問題的一個新的數(shù)

2、學規(guī)劃的制定，最佳的方式，給定大小的幾個產(chǎn)品輥要切出一個或多個標準件，標準類型。其目的是執(zhí)行這項任務，從而最大限度地考慮到從銷售收入，原卷??成本，改變切削模式的成本和費用。出售的裝飾。一個混合整數(shù)線性規(guī)劃（混合整數(shù)線性規(guī)劃）模型提出了一種解決的全局最優(yōu)使用標準技術(shù)。有不少的例子，包括工業(yè)界的實際，研究中，被提出來驗證電子$ ciency和該模型的適用性。</p><p>　　范圍和宗旨  

3、; 一維下料（修剪虧損）生產(chǎn)項目時出現(xiàn)問題，有可能在物理上，成片的大小分成了一維的多樣性（例如，當主人的紙分切卷成卷筒，寬度窄）。這些問題發(fā)生時，有規(guī)模沒有與相關經(jīng)濟，生產(chǎn)規(guī)模較大的原材料（主）卷。一般來說，在解決這些問題的目的有如下5點：1. 盡量減少修剪損失;2.  避免生產(chǎn)過度運行和/或;3.避免不必要的分切機設置。4.上述問題，尤其是在紙張加工工業(yè)的重要一卷紙時，需要一套要削減從原

4、料紙卷。由于產(chǎn)品的寬度是充分的原紙寬度無關，一個高度組合問題出現(xiàn)了。一般來說，切割產(chǎn)生的必然過程始終修剪損，已被燒毀或在某些廢物處理廠處理。在造紙行業(yè)的修剪，丟失問題，在最近幾年，主要是解決了采用啟發(fā)式規(guī)則。實際問題的表述。因此，在大多數(shù)情況下被事實限制了解決的方法應該能夠處理整個問題。因此，只有次優(yōu)解到原來的問題，并已取得5.通訊作者。電話：＃30-31-498-143，傳真：＃。30-31-498-180。 

5、0;E - mail地址：georgiad@cperi.certh.gr（只限喬治艾迪斯）。0305-0548/02 / $ - 見前面的問題2002年Else</p><p>　　席林1042克，M.C.喬治艾迪斯/計算機與運籌學研究29（2002）1041} 1058 很多時候，這個不能離開經(jīng)濟的問題留給了制造業(yè)。這項工作提出，為電子新算法的確定的文件轉(zhuǎn)換過程最佳切割方式。一個混合整數(shù)線性規(guī)劃模型

6、，提出這是解決全球最優(yōu)利用現(xiàn)有計算機工具。大量的問題，包括工業(yè)為例，提出說明該算法的適用性。 2002年Elsevier科學有限公司保留所有權(quán)利。關鍵詞：整數(shù)規(guī)劃;優(yōu)化;修剪損耗問題;紙加工行業(yè)1。簡介   一個重要的問題，這是經(jīng)常遇到的，如造紙行業(yè)與有關最經(jīng)濟的方式，給定大小的幾個產(chǎn)品推出要產(chǎn)生，切割在一個或多個標準寬度更廣的一個或多個可用的原始卷。這種解決方案問題涉及幾個交互決定： &

7、#160;其各項尺寸的產(chǎn)品數(shù)量，生產(chǎn)卷。 這可能是由于允許各不相同下限和上限。 在訂單室目前突出，而后者則對應的最大市場容量。但是，一定的折扣哦，可能要到銷售超過定單，以上數(shù)量為其中訂單可室。 每間標準寬度原始輥數(shù)量將會被削減。   勞斯萊斯，可在一個或多個標準寬度，對一臺直噴！erent單位單價。  針對每個原始滾切模式。切割發(fā)生在一個雇用一個在并行操作

8、上一卷刀號</p><p>　　包括任何批量折扣常態(tài)收入;</p><p>　　該卷的實際使用成本; 的費用，如果有的話，換在切割機刀職位; 廢物的處置費用的削減。   以上是一個高度組合的問題，這并不奇怪，傳統(tǒng)的解決方案往往是對人體進行手動的專業(yè)知識為基礎。這個問題類似于切割下料問題在行動，研究文獻中，凡訂購件數(shù)需要削減噢！更大的存

9、儲塊以最經(jīng)濟時尚。在60年代和70年代，一些文章對這一問題盡量減少修剪損失，例如[1,2]。 Hinxman [3]提出了一種可用的解決方案，很好地概括修剪方法損益和各種各樣的問題。 Gilmore和戈莫里[1]提出了一個基本的線性規(guī)劃的方法來削減庫存問題，同時放寬一些問題整數(shù)字符。 Gilmore和戈莫里[2]去scribed迭代求解方法，是非常大的訂單數(shù)量適當，計算便宜，但對于削減模式的數(shù)量所產(chǎn)生的值會用于非整數(shù)，這是無法

10、證明的最優(yōu)性或指示的優(yōu)選保證金。這些切割方式。因此，四舍五入值，得到由吉爾摩和算法戈莫里[2]可能很可能導致經(jīng)濟表現(xiàn)不佳。 Wascher [4]提出線性規(guī)劃方法下料問題考慮到多重目標，如原料成本，倉儲成本的生產(chǎn)過剩，修剪損耗搬遷費等。斯維尼[5]提出了求解一維下料問題的啟發(fā)式程序多個質(zhì)量等級。費雷拉等。 </p><p>　　本文提出了一種替代的數(shù)學規(guī)劃模型的直接結(jié)果在小的差距混合整數(shù)線性規(guī)劃的完整性。這一模式

11、的突出特點是，它不需要所有可能的切割方式先驗枚舉。接下來的部分介紹了正式聲明正在審議的問題和符號使用。第3節(jié)認為數(shù)學制定的目標函數(shù)和業(yè)務限制。其次是一些例如工業(yè)問題，其中包括一個案例研究說明了適用性和計算，周志武行為的建議制定。2。問題陳述和數(shù)據(jù)  正在考慮的任務是向他們出示我公司產(chǎn)品輥迪類型，類型寬度我被記為B，我我從一個或多個標準卷。所有原料及輥的長度該產(chǎn)品由他們造成的軋輥被認為是相同的。這是超越這項工作

12、的范圍，考慮二維的問題，即無論是寬度和長度原紙卷和切割模式被認為是變量。軋輥生產(chǎn)的產(chǎn)品大多是命令。最低訂購數(shù)量為卷筒產(chǎn)品我記的寬度授予，所以是對應的單位價格p。然而，客戶可能會愿意購買額外卷I型最多以數(shù)量n主題的每超出一般最低人數(shù)全產(chǎn)品推出折扣，在這種方式出售額外的輥數(shù)量往往是由于主要誘因，而從小生產(chǎn)廠家的角度來看這樣的折扣僅僅是為了減少損失通過修剪。 該產(chǎn)品將被卷從erent標準類型的原始輥切。單位價格一噸的原料輥式記為C

13、的標稱寬度的B.然而，有用的寬度T類型是由輥切割機使用。特別是，</p><p>　　3。數(shù)學公式  該數(shù)學公式的目的是確定每個原始輥型的T J被削減和每種類型的卷數(shù)我的產(chǎn)品要生產(chǎn)如此。3.1。關鍵變量  下面的整數(shù)變量的條件為：I型產(chǎn)品的數(shù)量，減少軋輥原始推出?第i種類型的產(chǎn)品生產(chǎn)了數(shù)卷和高于最低數(shù)量排序。  我們注意到，n不能超過：

14、 數(shù)N的最大的I型，可銷售的產(chǎn)品輥;在寬度為B產(chǎn)品，可容納在一個卷的最大數(shù)量最多，  對于類型T的原料輥達到最佳的參與B組; 數(shù)N的最大的可應用到原始類型的輥刀噸這導致對n以下范圍：      我們注意到，必須包含在模型中僅當N'全我們還介紹了以下這些二進制變量：</p><p>　　1，如果第j個滾被

15、削減的類型噸，如果為?紙卷切割模式是不同的軋輥j的！1  然而，制將提交??將只分配一個類型T的原始輥j的實際使用。因此，總輥子的數(shù)目，也將削減了優(yōu)化問題的解決決定。這將成為下一小節(jié)清楚。3.2。輥式?jīng)Q心限制  每個原始輥切必須是一個獨特的類型T在以下的限制這樣的結(jié)果：請注意，對于j'J號，它可能是y“后，所有類型T 0，這僅僅意味著它不要削減滾因子。  此

16、外，給定類型的軋輥有限噸原料可表示在以下方面約束3.3。切割的限制  我們必須確保，如果一個rollj要切斷，然后在最低和最高的局限性參與得到遵守。這是實現(xiàn)通過的限制，我們注意到，數(shù)量乙n表示所有產(chǎn)品卷筒總寬度被削減了生滾因子。如果y“對于一些輥式T，那么約束確保另一方面， 這體現(xiàn)了明顯的事實是，如果rollj實際上不是削減，那么沒有任何類型的產(chǎn)品可以滾動從它產(chǎn)生。 我們還需要確保產(chǎn)品的數(shù)量削減任何

17、輥輥型的T J不出來超過可以在部署這種類型的卷數(shù)刀。   3.4。生產(chǎn)的制約因素  每種類型的是我生產(chǎn)的產(chǎn)品包括卷筒總數(shù)最低訂購此加上產(chǎn)能過剩的數(shù)量：再加上這些限制的界限，確保輥型產(chǎn)品數(shù)量我</p><p>　　3.6。目標函數(shù)  該優(yōu)化目標是最大化的經(jīng)營噸同時考慮到   從各類型產(chǎn)品的銷售收入這包括從銷售收入

18、的最低訂購數(shù)量 價格p，加上額外數(shù)量的銷售單價在貼現(xiàn)收該卷的費用被削減。一般來說，每卷成本取決于它的類型?？偝杀究蓪憺镃Y。</p><p>　　我們注意到，對于每個rollj，最多一個長期的內(nèi)在總和不為零。  改變了刀具的位置的費用。 一般來說，刀位置必須改變，如果切割為給定的模式所使用的軋輥erent為上個季度。這是由變量z和在成本結(jié)果  那里的總和

19、等于變化所必需的總數(shù)。 在處置成本的任何削減生修剪產(chǎn)生的寬度原rollj給出了由迪！erence輥之間的寬度和所有產(chǎn)品的總寬度卷筒切斷它。前者的數(shù)量取決于類型軋輥，可表示為通過;再次，在這個總和最多的詞匯之一。      在下面的成本削減長期處理結(jié)果， 以上條款現(xiàn)在可以收集在下面的目標函數(shù)。3.7。簡并減少和限制收緊  在一般情

20、況下，上面介紹的基本配方是高度退化：由于任何可行點，人們可以簡單地生成所有可能的選擇形成要削減軋輥訂貨等等。此外，提供了同一類型所有原料連續(xù)輥切，所有這些將可行點內(nèi)容對應的目標函數(shù)值相同。上述財產(chǎn)可能產(chǎn)生不利e!在E美元的搜索過程ciency常態(tài)。因此，為了減少損失沒有任何解決方案的最優(yōu)性退化，我們引入下列順序限制：這確保了產(chǎn)品的總?cè)藬?shù)輥切生肉rollj！一出永遠不會比低?相應數(shù)量的軋輥，所有完全未使用的原料輥左上次在這個順序。<

21、;/p><p>　　另一種做法是為了在不增加用電秩序的原始卷。 然而，我們的實踐經(jīng)驗表明，這是不是作為約束。我們還注意到，約束（7）隱式征收較低的總?cè)藬?shù)的約束產(chǎn)品卷筒n剪切出原始輥因子。一個強有力的約束有時可能會得到考慮T類型的軋輥使用在最低可能的最廣泛的接觸，以產(chǎn)生可能的產(chǎn)品名單。這導致了約束3.8。評論  目標函數(shù)和在本節(jié)所介紹的所有約束是線性的。由于所有的變數(shù)是整數(shù)重視，

22、制定頒發(fā)對應一個整數(shù)線性規(guī)劃（指令級并行）問題。然而，限制（9）確保變量將自動承擔整數(shù)提供的值變量n這樣做。因此，可視為連續(xù)的數(shù)量，這留下一個混合整數(shù)線性規(guī)劃（混合整數(shù)規(guī)劃）問題我們。原則上，后者可解決了使用標準的混合整數(shù)線性規(guī)劃求解。4。例題  在本節(jié)中，我們考慮四個問題日益復雜的例子，以研究了我們的配方計算的行為。另外一個工業(yè)案例研究。還介紹了。在所有情況下，我們認為最大的原料輥接觸乙等于相應的輥寬度B的