基于模擬退火算法的MTS型實木家具生產調度優化研究

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

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

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

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

■圖1 待加工產品實物圖

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

1 實木家具生產調度產品加工工時的測定方法

實木家具產品的加工工時是模擬退火算法進行生產調度優化的數據基礎，產品的加工工時是指利用各種技術來確定合格工人按作業標準完成產品某一工序所需要的時間[6]。MTS型實木家具企業產品的加工工時的測定，一般采用秒表計時法和綜合類比法兩種方法結合的方式進行。

（1）秒表計時法

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

（2）綜合類比法

綜合類比法是指以家具產品的加工單元為中心，采用統計方法將相同或者類似的加工單元歸類，總結出加工工時表。在掌握家具產品的加工工序和動作分解的基礎上，利用加工工時表組合出產品工序的標準工時。綜合類比法主要用于加工特點具有相似性的類似家具產品和類似的工序[8]。

■圖2 模擬退火算法進化折線圖

2 基于模擬退火算法的MTS型家具生產調度優化

2.1 MTS型家具企業生產調度問題模型描述

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

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

（2）當家具零件的前一道工序加工完成之后才能繼續下一道工序；

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

（4）某個零部件在某個時刻只能在一臺機器設備上加工；

（5）產品的工序順序和加工時間已知；

（6）N個產品在確定加工順序時具有相同的優先級。

2.2 基于數學模型的生產調度問題求解

2.2.1 MTS型實木家具生產調度數學模型

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

■圖3 優化前后的生產調度甘特圖對比

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

2.2.2 算法的偽代碼編寫

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

表1 模擬退火算法的最優參數

2.2.3 實例分析

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

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

表2 產品加工用時表（單位：分鐘）

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

產品A[（1，11）（2，24）（3，29）（4，12）（5，22）（6，29）]

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

產品C[（1，9）（2，18）（3，25）（4，16）（5，16）（6，18）]

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

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

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

根據矩陣，在此生產實例中共有36道工序。假如按照傳統的排序方法，共有720種不同的排序方法，企業安排合理的生產調度的工作量極大[16-17]。鑒于模擬退火算法在組合優化問題中具有良好的表現，利用模擬退火算法對上述實例進行生產調度優化[18-19]。

2.2.4 仿真實驗與結果分析

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

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

上述仿真實驗的樣本數量為6件，在實際生產中樣本的數量會成倍增加，而且不同的產品加工時間也會產生巨大的變化。基于一般經驗法生產調度的難度會進一步增加，而模擬退火算法只需要在新產品的打樣期間記錄各工序所花費的加工工時，將其匯編成帶有加工機器編號和加工時間的矩陣，再轉換成計算機語言輸入到模擬退火算法的程序中，即可得出最優的生產排序方法，具有廣泛的適用性。

3 結語

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