考慮成批供料的大規模下料問題

郝信燁 劉懋圻 張燦榮 鄭力

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

關鍵詞：板材下料;成批供料;大規模混合整數規劃;列生成;歸并且還原

中圖分類號：TB114.1 文獻標識碼：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）是眾多行業中（如造紙業[1]、造船業[2]）面對的一個重要問題，其以最小化成本為目標，通過對庫存板材的切割，來滿足不同尺寸類型的需求[3～5]。合理的下料方案會為實際生產減少浪費，帶來經濟效益。基于同某家具廠合作的實際生產項目，本文對該廠CSP進行研究。該廠拼合板產品生產過程如下，盛有不同規格板材的托盤被挑選并從倉庫中運到線上，工人將刀具預設為若干種標準寬度，并在板材寬度方向上進行水平切割（順沖工序），產生短條;之后，在垂直方向上切去影響美觀的木料疤痕（橫截工序），產生橫截小塊，并將橫截小塊指接成長條;最終，用從長條上切下的拼合塊進行產品拼合。在此過程中，需要對如下問題進行決策，包括，如何挑選托盤來權衡運輸成本和板材多樣性，如何水平切割板材，如何選擇寬度來拼合最終產品，從而降低板材浪費率。當前，工人們按照經驗進行決策，材料浪費較為嚴重。

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

2 文獻綜述

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

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

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

3 問題描述與數學模型

本部分我們對實際生產情景進行描述，并建立KM。

3.1 問題描述

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

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

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

步驟3 順沖。工人把選擇的板材放在下料機上，按照設定好的若干種標準切割寬度（52mm， 62mm， 81mm和89mm）進行水平切割，產生短條。

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

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

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

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

（a）大規模：廠方的生產管理系統中導出的數據顯示，托盤和板材的數量非常多，導致算例規模較大。如，算例“曲柳_27mm”含有150個托盤和12980塊板材，其Kantorovich模型具有272730個決策變量，模型規模遠超大多數現有研究。

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

（c）材料等級：為了實現產品差異化，以應對消費者不同的偏好，本工廠將最終生產的拼合板產品分為不同等級。每個板材、短條都標有質量類型（即A，B，C，D），橫截小塊、長條、產品都有質量等級（如1，2，3，4，數字越小，等級越高）。關系如下：板材經過橫截工序產生的短條與板材的質量類型相同;在步驟4橫截中，不同質量類型的短條會按不同比例（即出料率）產生不同質量等級的橫截小塊，如表1 所示;某類型的橫截小塊只能指接入寬度等于它且等級不高于它的長條中;長條切得的拼合小塊的等級與其相同;拼合小塊的等級必須不低于它拼合而成的產品。需要說明的是，表1 中，出料率之和均小于1，因為板材必有疤痕帶來的物料損耗。

目前，工廠要求按照“最小余料”原則選擇產品拼合寬度，即對每種產品，選擇最終去掉余料最少的寬度的小塊進行拼合，且小塊的等級要與產品相同?；诖艘巹t，我們首先將產品需求轉化為相應寬度和等級的長條，稱為“延米數”。以此為生產需求，關注下料方案的設計。另外，我們假設除了必要的去余料與去疤痕過程，其他生產過程沒有物料損失。

3.2 數學模型

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

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

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

4 求解方法設計

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

4.1 Dantzig-Wolfe分解模型

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

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

（2）子問題模型

目標函數（13）包括托盤運輸成本、板材使用成本，以及與對偶變量有關的目標。約束（14）～（17）對應KM中的（2）～（5）。

4.2 初始列和上界構建方法

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

同時，我們設計基于LRMP的一種上界構造方法。本方法的基本原則是，當LRMP求解完畢，針對每個托盤p∈P，我們將mp∈Θp對應的解值作為概率，來隨機抽取該托盤p的一個下料方案，并用該方案來滿足需求延米數。當所有托盤抽取的方案無法滿足需求時，我們從第一個托盤順序篩查未切割或剩余足夠寬的板材，并按照構造初始列中提到的方法進行切割和需求滿足。

初始列和上界構造詳細流程如圖2所示。圖2 初始列（a）和上界（b）構造流程

4.3 子問題性質分析與算法設計

本部分基于子問題的模型結構，首先對子問題性質進行分析?；谄渫斜P選擇—板材選擇決策可分支特性，及BM模型特點，我們設計了三種精確求解方法，既縮減了問題規模，又消除了解空間的對稱性。

（1）子問題性質分析

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

（2）子問題求解方式

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

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

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

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

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

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

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

5 數值實驗

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

5.1 原始輸入數據規模

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

5.2 CPLEX性能測試

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

（a）達到最大計算時間7200s。

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

實驗結果如表4所示。

由結果可見，算例本身規模較大，且存在嚴重的解空間對稱性，導致CPLEX直接求解KM表現較差。因此，亟需開發能夠快速產生較優解的啟發式算法，便于工程應用。

5.3 CGH性能測試

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

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

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

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

通過與廠方溝通，我們總結出他們主要關注如下評價指標：

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

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

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

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

此外，我們根據工廠現行下料方式，即按照“先到先服務”原則，不斷抽取托盤及板材，并按照尚未滿足的最窄的需求進行下料。我們計算了工廠關于如上算例的實際的浪費率指標。統計結果如表5和表6，我們基于指標（a）～（c），有如下兩點總結。

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

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

綜上，我們基于子問題模型結構性質開發的CGH3優于CPLEX，它可以在較短時間內得到更高質量的解。CGH3不僅解決了原模型中解的對稱性缺點，同時很大程度上縮減了算例規模，使得大規模算例可以快速求解。與工廠現行下料方案對比，CGH3降低平均下料浪費率10.43%，帶來成本節約。

6 結論與展望

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

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

參 考 文 獻：

[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] 吳電建，閻春平，李俊，等.而向可加工性的矩形件優化下料方法[J].計算機集成制造系統，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] 管衛利，龔擊，薛煥堂.一維下料問題的一種混合啟發式算法[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