帶并行批處理機(jī)的柔性作業(yè)車間調(diào)度問題研究

劉 蓉，周 林，王 朝，唐紅濤，張海濤

(1.武漢理工大學(xué) 機(jī)電工程學(xué)院，湖北 武漢 430070；2.湖北省數(shù)字制造重點實驗室，湖北 武漢 430070)

作業(yè)車間調(diào)度問題(job shop scheduling problem, JSP)是先進(jìn)智能制造領(lǐng)域研究中基礎(chǔ)且重要的問題，是對生產(chǎn)過程進(jìn)行作業(yè)計劃和協(xié)調(diào)。先進(jìn)的調(diào)度方法能為企業(yè)提高生產(chǎn)效益，其主要任務(wù)是在特定的約束下，確定工件的加工順序和加工設(shè)備，以保證所選定的生產(chǎn)目標(biāo)最優(yōu)。柔性作業(yè)車間調(diào)度(flexible job shop scheduling problem ,FJSP)作為JSP的拓展，增加了加工機(jī)器選擇的柔性，每個機(jī)臺在每個時刻最多只能加工一個工件。在帶有并行批處理的柔性作業(yè)車間調(diào)度問題中，約束更為復(fù)雜，求解更為困難。在該問題中，每個單處理機(jī)在每個時刻最多只能加工一個工件，但每個并行批處理機(jī)允許同時加工多個工件且同一批次的工件加工時間相同[1]。在工程上，帶有并行批處理的柔性作業(yè)車間調(diào)度問題多存在于半導(dǎo)體企業(yè)及傳統(tǒng)鑄造企業(yè)，因此針對該問題尋求有效的調(diào)度機(jī)制和求解方案具有重要的應(yīng)用價值。

柔性作業(yè)車間調(diào)度屬于NP-Hard問題[2]，在汽車裝配、紡織、化工材料加工及半導(dǎo)體制造等方面得到了廣泛的應(yīng)用[3]。啟發(fā)式算法具有算法簡單、通用性強(qiáng)、求解效率高等優(yōu)點，被廣泛應(yīng)用于求解車間作業(yè)調(diào)度問題，如遺傳算法(GA)[4]、粒子群優(yōu)化算法(PSO)[5]、人工蜂群算法(ABC)[6]、灰狼算法(GWO)[7]等。對于柔性作業(yè)車間調(diào)度問題的研究出現(xiàn)了大量的研究成果，如在優(yōu)化算法研究方面，ZHANG等[8]提出了一種有效的遺傳算法來解決FJSP問題，能有效減少完工時間；XU等[9]設(shè)計了一種有效的教與學(xué)優(yōu)化算法(TIBO)，并驗證了其求解FJSP問題的優(yōu)越性。在FJSP應(yīng)用模型研究方面，SHEN等[10]考慮了帶順序相關(guān)調(diào)整時間的柔性作業(yè)車間調(diào)度問題；雷德明[11]研究了低碳策略下的柔性作業(yè)車間調(diào)度問題； ANDRADE-PINEDA等[12]考慮了雙資源約束情況下的柔性作業(yè)車間調(diào)度問題。

對于在FJSP基礎(chǔ)上引入批處理機(jī)的研究相對較少，如LI等[13]針對多臺單處理機(jī)和一臺批處理機(jī)的調(diào)度問題，提出了一種組合蟻群優(yōu)化算法來求解該問題。HAM[14]以半導(dǎo)體行業(yè)為生產(chǎn)背景，提出帶有并行批處理機(jī)的柔性作業(yè)車間調(diào)度問題，考慮了兼容的工件簇及工件間具有不同優(yōu)先級的情況。LIAO等[15]研究了單機(jī)與并行機(jī)的集成并行分批調(diào)度問題，并根據(jù)優(yōu)化的結(jié)構(gòu)特性和分批規(guī)則，提出了一種新的帶有變鄰域搜索的人工免疫系統(tǒng)算法(AIS-VNS)。由于多臺并行批處理機(jī)和單處理機(jī)對工件進(jìn)行反復(fù)訪問，增加了問題求解的難度，故針對該類問題的相關(guān)研究較少。因此筆者針對帶有并行批處理機(jī)的柔性作業(yè)車間調(diào)度問題，構(gòu)建了混合整數(shù)數(shù)學(xué)模型，設(shè)計了基于改進(jìn)遺傳算法的求解方法。在算法中，設(shè)計了分塊式集成解碼方法，在一次解碼中解決工序排序、機(jī)器配置和工件組批3個子問題?；诰垲惖倪x擇算法保證了種群的多樣性，基于關(guān)鍵路徑的局部搜索算子能有效改善算法的局部搜索能力。最后，通過仿真實驗來驗證所提算法解決此類問題的可行性和有效性。

1 問題描述及模型構(gòu)建

1.1 問題描述

原始的柔性作業(yè)車間調(diào)度問題(FJSP)可描述為n個工件(J1,J2,…,Jn)在m個加工資源(M1,M2,…,Mm)上加工，每個工件的加工工序都是確定的且不盡相同，每道工序可選擇多個加工資源。每個加工資源都是單處理機(jī)，即每個加工資源在同一時刻只能加工一個工件。研究的目的是確定每道工序的加工資源、加工順序及加工開始時間來使得整個調(diào)度系統(tǒng)的優(yōu)化指標(biāo)達(dá)到最優(yōu)，故該組合優(yōu)化問題可以分為兩個子問題：①加工機(jī)器配置子問題，即確定每道工序在哪個加工機(jī)器上加工；②工件的工序排序子問題，即對分配好加工機(jī)器的工序進(jìn)行排序。

在汽車模具鑄造生產(chǎn)過程中，部分機(jī)器具有并行批處理的加工能力，其他則屬于柔性作業(yè)車間中的單處理機(jī)范疇。汽車模具鑄造生產(chǎn)調(diào)度問題可描述為帶有并行批處理機(jī)的柔性作業(yè)車間調(diào)度問題，耦合了柔性作業(yè)車間的復(fù)雜性和并行批處理機(jī)的加工特點。在該問題中，部分單處理機(jī)被并行批處理機(jī)替代，即加工資源能同時加工多個工件，且加工的開始時間和結(jié)束時間相同。在并行批處理機(jī)加工時，屬于該批所有工件的加工時間與該批的工件數(shù)量和噸位有關(guān)(加工時間不定)。此外，每個并行批處理機(jī)的加工能力有限，每批工件的尺寸不盡相同，且不能超過并行批處理機(jī)的加工能力(考慮差異工件尺寸)。在實際生產(chǎn)過程中，考慮到加工工藝約束，單處理機(jī)和批處理機(jī)有著不重疊性，即某個工件的工序的多個可選資源集中不會同時存在單處理機(jī)和批處理機(jī)，且可選集合中所有機(jī)器的加工能力相同。因此，該組合優(yōu)化問題的劃分可在原始兩個子問題中增加一個子問題：并行批處理機(jī)的批次計劃，即工件組批。

1.2 模型構(gòu)建

(1)基本假設(shè)條件。①同一工件的同一工序在同一時刻只能被一臺機(jī)器加工；②單處理機(jī)和批處理機(jī)有著不重疊性；③每道工序一旦開始就不能被中斷；④不同工件的工序之間沒有先后次序約束，同一工件的工序之間有先后次序約束；⑤所有工件在零時刻都可以被加工；⑥不同工件之間具有相同的優(yōu)先級。

(2)模型參數(shù)說明。Ji表示第i個工件,i=1,2，…,n；Mk表示第k個機(jī)器,k=1,2,…,m；Wi表示第i個工件的重量；Oij表示第i個工件的第j道工序,j=1,2,…,Ni；Mij表示第i個工件的第j道工序的可選機(jī)器集；Sij表示工序Oij的加工開始時間；Cij表示工序Oij的完工時間；Bp表示并行批處理機(jī)p的加工批次集合，p表示該機(jī)器是并行批處理機(jī)；Cp表示并行批處理機(jī)p的加工能力；Tbp表示批處理機(jī)p的第b次任務(wù)的加工時間，b表示批次任務(wù)；Pijk表示工序Oij在單處理機(jī)k上的加工時間。

決策變量：Xijk=1表示工序Oij選擇機(jī)器k，否則Xijk=0；Yij=1表示工序Oij可選機(jī)器集中有并行批處理機(jī)，否則Yij=0；Zij=1表示工序Oij可選機(jī)器集中有單處理機(jī)，否則Zij=0；Tijpb=1表示工序Oij在并行批處理機(jī)p的第b批中加工，否則Tijpb=0；Bibp=1表示并行批處理機(jī)p的第b批次任務(wù)中包含工件i，否則Bibp=0。

(3)數(shù)學(xué)模型。

(1)

s.t.

Sij+Xijk×Pijk≤Cij,?i,j,k∈Mij

(2)

Cij≤Si(j+1),?i,j

(3)

(4)

(5)

Yij+Zij=1,?i,j

(6)

(7)

(8)

式(1)為該問題的優(yōu)化目標(biāo)，表示最小化最大完工時間；式(2)和式(3)表示工件工序加工有先后次序的約束；式(4)表示同一工件的同一工序在同一時刻只能被一臺機(jī)器加工；式(5)表示如果工序Oij的可選機(jī)器集為并行批處機(jī)，則該工序能且只能被分配到一個批次b中；式(6)表示單處理機(jī)和批處理機(jī)的不重疊性；式(7)表示并行批處理機(jī)的加工時間與該批次的任務(wù)重量有關(guān)，f表示兩者之間具有線性關(guān)系；式(8)表示每一批內(nèi)各任務(wù)重量之和小于并行批處理機(jī)的加工能力。

2 改進(jìn)遺傳算法求解調(diào)度模型

帶并行批處理機(jī)的柔性作業(yè)車間調(diào)度屬于NP-hard問題，可行解的數(shù)量隨著調(diào)度規(guī)模呈現(xiàn)指數(shù)級增加?；旌险麛?shù)規(guī)劃[16]、拉格朗日松弛法[17]等一些精確方法雖然能在小規(guī)模問題中找到最優(yōu)解，但是計算量大，耗時多，在求解大規(guī)模時受到限制。啟發(fā)式算法雖然在求解上穩(wěn)健性不足，但是其求解速度快，易于實現(xiàn)，計算復(fù)雜度低，也能得到滿意解，故啟發(fā)式算法在求解車間調(diào)度問題上得到了廣泛的應(yīng)用。遺傳算法借用生物遺傳特性，通過選擇、交叉和變異等操作機(jī)制模擬生物在自然環(huán)境的遺傳和進(jìn)化過程，進(jìn)而形成了自適應(yīng)全局優(yōu)化算法，具有較好的尋優(yōu)能力和魯棒性，被廣泛應(yīng)用于求解NP-hard問題，在車間調(diào)度方面的應(yīng)用也十分廣泛。為了進(jìn)一步改進(jìn)遺傳算法的全局尋優(yōu)能力，筆者設(shè)計一種基于聚類進(jìn)化的群體搜索策略來增加種群的多樣性。針對遺傳算法存在的局部尋優(yōu)能力差和“早熟”等缺陷，設(shè)計了基于關(guān)鍵路徑的局部搜索算子來改善遺傳算法的局部能力，可有效平衡遺傳算法的全局探索能力和局部搜索能力。

2.1 編碼和解碼

染色體的編碼與解碼是解決調(diào)度問題的關(guān)鍵，編碼就是將調(diào)度問題復(fù)雜的解空間用一種編碼方式來表示，從而將調(diào)度問題的解空間映射到染色體的編碼空間。解碼并不是編碼的反操作，而是將粒子編碼中摻雜著調(diào)度模型的各種約束和調(diào)度信息與優(yōu)化指標(biāo)聯(lián)系起來。

筆者采用基于機(jī)器和工序的分段編碼方式，采用工序排序部分(OS)和機(jī)器選擇部分(MS)來表示一個可行的調(diào)度方案。工序排序部分粒子長度為該次調(diào)度任務(wù)工序總數(shù)，對于第j次出現(xiàn)的工件號，就表示該工件的第j道工序；機(jī)器選擇部分長度和工序排序部分一樣，且順序一一對應(yīng)，每個機(jī)器碼意味著該工序可選機(jī)器集的順序號(非機(jī)器號)，這樣就保證了種群可行解的產(chǎn)生。

分段編碼能有效整合和解決工序排序和資源選擇問題，但是不能直接反映并行批處理機(jī)的加工批次計劃。因此，筆者設(shè)計了分塊式集成解碼規(guī)則來解決單處理機(jī)的工序排序和機(jī)器選擇問題，以及并行批處理機(jī)的工件組批問題，從而在一次解碼中得到混合活動調(diào)度方案。

為了更清晰地描述解碼過程，給出一個帶有并行批處理機(jī)的柔性作業(yè)車間調(diào)度算例，如表1所示。該案例中有2個工件，每個工件有5道工序。其中“—”表示該工序不可在該機(jī)器上加工，TBD表示加工時間不確定，與該批次的加工任務(wù)有關(guān)。該算例的一個可行解為:OS=[1,1,2,1,1,2,1,2,2,2],MS=[1,1,3,2,1,1,1,2,1,2]。

表1 帶有并行批處理機(jī)的柔性作業(yè)車間調(diào)度算例

根據(jù)各個工件中工序是否屬于批處理工序，可以將所有工序劃分批處理工序塊和單處理工序塊。由表1可知，O12、O15、O22和O24是批處理工序，且O12和O22為同一道批處理工序，即有著相同可選加工機(jī)器集。同理，O15和O24也是同一道批處理工序。以這些批處理工序為分界線，可以將整個工序劃分為工序塊，如圖1所示，該工序共劃分為3個單處理塊和2個批處理塊，共5個工序塊。根據(jù)各個工序塊中工序與可行解的對應(yīng)關(guān)系，將各個塊的基因取出，按照對應(yīng)的規(guī)則解碼，可得到可行的活動調(diào)度方案。

圖1 工序分塊圖

塊2為批處理塊，需要對該塊的工序進(jìn)行構(gòu)建批量計劃，其前驅(qū)工序塊1驅(qū)動塊2產(chǎn)生調(diào)度方案。前驅(qū)工序塊的各個工件完工時間不一致，其不同完工時間對于批處理塊2來說可被視為工件動態(tài)到達(dá)時間約束，又考慮到每個并行批處理機(jī)的加工能力有限(差異工件尺寸約束)，則批處理塊可被視為考慮差異工件尺寸和動態(tài)到達(dá)時間的分批問題。為解決該分批問題，采用基于時間排序的任務(wù)補(bǔ)充分批規(guī)則，即對于每個批處理塊的工序，將其前驅(qū)工序進(jìn)行完工時間升序排序，依次并成一批，直到總重量超出并行批處理機(jī)的加工能力。對于批處理工序的機(jī)器選擇問題，采用就近原則，即選擇最快能有空閑時間機(jī)器，若有多臺則隨機(jī)選擇一臺。每個批次的加工開始時間為該批次所有任務(wù)的前驅(qū)工序最大完工時間，加工時間與每個批次的總重量呈正相關(guān)關(guān)系，即總重量越重加工時間越久。

塊2中包含了工序O12和O22，前驅(qū)工序塊的完工時間為[4,5],可選機(jī)器集為M4。為了方便分批，假設(shè)工件1和工件2的總重量不超過該機(jī)器的加工能力，加工時間固定為6。對該塊進(jìn)行分批，O12的前驅(qū)工序完工時間(4)較早先分入該批次，隨后因滿足機(jī)器的加工能力O22也會被劃分到該批次，則O12和O22被劃分為同一批次。此外，該批次的加工開始時間為前驅(qū)工序塊的完工時間[4,5]中的最大值5。則塊2的調(diào)度方案可描述為：O12和O22被劃分為同一批次被并行批處理機(jī)M4在時刻5加工，其加工時間為6，完工時間矩陣為[11,11]。其他工序塊可以按照對應(yīng)的解碼方式得到各自的調(diào)度方案，最終的調(diào)度甘特圖如圖2所示。

圖2 調(diào)度算例的甘特圖

2.2 選擇算子

目前，遺傳算法的選擇算子主要有輪盤賭、隨機(jī)競爭、隨機(jī)聯(lián)賽等方式。筆者為了拓寬種群的多樣性，并避免基因特征相似的基因進(jìn)行交叉造成冗余信息的傳遞，設(shè)計了一種聚類的選擇方式。令聚類中心個數(shù)為K，具體選擇操作步驟為：①將種群中個體的適應(yīng)度值按照K-Means算法進(jìn)行聚類分類，得到一個具有K個簇的模型，簇內(nèi)的基因特征相似度較大，簇間的基因特征相似度較?。虎诔プ顑?yōu)基因所在的簇，其他簇內(nèi)隨機(jī)剔除個體，直至剩下的個體為種群的個體總數(shù)。

2.3 交叉算子

交叉的目的是將優(yōu)良父代的信息保存下來，產(chǎn)生新的優(yōu)良個體。為了避免相似信息的基因被冗余保存，考慮到簇間基因特征相似度較小，選擇兩個不同簇之間的父代進(jìn)行交叉，這樣就能保證種群基因信息的多樣性。筆者針對工序的排序部分采用的是基于工件的POX交叉；針對機(jī)器選擇部分設(shè)計了一種基于工序的機(jī)器交叉，如圖3所示，具體步驟為：①隨機(jī)生成變動工序集；②將P1中工序排序部分和非變動工序集對應(yīng)的機(jī)器選擇部分復(fù)制放在子代中；③將P2中變動工序集中對應(yīng)的機(jī)器按照P1中的順序依次插入到子代中。

圖3 基于工序的機(jī)器交叉

2.4 變異算子

變異算子主要是為了增強(qiáng)算法的局部搜索能力，防止算法陷入局部最優(yōu)解。針對工序排序部分的基因采用移位變異，即隨機(jī)選擇兩個位置，將這兩個位置的基因與其對應(yīng)的機(jī)器基因一起進(jìn)行位置互換。因為柔性作業(yè)調(diào)度中機(jī)器選擇的柔性和加工時間的不一致，所以針對機(jī)器選擇部分變異時，隨機(jī)選擇一個機(jī)器基因碼，在此工序的機(jī)器集中選擇最小加工時間的機(jī)器。針對工序部分和機(jī)器部分的兩種變異算子，均能保證在變異后產(chǎn)生的是可行解。

2.5 局部搜索策略

遺傳算法是一種自適應(yīng)全局優(yōu)化算法，存在局部尋優(yōu)能力差和“早熟”等缺陷。在變異算子的基礎(chǔ)上，為了進(jìn)一步增強(qiáng)算法局部搜索能力，設(shè)計了一種基于關(guān)鍵路徑的局部搜索策略。對于求解作業(yè)車間調(diào)度問題，關(guān)鍵路徑直接影響一個調(diào)度方案的最大完工時間,通過擾動關(guān)鍵路徑上的工序，有可能縮短當(dāng)前種群的最大完工時間。其中，在關(guān)鍵路徑上的工序視為關(guān)鍵工序，同一個機(jī)器上最大序列的連續(xù)關(guān)鍵工序組成關(guān)鍵塊。

基于關(guān)鍵路徑的局部搜索策略示意圖如圖4所示，虛線框內(nèi)是一個關(guān)鍵塊，針對關(guān)鍵塊變動塊首或者塊尾的相對位置。在一次移動中，若當(dāng)前塊只有兩道關(guān)鍵工序，則不做交換；若超過兩道關(guān)鍵工序，則選擇塊首或者塊尾作為移動源，隨機(jī)選擇與其不相鄰的關(guān)鍵工序作為移動點，將移動源插入移動點之前或者之后，隨后移動源和移動點之間的關(guān)鍵工序依次往前或者往后移動。

圖4 基于關(guān)鍵路徑的局部搜索策略

改進(jìn)遺傳算法求解模型的基本流程如圖5所示。隨機(jī)初始化種群，遺傳算法進(jìn)行全局尋優(yōu)，得到全局最優(yōu)解作為局部搜索算子的初始解，較好的初始解能有效保證局部搜索的性能，幫助算法跳出局部最優(yōu)解，平衡全局搜索和局部搜索之間的矛盾。

圖5 改進(jìn)遺傳算法流程圖

3 仿真分析

改進(jìn)遺傳算法的運行環(huán)境:Intel Core i5, CPU 2.30 GHz, RAM 4.00 GB, Window 7的64位操作系統(tǒng)和Matlab 2015a。對比算法分別為GA算法、GA+聚類算法、GPSO算法[18],每個算法都有相關(guān)的參數(shù)設(shè)置。GA和GA+聚類兩個算法的參數(shù)一致，GPSO算法的參數(shù)和文獻(xiàn)[18]中的設(shè)置一致。改進(jìn)遺傳算法的參數(shù)設(shè)置為：迭代次數(shù)T=100，種群規(guī)模P=40，交叉概率Pc=0.8，變異概率Pm=0.1。

由于當(dāng)前并沒有標(biāo)準(zhǔn)測試算例可用來測試帶并行批處理機(jī)的柔性作業(yè)調(diào)度問題，筆者以Brandimarte算例為基礎(chǔ)，擴(kuò)展成適用于帶并行批處理機(jī)的柔性車間調(diào)度問題的測試算例，共生成10個測試算例，如表2所示。以算例1為例，算例規(guī)模為10個工件、6臺單處理機(jī)和1臺并行批處理機(jī)，批處理工序為第3道工序，該工序的可選擇加工機(jī)器為M7，加工能力為80 kg，每個工件的重量為29-18-16-5-42-10-35-48-30-20。批處理工序的加工時間和該批的總重量呈正相關(guān)，如式(9)所示。前半部分表示與重量呈線性相關(guān)，后半部分表示該批每增加一個任務(wù)多花費0.5 h。

(9)

采用改進(jìn)遺傳算法和對比算法對10個測試算例進(jìn)行測試，得到的實驗結(jié)果如表3所示。為避免算法結(jié)果的偶然性，每個算例重復(fù)運行20次。為了保證公平性，其他算法的終止條件為改進(jìn)遺傳算法單獨運行一次的時間。Cbest為20次中的最優(yōu)解，Av(C)為平均值，dev表示改進(jìn)遺傳算法的最優(yōu)解C*與4個算法中最優(yōu)解C0的相對誤差，其計算公式如式(10)所示，dev為0表示改進(jìn)遺傳算法得到的結(jié)果最優(yōu)。

表2 擴(kuò)展后的測試算例

表3 實驗結(jié)果

(10)

由表3可知，改進(jìn)遺傳算法在10個算例中都取得不錯的結(jié)果，獲得了9個算例的最好解，相對誤差都為0，且每個算例在均值的表現(xiàn)都有著明顯的優(yōu)勢，具有較好的穩(wěn)定性。尤其是與GA算法和GA+聚類算法相比，改進(jìn)遺傳算法的優(yōu)勢非常明顯，驗證了改進(jìn)遺傳算法的有效性。MK02_1算例最優(yōu)值隨迭代次數(shù)的變化曲線如圖6所示，可知改進(jìn)遺傳算法和GA+聚類算法都增加了基于聚類的選擇算子，與傳統(tǒng)GA算相比有著更快的收斂速度，保證了種群的多樣性。同時，改進(jìn)遺傳算法取得的最優(yōu)解得到了明顯改善，驗證了局部搜索的有效性，能幫助算法跳出局部最優(yōu)解。與GPSO算法相比，改進(jìn)遺傳算法在10個工件的MK01和MK02算例中有一定的優(yōu)勢，而在15個工件算例中改進(jìn)遺傳算法解的質(zhì)量明顯優(yōu)過其他算法。

圖6 MK02_1算例最優(yōu)值隨迭代次數(shù)的變化曲線

MK01_1算例的調(diào)度甘特圖如圖7所示，可知該批次計劃共有4批，分別為工件{7,9}、{2,6,10}、{1,5}和{3,4,8}，均在機(jī)器M7上加工，最小完工時間為37.95 h。

4 結(jié)論

針對帶有并行批處理機(jī)的柔性作業(yè)車間調(diào)度問題，以最小化最大完工時間為優(yōu)化目標(biāo)構(gòu)建數(shù)學(xué)模型。針對問題特點，改進(jìn)了遺傳算法，設(shè)計了一種分塊式集成解碼規(guī)則，引入基于聚類的選擇算子，設(shè)計了基于關(guān)鍵路徑的局部搜索算子。仿真實驗表明：①構(gòu)建的混合整數(shù)模型能有效描述帶有并行批處理機(jī)的柔性作業(yè)車間調(diào)度過程；②改進(jìn)遺傳算法易實現(xiàn)，高效率且能得到高質(zhì)量解，能為該類調(diào)度問題提供合理有效的解決方案；③該模型貼近實際生產(chǎn)調(diào)度，求解方法簡便高效，具有較強(qiáng)的實際應(yīng)用價值。

圖7 MK01_1算例的調(diào)度甘特圖