考慮成批供料的大規(guī)模下料問題

郝信燁 劉懋圻 張燦榮 鄭力

摘 要：本文基于某家具廠實(shí)際生產(chǎn)場景，在大規(guī)模下料問題中考慮了成批供料等現(xiàn)實(shí)生產(chǎn)因素。我們建立了Kantorovich模型，其對(duì)應(yīng)的算例具有規(guī)模大、解空間對(duì)稱等特點(diǎn)，難以直接求解。為了解決計(jì)算困難，基于Dantzig-Wolfe框架將其分解，并通過列生成求解線性松弛主問題得到較緊的下界。通過對(duì)子問題的結(jié)構(gòu)分析，將其分解為可獨(dú)立求解的二級(jí)子問題?；跉w并且還原設(shè)計(jì)了三種子問題求解方式，有效縮減了子問題求解規(guī)模，并克服了解空間對(duì)稱性，進(jìn)而加速列生成迭代。基于工廠實(shí)際數(shù)據(jù)進(jìn)行數(shù)值實(shí)驗(yàn)，結(jié)果表明：本列生成啟發(fā)式算法優(yōu)于商用求解器CPLEX，其在較短計(jì)算時(shí)間內(nèi)得到高質(zhì)量的解。相比于工廠現(xiàn)行算法，本算法降低10.43%的下料浪費(fèi)。

關(guān)鍵詞：板材下料;成批供料;大規(guī)模混合整數(shù)規(guī)劃;列生成;歸并且還原

中圖分類號(hào)：TB114.1 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2097-0145（2022）01-0009-08 doi：10.11847/fj.41.1.9

Abstract：This paper stems from a real production research. It studies a large-scale cutting stock problem considering batch feed and some other constraints based on the real production. We establish a Kantorovich model， the instances corresponding to which are hard to solve due to the large scale and symmetry in the solution space. To tackle the computational difficulty， we decompose it based on the Dantzig-Wolfe framework， and solve the linearly-relaxed master problem by column generation in order to generate tight lower bounds. Based on the analysis of the structure， we decompose the sub-problems into second-level sub-problems which can be solved independently. Based on the idea of merge and recover， we develop three methods to solve the sub-problems， which reduce the scale of sub-problems and overcome the symmetry in the solution space， leading to accelerating the column generation process. We conduct computational experiments based on the real data from the factory. The experimental results indicate that， our approach outperforms CPLEX， a commercial solver. It can generate high-quality solutions in short computation time. Compared with the algorithm presently used in the factory， our approach reduces the cutting waste by 10.43%.

Key words：cutting stock; batch feed; large-scale mixed integer programming; column generation; merge and recover

1 引言

下料問題（Cutting Stock Problem，CSP）是眾多行業(yè)中（如造紙業(yè)[1]、造船業(yè)[2]）面對(duì)的一個(gè)重要問題，其以最小化成本為目標(biāo)，通過對(duì)庫存板材的切割，來滿足不同尺寸類型的需求[3～5]。合理的下料方案會(huì)為實(shí)際生產(chǎn)減少浪費(fèi)，帶來經(jīng)濟(jì)效益?；谕臣揖邚S合作的實(shí)際生產(chǎn)項(xiàng)目，本文對(duì)該廠CSP進(jìn)行研究。該廠拼合板產(chǎn)品生產(chǎn)過程如下，盛有不同規(guī)格板材的托盤被挑選并從倉庫中運(yùn)到線上，工人將刀具預(yù)設(shè)為若干種標(biāo)準(zhǔn)寬度，并在板材寬度方向上進(jìn)行水平切割（順沖工序），產(chǎn)生短條;之后，在垂直方向上切去影響美觀的木料疤痕（橫截工序），產(chǎn)生橫截小塊，并將橫截小塊指接成長條;最終，用從長條上切下的拼合塊進(jìn)行產(chǎn)品拼合。在此過程中，需要對(duì)如下問題進(jìn)行決策，包括，如何挑選托盤來權(quán)衡運(yùn)輸成本和板材多樣性，如何水平切割板材，如何選擇寬度來拼合最終產(chǎn)品，從而降低板材浪費(fèi)率。當(dāng)前，工人們按照經(jīng)驗(yàn)進(jìn)行決策，材料浪費(fèi)較為嚴(yán)重。

基于工廠實(shí)際生產(chǎn)情景，與經(jīng)典CSP相比，我們額外考慮了成批供料等生產(chǎn)約束。據(jù)我們所知，本文是首個(gè)將托盤成批供料納入CSP的研究。另外，本問題也有算例規(guī)模極大的特點(diǎn)，如算例“曲柳_27mm”具有272730個(gè)決策變量。據(jù)統(tǒng)計(jì)，現(xiàn)有的大多數(shù)文獻(xiàn)中，模型的變量均遠(yuǎn)小于本文，如Song等[6]的模型中有32580個(gè)決策變量。由于CSP本身為NP-hard[7]，且本問題具有額外的復(fù)雜特征，以及算例具有極大規(guī)模，因此，亟需開發(fā)高效、高質(zhì)量的啟發(fā)式算法，在實(shí)際生產(chǎn)中，求解時(shí)間受限的情況下使用。我們首先建立了Kantorovich模型（Kantorovich Model， KM）來精準(zhǔn)表達(dá)原問題，但其算例規(guī)模大，且具有解空間對(duì)稱等缺點(diǎn)，因此，空間復(fù)雜度較大，且用求解器難以直接求解。為了實(shí)現(xiàn)對(duì)本問題的高效求解，我們基于Dantzig-Wolfe 框架對(duì)KM按托盤分解，得到1個(gè)主問題（Master Problem， MP）與若干子問題，并通過基于列生成（Column Generation， CG）的啟發(fā)式算法（Column Generation-based Heuristic， CGH）生成KM上界。為了加速CG 迭代，通過對(duì)模型結(jié)構(gòu)的分析，我們發(fā)現(xiàn)子問題托盤與板材之間可分支求解的特點(diǎn)，進(jìn)而可以將子問題分解為可獨(dú)立求解的二級(jí)子問題，即，每個(gè)板材對(duì)應(yīng)的下料模型，簡稱板材模型（Board Model，BM）。另外，相同規(guī)格的板材BM模型相同。基于此特性，我們設(shè)計(jì)了3種子問題求解方式：基于托盤的歸并且還原，基于板材池的歸并且還原，基于分解板材池的歸并且還原。這些求解方式有效地縮減了子問題整體求解規(guī)模，并克服了解空間對(duì)稱性的困難。我們從該工廠的生產(chǎn)管理系統(tǒng)中導(dǎo)出實(shí)際數(shù)據(jù)并進(jìn)行測試，結(jié)果表明，我們的算法優(yōu)于商用求解器CPLEX12.8.0，可以在較短時(shí)間內(nèi)得到高質(zhì)量的解。相比于工廠現(xiàn)行下料算法，我們的算法能夠?yàn)楣S降低10.43% 的下料浪費(fèi)，從而極大地節(jié)約生產(chǎn)成本。

2 文獻(xiàn)綜述

作為組合優(yōu)化的經(jīng)典NP-hard問題[7]，CSP始終是學(xué)者們關(guān)注的焦點(diǎn)。CSP在現(xiàn)有研究中有兩種主要的建模方式。第一種是Kantorovich[8]最先對(duì)CSP進(jìn)行定義并建立的帶有指派類型決策變量的數(shù)學(xué)模型（后續(xù)稱之為Kantorovich模型）。Kantorovich模型直接決策并清楚指示了每塊板材應(yīng)該生產(chǎn)的產(chǎn)品?；诒灸Ｐ?，學(xué)者們開展了一系列研究。Abuabara 和Morabito[9]研究了航空材料工廠的一維CSP，他們建立了Kantorovich模型并直接通過CPLEX求解。Lee等[10]針對(duì)產(chǎn)品形狀可變的二維的CSP建立Kantorovich模型，并設(shè)計(jì)了基于背包問題模型的啟發(fā)式算法來求解。管衛(wèi)利等[11]基于Kantorovich 模型，對(duì)單規(guī)格和多規(guī)格線材切割進(jìn)行數(shù)值實(shí)驗(yàn)。在Kantorovich模型中，當(dāng)很多板材之間具有相同規(guī)格時(shí)，解空間會(huì)存在很嚴(yán)重的對(duì)稱性，即解不同但目標(biāo)函數(shù)值相同。此缺點(diǎn)對(duì)于基于“分支—定界”框架來求解整數(shù)規(guī)劃的求解器（如，CPLEX）來說，會(huì)引發(fā)長時(shí)間無效的分支，當(dāng)問題規(guī)模過大，會(huì)難以求解。另外，雖然Kantorovich模型線性松弛產(chǎn)生的下界在需求寬度種類較少的情況下質(zhì)量較高，但其空間復(fù)雜度較大，建立模型需要占用較多內(nèi)存和相對(duì)較長時(shí)間。

下料問題的第二種模型是Gilmore和Gomory[3，4]提出的基于下料方案的模型（后續(xù)稱之為Gilmore-Gomory模型），此模型克服了Kantorovich模型中對(duì)稱性的缺點(diǎn)，同時(shí)，其線性松弛模型提供比線性松弛的KM（Linearly-relaxed KM， LKM）更緊的下界。與Kantorovich模型不同，Gilmore-Gomory模型并沒有直接指出每塊板材產(chǎn)出的產(chǎn)品，而是基于每塊板材可以切割得到的產(chǎn)品的組合（即下料方案）進(jìn)行選擇。但在本模型中，下料方案隨著產(chǎn)品規(guī)模而指數(shù)級(jí)增長，因此模型中會(huì)有很多列。為了解決此問題，Gilmore和Gomory[3，4]提出了CG算法，來動(dòng)態(tài)地生成列，進(jìn)而對(duì)線性松弛的Gilmore-Gomory模型精確求解。之后，可基于此線性松弛解對(duì)原問題進(jìn)行啟發(fā)式或精確求解。Belov和Scheithauer[12]研究了一維、單規(guī)格板材的CSP，他們建立了Gilmore-Gomory模型，并通過分支—定價(jià)框架進(jìn)行求解。Cui 和Zhao[13]研究了二維的單規(guī)格CSP。在該研究中，下料得到的產(chǎn)品可以旋轉(zhuǎn)，此特征使得問題更加復(fù)雜。Furini等[14]研究了多規(guī)格板材、兩階段一刀切的二維CSP，并設(shè)計(jì)了基于CG的啟發(fā)式方法來求解。Wuttke和Heese[15]，Wang等[16]研究的CSP中，考慮了板材生產(chǎn)準(zhǔn)備成本。下料問題的其他模型，如De Carvalho模型[17]和Dyckhoff模型[18]，由于同本文的模型關(guān)聯(lián)較少，因此不做討論。

本研究中，我們將板材成批供料等約束引入CSP，這在現(xiàn)有研究中屬于首次。另外，我們基于含有超過20萬變量的實(shí)際算例進(jìn)行數(shù)值實(shí)驗(yàn)，據(jù)我們所知，當(dāng)前研究中尚未有如此大規(guī)模實(shí)際算例的測試。我們首先建立KM來對(duì)原問題進(jìn)行描述。為了高效求解原問題，我們通過Dantzig-Wolfe框架將其分解為一個(gè)主問題（Master Problem， MP，即，Gilmore-Gomory模型）和若干子問題，并用CG 求解線性松弛的主問題（Linearly-relaxed Master Problem， LMP）來得到較緊的下界。通過對(duì)子問題性質(zhì)分析，我們設(shè)計(jì)了子問題不同的求解方式，從而加速CG迭代過程。最后，我們通過啟發(fā)式挑選列，生成原問題的高質(zhì)量上界。

3 問題描述與數(shù)學(xué)模型

本部分我們對(duì)實(shí)際生產(chǎn)情景進(jìn)行描述，并建立KM。

3.1 問題描述

我們研究的是在某工廠實(shí)際生產(chǎn)中的考慮成批供料和材料等級(jí)的大規(guī)模CSP。本工廠主要產(chǎn)品為拼合板家具，其生產(chǎn)流程如圖1所示，具體描述如下。

步驟1 選擇托盤并運(yùn)輸。工人選擇盛放不同批次板材的托盤，并運(yùn)送至下料車間。

步驟2 選擇板材。工人選擇將要下料的板材。

步驟3 順沖。工人把選擇的板材放在下料機(jī)上，按照設(shè)定好的若干種標(biāo)準(zhǔn)切割寬度（52mm， 62mm， 81mm和89mm）進(jìn)行水平切割，產(chǎn)生短條。

步驟4 橫截。工人把短條放到另一種下料機(jī)上進(jìn)行橫截，垂直切掉短條上的疤痕，產(chǎn)生橫截小塊。

步驟5 指接。工人將橫截小塊指接成長條。

步驟6 拼合，去余料。工人從長條上切下與產(chǎn)品長度相同的拼合小塊，并將拼合小塊在寬度方向上進(jìn)行拼合，直至達(dá)到產(chǎn)品寬度。最終，寬度方向上多余的部分被切掉，得到最終的拼合板產(chǎn)品。

除以上描述之外，我們研究的問題有如下特征：

（a）大規(guī)模：廠方的生產(chǎn)管理系統(tǒng)中導(dǎo)出的數(shù)據(jù)顯示，托盤和板材的數(shù)量非常多，導(dǎo)致算例規(guī)模較大。如，算例“曲柳_27mm”含有150個(gè)托盤和12980塊板材，其Kantorovich模型具有272730個(gè)決策變量，模型規(guī)模遠(yuǎn)超大多數(shù)現(xiàn)有研究。

（b）成批供料：不同托盤盛放不同批次板材，不同批次板材規(guī)格有差異。選擇某個(gè)托盤后，托盤上的一批各種規(guī)格（長、寬）的板材被運(yùn)送到線上進(jìn)行切割。這需要權(quán)衡托盤運(yùn)輸成本與板材的多樣性。

（c）材料等級(jí)：為了實(shí)現(xiàn)產(chǎn)品差異化，以應(yīng)對(duì)消費(fèi)者不同的偏好，本工廠將最終生產(chǎn)的拼合板產(chǎn)品分為不同等級(jí)。每個(gè)板材、短條都標(biāo)有質(zhì)量類型（即A，B，C，D），橫截小塊、長條、產(chǎn)品都有質(zhì)量等級(jí)（如1，2，3，4，數(shù)字越小，等級(jí)越高）。關(guān)系如下：板材經(jīng)過橫截工序產(chǎn)生的短條與板材的質(zhì)量類型相同;在步驟4橫截中，不同質(zhì)量類型的短條會(huì)按不同比例（即出料率）產(chǎn)生不同質(zhì)量等級(jí)的橫截小塊，如表1 所示;某類型的橫截小塊只能指接入寬度等于它且等級(jí)不高于它的長條中;長條切得的拼合小塊的等級(jí)與其相同;拼合小塊的等級(jí)必須不低于它拼合而成的產(chǎn)品。需要說明的是，表1 中，出料率之和均小于1，因?yàn)榘宀谋赜邪毯蹘淼奈锪蠐p耗。

目前，工廠要求按照“最小余料”原則選擇產(chǎn)品拼合寬度，即對(duì)每種產(chǎn)品，選擇最終去掉余料最少的寬度的小塊進(jìn)行拼合，且小塊的等級(jí)要與產(chǎn)品相同。基于此規(guī)則，我們首先將產(chǎn)品需求轉(zhuǎn)化為相應(yīng)寬度和等級(jí)的長條，稱為“延米數(shù)”。以此為生產(chǎn)需求，關(guān)注下料方案的設(shè)計(jì)。另外，我們假設(shè)除了必要的去余料與去疤痕過程，其他生產(chǎn)過程沒有物料損失。

3.2 數(shù)學(xué)模型

本部分我們建立KM。首先，我們給出符號(hào)表示。在本文的數(shù)學(xué)模型中，除集合外，所有輸入變量小寫，決策變量大寫。

集合與索引：P為托盤集合，用p索引。B為板材集合，用b索引。Ωp 為托盤p中的板材集合。N為標(biāo)準(zhǔn)切割寬度集合，用n索引。Q為板材質(zhì)量類型集合，用q索引。G為質(zhì)量等級(jí)，用g索引。

目標(biāo)函數(shù)（1）最小化總成本，包括托盤運(yùn)輸成本與板材使用成本。約束（2）保證只有選擇了某托盤，其中的板材才能被選擇。約束（3）為板材寬度約束。約束（4）保證對(duì)于所有板材，其每種寬度的短條產(chǎn)生的延米數(shù)不能超過短條對(duì)應(yīng)的總長度。約束（5）為出料面積約束，我們假設(shè)理想情況，即出料時(shí)每個(gè)等級(jí)都可以達(dá)到其最大出料面積。約束（6）為考慮向下兼容的需求滿足約束。約束（7）和（8）說明決策變量的性質(zhì)。

4 求解方法設(shè)計(jì)

本節(jié)包括如下內(nèi)容：首先，我們按照Dantzig-Wolfe框架，將KM按托盤分解為MP和子問題。之后，介紹生成初始列與生成原問題上界的啟發(fā)式方法。最后，基于子問題的模型結(jié)構(gòu)進(jìn)行性質(zhì)分析，并介紹三種子問題求解方法。

4.1 Dantzig-Wolfe分解模型

本部分我們按照Dantzig-Wolfe框架，將KM按照托盤分解為1個(gè)MP與|P|個(gè)子問題模型。本模型具有角塊結(jié)構(gòu)，即子問題模型之間無耦合關(guān)系，因此，子問題可以獨(dú)立求解。首先，引入如下符號(hào)表示。

目標(biāo)函數(shù)（9）最小化所有被選擇方案中的總成本，包括托盤運(yùn)輸成本與板材使用成本。約束（10）對(duì)應(yīng)于約束（6），即需求滿足約束。約束（11）說明每個(gè)子問題必須選擇一個(gè)可行方案。約束（12）為決策變量性質(zhì)說明。除此之外，我們引入2組對(duì)偶變量：α和β，分別對(duì)應(yīng)于LRMP中的約束（10）和約束（11），用來構(gòu)建子問題的目標(biāo)函數(shù)。

（2）子問題模型

目標(biāo)函數(shù)（13）包括托盤運(yùn)輸成本、板材使用成本，以及與對(duì)偶變量有關(guān)的目標(biāo)。約束（14）～（17）對(duì)應(yīng)KM中的（2）～（5）。

4.2 初始列和上界構(gòu)建方法

為了使CG開始迭代，我們設(shè)計(jì)如下初始列構(gòu)建方法?；驹瓌t是，對(duì)于所有n∈N，g∈G，順序地不斷搜索未滿足的需求dng。 若有未滿足需求，則順序抽取托盤以及托盤中的板材。若板材剩余寬度不小于需求寬度，那么寬度方向水平切割一刀（順沖），得到的短條按照出料率產(chǎn)出橫截塊，橫截塊按照等級(jí)向下滿足需求。

同時(shí)，我們設(shè)計(jì)基于LRMP的一種上界構(gòu)造方法。本方法的基本原則是，當(dāng)LRMP求解完畢，針對(duì)每個(gè)托盤p∈P，我們將mp∈Θp對(duì)應(yīng)的解值作為概率，來隨機(jī)抽取該托盤p的一個(gè)下料方案，并用該方案來滿足需求延米數(shù)。當(dāng)所有托盤抽取的方案無法滿足需求時(shí)，我們從第一個(gè)托盤順序篩查未切割或剩余足夠?qū)挼陌宀模凑諛?gòu)造初始列中提到的方法進(jìn)行切割和需求滿足。

初始列和上界構(gòu)造詳細(xì)流程如圖2所示。圖2 初始列（a）和上界（b）構(gòu)造流程

4.3 子問題性質(zhì)分析與算法設(shè)計(jì)

本部分基于子問題的模型結(jié)構(gòu)，首先對(duì)子問題性質(zhì)進(jìn)行分析?；谄渫斜P選擇—板材選擇決策可分支特性，及BM模型特點(diǎn)，我們設(shè)計(jì)了三種精確求解方法，既縮減了問題規(guī)模，又消除了解空間的對(duì)稱性。

（1）子問題性質(zhì)分析

由于板材對(duì)應(yīng)BM可獨(dú)立求解，因此，我們分別求得每個(gè)板材對(duì)應(yīng)的BM目標(biāo)值即可。更進(jìn)一步地，對(duì)于相同規(guī)格（即長、寬、質(zhì)量類型均相同）的板材，由于其BM相同，因此，我們只需要求解不同規(guī)格板材對(duì)應(yīng)的BM，再將解通過板材-托盤進(jìn)行數(shù)量匹配，即可還原成各個(gè)子問題的解。根據(jù)此思路，我們進(jìn)行子問題如下求解方式的設(shè)計(jì)。

（2）子問題求解方式

本部分介紹三種子問題求解方式，如（a）～（c），根本原則是提取不同規(guī)格（即長、寬、質(zhì)量類型至少存在一種不同）的板材模型進(jìn)行求解，并通過板材-托盤匹配關(guān)系還原出子問題的解。子問題求解方式的圖形化表達(dá)，如圖2所示，其中T代表板材規(guī)格。具體說明如下。

（a）基于托盤的歸并且還原

本算法的核心是，在每個(gè)托盤中，提取出不同規(guī)格的板材，并將這些不同的板材打包成一個(gè)集合，得到一個(gè)規(guī)模更小的縮減的子問題。通過CPLEX求解此縮減的問題，再通過板材-托盤數(shù)量關(guān)系線性相加，從而還原出子問題的解?？s減的問題不僅規(guī)模更小，而且不存在解空間對(duì)稱性，因此，求解速度更快。

（b）基于板材池的歸并且還原

算法（a）中，雖然對(duì)于每個(gè)縮減的子問題不存在解空間對(duì)稱性，但是由于不同托盤中存在相同規(guī)格的板材，因此，從全局來說，存在對(duì)于相同BM的重復(fù)求解，這將會(huì)帶來時(shí)間的浪費(fèi)。因此，我們考慮直接將相同規(guī)格的板材打包，命名為“板材池”。對(duì)板材池對(duì)應(yīng)的模型進(jìn)行求解，通過b∈Ωp的匹配關(guān)系，以及板材在托盤中的數(shù)量關(guān)系來進(jìn)行子問題解的還原，即將板材池中與托盤匹配的BM目標(biāo)值線性相加。

（c）基于分解板材池的歸并且還原

算法（b）中，顯然，若板材池規(guī)模過大，求解效率會(huì)降低。因此，我們考慮將板材池進(jìn)行分解求解，分解規(guī)模在100～500之間隨機(jī)產(chǎn)生。由于相同規(guī)格的板材對(duì)應(yīng)的BM相同，因此本算法得到的各BM的解仍是各個(gè)BM的最優(yōu)解?；谶€原操作，可以得到各個(gè)子問題的最優(yōu)解。

5 數(shù)值實(shí)驗(yàn)

本部分包括如下內(nèi)容。首先，我們展示輸入數(shù)據(jù)的規(guī)模。然后，通過CPLEX求解KM的結(jié)果說明，在算例大規(guī)模情況下，直接求解難度較大和設(shè)計(jì)啟發(fā)式算法的必要性。隨后，我們測試了CGH的性能，如計(jì)算效率與可行解的質(zhì)量。最后，我們評(píng)價(jià)了CGH在實(shí)際指標(biāo)（如浪費(fèi)率）上的表現(xiàn)。所有的模型和算法均基于Java編寫，數(shù)值實(shí)驗(yàn)均在Windows服務(wù)器上進(jìn)行，處理器為Xeon E7-8850 2.00GHz，運(yùn)行內(nèi)存為512G，CPLEX版本為12.8.0。

5.1 原始輸入數(shù)據(jù)規(guī)模

本部分展示從該工廠生產(chǎn)管理系統(tǒng)中導(dǎo)出算例的數(shù)據(jù)規(guī)模，總結(jié)如表3所示。算例名稱格式為“原材料_厚度”，如“曲柳_10mm”指原材料為10mm厚的曲柳。由表中結(jié)果可見：算例規(guī)模均較大，變量數(shù)量均超過20萬，遠(yuǎn)超當(dāng)前其他研究中的算例規(guī)模;通過按照板材的長、寬、質(zhì)量類型進(jìn)行歸并，發(fā)現(xiàn)板材種類遠(yuǎn)小于板材數(shù)量，如“曲柳_27mm”算例中有12980個(gè)板材，歸并數(shù)據(jù)顯示其規(guī)格只有1595 種。因此可得兩方面結(jié)論，其一，若用CPLEX直接求解KM，其解空間嚴(yán)重的對(duì)稱性會(huì)嚴(yán)重影響“分支—定界”的效率，從而導(dǎo)致CPLEX難以求解。其二，說明了我們基于按板材規(guī)格縮減的方法求解子問題有意義。我們定義“供給/需求面積比”，即每個(gè)算例中，托盤中所有板材的總面積，除以計(jì)劃生產(chǎn)的產(chǎn)品總面積。結(jié)果中，較大的供需比說明提供板材過多，一定程度上會(huì)導(dǎo)致求解困難，但為了在全局上獲得更高質(zhì)量的解，我們選擇根據(jù)原始輸入數(shù)據(jù)直接進(jìn)行計(jì)算。

5.2 CPLEX性能測試

我們調(diào)用CPLEX12.8.0對(duì)以上算例進(jìn)行求解。按照工廠對(duì)計(jì)算時(shí)間以及對(duì)解的質(zhì)量的要求，我們設(shè)定CPLEX滿足如下條件之一即停止。

（a）達(dá)到最大計(jì)算時(shí)間7200s。

（b）算例上下界界限收斂至1.00%或以下。

實(shí)驗(yàn)結(jié)果如表4所示。

由結(jié)果可見，算例本身規(guī)模較大，且存在嚴(yán)重的解空間對(duì)稱性，導(dǎo)致CPLEX直接求解KM表現(xiàn)較差。因此，亟需開發(fā)能夠快速產(chǎn)生較優(yōu)解的啟發(fā)式算法，便于工程應(yīng)用。

5.3 CGH性能測試

本部分測試CGH的算法性能。我們將三種子問題求解方式對(duì)應(yīng)的CGH算法分別表示為CGH1、CGH2及CGH3，并分別測試如上三個(gè)算例。在列生成迭代時(shí)，每5次迭代調(diào)用一次上界啟發(fā)式算法。我們將CGH的停止條件設(shè)為如下，當(dāng)其中任意一個(gè)滿足時(shí)，停止迭代。

（a）達(dá)到最大計(jì)算時(shí)間：CGH每次迭代的當(dāng)前時(shí)刻達(dá)到或超過7200s。

（b）CGH產(chǎn)生的上界與CG下界的相對(duì)界限收斂至1.00%或以下：計(jì)算方式為GapCGH-CG=UBCGH-LBCGUBCGH×100%，其中UBCGH表示CGH產(chǎn)生的原問題上界，LBCG表示CG產(chǎn)生的原問題下界。

（c）無有效可添加列：當(dāng)所有子問題的目標(biāo)值均大于-10-5時(shí)，視為無有效可添加列。

通過與廠方溝通，我們總結(jié)出他們主要關(guān)注如下評(píng)價(jià)指標(biāo)：

（a）計(jì)算時(shí)間：目前，廠方要求計(jì)算時(shí)間控制在7200s之內(nèi)，計(jì)算效率需要盡可能高。

（b）總成本：即目標(biāo)函數(shù)值或可行解。首先，我們用GapCGH-CG評(píng)價(jià)可行解的質(zhì)量。另外，我們也關(guān)注CGH產(chǎn)生的上界與KM得到的上界（UBKM）的相對(duì)界限，計(jì)算方式為

以及CG產(chǎn)生的下界與LKM得到的下界（LBLKM）的相對(duì)界限，計(jì)算方式為

（c）下料浪費(fèi)率：在“橫截”步驟中，剩余的短條寬度小于最低標(biāo)準(zhǔn)寬度52mm。由于機(jī)器工藝的限制，這些短條無法繼續(xù)被切割，因此，是一種浪費(fèi)，計(jì)算方式為

此外，我們根據(jù)工廠現(xiàn)行下料方式，即按照“先到先服務(wù)”原則，不斷抽取托盤及板材，并按照尚未滿足的最窄的需求進(jìn)行下料。我們計(jì)算了工廠關(guān)于如上算例的實(shí)際的浪費(fèi)率指標(biāo)。統(tǒng)計(jì)結(jié)果如表5和表6，我們基于指標(biāo)（a）～（c），有如下兩點(diǎn)總結(jié)。

（1）解的質(zhì)量與計(jì)算效率：總的來說，三種子問題求解方法均可以產(chǎn)生高質(zhì)量解，且CGH3效率最高?？尚薪赓|(zhì)量方面，對(duì)于算例“曲柳_10mm”，CGH在較短時(shí)間內(nèi)產(chǎn)生的可行解質(zhì)量與CPLEX7200s之內(nèi)產(chǎn)生的可行解質(zhì)量基本相同，且用時(shí)最短在30s之內(nèi)。對(duì)于另外2個(gè)算例，CGH可行解質(zhì)量較CPLEX提高30.00%左右，這顯示了CGH求解大規(guī)模算例時(shí)的有效性。下界方面，CG均可提供比LKM更緊的上界。收斂性方面，CGH可行解距離CG下界的相對(duì)界限均在15.00%之內(nèi)，這在大規(guī)模算例用CPLEX難以求解時(shí)，提供了較好的可行解質(zhì)量評(píng)估標(biāo)準(zhǔn)。效率方面，CGH3效率明顯高于其他兩種方法。CGH2 中，由于其板材池對(duì)應(yīng)的數(shù)學(xué)模型規(guī)模過大，導(dǎo)致CPLEX求解耗時(shí)過多，如算例“曲柳_27mm”，此結(jié)果與我們對(duì)三種縮減方法的分析是一致的。

（2）下料浪費(fèi)率：基于工廠當(dāng)前下料算法，平均下料浪費(fèi)率為27.72%?；贑GH3的求解結(jié)果，平均下料浪費(fèi)率為17.29%?？梢?，我們開發(fā)的CGH 降低平均下料浪費(fèi)率10.43%。 另外，我們發(fā)現(xiàn)了“曲柳_10mm”浪費(fèi)率高的原因：本算例中，板材寬度均為90mm，只能順沖出一條短條，當(dāng)短條寬度與板材寬度相差較大時(shí)，會(huì)產(chǎn)生相對(duì)較多浪費(fèi)，這也提示工廠在購買板材時(shí)可多考慮較寬板材。

綜上，我們基于子問題模型結(jié)構(gòu)性質(zhì)開發(fā)的CGH3優(yōu)于CPLEX，它可以在較短時(shí)間內(nèi)得到更高質(zhì)量的解。CGH3不僅解決了原模型中解的對(duì)稱性缺點(diǎn)，同時(shí)很大程度上縮減了算例規(guī)模，使得大規(guī)模算例可以快速求解。與工廠現(xiàn)行下料方案對(duì)比，CGH3降低平均下料浪費(fèi)率10.43%，帶來成本節(jié)約。

6 結(jié)論與展望

本文基于同某家具廠的實(shí)際生產(chǎn)合作項(xiàng)目，在CSP中考慮了成批上料等現(xiàn)實(shí)生產(chǎn)因素。我們首先基于生產(chǎn)情景建立數(shù)學(xué)模型KM。為了克服大規(guī)模算例的求解困難，我們基于Dantzig-Wolfe 框架，將KM 分解為一個(gè)MP和若干子問題，并基于CG對(duì)LMP進(jìn)行求解，進(jìn)而用基于啟發(fā)式挑選列的CGH方法，生成原問題上界。為了加速CG迭代，通過對(duì)子問題結(jié)構(gòu)的分析，我們發(fā)現(xiàn)子問題的可分支特性，進(jìn)而將子問題分解為可獨(dú)立求解的二級(jí)子問題BM?；诖颂卣鳎覀冮_發(fā)了三種高效的子問題求解方式：基于托盤的縮減且還原，基于板材池的縮減且還原，基于分解板材池的縮減且還原?；趶墓S生產(chǎn)管理系統(tǒng)中導(dǎo)出的實(shí)際算例，我們進(jìn)行數(shù)值實(shí)驗(yàn)，結(jié)果表明，當(dāng)由于問題規(guī)模過大以及解空間對(duì)稱性嚴(yán)重而導(dǎo)致CPLEX 求解性能極差時(shí)，CGH3 可以高效求解此大規(guī)模問題，在較短時(shí)間內(nèi)產(chǎn)生高質(zhì)量的解。如對(duì)于三個(gè)算例，CGH3產(chǎn)生的可行解質(zhì)量與CPLEX可行解相當(dāng)（如稍差2.01%）或更優(yōu)（如質(zhì)量提高30.30%、32.60%），CGH和CG的上下界平均相對(duì)界限為8.99%，且運(yùn)行時(shí)間遠(yuǎn)低于CPLEX。 在實(shí)際的浪費(fèi)率指標(biāo)上，CGH3也有較好表現(xiàn)。通過與工廠現(xiàn)行下料方案相比，CGH3 降低平均下料浪費(fèi)率10.43%。

我們的研究亦有可拓展之處。（1）嘗試其他分解思路，如將KM直接按照板材分解且按照板材挑選下料方案并構(gòu)建上界。（2）板材池分割求解時(shí)，較寬的板材按照較小規(guī)模分解，而較窄板材由于背包約束的解空間較小，單個(gè)BM求解較快，可以按照較大規(guī)模分解。（3）聯(lián)立考慮下料和拼合工序，理論上將產(chǎn)生不會(huì)比當(dāng)前更差的最優(yōu)解。

參 考 文 獻(xiàn)：

[1] Kallrath J， Rebennack S， Kallrath J， et al.. Solving real-world cutting stock-problems in the paper industry： mathematical approaches， experience and challenges[J]. European Journal of Operational Research， 2014， 238（1）： 374-389.

[2] 吳電建，閻春平，李俊，等.而向可加工性的矩形件優(yōu)化下料方法[J].計(jì)算機(jī)集成制造系統(tǒng)，2018，24（6）：1374-1382.

[3] Gilmore P C， Gomory R E. A linear programming approach to the cutting-stock problem[J]. Operations Research， 1961， 9（6）： 849-859.

[4] Gilmore P C， Gomory R E. A linear programming approach to the cutting stock problem-Part II[J]. Operations Research， 1963， 11（6）： 863-888.

[5] Melega G M， de Araujo S A， Jans R. Classification and literature review of integrated lot-sizing and cutting stock problems[J]. European Journal of Operational Research， 2018， 271（1）： 1-19.

[6] Song G P， Kowalczyk D， Leus R. The robust machine availability problem-bin packing under uncertainty[J]. IISE Transactions， 2018， 50（11）： 997-1012.

[7] Bischoff E E， Wascher G. Cutting and packing[J]. European Journal of Operational Research， 1995， 84（3）： 503-505.

[8] Kantorovich L V. Mathematical methods of organizing and planning production[J]. Management Science， 1960， 6（4）： 366-422.

[9] Abuabara A， Morabito R. Cutting optimization of structural tubes to build agricultural light aircrafts[J]. Annals of Operations Research， 2009， 169（1）： 149.

[10] Lee J， Kim B， Johnson A L. A two-dimensional bin packing problem with size changeable items for the production of wind turbine flanges in the open die forging industry[J]. IIE Transactions， 2013， 45（12）： 1332-1344.

[11] 管衛(wèi)利，龔擊，薛煥堂.一維下料問題的一種混合啟發(fā)式算法[J].機(jī)械設(shè)計(jì)與制造，2018，（8）：237-239.

[12] Belov G， Scheithauer G. A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting[J]. European Journal of Operational Research， 2006， 171（1）： 85-106.

[13] Cui Y， Zhao Z. Heuristic for the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns[J]. European Journal of Operational Research， 2013， 231（2）： 288-298.

[14] Furini F， Malaguti E， Durán R M， et al.. A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size[J]. European Journal of Operational Research， 2012， 218（1）： 251-260.

[15] Wuttke D A， Heese H S. Two-dimensional cutting stock problem with sequence dependent setup times[J]. European Journal of Operational Research， 2018， 265（1）： 303-315.

[16] Wang D， Xiao F， Zhou L， et al.. Two-dimensional skiving and cutting stock problem with setup cost based on column-and-row generation[J]. European Journal of Operational Research， 2020， 286（2）： 547-563.

[17] De Carvalho J M V. Exact solution of bin-packing problems using column generation and branch-and-bound[J]. Annals of Operations Research， 1999， 86： 629-659.

[18] Dyckhoff H. A new linear programming approach to the cutting stock problem[J]. Operations Research， 1981， 29（6）： 1092-1104.

3631500338258