大規(guī)模柔性作業(yè)車間組批調(diào)度及求解方法研究

尹 慢，王 爽，張 劍，鄒益勝

（西南交通大學(xué)先進(jìn)設(shè)計與制造技術(shù)研究所，四川 成都 610031）

1 引言

不超過20×50（機(jī)床×工件）的車間調(diào)度問題為中小規(guī)模調(diào)度問題[1]，大規(guī)模車間調(diào)度問題則有以下幾種情況[2]：（1）工件數(shù)J>50，機(jī)器數(shù) M>20 時；（2）當(dāng) J≤50，M>20，J×M>1000 時；（3）當(dāng) J>50，M≤20，J×M>1000時。不少學(xué)者針對作業(yè)車間調(diào)度問題提出很多求解效果較好的優(yōu)化方法[3]，但是求解規(guī)模通常都是中小規(guī)模[4]。大多數(shù)優(yōu)化算法因其求解效率和質(zhì)量問題，不能直接用于求解大規(guī)模調(diào)度問題。目前解決大規(guī)模調(diào)度的方法有：智能優(yōu)化算法、拉格朗日松弛分解法、基于問題分解法[4]。

各種分解法和智能優(yōu)化算法首先被應(yīng)用于規(guī)模不斷增大的車間調(diào)度問題。文獻(xiàn)[5]采用拉格朗日分解法，將調(diào)度問題的數(shù)學(xué)模型分解成若干個獨立的調(diào)度子問題，分別求出各個子問題的解，然后將其解構(gòu)成原問題的解。文獻(xiàn)[6]通過將機(jī)器分解為不同的加工單元，降低了求解的難度。文獻(xiàn)[7-8]都采用了移動瓶頸機(jī)分解的方法，在滿足瓶頸工序調(diào)度的前提下，非瓶頸工序進(jìn)行快速調(diào)度，從而降低大規(guī)模作業(yè)車間調(diào)度問題的復(fù)雜度。文獻(xiàn)[9-10]將調(diào)度的總時間劃分成若干個時間區(qū)間，從而將調(diào)度問題分解成若干個子問題，每個子問題與一個時間區(qū)間對應(yīng)。這些方法的優(yōu)點是能較好的表征動態(tài)調(diào)度問題，對動態(tài)大規(guī)模調(diào)度問題有較好的適應(yīng)性，但會出現(xiàn)死鎖現(xiàn)象。

隨著工件數(shù)、機(jī)器數(shù)的增加，JSP問題的求解空間變得復(fù)雜，傳統(tǒng)的求解算法在解的質(zhì)量和求解時間上不能滿足要求。因此提出基于工件組批調(diào)度，將小批量多種類的零件按照其特性進(jìn)行相似性聚類后再調(diào)度。采用基于OBX的自適應(yīng)遺傳算法對每個批次的批量大小進(jìn)行優(yōu)化，從而降低調(diào)度規(guī)模及其復(fù)雜性，以獲取最優(yōu)調(diào)度結(jié)果。經(jīng)實例驗證該方法可以有效地縮減工件完工時間、減少訂單拖延期和尋優(yōu)時間。

2 基于工件特性相似組批方法

該方法首先將加工工藝類似、管徑尺寸在同一范圍內(nèi)，且毛坯材質(zhì)相同的零件進(jìn)行聚類組批，每個工件都有各自的交付期，組批之后按照本批當(dāng)中最早交付期進(jìn)行調(diào)度。例如有10件工件，其主要特性，如表1所示。管徑有兩個尺寸范圍（6～12）mm和（14～38）mm，工件的主要工藝采用 A、B、C、D、E、F、G代替，其中E和F可以使用同種機(jī)器加工，在工序順序相同的條件下，同種工序或不同工序均可采用同類型機(jī)器的情況都可認(rèn)為是工藝類似，按照以上組批方法可得組批結(jié)果為：第一組（1、5、9），其交付期為2017/07/1；第二組（2、10），其交付期為 2017/07/1；第三組（3、4、6、7、8），其交付期為 2017/07/2。

表1 工件特性表Tab.1 Workpiece Characteristic Table

3 問題描述

所討論的柔性作業(yè)車間調(diào)度問題可以詳細(xì)描述為，在m臺設(shè)備（上加工 n 件工件（J=｛JlJ1，J2…Jn，l=1，2…n｝），每個工件包含 N 個事先確定加工順序的工序，每個工序可以在多臺設(shè)備上加工。組批之后形成r類工件R=第 i類工件的第 j道工序在設(shè)備 k 上加工時間為Tijk，Tpi表示第i類工件的第p批次最后一道工序的完工時間，Ds表示工件s的交付期，Dpi表示第i類工件的第p批次的交付期。調(diào)度目標(biāo)是使最大完工時間最小及總拖延期最小。

式（3）表示第i類工件第p批次的第j道工序加工時間等于本批次所有工件加工時間之和。

式（4）同一批次同一個工件的后一道工序的開工時間大于前道工序的完工時間：

式（5）占用同一臺機(jī)器，后一個批次工件的開工時間大于前一個批次工件的完工時間。

每類工件所有批次工件數(shù)量總和等于所有工件數(shù)總和，如式（6）所示。

第i類工件的第p批次的交付期等于本批中最早交付期，如式（7）所示。

具體符號含義，如表2所示。

表2 符號含義Tab.2 Symbolic Meaning

4 基于OBX交叉方式的自適應(yīng)遺傳算法

4.1 編碼

為適應(yīng)大規(guī)模柔性作業(yè)調(diào)度問題而采用三層編碼方式。假設(shè)有兩類工件，每個工件有兩道工序，如圖1所示。第一層表示工件組批后形成的批次數(shù)量，采用整數(shù)編碼Chrom（1，1）表示第1類工件組成2批。由于基于工序編碼的簡單并能保證可行解的產(chǎn)生[11]，故第二層采用基于工序的編碼方式，表示工件工序的加工順序，其中101表示第1類工件的第一個批次，102表示第1類工件的第二個批次，101第一次出現(xiàn)在工序基因內(nèi)表示其第一道工序，依次類推，工序基因表示的加工順序為101→201→102→101→201→102。第三層采用整數(shù)編碼，表示工件工序加工所選擇的機(jī)器，Chrom（1，9）表示工件101的第一道工序在可選機(jī)器集Mij內(nèi)選擇第一臺機(jī)器2。

圖1 染色體編碼圖Fig.1 Chromosome Coding Diagram

4.2 選擇

選擇算子采用輪盤賭注的方法，因該方法便于操作，故被廣泛地運用于選擇操作。在此方法中個體被選擇的概率和其自身的適應(yīng)度值相關(guān)，適應(yīng)度值越大被保留下來的概率就越大。

4.3 交叉方式

種群經(jīng)交叉洗牌后，隨機(jī)選擇兩個個體，并截取其工序基因交叉，如圖 2（a）所示。采用基于 Order-Based Crossover（OBX）的改進(jìn)交叉算子，其交叉步驟見圖，如圖2（a）所示。首先在父代P1中隨機(jī)選擇待交叉基因，形成交叉基因池Pos（201，101，102）。基因Chrom2的第一類工件批次數(shù)為1，由于在Chrom2的工序基因中沒有 102，故從 Pos（201，101，102）中刪除 102，最終用于交叉的基因有Pos（201，101）。然后在父代P2隨機(jī)選擇一個201和101，如圖2（b）所示。并刪除P2中被選中的基因。最后用P1被選中的基因順次填補P2中空缺的基因形成子代C2，如圖2（c）所示。P1 去除未被選中的基因，剩余 Pos1（102，201，101，102），用P2 中剩余的基因 Pos2（101，202，201，202）并去除 P1 中沒有的個體202，依次填補P1中的空缺形成子代C1，如圖2（c）所示。

圖2 基于OBX的工序交叉流程圖Fig.2 Process Cross Flow Chart Based on OBX

染色體交叉長度會影響算法性能，這里研究染色體交叉長度與算法求解精度及運算速度之間的關(guān)系。選擇染色體長度的10%到100%進(jìn)行交叉，并各運算10次求其平均值，然后求加權(quán)值，得出交叉長度在占染色體長度為10%時最優(yōu)。為了找出更優(yōu)的目標(biāo)值，又選擇染色體長度的10%到20%進(jìn)行交叉進(jìn)行仿真運算得出選擇染色體長度12%進(jìn)行交叉可以獲得更精確的解和提高運算速度，故選擇交叉長度為12%。

4.4 變異

變異分為批次變異和機(jī)器變異，其中批次變異，如圖3（a）所示。每次批次變異后工序基因和機(jī)器基因都需要重新解碼形成新的染色體，以保證染色體的合法性，如第一類工件批次減少1則工序基因相應(yīng)的減少一個工件102，而第二類工件的批次增加1則工序基因則增加工件202，兩者的機(jī)器基因均根據(jù)工序基因選擇相應(yīng)的機(jī)器。機(jī)器變異，如圖3（b）所示。如Parent（1，9）變異為2，表示選擇M11（2，3）中的3號機(jī)器。

圖3 變異流程圖Fig.3 Variation Flow Chart

4.5 交叉率及變異率正弦自適應(yīng)

正弦自適應(yīng)是交叉率及比變異率根據(jù)個體平均適應(yīng)度值以及最大適應(yīng)度值按照線性函數(shù)曲線變化的一種自適應(yīng)方法[12]。在優(yōu)化過程的初始階段選取較大的交叉率和變異率可以獲得較快的收斂速度且保持種群的多樣性，經(jīng)多次迭代后，為避免最優(yōu)解被破壞，此時選取較小的交叉率和變異率進(jìn)行細(xì)致搜索，經(jīng)實驗驗證，正弦自適應(yīng)遺傳算法可以提高算法的收斂速度及收斂精度，并且利用此方法可以保證算法搜索的全局性和精確性。

5 實例驗證

某工廠生產(chǎn)導(dǎo)管類零件，抽取其中的典型零件進(jìn)行實驗，每個工件有4道工序且有各自的交付期，每個工件的加工時間及加工準(zhǔn)備時間由廠方提供（單位：分鐘），初始參數(shù)設(shè)置：交叉率0.1，變異率0.04，種群規(guī)模40，迭代終止條件300代。

實驗設(shè)計為四種規(guī)模，分別為 230×18、460×18、690×18 及1150×18（工件數(shù)量×機(jī)器數(shù)量），按照上述組批方法，將零件隨機(jī)組成不同的批次，然后采用基于OBX交叉方式的自適應(yīng)遺傳算法優(yōu)化。設(shè)計4組實驗進(jìn)行對比，在相同的運行環(huán)境下每組實驗各運行10次，并取其平均值進(jìn)行對比。運行結(jié)果，如表3所示。

表3 實驗結(jié)果數(shù)據(jù)表Tab.3 Data Table of Experimental Results

由表3可知，四種不同大規(guī)模的JSP問題經(jīng)過組批調(diào)度之后拖延期均為0，而非組批調(diào)度方法均有不同程度的拖延；最大完工時間至少縮減17%，最多縮減25%；運算效率至少提高61%，最大提高69%。

6 結(jié)論

大規(guī)模柔性作業(yè)車間問題隨著工件數(shù)、機(jī)器數(shù)的增加，求解空間變得復(fù)雜，傳統(tǒng)的求解算法在解的質(zhì)量和求解時間上不能滿足要求。針對此問題提出基于工件組批調(diào)度，采用基于OBX的自適應(yīng)遺傳算法對每個批次的批量大小及加工順序進(jìn)行優(yōu)化，從而降低調(diào)度規(guī)模及其復(fù)雜性，減小完工時間，無拖延期，大幅度提高了優(yōu)化求解效率。