■王 迅，陳星艷，陶 濤，戴向東，黃艷麗，歐陽周洲，郝紹平 ，詹秀麗，呂 宙

(1.中南林業(yè)科技大學，湖南長沙 410004；2.農(nóng)林生物質(zhì)綠色加工技術(shù)國家地方聯(lián)合工程研究中心，湖南長沙 410004；3. 木竹資源高效利用省部共建協(xié)同創(chuàng)新中心，湖南長沙 410004；4.歐派家居集團股份有限公司，廣東廣州 510000）

隨著板式定制家具的流行，企業(yè)生產(chǎn)通常采用“多品種小批量”的個性化定制生產(chǎn)模式。但由于個性化定制產(chǎn)品結(jié)構(gòu)和外觀的多樣性，且家具車間調(diào)度大多憑借經(jīng)驗進行[1-3]，給企業(yè)的生產(chǎn)帶來了一定難度，造成了生產(chǎn)效率低下等現(xiàn)象。定制家具的個性化與生產(chǎn)高效性之間的矛盾是定制家具行業(yè)急需解決的難題[4-6]。

遺傳算法是通過模擬自然界中遺傳機理和自然選擇過程而提出的，其優(yōu)點在于在全局解空間具有良好的搜索性能以及自適應(yīng)優(yōu)化等特點，廣泛應(yīng)用于調(diào)度領(lǐng)域[7-8]。本文利用該算法解決板式定制家具相同并行機混合流水車間調(diào)度問題，優(yōu)化目標函數(shù)為最小化最大完工時間，以期提高車間生產(chǎn)效率和設(shè)備資源利用率，為車間提供科學的調(diào)度方案，從而一定程度上解決定制家具產(chǎn)品個性化與生產(chǎn)高效性之間的矛盾。

1 板式定制家具相同并行機混合流水車間調(diào)度問題

1.1 問題描述

■圖1 板式定制家具相同并行機混合流水車間布局圖

板式定制家具相同并行機混合流水車間調(diào)度問題（HFSP）可以描述為：n個具有相同加工路徑的板件經(jīng)過m道工序進行加工，至少有一個加工工序的并行機器數(shù)量大于1，且同一工序并行機的處理性能完全相同，示意圖如圖1所示。已知所有板件的加工時間，問題的目標是要確定n個板件在每個加工工序的加工順序以及對應(yīng)的設(shè)備分配方案，從而使得所有板件的最大總完工時間最小[9-11]。問題的假設(shè)條件如下：

（1）一個板件同一時間不能在多臺設(shè)備上進行加工；

（2）每臺設(shè)備同一時間只能加工一個板件；

（3）每個板件在設(shè)備上的加工時間已知，且加工時間因板件類型的不同而不同；

（4）同一板件的工序之間存在先后約束關(guān)系，不同板件的工序間不存在約束關(guān)系；

（5）在同一臺設(shè)備上切換板件的調(diào)機時間算在加工時間內(nèi)；

（6）不同工序之間有無限的緩沖區(qū)間[12]；

（7）忽略設(shè)備故障等問題。

1.2 問題建模

有關(guān)變量如下，記n為板件數(shù)，j為板件序號，m為工序數(shù)，i為工序序號，q為機器序號，Pji為板件j在工序i加工所需的加工時間，Sji為板件j在工序i的開始加工時間，F(xiàn)ji為板件j在工序i的完工時間，mi為工序i的并行機數(shù)量，Cmax是所有板件的最大總完工時間，設(shè)置整個生產(chǎn)的開始時間為0，L是一個很大的常數(shù)。同時定義以下兩個變量：

建立板式定制家具車間帶相同并行機的混合流水車間調(diào)度數(shù)學模型如下：

上述數(shù)學模型的優(yōu)化目標是使得最大總完工時間最小化，即式（1），對于板式定制家具相同并行機混合流水車間調(diào)度而言，就是要確定板件在各個工序的加工順序，以及每個工序的設(shè)備分配情況，使得Cmax最小。其中：式（2）表示所有板件的最大總完工時間等于板件j在工序i的完工時間集合中最大的那個數(shù)；式（3）用來計算每個板件在任何一個工序的完工時間；式（4）保證每個板件在每個工序只能由該工序的一臺設(shè)備加工；式（5）保證每個板件必須在上一道工序加工完成后才能開始現(xiàn)工序的加工；式（6）和式（7）是對設(shè)備加工容量的約束，即同一臺設(shè)備不能同時加工兩個板件；式（8）是變量約束。

2 板式定制家具相同并行機混合流水車間調(diào)度遺傳算法設(shè)計

2.1 算法原理

遺傳算法是通過模擬自然界中遺傳機理和自然選擇過程而提出的搜索算法，包括繁殖、雜交和突變等現(xiàn)象[13]。求解流程如圖2所示。

2.2 算法設(shè)計

2.2.1 染色體編碼

假設(shè)要加工n個板件，每一個板件要經(jīng)過m道工序，每一道工序的并行機數(shù)量為mi。構(gòu)造一個n×m的編碼矩陣如下所示：

■圖2 遺傳算法流程圖

其中，行表示工序過程,列表示工件序號，染色體基因aij攜帶第i道工序中板件j在哪一臺機器上被加工的信息。通常aij由整數(shù)和小數(shù)兩部分組成,整數(shù)部分表示板件j在工序i的加工設(shè)備序號，小數(shù)部分表示在同一臺設(shè)備上加工發(fā)生沖突后的先后順序，數(shù)值較小的優(yōu)先被加工[14]。

因此，在上述矩陣編碼的基礎(chǔ)上可以構(gòu)造算法的染色體：由m段組成，每一段表示不同的工序，用標識符“0”隔開，每小段含有n個基因，因而每個染色體長度為m*(n-1)?？捎孟率鼍仃嚤硎荆?/p>

2.2.2 種群初始化和適應(yīng)度函數(shù)確定

本文采用產(chǎn)生隨機數(shù)的方式來產(chǎn)生初始解。在本文的車間調(diào)度模型中，目標函數(shù)是尋求所有板件加工完工時最小的總完工時間。因此，本文以最大總完工時間即Cmax的倒數(shù)作為適應(yīng)度函數(shù)，即適應(yīng)度函數(shù)F = 1/Cmax。

2.2.3 選擇操作

本文采用二元錦標賽選擇法，即在當前所選擇的種群中隨機選擇兩個個體為一組，通過比較，適應(yīng)度較大個體被選擇進入下一代進行運算，該策略可有效保留非最優(yōu)個體，有效提升算法的全局搜索性能[15]，從而避免陷入局部最優(yōu)解。

2.2.4 交叉操作

本文中首先依據(jù)一定的交叉概率從種群中隨機選取兩個個體作為父代，并隨機選取兩個不同的基因位置，將兩位置之間的基因進行互換，再根據(jù)原有的父代基因排列順序填補交叉部分中遺失的基因。例如：

隨機選取兩個父代染色體為：

隨機選取兩個不同的基因位置進行交叉操作：

補齊空位后得到子代染色體為：

2.2.5 變異操作

本文中染色體變異方式為單點基因互換，可避免由于交叉操作引起的某些基因的永久性丟失[16-17]，防止算法過早收斂和陷入局部最優(yōu)解。例如：

若父代染色體為：

隨機產(chǎn)生兩個正整數(shù)r1=4，r2=6，進行基因互換得到子代染色體為：

3 實例仿真

本文以某個時期內(nèi)某一板式定制家具車間生產(chǎn)的一批訂單為例，選取這一批次開料后的15塊需要排鉆的板件（分別編號為1-15），這15塊板件經(jīng)過相同的4道生產(chǎn)工序。開料工序由1臺電子開料鋸進行加工，封邊工序由2條加工能力相同的柔性封邊線進行加工，排鉆工序由2臺加工能力相同的六面鉆進行加工，包裝工序由1條自動包裝線進行加工，各板件在不同工序上的加工時間如表1所示（表內(nèi)的單位為秒），求這15塊板件在各個工序上的加工順序。

表1 各板件在各工序上的加工時間表

用python編寫上述遺傳算法的程序。其中，參數(shù)的選擇大多依靠經(jīng)驗值：（1）種群規(guī)模太小時，會導致精度不足且解不穩(wěn)定，種群規(guī)模越大時，雖然越可能找到全局解，但是太大的話會導致性能下降、運行時間變長，一般取20-100；（2）迭代次數(shù)太小時，種群還未成熟，算法不容易收斂，迭代次數(shù)太大時，算法會早熟，繼續(xù)進化只會增加運行時間和資源浪費，一般取100-500；（3）交叉概率太小時，無法有效更新種群，當交叉概率太大時，隨機性增大，容易錯失最優(yōu)個體，一般取0.4-0.99；（4）變異概率太小時，會大大降低種群多樣性，丟失一部分有效基因且不易修復，變異概率太大時，可保證種群多樣性，但容易使算法發(fā)生退化，一般取0.0001-0.1。本文中，選取種群大小N=20，迭代次數(shù)M=400，交叉概率pc=0.6，變異概率pm=0.1。

為確保該遺傳算法的有效性，本文對遺傳算法進行10次獨立實驗，結(jié)果記錄如表2所示（表內(nèi)的單位為秒）：

表2 運行結(jié)果記錄表

其中，遺傳算法迭代結(jié)果最好的一次進化過程即上述第5次迭代結(jié)果如圖3所示，橫坐標代表迭代次數(shù)，縱坐標代表每代個體即加工板件的完工時間。由圖可知，目標函數(shù)隨著種群的進化而逐漸減小，進化到315代左右后，基本收斂于極值。同時，利用python軟件生成了板式定制家具帶相同并行機混合流水車間調(diào)度的甘特圖（圖4），圖中可以看出各板件在各工序上的加工順序以及設(shè)備分配情況。

■圖3 遺傳算法進化曲線圖

■圖4 混合流水車間調(diào)度甘特圖

通過以上仿真數(shù)據(jù)可知，本例的最小化最大總完工時間為428.8秒，各板件具體的加工順序和設(shè)備分配情況如表3所示，1-60表示所有板件開始加工時的時間節(jié)點排序情況，例如14表示在此次生產(chǎn)調(diào)度中，板件5的封邊工序是在第1臺柔性封邊線上進行加工的，它在所有板件全部工序的調(diào)度順序中是14。而在車間實際的生產(chǎn)當中，完成這十五塊板件的總加工時間為465.8秒，總加工時間減少了37秒，生產(chǎn)效率提升了8.6%，縮短了產(chǎn)品的總完工時間。上述的混合流水車間調(diào)度問題只針對15塊板件進行了計算，在實際生產(chǎn)中會有更多的板件，此時只需要在代碼中增加不同板件的加工時間，即可實現(xiàn)更大數(shù)量板件的相同并行機混合流水車間調(diào)度。

表3 板件的加工順序及設(shè)備分配情況表

4 結(jié)論

本文通過對板式定制家具相同并行機混合流水車間調(diào)度問題進行介紹和數(shù)學建模，利用遺傳算法，設(shè)置目標函數(shù)為最小化最大完工時間，對板式定制家具的調(diào)度問題進行了優(yōu)化。通過實際數(shù)據(jù)進行仿真實驗，證明該算法能夠縮短生產(chǎn)時間、提高生產(chǎn)效率，在混合流水車間調(diào)度中求解具有可行性及有效性。