外文翻譯--計(jì)算機(jī)與運(yùn)籌學(xué)研究一種最佳切割方式的確定算法 中文版

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