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

郝信燁 劉懋圻 張燦榮 鄭力

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

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

中圖分類號：TB114.1 文獻(xiàn)標(biāo)識碼：A 文章編號：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]）面對的一個重要問題，其以最小化成本為目標(biāo)，通過對庫存板材的切割，來滿足不同尺寸類型的需求[3～5]。合理的下料方案會為實(shí)際生產(chǎn)減少浪費(fèi)，帶來經(jīng)濟(jì)效益。基于同某家具廠合作的實(shí)際生產(chǎn)項(xiàng)目，本文對該廠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)品拼合。在此過程中，需要對如下問題進(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ù)我們所知，本文是首個將托盤成批供料納入CSP的研究。另外，本問題也有算例規(guī)模極大的特點(diǎn)，如算例“曲柳_27mm”具有272730個決策變量。據(jù)統(tǒng)計，現(xiàn)有的大多數(shù)文獻(xiàn)中，模型的變量均遠(yuǎn)小于本文，如Song等[6]的模型中有32580個決策變量。由于CSP本身為NP-hard[7]，且本問題具有額外的復(fù)雜特征，以及算例具有極大規(guī)模，因此，亟需開發(fā)高效、高質(zhì)量的啟發(fā)式算法，在實(shí)際生產(chǎn)中，求解時間受限的情況下使用。我們首先建立了Kantorovich模型（Kantorovich Model， KM）來精準(zhǔn)表達(dá)原問題，但其算例規(guī)模大，且具有解空間對稱等缺點(diǎn)，因此，空間復(fù)雜度較大，且用求解器難以直接求解。為了實(shí)現(xiàn)對本問題的高效求解，我們基于Dantzig-Wolfe 框架對KM按托盤分解，得到1個主問題（Master Problem， MP）與若干子問題，并通過基于列生成（Column Generation， CG）的啟發(fā)式算法（Column Generation-based Heuristic， CGH）生成KM上界。為了加速CG 迭代，通過對模型結(jié)構(gòu)的分析，我們發(fā)現(xiàn)子問題托盤與板材之間可分支求解的特點(diǎn)，進(jìn)而可以將子問題分解為可獨(dú)立求解的二級子問題，即，每個板材對應(yīng)的下料模型，簡稱板材模型（Board Model，BM）。另外，相同規(guī)格的板材BM模型相同。基于此特性，我們設(shè)計了3種子問題求解方式：基于托盤的歸并且還原，基于板材池的歸并且還原，基于分解板材池的歸并且還原。這些求解方式有效地縮減了子問題整體求解規(guī)模，并克服了解空間對稱性的困難。我們從該工廠的生產(chǎn)管理系統(tǒng)中導(dǎo)出實(shí)際數(shù)據(jù)并進(jìn)行測試，結(jié)果表明，我們的算法優(yōu)于商用求解器CPLEX12.8.0，可以在較短時間內(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]最先對CSP進(jìn)行定義并建立的帶有指派類型決策變量的數(shù)學(xué)模型（后續(xù)稱之為Kantorovich模型）。Kantorovich模型直接決策并清楚指示了每塊板材應(yīng)該生產(chǎn)的產(chǎn)品。基于本模型，學(xué)者們開展了一系列研究。Abuabara 和Morabito[9]研究了航空材料工廠的一維CSP，他們建立了Kantorovich模型并直接通過CPLEX求解。Lee等[10]針對產(chǎn)品形狀可變的二維的CSP建立Kantorovich模型，并設(shè)計了基于背包問題模型的啟發(fā)式算法來求解。管衛(wèi)利等[11]基于Kantorovich 模型，對單規(guī)格和多規(guī)格線材切割進(jìn)行數(shù)值實(shí)驗(yàn)。在Kantorovich模型中，當(dāng)很多板材之間具有相同規(guī)格時，解空間會存在很嚴(yán)重的對稱性，即解不同但目標(biāo)函數(shù)值相同。此缺點(diǎn)對于基于“分支—定界”框架來求解整數(shù)規(guī)劃的求解器（如，CPLEX）來說，會引發(fā)長時間無效的分支，當(dāng)問題規(guī)模過大，會難以求解。另外，雖然Kantorovich模型線性松弛產(chǎn)生的下界在需求寬度種類較少的情況下質(zhì)量較高，但其空間復(fù)雜度較大，建立模型需要占用較多內(nèi)存和相對較長時間。

下料問題的第二種模型是Gilmore和Gomory[3，4]提出的基于下料方案的模型（后續(xù)稱之為Gilmore-Gomory模型），此模型克服了Kantorovich模型中對稱性的缺點(diǎn)，同時，其線性松弛模型提供比線性松弛的KM（Linearly-relaxed KM， LKM）更緊的下界。與Kantorovich模型不同，Gilmore-Gomory模型并沒有直接指出每塊板材產(chǎn)出的產(chǎn)品，而是基于每塊板材可以切割得到的產(chǎn)品的組合（即下料方案）進(jìn)行選擇。但在本模型中，下料方案隨著產(chǎn)品規(guī)模而指數(shù)級增長，因此模型中會有很多列。為了解決此問題，Gilmore和Gomory[3，4]提出了CG算法，來動態(tài)地生成列，進(jìn)而對線性松弛的Gilmore-Gomory模型精確求解。之后，可基于此線性松弛解對原問題進(jìn)行啟發(fā)式或精確求解。Belov和Scheithauer[12]研究了一維、單規(guī)格板材的CSP，他們建立了Gilmore-Gomory模型，并通過分支—定價框架進(jìn)行求解。Cui 和Zhao[13]研究了二維的單規(guī)格CSP。在該研究中，下料得到的產(chǎn)品可以旋轉(zhuǎn)，此特征使得問題更加復(fù)雜。Furini等[14]研究了多規(guī)格板材、兩階段一刀切的二維CSP，并設(shè)計了基于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來對原問題進(jìn)行描述。為了高效求解原問題，我們通過Dantzig-Wolfe框架將其分解為一個主問題（Master Problem， MP，即，Gilmore-Gomory模型）和若干子問題，并用CG 求解線性松弛的主問題（Linearly-relaxed Master Problem， LMP）來得到較緊的下界。通過對子問題性質(zhì)分析，我們設(shè)計了子問題不同的求解方式，從而加速CG迭代過程。最后，我們通過啟發(fā)式挑選列，生成原問題的高質(zhì)量上界。

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

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

3.1 問題描述

我們研究的是在某工廠實(shí)際生產(chǎn)中的考慮成批供料和材料等級的大規(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個托盤和12980塊板材，其Kantorovich模型具有272730個決策變量，模型規(guī)模遠(yuǎn)超大多數(shù)現(xiàn)有研究。

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

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

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

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

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

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

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

4 求解方法設(shè)計

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

4.1 Dantzig-Wolfe分解模型

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

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

（2）子問題模型

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

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

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

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

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

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

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

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

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

（2）子問題求解方式

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

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

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

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

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

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

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

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

本部分包括如下內(nèi)容。首先，我們展示輸入數(shù)據(jù)的規(guī)模。然后，通過CPLEX求解KM的結(jié)果說明，在算例大規(guī)模情況下，直接求解難度較大和設(shè)計啟發(fā)式算法的必要性。隨后，我們測試了CGH的性能，如計算效率與可行解的質(zhì)量。最后，我們評價了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個板材，歸并數(shù)據(jù)顯示其規(guī)格只有1595 種。因此可得兩方面結(jié)論，其一，若用CPLEX直接求解KM，其解空間嚴(yán)重的對稱性會嚴(yán)重影響“分支—定界”的效率，從而導(dǎo)致CPLEX難以求解。其二，說明了我們基于按板材規(guī)格縮減的方法求解子問題有意義。我們定義“供給/需求面積比”，即每個算例中，托盤中所有板材的總面積，除以計劃生產(chǎn)的產(chǎn)品總面積。結(jié)果中，較大的供需比說明提供板材過多，一定程度上會導(dǎo)致求解困難，但為了在全局上獲得更高質(zhì)量的解，我們選擇根據(jù)原始輸入數(shù)據(jù)直接進(jìn)行計算。

5.2 CPLEX性能測試

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

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

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

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

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

5.3 CGH性能測試

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

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

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

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

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

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

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

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

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

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

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

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

綜上，我們基于子問題模型結(jié)構(gòu)性質(zhì)開發(fā)的CGH3優(yōu)于CPLEX，它可以在較短時間內(nèi)得到更高質(zhì)量的解。CGH3不僅解決了原模型中解的對稱性缺點(diǎn)，同時很大程度上縮減了算例規(guī)模，使得大規(guī)模算例可以快速求解。與工廠現(xiàn)行下料方案對比，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 分解為一個MP和若干子問題，并基于CG對LMP進(jìn)行求解，進(jìn)而用基于啟發(fā)式挑選列的CGH方法，生成原問題上界。為了加速CG迭代，通過對子問題結(jié)構(gòu)的分析，我們發(fā)現(xiàn)子問題的可分支特性，進(jìn)而將子問題分解為可獨(dú)立求解的二級子問題BM。基于此特征，我們開發(fā)了三種高效的子問題求解方式：基于托盤的縮減且還原，基于板材池的縮減且還原，基于分解板材池的縮減且還原。基于從工廠生產(chǎn)管理系統(tǒng)中導(dǎo)出的實(shí)際算例，我們進(jìn)行數(shù)值實(shí)驗(yàn)，結(jié)果表明，當(dāng)由于問題規(guī)模過大以及解空間對稱性嚴(yán)重而導(dǎo)致CPLEX 求解性能極差時，CGH3 可以高效求解此大規(guī)模問題，在較短時間內(nèi)產(chǎn)生高質(zhì)量的解。如對于三個算例，CGH3產(chǎn)生的可行解質(zhì)量與CPLEX可行解相當(dāng)（如稍差2.01%）或更優(yōu)（如質(zhì)量提高30.30%、32.60%），CGH和CG的上下界平均相對界限為8.99%，且運(yùn)行時間遠(yuǎn)低于CPLEX。 在實(shí)際的浪費(fèi)率指標(biāo)上，CGH3也有較好表現(xiàn)。通過與工廠現(xiàn)行下料方案相比，CGH3 降低平均下料浪費(fèi)率10.43%。

我們的研究亦有可拓展之處。（1）嘗試其他分解思路，如將KM直接按照板材分解且按照板材挑選下料方案并構(gòu)建上界。（2）板材池分割求解時，較寬的板材按照較小規(guī)模分解，而較窄板材由于背包約束的解空間較小，單個BM求解較快，可以按照較大規(guī)模分解。（3）聯(lián)立考慮下料和拼合工序，理論上將產(chǎn)生不會比當(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ī)集成制造系統(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è)計與制造，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