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

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

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

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

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

1.1 問題描述

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

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

1.2 模型構(gòu)建

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

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

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

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

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

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

帶并行批處理機的柔性作業(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)用。遺傳算法借用生物遺傳特性，通過選擇、交叉和變異等操作機制模擬生物在自然環(huán)境的遺傳和進化過程，進而形成了自適應(yīng)全局優(yōu)化算法，具有較好的尋優(yōu)能力和魯棒性，被廣泛應(yīng)用于求解NP-hard問題，在車間調(diào)度方面的應(yīng)用也十分廣泛。為了進一步改進遺傳算法的全局尋優(yōu)能力，筆者設(shè)計一種基于聚類進化的群體搜索策略來增加種群的多樣性。針對遺傳算法存在的局部尋優(yōu)能力差和“早熟”等缺陷，設(shè)計了基于關(guān)鍵路徑的局部搜索算子來改善遺傳算法的局部能力，可有效平衡遺傳算法的全局探索能力和局部搜索能力。

2.1 編碼和解碼

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

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

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

為了更清晰地描述解碼過程，給出一個帶有并行批處理機的柔性作業(yè)車間調(diào)度算例，如表1所示。該案例中有2個工件，每個工件有5道工序。其中“—”表示該工序不可在該機器上加工，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 帶有并行批處理機的柔性作業(yè)車間調(diào)度算例

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

圖1 工序分塊圖

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

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

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

2.2 選擇算子

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

2.3 交叉算子

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

圖3 基于工序的機器交叉

2.4 變異算子

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

2.5 局部搜索策略

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

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

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

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

圖5 改進遺傳算法流程圖

3 仿真分析

改進遺傳算法的運行環(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ù)和文獻[18]中的設(shè)置一致。改進遺傳算法的參數(shù)設(shè)置為：迭代次數(shù)T=100，種群規(guī)模P=40，交叉概率Pc=0.8，變異概率Pm=0.1。

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

(9)

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

表2 擴展后的測試算例

表3 實驗結(jié)果

(10)

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

4 結(jié)論

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

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