■康友冰，王張恒，孫德林 Kang Youbing & Wang Zhangheng & Sun Delin

(中南林業(yè)科技大學(xué)材料科學(xué)與工程學(xué)院，湖南長沙，410004）

MTS型實木家具企業(yè)作為一種典型的家具生產(chǎn)企業(yè)，產(chǎn)品種類繁多，且制作工藝復(fù)雜，導(dǎo)致家具生產(chǎn)調(diào)度和生產(chǎn)控制的難度較大。隨著家具更新?lián)Q代的速度不斷加快，實木家具產(chǎn)品的生命周期越來越短，這對家具生產(chǎn)調(diào)度提出了更高的要求。同時，由于交貨期不斷的縮短，進(jìn)一步加大了家具企業(yè)生產(chǎn)調(diào)度的難度[1]。我國家具企業(yè)經(jīng)過多年的努力，裝備水平已經(jīng)逐漸趕上發(fā)達(dá)國家，但在生產(chǎn)調(diào)度理論和實踐經(jīng)驗方面還存在著較大的差距,企業(yè)中仍普遍存在著生產(chǎn)隨意性較大、生產(chǎn)調(diào)度不夠科學(xué)以及作業(yè)排序混亂等問題。

目前國內(nèi)外，遺傳算法和蟻群等智能優(yōu)化算法已經(jīng)被運(yùn)用于解決家具生產(chǎn)調(diào)度問題，并且取得了一定的成果。例如：呂玉翠[2]利用啟發(fā)式算法對板式家具的生產(chǎn)調(diào)度問題進(jìn)行求解，優(yōu)化了板式家具生產(chǎn)調(diào)度。丁傳讓[3]研究了基于蟻群算法的家具生產(chǎn)調(diào)度方法，使家具生產(chǎn)調(diào)度的效率得到了很大的提升；沈國鋒[4]利用遺傳算法對美式家具的生產(chǎn)調(diào)度方法進(jìn)行了優(yōu)化研究，提升了生產(chǎn)調(diào)度的效率。模擬退火算法(Simulated Annealing, SA)是模仿金屬退火過程的一種高效的啟發(fā)式優(yōu)化算法，基本思想是在一個固定的溫度下，算法會從一個狀態(tài)隨機(jī)的搜索到另一個狀態(tài)，然后由不斷變化的概率值來判斷當(dāng)前解是否為最優(yōu)解，隨著溫度的不斷下降直到降低到一個最低溫度，搜索過程將會以概率1停留到最優(yōu)解。模擬退火算法具有很強(qiáng)的全局優(yōu)化性能和魯棒性，它的搜索方式簡單有效，既避免了數(shù)值算法的高計算量和蟻群算法收斂速度慢的缺點，又避免了遺傳算法局部搜索算法過早收斂于局部最優(yōu)解的缺點[5]。根據(jù)實木家具的生產(chǎn)特點，模擬退火算法的原理與實木家具生產(chǎn)調(diào)度問題的優(yōu)化過程極為相似。

■圖1 待加工產(chǎn)品實物圖

因此，為了解決MTS型家具企業(yè)存在著生產(chǎn)隨意性較大、生產(chǎn)調(diào)度不夠科學(xué)以及作業(yè)排序混亂等問題。本文將模擬退火算法運(yùn)用到MTS型實木家具生產(chǎn)調(diào)度問題中，利用秒表計時法和綜合類比法獲得產(chǎn)品的加工工時，并采用python軟件進(jìn)行仿真實驗，以最小化最大完工時間為目標(biāo)函數(shù)進(jìn)行優(yōu)化，利用模擬退火算法找到一種科學(xué)的生產(chǎn)調(diào)度方法，以提高M(jìn)TS型實木家具生產(chǎn)調(diào)度的合理性、科學(xué)性和秩序性。

1 實木家具生產(chǎn)調(diào)度產(chǎn)品加工工時的測定方法

實木家具產(chǎn)品的加工工時是模擬退火算法進(jìn)行生產(chǎn)調(diào)度優(yōu)化的數(shù)據(jù)基礎(chǔ)，產(chǎn)品的加工工時是指利用各種技術(shù)來確定合格工人按作業(yè)標(biāo)準(zhǔn)完成產(chǎn)品某一工序所需要的時間[6]。MTS型實木家具企業(yè)產(chǎn)品的加工工時的測定，一般采用秒表計時法和綜合類比法兩種方法結(jié)合的方式進(jìn)行。

（1）秒表計時法

秒表計時法是根據(jù)家具生產(chǎn)現(xiàn)場作業(yè)的內(nèi)容，以自主設(shè)計的表格為基礎(chǔ)，用秒表進(jìn)行計時，將獲得的數(shù)據(jù)記錄在表格中，每個產(chǎn)品的工序工時需重復(fù)計時多次，計算出平均值，但工人進(jìn)行圖紙校核、劃線、調(diào)機(jī)以及產(chǎn)品零件的待料等其他操作時，不計入加工時間內(nèi)[7]。

（2）綜合類比法

綜合類比法是指以家具產(chǎn)品的加工單元為中心，采用統(tǒng)計方法將相同或者類似的加工單元?dú)w類，總結(jié)出加工工時表。在掌握家具產(chǎn)品的加工工序和動作分解的基礎(chǔ)上，利用加工工時表組合出產(chǎn)品工序的標(biāo)準(zhǔn)工時。綜合類比法主要用于加工特點具有相似性的類似家具產(chǎn)品和類似的工序[8]。

■圖2 模擬退火算法進(jìn)化折線圖

2 基于模擬退火算法的MTS型家具生產(chǎn)調(diào)度優(yōu)化

2.1 MTS型家具企業(yè)生產(chǎn)調(diào)度問題模型描述

MTS型家具生產(chǎn)調(diào)度的模式是基于生產(chǎn)庫存，由設(shè)計、銷售和生產(chǎn)等部門共同確定下一個生產(chǎn)周期所需要生產(chǎn)家具產(chǎn)品的類型和數(shù)量。根據(jù)這個特點，MTS型家具企業(yè)生產(chǎn)調(diào)度問題可以總結(jié)為作業(yè)車間調(diào)度問題（Job shop scheduling problem ,以下簡稱JSP），即整個家具加工系統(tǒng)有N個產(chǎn)品等待加工，一共有M個加工工序，需要M個加工機(jī)器，各工序的加工時間和每個產(chǎn)品的加工工序順序已確定，每個產(chǎn)品必須嚴(yán)格按照給定的順序加工[9-11]。生產(chǎn)調(diào)度優(yōu)化的最終目標(biāo)是確定N個產(chǎn)品的加工順序，在滿足所有約束條件的情況下使得完成所有加工工序的總加工時間最短。綜上所述，可以將MTS型家具企業(yè)JSP問題的約束條件描述為：

（1）家具零部件的每道工序必須在固定的機(jī)器上加工；

（2）當(dāng)家具零件的前一道工序加工完成之后才能繼續(xù)下一道工序；

（3）某個時刻某個機(jī)器只能加工一個家具零部件；

（4）某個零部件在某個時刻只能在一臺機(jī)器設(shè)備上加工；

（5）產(chǎn)品的工序順序和加工時間已知；

（6）N個產(chǎn)品在確定加工順序時具有相同的優(yōu)先級。

2.2 基于數(shù)學(xué)模型的生產(chǎn)調(diào)度問題求解

2.2.1 MTS型實木家具生產(chǎn)調(diào)度數(shù)學(xué)模型

在不考慮插單的情況下，企業(yè)在接受多個同等重要的訂單時，需要根據(jù)訂單合理進(jìn)行生產(chǎn)調(diào)度，面臨如何進(jìn)行訂單的排序才能使生產(chǎn)車間在最少的時間內(nèi)加工完全部產(chǎn)品。因此，將MTS型家具企業(yè)作業(yè)車間生產(chǎn)調(diào)度問題的優(yōu)化目標(biāo)設(shè)為最小化最大完工時間。達(dá)到這個目標(biāo)只需要找到最后一臺機(jī)器的完工時間最小值。令G為此數(shù)學(xué)模型的目標(biāo)函數(shù)，(i，j)表示作業(yè)i的第j個工序。Sij和Eij分別表示(i，j)的加工起始時刻和加工時間[12-13]。Ck為第k臺機(jī)器的完工時間，則問題的數(shù)學(xué)模型如下：

■圖3 優(yōu)化前后的生產(chǎn)調(diào)度甘特圖對比

公式①為目標(biāo)函數(shù)，使最遲完工的機(jī)器加工時間最短；公式②表示1個作業(yè)只能在加工完成前一道工序后才可以加工后一道工序；公式③表示每個零件開始加工第1道工序的起始加工時刻大于或等于0。

2.2.2 算法的偽代碼編寫

根據(jù)問題的數(shù)學(xué)模型，利用PyCharm Community Edition 2021.2.2軟件進(jìn)行算法代碼的編寫，需要設(shè)置的參數(shù)包括：最大溫度、最小溫度、鏈長、冷卻耗時，由于模擬退火算法對參數(shù)的設(shè)置沒有明確的規(guī)定，通過已有文獻(xiàn)[14]對不同參數(shù)組合的研究，確定優(yōu)化參數(shù)如表1所示。

表1 模擬退火算法的最優(yōu)參數(shù)

2.2.3 實例分析

某新中式家具公司木工生產(chǎn)車間接到了來自設(shè)計部的6個產(chǎn)品需要加工，如圖1所示，分別是A、B、C、D、E、F。

根據(jù)生產(chǎn)工序，這6個產(chǎn)品分別要經(jīng)過下料、刨光、砂光、開榫、鉆孔和銑型等加工工序，分別用編號1、2、3、4、5、6表示[15]。利用秒表計時法和綜合類比法得出了各產(chǎn)品的加工工時如表2所示。

表2 產(chǎn)品加工用時表（單位：分鐘）

根據(jù)各產(chǎn)品的加工時間和機(jī)器，對每個產(chǎn)品的每道工序進(jìn)行編號處理，編號（m,n）中m代表當(dāng)前的工序必須要在第m臺機(jī)器上加工，n表示當(dāng)前的工序的加工時間，加工時間的單位為1，機(jī)器的作業(yè)編號從1開始。例：產(chǎn)品X[（m1，n1）（m2，n2）（m3，n3）……（mx，ny）] ，根據(jù)上述編號的規(guī)則構(gòu)建相應(yīng)的矩陣。

產(chǎn)品A[（1，11）（2，24）（3，29）（4，12）（5，22）（6，29）]

產(chǎn)品B[（1，16）（2，29）（3，32）（4，19）（5，27）（6，28）]

產(chǎn)品C[（1，9）（2，18）（3，25）（4，16）（5，16）（6，18）]

產(chǎn)品D[（1，12）（2，34）（3，27）（4，18）（5，25）（6，26）]

產(chǎn)品E[（1，14）（2，25）（3，26）（4，11）（5，19）（6，21）]

產(chǎn)品F[（1，10）（2，26）（3，24）（4，17）（5，13）（6，19）]

根據(jù)矩陣，在此生產(chǎn)實例中共有36道工序。假如按照傳統(tǒng)的排序方法，共有720種不同的排序方法，企業(yè)安排合理的生產(chǎn)調(diào)度的工作量極大[16-17]。鑒于模擬退火算法在組合優(yōu)化問題中具有良好的表現(xiàn)，利用模擬退火算法對上述實例進(jìn)行生產(chǎn)調(diào)度優(yōu)化[18-19]。

2.2.4 仿真實驗與結(jié)果分析

根據(jù)表1和表2，進(jìn)行仿真實驗，從圖2中可以看出算法在進(jìn)化到13代以后，最優(yōu)解趨近于極值，說明此時得到了最優(yōu)解。程序的運(yùn)行結(jié)果輸出值包括best_x和best_y，其中best_x代表產(chǎn)品的最優(yōu)加工順序，即為A-B-D-C-E-F, best_y表示最小化最大完工時間，即產(chǎn)品的最小化最大完工時間為254min。

利用CAD軟件輸出了最優(yōu)排序方案的生產(chǎn)調(diào)度甘特圖，通過甘特圖可以清楚地看到最優(yōu)的加工順序、每件產(chǎn)品的加工進(jìn)程和某道工序的設(shè)備空閑時間。為了驗證模擬退火算法對MTS型家具生產(chǎn)調(diào)度的科學(xué)性，將模擬退火算法仿真實驗的排序結(jié)果（圖2b）與該實木家具車間實際采用的一般經(jīng)驗法所得排序結(jié)果（圖2a）對比，通過圖中的數(shù)據(jù)可以得出，模擬退火算法得到的排序方案的最小完工時間為254min，相比于一般經(jīng)驗法得出的排序方法的用時減少了23min，整體的生產(chǎn)效率提升了8.3%。通過以上對結(jié)果的比較分析，證明了模擬退火算法在求解MTS家具企業(yè)JSP問題的可行性和有效性。

上述仿真實驗的樣本數(shù)量為6件，在實際生產(chǎn)中樣本的數(shù)量會成倍增加，而且不同的產(chǎn)品加工時間也會產(chǎn)生巨大的變化?；谝话憬?jīng)驗法生產(chǎn)調(diào)度的難度會進(jìn)一步增加，而模擬退火算法只需要在新產(chǎn)品的打樣期間記錄各工序所花費(fèi)的加工工時，將其匯編成帶有加工機(jī)器編號和加工時間的矩陣，再轉(zhuǎn)換成計算機(jī)語言輸入到模擬退火算法的程序中，即可得出最優(yōu)的生產(chǎn)排序方法，具有廣泛的適用性。

3 結(jié)語

生產(chǎn)調(diào)度問題是實木家具企業(yè)生產(chǎn)過程中的重點問題，科學(xué)合理的生產(chǎn)調(diào)度對提高企業(yè)生產(chǎn)效率具有重要影響。家具產(chǎn)品排序是家具生產(chǎn)調(diào)度的核心，利用智能優(yōu)化算法可以高效地解決此類組合優(yōu)化問題。根據(jù)MTS型實木家具企業(yè)的生產(chǎn)數(shù)據(jù)，利用模擬退火算法程序輸出了最優(yōu)的排序方法，證實了模擬退火算法在解決MTS型實木家具企業(yè)生產(chǎn)調(diào)度問題的可行性，企業(yè)管理人員可以參考該方法得到的結(jié)果制定生產(chǎn)調(diào)度方案，可以有效地縮短產(chǎn)品的總加工時間，提高產(chǎn)品的生產(chǎn)效率。