龐凱民，朱 波，張宏碩，劉 寧，張連富

（1.昆明理工大學(xué) 機電工程學(xué)院，云南 昆明 650500；2.沈陽機床（集團）有限責(zé)任公司，遼寧 沈陽 110142）

0 引言

線型材料在下料時只需考慮長度方向尺寸，屬于一維下料范疇。開展一維優(yōu)化下料研究，對提升線型材料利用率、降低生產(chǎn)成本具有重要意義［1-2］。一維優(yōu)化下料問題在學(xué)術(shù)界已經(jīng)研究多年，近年不斷有優(yōu)化算法提出，如黃秀玲等［3］采用蟻群算法和遺傳混合模擬退火算法求解多規(guī)格一維型材優(yōu)化下料問題；Pitombeiraneto 等［4］提出基于固定優(yōu)化策略和隨機局部搜索相結(jié)合算法。這些研究都聚焦在求解算法上，尋求一種有效的搜索算法，從巨大的下料解空間中搜索出近似最優(yōu)解，由此獲得更高的原材料利用率。與此同時，有些學(xué)者面向企業(yè)實際下料需求特性開展研究，從算法的優(yōu)化運用角度提出提升原材料利用率的方法，集中式下料就是這樣的一種典型方法。該方法通過將多個具有相似需求的下料任務(wù)（來自多個項目或者同行業(yè)的多個制造企業(yè)）進行整合，使得多個較小規(guī)模的下料問題融合為少數(shù)較大規(guī)模的下料問題，由此增加零件之間互補和契合的可能性，有利于獲得更優(yōu)的下料方案，從而提升原材料利用率，降低設(shè)備投入成本和開機成本。集中式下料研究有：張穎［5］將集中下料生產(chǎn)與實際鋼材下料系統(tǒng)相結(jié)合，有效降低了下料成本；張洪等［6］針對某小批量產(chǎn)品在前期由于技術(shù)狀態(tài)反復(fù)、工藝過程與材料消耗變更等問題，在優(yōu)化工藝的同時引入集中下料思想，有效降低了產(chǎn)品成本。

為了更好滿足客戶的個性化需求，產(chǎn)品大規(guī)模定制、多批次、小批量生產(chǎn)成為制造企業(yè)的主要生產(chǎn)模式，該模式?jīng)Q定了制造企業(yè)下料具有如下特點：下料批次多、批次下料需求相似、單個批次下料規(guī)模不大、后續(xù)批次下料需求不明確等。針對這些下料特點，如果只針對每一批次進行優(yōu)化而不考慮余料的使用（在本文中定義為批次下料）是難以獲得較好的原材料總體利用率的。因此，有學(xué)者提出基于庫存的下料，即將每次下料產(chǎn)生的余料進庫存，每次下料優(yōu)先使用庫存余料，使余料能夠得到有效利用。相關(guān)研究有：管衛(wèi)利等［7］提出一種混合啟發(fā)式下料算法，將庫存余料參與到后續(xù)的下料過程；王婷婷等［8］提出一種運用動態(tài)規(guī)劃與枚舉結(jié)合的方法的優(yōu)化下料算法，可有效降低生產(chǎn)成本。但是，由于后續(xù)批次下料需求未知，實質(zhì)是被動利用余料，無法充分挖掘多次下料需求互補和契合的可能性。如果能對后續(xù)多個批次的下料需求進行準確預(yù)測，就可以按照集中式下料思想將多個批次的小規(guī)模下料任務(wù)整合成少數(shù)較大規(guī)模的下料任務(wù)，也即一次下料結(jié)合庫存多余零件滿足多次需求，從而實現(xiàn)更優(yōu)的材料總體利用率。相對集中式下料對下料需求的橫向整合，這是對下料需求的縱向整合，要解決的關(guān)鍵問題是對后續(xù)批次下料需求的準確預(yù)測。目前關(guān)于需求預(yù)測方法研究較多，其中深度學(xué)習(xí)模型之長短期記憶網(wǎng)絡(luò)（LSTM）不僅能處理時間序列信息的延續(xù)性問題，還能應(yīng)對長序列訓(xùn)練過程中的梯度消失和梯度爆炸問題，對解決預(yù)測問題具有顯著優(yōu)越性；王旭東等［9］提出一種基于LSTM 的單變量短期家庭電力需求預(yù)測模型，以此預(yù)測短期家庭的用電情況；林友芳等［10］提出一種基于LSTM 的出發(fā)地——目的地（OD）客運需求預(yù)測模型，通過顯式建?？瓦\需求時間序列內(nèi)部的時間依賴關(guān)系和序列之間的空間依賴關(guān)系來預(yù)測未來一段時間所有OD 的客運需求量；李穎宏等［11］針對不同地域間出行的自流動性和關(guān)聯(lián)性，提出基于LSTM 的共享單車需求預(yù)測模型，以此預(yù)測在不同時間段內(nèi)共享單車的需求量；王曉飛等［12］基于Prophet-LSTM 模型，通過將PM2.5 日值濃度序列分解成趨勢、周期和隨機波動分量后，對隨機波動分量建立LSTM 模型，以此對PM2.5 濃度進行預(yù)測。

本文提出一種融合下料需求預(yù)測的多批次線型材料優(yōu)化下料方法。以LSTM 為預(yù)測工具對后續(xù)批次下料需求進行預(yù)測，根據(jù)預(yù)測結(jié)果按照集中式下料思想整合下料任務(wù)，通過經(jīng)典的列生成法進行求解，并輔之以貪心算法補償下料，解決預(yù)測誤差導(dǎo)致的問題，最終實現(xiàn)原材料總體利用率最高目標。相比于傳統(tǒng)的線型材料優(yōu)化下料模型，本文提出的LSTM-CSP 模型從算法優(yōu)化角度出發(fā)，對生產(chǎn)周期內(nèi)后續(xù)零件需求量進行預(yù)測與集成，將多個較小規(guī)模的下料問題融合為少數(shù)較大規(guī)模的下料問題，保持需求量在不同批次間的關(guān)聯(lián)。相比于傳統(tǒng)的預(yù)測方法，LSTM 對于時間序列信息的預(yù)測精度更高?；谙嚓P(guān)理論，本文構(gòu)建了方法模型（LSTM-CSP），并將某制造企業(yè)型材下料的實際需求數(shù)據(jù)生成仿真數(shù)據(jù)集，開展仿真實驗，驗證了模型的有效性。

1 相關(guān)理論及方法

1.1 一維優(yōu)化下料問題數(shù)學(xué)模型

一維優(yōu)化下料問題原型可描述為：給定K種原材料，每種原材料長度和價格分別為Li、Vi，（i=1,2…K）；給定M種需要下料生成的零件，每種零件的長度為lj（j=1,2…M），di為第i種零件的需求量，設(shè)在滿足所有零件的下料需求前提下如何使消耗的原材料總成本最小。構(gòu)建數(shù)學(xué)模型如下：

其中，目標函數(shù)ZC是消耗原材料的價格總和；VK為第K種原材料價格；K為原材料種數(shù)；為采用第j種下料方式使用原材料K的數(shù)量；nK為第K種原材料的下料方案總數(shù)；di為第i種零件需求量；為使用第j種下料方式在第K種原材料上獲得的第i種零件數(shù)量；為 第K種原材料上的一種可行的下料方式，通過求解一維背包問題得到，作為一個新的列參與到列生成法的迭代運算中。

1.2 列生成法

列生成法是一種求解大規(guī)模線性規(guī)劃問題的解析算法，可有效降低變量的基變換次數(shù)，提升求解效率。優(yōu)化下料是典型的NP 問題，列生成法將一維優(yōu)化下料問題（主問題）限制到一個變量少、規(guī)模小的限制主問題（RMP）上，并對其進行求解［13-14］。所得解為RMP 的最優(yōu)解而非主問題的最優(yōu)解，因此需要通過一個子問題去檢查是否存在未進基的變量使RMP 獲得更好的解，即通過求解子問題來獲取進基變量，并添加相應(yīng)的列到RMP 中重新求解。當該變量存在時，將其添加到限制主問題中再次進行迭代求解；當不存在這樣的變量時，即找到了問題的最優(yōu)解。

主問題轉(zhuǎn)化為限制主問題時，將一些變量強制限制為非基變量，通過子問題判斷檢驗數(shù)σj=cj-cB B-1aj來找到進基的非基變量并將其列添加到RMP 中再次求解［15］。通過將RMP 轉(zhuǎn)化為對應(yīng)的對偶問題，可以進一步縮小RMP中的變量［16］，更方便得到cB B-1。列生成法流程如圖1 所示。

Fig.1 Flow of column generation method圖1 列生成法流程

1.3 LSTM 神經(jīng)網(wǎng)絡(luò)

長短期記憶人工神經(jīng)網(wǎng)絡(luò)（LSTM）是一種改良的遞歸神經(jīng)網(wǎng)絡(luò)，不僅能有效處理時間序列信息的延續(xù)性問題［17］，還通過在隱藏層單元增添3 個信息控制單元有效解決了長序列訓(xùn)練過程中的梯度消失和梯度爆炸問題［18］。

當前時刻為t時，輸出值h(t)不僅與輸入x(t)有關(guān)，還與上一時刻的輸出值h(t-1)有關(guān)。LSTM 的隱藏層單元A可將上一時刻輸出狀態(tài)h(t-1)傳輸給下一時刻，由上一時刻狀態(tài)h(t-1)和當前輸入x(t)共同決定當前輸出狀態(tài)h(t)。LSTM 在隱藏單元層內(nèi)通過增加3 個控制單元（輸入門，遺忘門，輸出門）來控制整個細胞的活動狀態(tài)，判斷信息是否保留。輸入門、遺忘門、輸出門分別控制輸入狀態(tài)、輸出狀態(tài)和記憶細胞狀態(tài)，由此完成對前一狀態(tài)的更新［19］，其表達式如下：

實驗組44例糖尿病患者中男26例,女18例,男女比例為13:9,患者年齡在35歲至79歲,平均年齡在(45.6±3.6)歲,平均病程在(2.3±0.5)月,其中有11例患者為Ⅰ型糖尿病患者,有33例患者為Ⅱ型糖尿病患者。對照組44例糖尿病患者中男27例,女17例,男女比例為27:17,患者年齡在39歲至77歲,平均年齡在(44.8±3.5)歲,平均病程在(2.2±0.4)月,其中有13例患者為Ⅰ型糖尿病患者,有31例患者為Ⅱ型糖尿病患。兩組患者在年齡、性別比例、病程等一般資料上數(shù)據(jù)差異小(P>0.05)。

式中，W(t)為權(quán)重系數(shù)矩陣，i(t)的權(quán)重系數(shù)矩陣為Wix(t)，同理，b(t)為偏置矩陣，i(t)的偏置矩陣為bi(t)，σ為sigmoid函數(shù)，tan 為雙曲正切函數(shù)，而狀態(tài)信息C(t)、隱藏層輸出h(t)和網(wǎng)絡(luò)輸出y(t)可表達為：

每個序列索引位置過程可歸結(jié)為：更新遺忘門輸出、更新輸入門兩部分輸出、更新細胞狀態(tài)、更新輸出門輸出、更新當前序列索引預(yù)測輸出。LSTM 工作原理如圖2 所示。

Fig.2 Overall flow of LSTM圖2 LSTM 整體流程

2 多批次優(yōu)化下料模型

融合LSTM 預(yù)測需求的線型材料多批次優(yōu)化下料模型——LSTM-CSP 模型由3 個模塊構(gòu)成，分別為零件需求預(yù)測模塊、優(yōu)化下料模塊和補償下料模塊，其工作流程如圖3 所示。

零件需求預(yù)測模塊對每種零件的歷史需求量進行統(tǒng)計生成訓(xùn)練集，訓(xùn)練出長短期記憶網(wǎng)絡(luò)（LSTM）來對未來一個主生產(chǎn)計劃周期內(nèi)（本文根據(jù)企業(yè)調(diào)研情況確定為7 天）的需求量進行預(yù)測，并將預(yù)測結(jié)果提供給后續(xù)的優(yōu)化下料模塊。該模塊中，LSTM 根據(jù)其自身特點，通過控制門對數(shù)據(jù)進行流向控制，將序列信息（不同零件的需求量）進行循環(huán)并預(yù)測下一個批次中不同零件需求量。

優(yōu)化下料模塊匯總預(yù)測的各個批次零件需求，構(gòu)建一維優(yōu)化下料問題，并利用列生成法進行求解，求解步驟如下：①將各個零件的預(yù)測需求量集成；②將零件總體需求量作為約束帶入優(yōu)化下料模型；③采用啟發(fā)式算法構(gòu)造初始解；④將初始解帶入到LSTM-CSP 模型中；⑤采用列生成法求解；⑥判斷預(yù)測集成的零件需求量是否滿足零件的實際需求量，若滿足則退出優(yōu)化下料模塊；若不滿足則轉(zhuǎn)入補償下料模塊。

補償下料模塊用于解決零件需求預(yù)測存在誤差和下料零件需求必須滿足之間的矛盾。在下料過程中，首先在每種原材料上分別進行下料，得到一個初始的下料解，并將其加入到模型中，并采用列生成法進行迭代求解，從而得出最優(yōu)下料方案。

Fig.3 Flow of LSTM-CSP model圖3 LSTM-CSP 模型流程

3 仿真實驗

3.1 實驗數(shù)據(jù)集

對某金屬門窗企業(yè)的鋁型材下料工序進行調(diào)研，獲取其典型原材料和下料零件規(guī)格，如表1 所示。

對每種零件的實際需求量進行統(tǒng)計。每種零件收集到2 815條數(shù)據(jù)，其中，1-2 000條作為訓(xùn)練數(shù)據(jù)，2 001-2 808條作為測試數(shù)據(jù)，剩余的7 條作為零件實際需求量，數(shù)據(jù)如表2 所示。

3.2 實驗結(jié)果與分析

3.2.1 零件需求預(yù)測性能實驗

對需求的準確預(yù)測是本模型實現(xiàn)的核心，因此首先對模型的預(yù)測性能進行實驗測試。在實驗過程中發(fā)現(xiàn)LSTM-CSP 算法的預(yù)測窗口（即步長λ）對預(yù)測性能有影響?？紤]到反向傳播的有效性和訓(xùn)練的難度，通常以訓(xùn)練樣本的一半作為基礎(chǔ)步長設(shè)置。前期實驗結(jié)果表明，λ=1 350時預(yù)測精度達到最高。為探究步長對模型預(yù)測精度的影響，本文分別選擇λ=750，λ=1 350 和λ=1 900 時對LSTMCSP 算法進行對比實驗。

Table 1 Data of raw materials and parts表1 原材料與零件數(shù)據(jù)

Table 2 Actual demand data of parts表2 零件實際需求數(shù)據(jù)

本文使用平均絕對百分誤差、均方根誤差和決定系數(shù)作為模型預(yù)測性能的評價指標［20］。

（1）平均絕對百分誤差（MPAE）。MAPE 不僅計算真實值與預(yù)測值之間的差值，還考慮了該差值與真實值的比例。

（2）均方根誤差（RMSE）。方根誤差對預(yù)測值誤差大小十分敏感，能夠很好地體現(xiàn)預(yù)測的精準度。

（3）決定系數(shù)（R2score）。決定系數(shù)用于判斷回歸方程的擬合程度，可以用于衡量模型預(yù)測能力，決定系數(shù)越大表示模型的預(yù)測性能越好，計算公式如下：

在λ=750、λ=1 350 和λ=1 900 時在測試集上進行測試，4 種零件預(yù)測結(jié)果評價指標如表3 所示。

當決定系數(shù)R2超過0.85 即可認為模型具有較好的預(yù)測性能［21］。通過需求預(yù)測性能實驗可以看出，LSTM-CSP（λ=750，1 350，1 900）具有良好的預(yù)測性能，其中λ=1 350時，4 種零件整體預(yù)測效果最好。對比3 次實驗發(fā)現(xiàn)，λ=1 350 時其均方根誤差（RMSE）和平均絕對百分誤差（MPAE）要小于λ=750 和λ=1 900 的值。

Table 3 Evaluation index of LSTM-CSP表3 LSTM-CSP 的評價指標

選取5 個連續(xù)的主生產(chǎn)計劃（35 天）進行實驗，當λ=1 350 時，部分零件的預(yù)測結(jié)果擬合程度如圖4 所示。

Fig.4 Fitting figures of prediction of cutting parts圖4 零件的預(yù)測結(jié)果擬合程度

LSTM 網(wǎng)絡(luò)在處理時間序列信息的延續(xù)性問題時，需要將λ個數(shù)據(jù)加入到細胞中。當λ從零開始增大時，細胞中有關(guān)數(shù)據(jù)增加，其預(yù)測性能不斷提高。但是LSTM 網(wǎng)絡(luò)的隱藏層信息容量（隱藏單元個數(shù)）是有限的，當λ增大到一定界限后會超過其飽和點，算法會出現(xiàn)過擬合現(xiàn)象，對后續(xù)數(shù)據(jù)不敏感，從而預(yù)測性能隨之下降。此次需求預(yù)測性能實驗中，當λ=750 時，LSTM 網(wǎng)絡(luò)的隱藏層信息容量未達到飽和點，其預(yù)測性能未達到最優(yōu)；當λ=1 900 時，LSTM網(wǎng)絡(luò)的隱藏層信息容量超過飽和點，出現(xiàn)過擬合，其預(yù)測性能降低。因此，在使用LSTM-CSP 時需要選擇合適的預(yù)測窗口λ。

在LSTM-CSP 中，不同的預(yù)測窗口會對預(yù)測精度產(chǎn)生影響，進而影響到下料的原材料利用率和原材料總成本。3 種預(yù)測窗口（λ=750、1 350、1 900）下原材料利用的總成本與利用率如表4 所示。

Table 4 LSTM-CSP blanking scheme under different forecast windows表4 不同預(yù)測窗口下LSTM-CSP 下料方案

通過零件需求預(yù)測性能實驗發(fā)現(xiàn)，LSTM-CSP（λ=1 350）在原材料利用率上比LSTM-CSP（λ=750）和LSTMCSP（λ=1 900）都有大幅度提升。隨著原材料利用率的提升，其成本也隨之減少。因此，本文在優(yōu)化性能對比實驗中選擇LSTM-CSP（λ=1 350）作為實驗?zāi)Ｐ汀?/p>

3.2.2 優(yōu)化下料性能比較實驗

為了驗證所提模型的有效性，以單次下料（追求每個批次下料最優(yōu)，不考慮余料的使用）和基于庫存下料（追求每個批次下料最優(yōu)，將余料納入庫存并在下次下料時優(yōu)先使用）作為對照，進行對比實驗。對比的指標分別為原材料利用率和原材料總成本。其中：

原材料利用率=零件總長度/原材料總長度

原材料總成本=原材料使用根數(shù)*原材料單價

單次下料算法對7 個批次進行優(yōu)化下料，每次完成一個批次；基于庫存下料算法對7 個批次的優(yōu)化下料問題進行下料，每一個批次下料完成后將余料加入到庫存中，并在下一批次中優(yōu)先使用庫存余料。兩者的下料方案總成本如表5 所示。

Table 5 Single blanking and optimization scheme based on inventory blanking algorithm表5 單次下料和基于庫存下料算法優(yōu)化方案

表6 給出每次下料中詳細的預(yù)測需求。其中，零件1生產(chǎn)663件，零件2生產(chǎn)679件，零件3生產(chǎn)622件，零件4生產(chǎn)602件，零件5生產(chǎn)645件，零件6生產(chǎn)603件，零件7生產(chǎn)612 件。表7 給出每種原材料的下料用量與利用率。

Table 6 Parts forecast demand data表6 零件預(yù)測需求數(shù)據(jù)

對比實際需求量后發(fā)現(xiàn)，零件1多生產(chǎn)2件，零件2少生產(chǎn)4件，零件3少生產(chǎn)6件，零件4多生產(chǎn)4件，零件5多生產(chǎn)5件，零件7 多生產(chǎn)8 件；因此，對少生產(chǎn)的零件再次下料。使用原材料5 和原材料3 進行補償下料，兩者各使用1根。表8 給出了LSTM-CSP（λ=1 350）算法的原材料利用率和原材料總成本。

Table 7 Optimal blanking scheme of LSTM-CSP（λ=1 350）algorithm表7 LSTM-CSP（λ=1 350）算法優(yōu)化下料方案

Table 8 Cost of blanking scheme of LSTM-CSP（λ=1 350）algorithm表8 LSTM-CSP（λ=1 350）算法下料方案成本

通過優(yōu)化性能對比實驗發(fā)現(xiàn)，LSTM-CSP 算法在原材料利用率上比單次下料和基于庫存下料算法都有大幅度提升。隨著原材料利用率提升，其成本也隨之減少。相比于單次下料，LSTM-CSP 算法下料所得出的原材料成本更低，減少了14 963.4 元。LSTM-CSP 結(jié)合了集中下料思想，將零件的需求量進行縱向集中，擴大多批次型材優(yōu)化下料問題的解空間。相比基于庫存余料的型材優(yōu)化下料算法，單獨考慮了庫存來擴大解空間范圍，結(jié)果是LSTM-CSP 方法更加有效合理。

4 結(jié)語

本文針對多批次線型材料優(yōu)化下料問題提出了一種融合LSTM 需求預(yù)測的下料方法，構(gòu)建了相應(yīng)模型LSTMCSP。該模型利用LSTM 對后續(xù)多個批次的零件需求量進行預(yù)測，將預(yù)測的需求整合成一個優(yōu)化下料問題并利用列生成法進行求解，同時通過貪婪法對因預(yù)測誤差造成的下料零件數(shù)量不足進行補償下料?；谀承筒募庸て髽I(yè)的實際下料數(shù)據(jù)生成仿真數(shù)據(jù)集，進行仿真實驗驗證。優(yōu)化下料性能比較實驗結(jié)果表明，相比傳統(tǒng)的按批次下料和基于庫存下料方法，本文方法使線型材料多批次下料的原材料總體利用率得到提高，總成本顯著減少。其中，與按批次下料方法相比提升了0.141 7%，金額減少了14 963.4 元；相比基于庫存下料方法提升了0.031 3%，金額減少了14 332.4元。本文還對LSTM-CSP 算法中預(yù)測窗口λ 進行了研究，選取適當?shù)摩?不僅可以有效降低時間復(fù)雜度，還可降低原材料總成本，提高原材料利用率。實驗表明，本文方法能夠有效提升線型材料多批次優(yōu)化下料性能。后續(xù)將繼續(xù)探索該方法在二維原材料優(yōu)化下料中的應(yīng)用。