外文翻譯--計算機與運籌學研究一種最佳切割方式的確定算法 中文版

計 算機與運籌學研究一種最佳切割方式的確定算法 席林，邁克爾喬治艾迪斯 * 汽巴精化公司的 CH - 1870 Monthey，瑞士 研究與技術中心 - 海拉斯，化工過程工程研究所，寶盒 361 熱敏電阻 57001，希臘塞薩洛尼基 摘要 本文提出了在確定問題的一個新的數(shù)學規(guī)劃的制定，最佳的方式，給定大小的幾個產(chǎn)品輥要切出一個或多個標準件，標準類型。其目的是執(zhí)行這項任務，從而最大限度地考慮到從銷售收入，原卷 成本，改變切削模式的成本和費用 。出售的裝飾。一個混合整數(shù)線性規(guī)劃（混合整數(shù)線性規(guī)劃）模型提出 了一種解決的全局最優(yōu)使用標準技術。有不少的例子，包括工業(yè)界的實際，研究中，被提出來驗證電子 $ ciency和該模型的適用性。 范圍和宗旨 一維下料（修剪虧損）生產(chǎn)項目時出現(xiàn)問題，有可能在物理上，成片的大小分成了一維的多樣性（例如，當主人的紙分切卷成卷筒，寬度窄）。這些問題發(fā)生時，有規(guī)模沒有與相關經(jīng)濟，生產(chǎn)規(guī)模較大的原材料（主）卷。一般來說，在解決這些問題的目的有如下 5 點： 1. 盡量減少修剪損失 ； 2. 避免生產(chǎn)過度運行和 /或 ； 3.避免不必要的分切機設置。 4.上述問題，尤其是在紙張加工工業(yè)的 重要一卷紙時，需要一套要削減從原料紙卷。由于產(chǎn)品的寬度是充分的原紙寬度無關，一個高度組合問題出現(xiàn)了。一般來說，切割產(chǎn)生的必然過程始終修剪損，已被燒毀或在某些廢物處理廠處理。 在造紙行業(yè)的修剪，丟失問題， 在最近幾年，主要是解決了采用啟發(fā)式規(guī)則。實際問題的表述。因此，在大多數(shù)情況下被事實限制了解決的方法應該能夠處理 整個問題。因此，只有次優(yōu)解到原來的問題，并已取得 5.通訊作者。電話： 30-31-498-143，傳真：。 30-31-498-180。 E - mail 地址： georgiadcperi.certh.gr（只限喬治艾迪斯）。 0305-0548/02 / $ - 見前面的問題 2002年 Elsevier科學有限公司保留所有權利。 有價證券投資收益：秒 0 3 0 5 - 0 5 4 8（ 0 0） 0 0 1 0 2 - 7 席林 1042 克， M.C.喬治艾迪斯 /計算機與運籌學研究 29（ 2002） 1041 1058 很多時候，這個不能離開經(jīng)濟的問題留給了制造業(yè)。這項工作提出，為電子新算法的確定的文件轉換過程最佳切割方式。一個混合整數(shù)線性規(guī)劃模型，提出這是解決全球最優(yōu)利用現(xiàn)有計算機工具。大量的問 題，包括工業(yè)為例，提出說明該算法的適用性。 2002 年 Elsevier科學有限公司保留所有權利。 關鍵詞：整數(shù)規(guī)劃 ；優(yōu)化 ；修剪損耗問題 ；紙加工行業(yè) 1。簡介 一個重要的問題，這是經(jīng)常遇到的，如造紙行業(yè)與有關最經(jīng)濟的方式，給定大小的幾個產(chǎn)品推出要產(chǎn)生，切割在一個或多個標準寬度更廣的一個或多個可用的原始卷。這種解決方案 問題涉及幾個交互決定： 其各項尺寸的產(chǎn)品數(shù)量，生產(chǎn)卷。 這可能是由于允許各不相同下限和上限。 在訂單室目前突出，而后者則對應的最大市場容量。但是，一定的折扣哦，可能要到銷售超過 定單，以上數(shù)量為其中訂單可室。 每間標準寬度原始輥數(shù)量將會被削減。 勞斯萊斯，可在一個或多個標準寬度，對一臺直噴！ erent 單位單價。 針對每個原始滾切模式。切割發(fā)生在一個雇用一個在并行操作上一卷刀號機的地方， 標準寬度。雖然刀的位置可能會更改從一個滾動到下一個，這樣的變化可能會產(chǎn)生一定的費用。此外，可能有一定的技術的限制， 刀位置可實現(xiàn)任何特定的切割機。 上述問題的最優(yōu)解往往與最小化的 trima 廢物一般是不可避免的，因為標準寬度輥使用。然而，修剪丟失最小化，并不一定意味著對原材料的成本最 小化（卷）特別是如果正在使用的幾種標準卷筒尺寸可供選擇。一個更直接的經(jīng)濟標準是同時考慮到經(jīng)營噸最大化： 從產(chǎn)品銷售輥， 包括任何批量折扣常態(tài)收入 ； 該卷的實際使用成本 ； 的費用，如果有的話，換在切割機刀職位 ； 廢物的處置費用的削減。 以上是一個高度組合的問題，這并不奇怪，傳統(tǒng)的解決方案往往是對人體進行手動的專業(yè)知識為基礎。這個問題類似于切割下料問題在行動，研究文獻中，凡訂購件數(shù)需要削減噢！更大的存儲塊以最經(jīng)濟時尚。在 60 年代和 70 年代，一些文章對這一問題盡量減少修剪損失，例如 1,2。 Hinxman 3提出了一種可用的解決方案，很好地概括修剪方法損益和各種各樣的問題。 Gilmore 和戈莫里 1提出了一個基本的線性規(guī)劃的方法來削減庫存問題，同時放寬一些問題整數(shù)字符。 Gilmore 和戈莫里 2去 scribed 迭代求解方法，是非常大的訂單數(shù)量適當，計算便宜，但對于削減模式的數(shù)量所產(chǎn)生的值會用于非整數(shù)，這是無法證明的最優(yōu)性或指示的優(yōu)選保證金。這些切割方式。因此，四舍五入值，得到由吉爾摩和算法戈莫里 2可能很可能導致經(jīng)濟表現(xiàn)不佳。 Wascher 4提出線性規(guī)劃方法下料問題考慮到多重目標，如原料成本，倉儲成本的生產(chǎn)過剩，修剪損耗搬遷費等。斯維尼 5提出了求解一維下料問題的啟發(fā)式程序多個質量等級。費雷拉等。 6認為兩階段滾切問題，基于啟發(fā)式的方法。 Gradisar 等。 7提出一個電子序列啟發(fā)式 $古程序以及為在服裝行業(yè)的最優(yōu)化軟件工具推出。后來， Gradisar 等。 8開發(fā)了一個改進方案的戰(zhàn)略基礎上的近似組合，系統(tǒng)蒸發(fā)散和啟發(fā)式領先的一維下料幾乎最優(yōu)解問題。一種軟件工具，還制定。 近年來，整數(shù)規(guī)劃技術已用于裁切損耗的解決方案和生產(chǎn)在造紙行業(yè)的優(yōu)化問題。和工作的韋斯特倫 德在一博 Akademi 大學是芬蘭的同事在這方面的重要貢獻。 Harjunkoski9考慮到修剪損耗問題的數(shù)學規(guī)劃方法，提出了兩個制定 erent 的類型。這對需要在使用和切割模式對輥切而必須根據(jù)每個這樣的模式處理數(shù)為未知數(shù)。在整數(shù)非線性數(shù)學問題，這結果（ INLP）涉及雙線性問題每次切割的變量描述模式和相應數(shù)量的本卷切方式。兩地！的線性化 INLP 獲得一個混合整數(shù)線性規(guī)劃 erent 方式（混合整數(shù)規(guī)劃）模式進行了介紹。然而，這些 linearizations 往往導致 signi“不能增加變量和約束數(shù)量，以及作為一個大 型的完整性的差距。第二種類型，由 Harjunkoski 9提出的制定是基于采用“ xed 切割模式集是先天決定。在一個混合整數(shù)規(guī)劃，有一個比一個更小的差距，這結果的完整性從 INLP 制定線性造成上述。然而，解決的辦法獲得的最佳保證只有當所有非劣切削模式是鑒定出“ ED 和考慮。這種模式的數(shù)量可能相當龐大的現(xiàn)實工業(yè)問題。 上述工作的延伸， Harjunkoski 10提出的線性和凸 配方解決非凸修剪丟失的問題。韋斯特倫德 11考慮了二維修剪損耗在轉換文件的問題。阿非凸優(yōu)化模型，同時提出在寬度和長度的原紙被視為變量。 兩步求解過程是用在所有可行的切割模式是生成一個混合整數(shù)線性規(guī)劃問題，然后解決了。在一個類似的方式，生產(chǎn)中的紙張加工工業(yè)的結構優(yōu)化問題已解決的韋斯特倫德 12。調度紙張加工方面的切割機，同步了 CON -sidered 與由韋斯特倫德 13修剪丟失的問題。最近， Harjunkoski 14成立成一個總體框架的環(huán)境影響因素的修剪丟失最小化。 本文提出了一種替代的數(shù)學規(guī)劃模型的直接結果在小的差距混合整數(shù)線性規(guī)劃的完整性。這一模式的突出特點是，它不需要所有可能的切割方式先驗枚舉。接下來的部分介紹了正式聲明正在 審議的問題和符號使用。第 3 節(jié)認為數(shù)學制定的目標函數(shù)和業(yè)務限制。其次是一些例如工業(yè)問題，其中包括一個案例研究說明了適用性和計算，周志武行為的建議制定。 2。問題陳述和數(shù)據(jù) 正在考慮的任務是向他們出示我公司產(chǎn)品輥迪類型，類型寬度我被記為 B，我我從一個或多個標準卷。所有原料及輥的長度該產(chǎn)品由他們造成的軋輥被認為是相同的。這是超越這項工作的范圍，考慮二維的問題，即無論是寬度和長度 原紙卷和切割模式被認為是變量。軋輥生產(chǎn)的產(chǎn)品大多是命令。最低訂購數(shù)量為卷筒產(chǎn)品我記的寬度授予，所以是對應的單位價格 p。然而，客戶 可能會愿意購買額外卷 I型最多以數(shù)量 n主題的每超出一般最低人數(shù)全產(chǎn)品推出折扣，在這種方式出售額外的輥數(shù)量往往是由于主要誘因，而從小生產(chǎn)廠家的角度來看這樣的折扣僅僅是為了減少損失通過修剪。 該產(chǎn)品將被卷從 erent 標準類型的原始輥切。單位價格一噸的原料輥式記為 C 的標稱寬度的 B.然而，有用的寬度 T類型是由輥切割機使用。特別是，每個原始輥式， T“的一，的特點是最大可能的總的參與，所有產(chǎn)品的總寬度可以從這種類型的原料輥切卷。也可能有最低需要這種類型的總接觸輥乙。在一般最大卷數(shù) N 的產(chǎn)品可切割的原始類型 T 將推出一般是由 刀和可用機器等特點。此外，在某些情況下，有可能在給定數(shù)目的原始輥 Jh的限制 T 型 針對每個原始滾切模式，是由刀的位置。 頻繁在這些位置的變化一般都不可取。因此，每一個這樣的變化可能相關聯(lián)與非零成本角作者從可用原料輥輥生產(chǎn)所需的產(chǎn)品可能會導致修剪廢物可能需要處置。這種處理單位修剪寬度成本記在給定的數(shù)據(jù)為基礎，我們獲得的原始輥數(shù)量的上限 j 的可能需要削減。這是假設得到數(shù) N 的最大的軋輥產(chǎn)品每種類型我會產(chǎn)生，這類型噸原料卷，允許的最小最小 參與 B 將被使用 ；并且每個原始卷將被用來生產(chǎn)產(chǎn)品的軋輥只有一個單一類型?？傮w而言，這將 導致以下上界原卷數(shù) 我們還可以計算其對原卷數(shù)最低下限 要滿足現(xiàn)有訂單的最低需求。我們通過這個假設輥類型噸，允許最大可能參與 B 的使用，是沒有修剪生產(chǎn)。然而，我們還必須采取的數(shù)目可能的局限刀。總體而言，這會導致較低的軋輥，可能次數(shù)的上限以下須： 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 不能超過： 數(shù) N 的最大的 I 型，可銷售的產(chǎn)品輥 ；在寬度為 B 產(chǎn)品，可容納在一個卷的最大數(shù)量最多， 對于類型 T 的原料輥達到最佳的參與 B 組 ； 數(shù) N 的最大的可應用到原始類型的輥刀噸 這導致對 n 以下范圍： 我們注意到，必須包含在模型中僅當 N全我們還介紹了以下這些二進制變量： 1，如果第 j 個滾被削減的類型噸，如果為 紙卷切割模式是不同的軋輥 j 的！ 1 然而，制將提交 將只分配一個類型 T 的原始輥 j 的實際使用。因此，總輥子的數(shù)目，也將削減了優(yōu)化問題的解決決定。這將成為下一小節(jié)清楚。 3.2。輥式?jīng)Q心限 制 每個原始輥切必須是一個獨特的類型 T在以下的限制這樣的結果：請注意，對于 jJ 號，它可能是 y“后，所有類型 T 0，這僅僅意味著它不要削減滾因子。 此外，給定類型的軋輥有限噸原料可表示在以下方面約束 3.3。切割的限制 我們必須確保，如果一個 rollj 要切斷，然后在最低和最高的局限性參與得到遵守。這是實現(xiàn)通過的限制，我們注意到，數(shù)量乙 n表示所有產(chǎn)品卷筒總寬度被削減了生滾因子。如果 y“對于一些輥式 T，那么約束確保另一方面， 這體現(xiàn)了明顯的事實是，如果 rollj 實際上不是削減，那么沒有任何類型 的產(chǎn)品可以滾動從它產(chǎn)生。 我們還需要確保產(chǎn)品的數(shù)量削減任何輥輥型的 T J 不出來超過可以在部署這種類型的卷數(shù)刀。 3.4。生產(chǎn)的制約因素 每種類型的是我生產(chǎn)的產(chǎn)品包括卷筒總數(shù)最低訂購此加上產(chǎn)能過剩的數(shù)量： 再加上這些限制的界限，確保輥型產(chǎn)品數(shù)量我公司生產(chǎn)之間的最小和最大邊界 N和 N，分別所在。 3.5。轉換限制 如果更改裁剪招致非零成本 C 0，我們需要確定這樣的變化會 發(fā)生。為此，我們包括以下約束：請注意，這將使 Z到僅當 n是零“為我所有產(chǎn)物 N 卷，也就是說，如果 rollsj andj！ 1 在完全相同的方式削減。在這里， M 是 n個常數(shù)的上限（見 3.1 節(jié)）。 3.6。目標函數(shù) 該優(yōu)化目標是最大化的經(jīng)營噸同時考慮到 從各類型產(chǎn)品的銷售收入這包括從銷售收入的最低訂購數(shù)量 價格 p，加上額外數(shù)量的銷售單價在貼現(xiàn)收 該卷的費用被削減。一般來說，每卷成本取決于它的類型。總成本可寫為 CY。 我們注意到，對于每個 rollj，最多一個長期的內在總和不為零。 改變了刀具的位置的費用。 一 般來說，刀位置必須改變，如果切割為給定的模式所使用的軋輥 erent 為上個季度。這是由變量 z和在成本結果 那里的總和等于變化所必需的總數(shù)。 在處置成本的任何削減生修剪產(chǎn)生的寬度原 rollj 給出了由迪！ erence輥之間的寬度和所有產(chǎn)品的總寬度卷筒切斷它。前者的數(shù)量取決于類型軋輥，可表示為通過 ；再次，在這個總和最多的詞匯之一。 在下面的成本削減長期處理結果， 以上條款現(xiàn)在可以收集在下面的目標函數(shù)。 3.7。簡并減少和限制收緊 在一般情況下，上面介紹的基本配方是高度退化：由于任何可行點，人們 可以簡單地生成所有可能的選擇形成要削減軋輥訂貨等等。此外，提供了同一類型所有原料連續(xù)輥切，所有這些將可行點內容對應的目標函數(shù)值相同。 上述財產(chǎn)可能產(chǎn)生不利 e!在 E 美元的搜索過程 ciency常態(tài)。 因此，為了減少損失沒有任何解決方案的最優(yōu)性退化，我們引入下列順序限制： 這確保了產(chǎn)品的總人數(shù)輥切生肉 rollj！一出永遠不會比低 相應數(shù)量的軋輥，所有完全未使用的原料輥左上次在這個順序 。 另一種做法是為了在不增加用電秩序 的原始卷。 然而，我們的實踐經(jīng)驗表明，這是不是作為約束。我們還注意到，約束（ 7）隱式征收較低的總人數(shù)的約束產(chǎn)品卷筒 n剪切出原始輥因子。一個強有力的約束有時可能會得到考慮 T類型的軋輥使用在最低可能的最廣泛的接觸，以產(chǎn)生可能的產(chǎn)品名單。這導致了約束 3.8。評論 目標函數(shù)和在本節(jié)所介紹的所有約束是線性的。由于所有的變數(shù)是整數(shù)重視，制定頒發(fā)對應一個整數(shù)線性規(guī)劃（指令級并行）問題。然而，限制（ 9）確保變量將自動承擔整數(shù)提供的值變量 n這樣做。因此，可視為連續(xù)的數(shù)量，這留下一個混合整數(shù)線性規(guī)劃（混合整數(shù)規(guī)劃） 問題我們。原則上，后者可解決了使用標準的混合整數(shù)線性規(guī)劃求解。 4。例題 在本節(jié)中，我們考慮四個問題日益復雜的例子，以研究了我們的配方計算的行為。另外一個工業(yè)案例研究。還介紹了。在所有情況下，我們認為最大的原料輥接觸乙等于相應的輥寬度 B 的 GAMS 本身 / CPLEX 求解器比 6.0 已經(jīng)解決方案中使用 15 和所有的計算，進行了一個 Alpha 服務器 4100。為 0.1，完整性差距承擔了所有問題的解決。 4.1。例 1 我們的“ rst 例子是根據(jù) Harjunkoski 9給出的。一些不同的翻譯成本 安科$ cients 是為輕微迪要帳號！ erences 中所用的目標函數(shù)兩種制劑。還要注意，這些作家使用的目標是成本最小化為反對噸的最大化，因此，他們的目標函數(shù)符號相反對我們的。 表 1 例如 1 原料的滾動輥式寬度 B 最高。灑乙！ B 最高。削減成本 c 1 1900 毫米 200 毫米 5 一千九英鎊 表 2 例如 1 生產(chǎn)數(shù)據(jù) 產(chǎn)品幅寬乙分鐘。數(shù)量最多。數(shù)量價格折扣 I型（毫米）神經(jīng)網(wǎng)絡電腦， 這個問題的目的是確定生產(chǎn)四迪！的 erent 類型的最佳切削模式從原始單一類型產(chǎn)品的軋輥輥。后者的特點見表 1。生產(chǎn)要求如表 2 總結。為改變切削 模式的成本 是 1 英鎊，而招致的任何費用修剪處理。 Harjunkoski 9假設一 家四迪！ erent最大切割圖案，從而導致一個模型的規(guī)模縮小。在我們的情況下，這種模式的數(shù)量是由解決方案。同時，從表現(xiàn)形式（ 1）及（ 2），我們確定 J“的 10 和 J” 8。 解決方案，我們得到的是相同的，報告由 Harjunkoski 9涉及生產(chǎn)最低訂購量的產(chǎn)品輥加一額外的 2 型 3 型輥和另一個。形象地提出了解決方案圖。 1，對應于目標函數(shù)值！ 1622.0 英鎊，因此給定的操作招致的損失的經(jīng)濟數(shù)據(jù)。 最佳的解決方案（在一個最優(yōu)利 潤率為 0.1）被發(fā)現(xiàn)在不到 1 個 CPU 的 s 在節(jié)點分支定界算法 49 使用廣度“ rst 搜索策略。必須指出，我們制定的完整性差距媲美的配方，為一由 Harjunkoski 9提出的事實，盡管它不使用任何先驗的枚舉切割模式。我們還研究制定，以少量的節(jié)點檢測最佳點（見表 3）。 每個豎條對應一個 DI！ erent 輥被削減。相應的輥式顯示上方 每個酒吧。每個酒吧分為相應的部分指定類型的張數(shù)。黑暗的陰影在酒吧上段是修剪損耗，其寬度為百分比顯示在底部的數(shù)值 例如 1 計算統(tǒng)計 充分放松的最佳節(jié)點變量約束的完整性客觀的客 觀差距（）在 B B 酒店（斌/詮釋 /續(xù)）（！） 1622.0（?。?1619.4 0.18 49 60（ 13/44/3） 115 4.2。例 2 對這個問題的數(shù)據(jù)載于表 4 和 5。沒有改變的成本削減用于裝飾圖案或處置。使用表達式（ 1）及（ 2），它可以計算出一個先驗的所需將于 11 至 15 號原卷。 雖然這個問題涉及的產(chǎn)品，只有 9 卷類型，有一個 3971 直接投資總！ erent 切割方式，所有這些都是相對于最小和最大允許總可行聘用軋輥，該可應用于輥和刀的最大數(shù)量最大的紙張數(shù)量排序。因此，任何制定明確的模式，依賴于枚舉就必須 涉及到大量的離散變量。這是，當然，與傳統(tǒng)的方法來削減庫存問題人所共知的問題。 我們的算法獲得關于這個問題，準確的（ 0的最優(yōu)利潤率）的最佳解決方案在不到 1 個 CPU 秒提出這個解決方案是在圖。 2。計算性能統(tǒng)計資料載于表 6。 例如 2 卷原始特征 輥式寬度 B 最高。灑乙！ B 最高。削減成本 c 1 1900 毫米 200 毫米 5 一六英鎊 例 2 和 3 的生產(chǎn)數(shù)據(jù)產(chǎn)品幅寬乙分鐘。數(shù)量最多。數(shù)量價格折扣 I型（毫米）神經(jīng)網(wǎng)絡電腦 對例 2，第 3 和第 4 計算統(tǒng)計 充分放松的最佳配方節(jié)點變量約束的完整性 客觀的客觀差距。 例如 3 卷原始 特征輥式寬度 B 最高。灑乙！ B 最高。削減成本 c 4.3。范例 3 這個例子是類似的實例 2 中，只有迪！ erence 是，高達 6 成卷的迪生！ erent 一種是現(xiàn)在也可被削減（見表 7）。由于現(xiàn)在可以更廣泛地輥，最低所需卷數(shù)減少到 9 J 是（從 11 例 2），但最 高數(shù)量 軋輥 保持不變， 即 15。 準確的（ 0的最優(yōu)保證金），獲得最佳的解決方案，在不到 1 個 CPU 秒該圖提出的解決方案。 3 計算性能如表 6 所示的統(tǒng)計數(shù)字。該最高 2 型原料輥數(shù)量是使用。有趣的是，提及的是，如果沒有對 2 型原料輥數(shù)量的上限是強加的，只有這種類型的軋輥實際從事。在更高的親“的 C 三千三百八十噸這就結果。 4.4。范例 4 這個例子是類似的實例 2 中，只有迪！ erence 正科的成本為 $ cients 變廢為裝飾， 切割處理模式， C 和等于 10 和 1，分別。在計算性能見表 6。我們注意到，有相當數(shù)量較大的節(jié)點分支定界樹是需要比較例 2。然而，完整性差距相對較小。 4.5。例 5 一 justi“與我們制定教育署關注的是何種方式計算成本可能隨著訂單要令人滿意“版人數(shù)有所增加。這是因為更多的訂貨會 例如 5 計算統(tǒng)計 例 2 中的節(jié)點的 CPU 全面優(yōu)化變量約束的數(shù)目軋輥 通常意味著更多的原料輥不得不被切割考慮，（例如，更高的 J）。的數(shù)量變量和約束在我們的配方與后者呈線性增加。為了研究如何制訂了該計算性能隨對訂購產(chǎn)品的軋輥的數(shù)目，我們進行了三次另外的實驗中使用原始例 2，但數(shù)據(jù)乘以2， 4， 10 和 15 的訂購數(shù)量的因素（見附表 8），分別。結果如表 8 總結。正如預期的更大的訂購產(chǎn)品的數(shù)量軋輥，造成較大的數(shù)學問題和 DI美元的解決方案culty。例如，問題的最優(yōu)解的兩倍的訂單數(shù)量使得 25 迪使用！ erent 這是自動切割的算法確定模式。然而，即使有了 最大的問題（涉及 1340 產(chǎn)品從268 張卷筒生產(chǎn)原料），但仍可能確定在不到 1 分鐘計算在桌面上的最優(yōu)解工作站。整體性的差距也仍然在所有的例子非常小。同樣的問題還解決了的情況下有兩個迪！ erent 輥可用的類型（如例 3）以及訂單總數(shù)超過 600 張。該解決方案對應一個目標函數(shù)的 C 31550 零完整性的差距。所生產(chǎn)的總數(shù)為 660張來自 120個原始卷。這個問題涉及到 1823 整數(shù)變量和解決方案，得到 43 秒的 CPU 4.6。工業(yè)個案研究 這是一個工業(yè)為例，每天修剪損設在馬其頓優(yōu)化問題造紙廠（梅爾）在希臘北部 S.A.公司。褪黑素是主要的造紙生產(chǎn)企業(yè)之一在希臘超過年產(chǎn) 10 萬噸。通常包括每日秩序 5 15 迪！輥 erent 類型的產(chǎn)品以 10總重量 100 噸。到目前為止，盡量減少修剪的損耗，目前已進行采用啟發(fā)式為基礎的技術和人力的專業(yè)知識與修剪平均損耗 4 7的順序而定。對這個問題的所有數(shù)據(jù)都依從表 9 和 10，對應于近似的值。 假設的廢 物處置修剪以及改變切削模式的解決方案不花錢 被描繪圖。 4。請注意， 9 原始輥滿足生產(chǎn)需要。阿總數(shù) 1100 節(jié)點審查了分支定界樹，需要的計算時間少。 表 9 工業(yè)原料的滾動個案研究 輥式寬度 B 最高。灑乙！ B 最高。削減成本 c 1 三百六十厘米 40 厘米 515 9 表 10 為工業(yè)生產(chǎn)數(shù)據(jù)為例 產(chǎn)品幅寬乙（厘米）最小。數(shù)量最多。數(shù)量價格折扣 I型神經(jīng)網(wǎng)絡電腦 圖。 4。解無廢物處置和變化的成本削減工業(yè)為例。 5。解決方案與廢物處置和變化的成本削減工業(yè)為例。超過 5 秒的 CPU 該目標函數(shù)代表親“噸最優(yōu)值是 C3105.8 它等于完全放松的目的。修剪的平均損耗是1.126，并代表大約 55的改善比較，現(xiàn)時的做法基于純粹的人 專業(yè)知識。 同樣的問題也解決了假設美元的成本安科廢物處置 cients 為改變切削模式是等于 0.39 和 58.8，分別為（見圖 4）。該最優(yōu)值噸，而現(xiàn)在C2842的完全松弛問題的價值是 C3044。大約 9000點被認為需要 1分鐘的 CPU計算時間。這是值得注意的是，既然改變裁剪成本考慮在內，只有三這樣的變化，而平均修剪損耗仍然與前面的情況相同。然而，應該強調的是，在削減節(jié)省的時間，由于同時 minimiz -改變切割圖案，通報 BULLETIN 已 signi 植物 tability“親上不能影響”。這是由于生產(chǎn)速度增長比例幾乎與總切削減少時間。 5。結論 本文介紹了優(yōu)化確定為一個新的數(shù)學公式切一維問題的圖案。在前面的配方，其主要優(yōu)勢在于它的小的差距，其完整性變量和約束較 少。為達到這個目的，而不需要訴諸先天生成的切割方式，并在問題規(guī)模增加而組合 從這樣一種做法。 在中等大小混合整數(shù)規(guī)劃問題的結果，在制訂目前的范圍提供商業(yè)解決者。配方的完整性差距普遍偏小，雖然迪的解決方案增加 $ culty，涉及轉換和廢物處置費用的問題。 無論是這里提出的制定和審查了本文前面的大部分主要是與確保各項訂單 ful 關注“ lled。只有韋斯特爾工作隆德 13其實認為倍，由于此類訂單。一個有趣的方面提出制定明確的特點是，它的卷已被削減順序兩個條款的類型的每種原料輥和裁剪為它用。這將打開的可能性引 進更多的變量和約束特征的時間點是每卷切斷，從而確定最佳切割調度。 致謝 致謝感謝博士 Iiro Harjunkoski 有關問題的一些有益的討論本文研究。筆者也感謝議員 Sotiris Kiourtsides，生產(chǎn)經(jīng)理馬其頓造紙廠薩，為工業(yè)提供了個案研究和討論，對一些有價值的在修剪損耗問題的實際問題。 參考文獻 1吉爾摩電腦，戈莫里再生能源。一個線性規(guī)劃的方法來削減庫存問題。運籌學 1961； 9:849 59。 2吉爾摩電腦，戈莫里再生能源。一個線性規(guī)劃的方法來削減庫存問題 *第二部分。 行動 研究 1963； 11:863 88。 3 Hinxman人工智能。裁切損耗和品種問題。一項調查。歐洲運籌學雜志 1980； 5:8 18。 4 Wascher 克線性規(guī)劃為基礎的方法來削減庫存的多目標問題。歐洲雜志 運籌學 1990； 44:175 84。 5斯威尼體育，哈斯勒刻錄。一維與多輥下料質量等級的