徐宗煌，徐劍莆，李世龍，林慧雅，許美燕

（1.福州理工學院 應用科學與工程學院，福建 福州 350506；2.福州理工學院 計算與信息科學學院，福建 福州 350506；3.福州理工學院 商學院，福建 福州 350506 ）

本文討論的問題和應用的數(shù)據(jù)均來源于2019 年第十六屆五一數(shù)學建模競賽B 題.木板切割，實際上是屬于二維下料優(yōu)化問題，其主要應用在機械加工、切割下料以及工廠車間布局等制造生產(chǎn)加工領域[1].由于二維下料優(yōu)化問題自身的復雜性，在實際生產(chǎn)應用中，往往會造成原料的大量浪費，從而提高產(chǎn)品成本.因此，如何提高原材料的利用率而節(jié)省產(chǎn)品加工成本，具有非常重要的實用價值.

從數(shù)學計算復雜性理論看，木板切割的優(yōu)化問題屬于NP 完全問題[2].目前，國內(nèi)外許多學者對二維下料優(yōu)化問題進行了諸多研究，主要是采用啟發(fā)式算法、禁忌搜索算法、遺傳算法以及模擬退火算法等大量的優(yōu)化方法.本文基于循環(huán)嵌套啟發(fā)式貪心算法、遺傳模擬退火算法以及價值修正的順序啟發(fā)式算法等優(yōu)化方法，分別對切割單個產(chǎn)品、多個產(chǎn)品以及考慮生產(chǎn)任務需求的木板切割優(yōu)化方案進行了探究分析.

1 模型假設

在問題求解過程中，考慮到實際情況與簡化計算的需要，提出以下假設：1）將木板和產(chǎn)品的長度和寬度均看作是矩形；2）在切割過程中，木板厚度和割縫寬度忽略不計；3）該批木板的材質分布均勻，不會影響切割產(chǎn)品的效果；4）所給的木板和產(chǎn)品尺寸均為真實有效.

2 單個產(chǎn)品木板最優(yōu)切割方案

2.1 研究思路

在一塊木板上只切割P1 產(chǎn)品，首先利用循環(huán)嵌套式的啟發(fā)式算法，使得沿木板四條邊方向上的利用率達到最優(yōu)；再結合Packing 問題的貪心算法，以木板利用率最高為優(yōu)化目標，逐層優(yōu)化，最終得到單個產(chǎn)品的最優(yōu)切割方案.

2.2 模型建立

設木板尺寸為L×W，P1 產(chǎn)品尺寸為l×w，要使木板切割盡可能多的P1，應盡量利用l 和w 的各種組合，使得L 和W 方向上的利用率盡可能高，即對L 和W 邊上同時對l 和w 進行組合優(yōu)化[3]，使得木板四條邊的尺寸利用達到最優(yōu).其優(yōu)化示意圖如圖1.

圖1 基于循環(huán)嵌套啟發(fā)式算法的優(yōu)化示意圖

2.2.1 確定目標函數(shù) 顯然，最優(yōu)切割方案的目的是為了使木板的利用率最高，令μ 為木板的利用率；N 為木板切割P1 產(chǎn)品的數(shù)量，則P1 產(chǎn)品的最優(yōu)切割方案的目標函數(shù)為

2.2.2 確定約束條件 如圖1 所示，當木板上L 邊上切割了m 個l 邊，則可以再切割n=[（L-ml）/w]個w邊；而當右W 邊上切割了i 個l 邊，則還可切割w 邊的個數(shù)為j=[（W-il）/w]；同理，可根據(jù)木板上L 邊上l 的個數(shù)p 和右W 邊上l 的個數(shù)s 分別確定各自邊上w 的個數(shù)q 和t，結合問題的要求與已知條件，主要考慮以下3 個約束條件.

1) 約束條件1

基于保證木板在L 邊和W 邊的利用率，即要保證木板四條邊上所留的空隙不能再放入P1 產(chǎn)品的較小邊，即w 邊，則該約束條件為

2) 約束條件2

基于i 和t 以及p 和n 之間的約束條件為

式(3)中，“[ ]”表示取整符號.

3) 約束條件3

基于保證在切割時不能出現(xiàn)P1 產(chǎn)品之間發(fā)生干涉的情況，該約束條件為

2.3 問題求解

基于以上分析，利用在貨物裝載和木材下料等領域應用廣泛的二維矩形Packing 問題的貪心算法[4-7]，同時結合循環(huán)嵌套式的啟發(fā)式算法[8-9]，以木板利用率最高為優(yōu)化目標，由外及里，逐層優(yōu)化，如圖2 所示.利用MATLAB 編程得到P1 產(chǎn)品的最優(yōu)方案切割圖，如圖3 所示.最優(yōu)的切割方案為：P1 產(chǎn)品的數(shù)量為59 件，木板利用率為98.297 9%.

圖2 模型主程序流程圖

圖3 P1 產(chǎn)品的最優(yōu)方案切割圖

3 多個產(chǎn)品木板最優(yōu)切割方案

3.1 研究思路

考慮到P1 和P3 產(chǎn)品的切割次序和切割方向是影響木板切割利用率最重要的因素，將遺傳算法和模擬退火算法結合起來形成自適應遺傳模擬退火算法[10-11].這樣不僅可以大大提高計算的效率，而且可以避免陷入局部最優(yōu)，從而在木板上切割P1 和P3 產(chǎn)品可以取得比較理想的結果，同時給出木板利用率由高到低排序的前3 種切割方案.

3.2 模型建立

3.2.1 確定目標函數(shù) 通過以上分析，顯然，最優(yōu)切割方案使木板的利用率最高.令μ為木板的利用率，Ni為切割第i 種產(chǎn)品的數(shù)量，則最優(yōu)切割方案的目標函數(shù)為

3.2.2 確定約束條件 同樣的，已知木板尺寸為L×W，產(chǎn)品尺寸為li×wi（i=1,3），即P1 產(chǎn)品尺寸為l1×w1，P3 產(chǎn)品尺寸為l3×w3，Ni為切割第i 種產(chǎn)品的數(shù)量.而mi表示第i 種產(chǎn)品橫放時所需的行數(shù)，ni表示第i種產(chǎn)品豎放時所需的行數(shù)，xi表示豎放時一行的產(chǎn)品個數(shù)，yi表示橫放時一行的產(chǎn)品個數(shù)，ri=0 表示該產(chǎn)品的豎放方式，ri=1 表示該產(chǎn)品的橫放方式.結合問題的要求與已知條件，主要考慮以下兩個約束條件.

1) 約束條件1

基于保證木板在L 邊和W 邊方向上，P1 和P3 產(chǎn)品尺寸和不能超過木板尺寸，則該約束條件為

式(6)中，k 表示有k 種產(chǎn)品.

2) 約束條件2

基于在切割P1 和P3 產(chǎn)品時，其數(shù)量關系必須滿足以下限制約束條件

3.3 問題求解

利用自適應遺傳模擬退火算法[12]從一組隨機產(chǎn)生的初始解（初始群體）開始全局最優(yōu)解的搜索來產(chǎn)生P1 和P3 產(chǎn)品的切割次序以及切割方向，其主要步驟如下.

3.3.1 設計基因編碼 為降低算法復雜性，采用十進制編碼方式對木板切割進行優(yōu)化，設有n 個切割產(chǎn)品，則切割產(chǎn)品次序編號為1，2，…，n，第i 個切割產(chǎn)品的編號為i，則這n 個待切割產(chǎn)品的一個排列為δ=[x1,x2,…,xn]，其中xi表示排列δ 中第i 個切割產(chǎn)品的編號.由于各個產(chǎn)品在切割過程中可以90°旋轉，因此在排列δ 中為各個切割產(chǎn)品增加旋轉變量ri，即

3.3.2 設計適應度函數(shù) 問題的目標在于提高木板的利用率，因此采用最優(yōu)切割方案的目標函數(shù)式(5)作為適應度函數(shù)，即

式(9)中，Xi為種群中的某一個個體，代表唯一的產(chǎn)品切割方案，因此f（Xi）即為切割序列Xi的木板利用率，f（Xi）值越大，表明木板切割方案最優(yōu).

3.3.3 交叉和變異操作 采用一種自適應調整交叉和變異概率的方法來改善算法的行為和性能，同時利用以下概率調整公式

來調整種群中的某一個個體Xi的交叉和變異概率.式(10)中：Pc和Pm分別為該算法的交叉和變異概率；fb（X）、fw（X）和f（Xi）分別表示每一代所有個體中最優(yōu)、最差個體以及Xi的適應度值.

3.3.4 模擬退火操作 對經(jīng)過交叉和變異操作后生成的新種群個體Xi，基于Metropolis 的接受準則，計算新個體被接受的概率，其接受準則為

式(11)中，fi(T)為個體基本變換前適應度；fj(T)為個體基本變換后適應度；T 為當前溫度.

3.3.5 構造初始種群的個體 一半通過優(yōu)先級函數(shù)產(chǎn)生，一半通過隨機數(shù)作為優(yōu)先級產(chǎn)生，優(yōu)先級函數(shù)公式為

式（12）中，Pi為第i 個產(chǎn)品基因優(yōu)先級；pr為該產(chǎn)品長寬比值所占權重；ps為產(chǎn)品面積所占權重且滿足pr+ps=1；函數(shù)生成的隨機數(shù)Ri∈（0，1）.

利用MATLAB 編程，將木板、P1 和P3 產(chǎn)品的尺寸輸入，可得到P1 和P3 產(chǎn)品的切割方案，圖4 所示為木板利用率由高到低排序的前3 種方案切割圖.木板利用率前3 的切割方案為：1) P1 產(chǎn)品的數(shù)量為0件，P3 產(chǎn)品的數(shù)量為48 件，木板利用率為99.172 3%；2) P1 產(chǎn)品的數(shù)量為43 件，P3 產(chǎn)品的數(shù)量為13件，木板利用率為98.500 0%；3)P1 產(chǎn)品的數(shù)量為59 件，P3 產(chǎn)品的數(shù)量為0 件，木板利用率為98.297 9%.

4 考慮生產(chǎn)任務需求的最優(yōu)切割方案

4.1 研究思路

在生產(chǎn)任務需求一定的情況下，考慮到順序啟發(fā)式算法可以在木板切割產(chǎn)品過程中，隨著產(chǎn)品的生成數(shù)量不斷的增加，其切割所需剩余量也發(fā)生相應變化.但傳統(tǒng)的SHP 算法[13-14]在生成木板切割方案時存在一定的缺陷，它容易使得好的切割方案在前面出現(xiàn)，而導致后面的切割方案的材料利用率偏低.采用順序價值修正策略[15-17]，依次生成各個切割方案，并根據(jù)該切割方案中產(chǎn)生的產(chǎn)品數(shù)來修正產(chǎn)品生產(chǎn)任務剩余量，重復此過程，直至所有產(chǎn)品剩余的生產(chǎn)任務均為零，從而得到木板總利用率最高的切割方案，其主要流程圖如圖5 所示.

圖5 順序啟發(fā)式算法流程圖

4.2 模型建立

假設初始化各個產(chǎn)品的價值為產(chǎn)品各自的面積，則生成切割方案可根據(jù)單位面積價值的大小確定，且產(chǎn)品的當前待切割方案為Pj=[a1j,a2j,…，anj]，aij為該方式中含產(chǎn)品i 的個數(shù)，i=1,2，…，n.而每生成一個切割方案都通過

式(13)中aij＞0，si為產(chǎn)品i 的面積；p＞1 為控制參數(shù)；g1和g2為價值修正的控制系數(shù)，g1+g2=1，且滿足

式(14)中，di為產(chǎn)品i 的生產(chǎn)任務為產(chǎn)品i 剩余的工作任務需求；Ω 為隨機產(chǎn)生，Ω?且

式(13)可寫成

4.3 問題求解

通過以上分析，利用MATLAB 編程，將木板的尺寸、P1～P4 產(chǎn)品的尺寸以及生產(chǎn)任務輸入，得到木板總利用率最高的切割方案，圖6 所示為完成P1～P4 產(chǎn)品生產(chǎn)任務的木板切割方案圖.表1 為考慮生產(chǎn)任務需求的最優(yōu)切割方案.

圖6 最優(yōu)方案切割圖

表1 考慮生產(chǎn)任務需求的最優(yōu)切割方案

由表1 可以看出，當需要同時完成P1～P4 產(chǎn)品的生產(chǎn)任務時，需要7 種切割方案才能使木板的總利用率最高.此時木板的數(shù)量為139 塊，總利用率為97.757 7%.

5 結論

本文基于循環(huán)嵌套啟發(fā)式貪心算法、遺傳模擬退火算法以及價值修正的順序啟發(fā)式算法等優(yōu)化方法，分別對切割單個產(chǎn)品、多個產(chǎn)品以及考慮生產(chǎn)任務需求的木板切割優(yōu)化方案進行了探究分析.在保證思路嚴謹?shù)那疤嵯?，基于啟發(fā)式算法化繁為簡，大大降低了算法的計算復雜度，可操作性強，最終得到較為理想的切割方案，對機械加工、切割下料以及工廠車間布局等制造生產(chǎn)加工的過程有一定理論指導和參考價值.