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

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

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

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

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

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

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

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

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

（1）秒表計(jì)時(shí)法

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

（2）綜合類比法

綜合類比法是指以家具產(chǎn)品的加工單元為中心，采用統(tǒng)計(jì)方法將相同或者類似的加工單元?dú)w類，總結(jié)出加工工時(shí)表。在掌握家具產(chǎn)品的加工工序和動(dòng)作分解的基礎(chǔ)上，利用加工工時(shí)表組合出產(chǎn)品工序的標(biāo)準(zhǔn)工時(shí)。綜合類比法主要用于加工特點(diǎ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)庫(kù)存，由設(shè)計(jì)、銷售和生產(chǎn)等部門共同確定下一個(gè)生產(chǎn)周期所需要生產(chǎn)家具產(chǎn)品的類型和數(shù)量。根據(jù)這個(gè)特點(diǎn)，MTS型家具企業(yè)生產(chǎn)調(diào)度問題可以總結(jié)為作業(yè)車間調(diào)度問題（Job shop scheduling problem ,以下簡(jiǎn)稱JSP），即整個(gè)家具加工系統(tǒng)有N個(gè)產(chǎn)品等待加工，一共有M個(gè)加工工序，需要M個(gè)加工機(jī)器，各工序的加工時(shí)間和每個(gè)產(chǎn)品的加工工序順序已確定，每個(gè)產(chǎn)品必須嚴(yán)格按照給定的順序加工[9-11]。生產(chǎn)調(diào)度優(yōu)化的最終目標(biāo)是確定N個(gè)產(chǎn)品的加工順序，在滿足所有約束條件的情況下使得完成所有加工工序的總加工時(shí)間最短。綜上所述，可以將MTS型家具企業(yè)JSP問題的約束條件描述為：

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

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

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

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

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

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

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

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

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

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

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

2.2.2 算法的偽代碼編寫

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

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

2.2.3 實(shí)例分析

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

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

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

根據(jù)各產(chǎn)品的加工時(shí)間和機(jī)器，對(duì)每個(gè)產(chǎn)品的每道工序進(jìn)行編號(hào)處理，編號(hào)（m,n）中m代表當(dāng)前的工序必須要在第m臺(tái)機(jī)器上加工，n表示當(dāng)前的工序的加工時(shí)間，加工時(shí)間的單位為1，機(jī)器的作業(yè)編號(hào)從1開始。例：產(chǎn)品X[（m1，n1）（m2，n2）（m3，n3）……（mx，ny）] ，根據(jù)上述編號(hào)的規(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)實(shí)例中共有36道工序。假如按照傳統(tǒng)的排序方法，共有720種不同的排序方法，企業(yè)安排合理的生產(chǎn)調(diào)度的工作量極大[16-17]。鑒于模擬退火算法在組合優(yōu)化問題中具有良好的表現(xiàn)，利用模擬退火算法對(duì)上述實(shí)例進(jìn)行生產(chǎn)調(diào)度優(yōu)化[18-19]。

2.2.4 仿真實(shí)驗(yàn)與結(jié)果分析

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

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

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

3 結(jié)語(yǔ)

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