馬千慧，梁曉磊，劉星雨，張孟鏑，黃 凱

武漢科技大學 汽車與交通工程學院，武漢 430065

柔性作業(yè)車間調度問題（flexible job-shop scheduling problem，FJSP）包含工序排序和機器選擇兩個子問題，是典型的NP-hard問題，也一直是國內外學者研究的熱點。目前對FJSP的研究主要集中在考慮加工時間且以最小化最大完工時間為目標[1-3]，求解方法也多以智能優(yōu)化算法為主，如遺傳算法[4]、狼群算法[5]、混合遺傳雜草算法[6]等。大多數研究中考慮了工件在機器上的加工過程，卻忽略了工件的搬運過程。而現代制造業(yè)正向智能化方向升級，工件在機器之間的裝卸件大多通過自動導引小車（automatic guided vehicle，AGV）進行搬運，AGV在加工設備和運輸資源的集成調度及協同優(yōu)化中發(fā)揮的作用成為智能制造系統高效運作的重要支撐，因此考慮AGV調度與FJSP問題的結合有重要的實用價值。

目前對于AGV參與下的FJSP的研究主要集中在機器分配、工序調度、AGV調度分配、AGV路徑選擇等四個方面，如楊立熙等[7]、張國輝等[8]考慮了工序間的運輸時間，但沒有考慮運輸設備的調度；賀長征等[9]、Zheng等[10]考慮了機器和AGV的集成調度，但都以單目標優(yōu)化為主，對AGV數量和調度目標兩者之間的關系分析不足；在多目標優(yōu)化問題上，有學者考慮以車間總能量消耗最小和最大完工時間最小為目標[11]、以最小化綜合能耗成本和完工時間為目標[12]、以最大完工時間最小和AGV利用率最大為目標[13]構建模型，但較少考慮AGV因素下的優(yōu)化指標。AGV作為運輸設備和約束條件，在加工過程中將其作為調度目標的考慮因素是必要的。在求解算法中，近年研究多采用多目標優(yōu)化算法進行求解，如鞠錄巖等[14]提出改進NSGA算法求解多目標柔性作業(yè)車間調度問題，景志強等[15]提出NSGA-Ⅱ和模擬退火算法的混合算法，董海等[16]將入侵腫瘤生長優(yōu)化算法和NSGA-Ⅲ算法進行混合，但算法對問題的求解效率還需進一步提升。

在實際制造過程中，由于加工任務的到達是隨機的，每個工件設置不同的到達時間，有些工件的完工限制在一定時間范圍內，需滿足客戶要求在交貨期前完工，因此本文在考慮加工時間的同時，結合考慮工件的到達時間、交貨期等多時間因素，集成AGV調度和機器調度，建立多目標柔性作業(yè)車間調度模型，研究AGV數量變化與調度目標的關系。在求解方面，針對NSGA-Ⅱ算法運算復雜和精英策略不足的缺點，提出一種改進的NSGA-Ⅱ優(yōu)化算法對本文模型進行有效求解。

1 機器/AGV雙約束的FJSP調度問題描述與建模

1.1 問題描述

假設包含多道工序的n個工件可以在不同的m臺機器上進行加工，且有V臺相同的AGV在車間運送工件，所有工序按照規(guī)定的加工工藝路線在可加工機器集中的機器上加工，一道工序操作完成后，其下一道工序加工前要考慮AGV的運輸情況。本文提出在柔性作業(yè)車間調度問題中同時調度機器和AGV，充分考慮到達時間、加工時間、運輸時間、交貨期等多時間因素，建立機器/AGV雙約束的FJSP模型，調度以最小化最大完工時間、最小化總延期、最小化設備總負荷為目標。模型假設：零時刻AGV在入庫區(qū)準備就緒；AGV一次只能運載一個工件，且沿著預定的雙向單通道最短路徑行駛，且規(guī)定某一時刻一條路徑上只允許行駛一臺AGV；AGV執(zhí)行完當前運輸任務后直接前往下一運輸任務加工機器旁，不返回入庫區(qū)；考慮工件從入庫區(qū)到各機器和最后一道工序加工完后到出庫區(qū)的運輸時間；任意時刻每臺機器只能加工一個工件；不同工件間沒有優(yōu)先級，同一工件各工序存在先后順序；假定全部工件由AGV運送至出庫區(qū)即為加工完成；不考慮機器故障、AGV路徑沖突和碰撞等因素。

1.2 參數定義

模型參數定義如表1所示。

表1 參數定義Table 1 Parameters definition

其中：

1.3 模型建立

模型約束構建如下：

式（7）表示某時刻某工件只能被一臺機器加工；式（8）表示每臺AGV每次只接受一個運送任務；式（9）表示AGV需在工件工序加工完成后接受運送任務；式（10）表示AGV零時刻在入庫區(qū)等待；式（11）表示工件Ji加工完后被送至出庫區(qū)；式（12）表示同一工件兩個相鄰工序的加工約束；式（13）表示同一機器上緊前工序的加工約束；式（14）表示工件的第一道工序開始加工前需由AGV從入庫區(qū)搬運至第一臺機器；式（15）表示工件最后一道工序加工完后需由AGV搬運至出庫區(qū)；式（16）表示AGV完成運送任務Wi,j的結束運輸時間為開始運輸時間加上運輸時間；式（17）表示機器的加工能力限制；式（18）表示AGV的能力限制；式（19）表示交貨期限制；式（20）表示當前機器空閑時才能加工工件。

由于考慮了工件的到達時間，且假設AGV運送任務狀態(tài)分為裝卸件兩種，則需要探究是否為第一道工序、AGV搬運運送任務到達某一機器時該機器的工作情況：

（1）當AGV執(zhí)行裝件運送任務時，若為第一道工序，AGV工作時間即運輸時間；若非第一道工序，AGV工作時間為AGV所在機器、裝件點和加工機器三點間的運輸時間之和，計算如式（21）所示：

（2）當AGV執(zhí)行卸件運送任務時，若待接受運送工序已加工完，AGV工作時間為AGV所在機器、待接受運送工序加工完成機器與卸件點三點間的運輸時間之和；若未加工完，需判斷該工序完工時間與AGV運輸時間的大小，AGV工作時間取最大值與該機器到卸件點的運輸時間之和。計算公式為：

相應地，考慮AGV運輸時間約束和機器可用時間段時，需要探究是否為第一道工序以及機器是否空閑的工作情況：

（1）當機器空閑時，若為第一道工序，工件開始加工時間為到達時間與Tv,Wi,j之和；若非第一道工序，工件開始加工時間為該工序上一道工序的完工時間與Tv,Wi,j之和。計算公式為：

（2）當機器不可用時，若為第一道工序，工件開始加工時間由到達時間與Tv,Wi,j兩者之和、機器開始空閑時間中的最大值決定；若非第一道工序，工件開始加工時間由該工序上一道工序的完工時間與Tv,Wi,j之和、機器開始空閑時間中的最大值決定。計算公式為：

綜上，工件的結束加工時間的計算方式為：

根據以上約束模型，考慮到車間效率、客戶滿意度和設備使用情況，設置最大完工時間、總延期和設備總負荷最小三個目標，目標函數構建如下：

（1）最小化最大完工時間：

工件從入庫到出庫整個流程結束表示其加工完成，則工件最大完工時間為結束加工時間與加工完后從最后一臺機器到出庫區(qū)的運輸時間之和。

（2）最小化總延期：

為滿足交貨期限制，減少總延期時間以提高客戶滿意度。

（3）最小化設備總負荷：

將AGV作為考慮因素加入設備總負荷優(yōu)化指標中，其中包含機器負荷和AGV負荷（負載和空載），以提高設備利用率。

2 求解算法設計

2.1 AGV調度規(guī)則

為了合理分配車間調度資源和提高系統效率，提出新的AGV調度規(guī)則以確定加工工件和AGV的分配關系。針對本文FJSP模型特點，AGV調度規(guī)則分為單AGV和多AGV兩種情況，如圖1所示：（1）單AGV時，AGV完成上一運送任務后立即進行下一運送任務運輸；（2）多AGV時，如果每臺AGV在完成下一工序運輸任務的時間節(jié)點都大于下一工序能開始加工的時間，則選擇最早能完成運輸任務的AGV；如果僅有一臺AGV在完成下一工序運輸任務的時間節(jié)點在該工序能開始加工的時間之前，則選擇此AGV；如果有多臺AGV在完成下一工序運輸任務的時間節(jié)點在該工序能開始加工的時間之前，則選擇其中完成運輸任務時AGV運行距離最短的AGV。新的AGV調度規(guī)則在工件加工過程中根據不同情況考慮AGV最早到達和距離最短，使得工件在加工時獲得一個最早的開始加工時間。

圖1 AGV調度規(guī)則Fig.1 AGV scheduling rules

2.2 算法編碼及解碼策略設計

為提高NSGA-Ⅱ算法求解效率，本文設計了基于工序和啟發(fā)策略的編碼和解碼策略。以一個3×5（3個工件、5臺機器）FJSP問題為例，工件加工及AGV信息如表2所示。

表2 3×5 FJSP問題實例Table 2 Example of 3×5 FJSP problem

針對本文構建模型，采用基于工序的擴展染色體編碼，染色體結構如圖2所示。該染色體由兩部分組成，第一部分采用基于工序的編碼，基因位上工件號出現的次數代表該工件的第幾道工序，如第一個基因位上的數值2表示工件2的第一道工序，第二個基因位上的數值1表示工件1的第一道工序，以此類推；第二部分采用基于機器的編碼，基因位上的數值代表相應工序的可選機器號，如第一個基因位上的數值2代表工件2的第一道工序選擇機器2加工，第二個基因位上的數值3代表工件1的第一道工序選擇機器3加工，以此類推。

圖2 FJSP染色體編碼Fig.2 FJSP chromosome coding

上述編碼操作可以解決工序順序和機器分配問題，而AGV的調度體現在解碼中。本文構建了一種基于AGV分配的貪婪式解碼策略。以圖1染色體為例，具體步驟如下：

（1）根據染色體編碼可以獲得相應基因位的信息，包括工序基因P，加工機器Mk，進行運送任務的AGV號Pv以及AGV接受運送任務時所在的機器M′v,Wi,j，將獲取的信息作為解碼的輸入條件。

（2）從左到右讀取染色體基因，轉換成相應工序Oi,j和機器Mk，通過選擇的加工機器確定加工時間Pi,j,k，得到前置工序Oi,(j－1)的結束加工時間Ei,(j－1),k，前置工序所在機器位置Mv,Wi,j。

（3）確定工序開始加工時間Si,j,k。解碼計算時需考慮工件和加工機器的約束，見公式（23）、（24）。

（4）確定AGV運輸時間Tv,Wi,j。解碼計算時需考慮機器和AGV的雙約束，見公式（21）、（22）。

（5）確定AGV號Pv。通過AGV調度規(guī)則根據不同情況判斷選擇最早到達還是距離最短，即判斷AGV完成下一工序運輸任務的時間節(jié)點Te,v,Wi,j與該工序能開始加工的時間節(jié)點Si,(j+1),k的大小關系。

（6）確定工序結束加工時間Ei,j,k和完工時間。見公式（23）、（24）、（25）。

（7）重復步驟（2）～（6），直到所有的工件加工完成為止，得到每個工件每道工序的開始加工時間、加工機器、AGV和完工時間，即生成調度方案。

2.3 算法操作算子設計

（1）選擇算子

首先對初始種群進行排序并分級，找到種群中所有不被其他個體支配的個體作為第一級非支配個體集合，不斷分級操作，直到所有的個體分級完成，再進行擁擠度估計。經過非支配排序和擁擠度計算，本文采用二元錦標賽選擇方法，每次隨機選擇兩個個體，優(yōu)先選擇排序等級高的個體，如果排序等級一樣，優(yōu)先選擇擁擠度大的個體，如果擁擠度相同則選擇序號小的個體。

（2）交叉變異算子

針對染色體編碼以及機器可選的特點，在保證可行解的前提下，設計分段交叉和變異操作。

工序交叉：將所有工件隨機分成兩組J1、J2，隨機選擇兩個不同的父代工序染色體，將F1中屬于J1的工序位置保留到Z1，將F2中屬于J2的工序位置保留到Z2；將F2中屬于J2的工序復制到Z1的剩余位置，將F1中屬于J1的工序復制到Z2的剩余位置。其交叉過程見圖3（a）所示。

圖3 染色體交叉操作過程Fig.3 Chromosome crossover procedure

機器交叉：選擇兩個不同的父代染色體，隨機生成進行機器交叉的工序位置做為父代1交叉的位置，然后與父代2對應的位置進行機器交叉。例如，選擇F1中工件2的第一道工序作為交叉位置點，找出F2中此工序的位置，將此位置作為機器基因交叉點。其交叉過程見圖3（b）所示。

工序變異：選擇一個父代染色體，隨機生成兩個需要進行工序變異的工序位置，將兩個位置的工序進行交換，為滿足對應加工工序的機器不變，對機器序列進行重新排序。例如：把工件1的第一道工序與工件3的第二道工序進行交換，交換后此時工件3的第二道工序變?yōu)榈谝坏拦ば?，改變了工序順序，機器選擇發(fā)生了變化，需對機器進行重新選擇，修正之后加工機器可能從機器3變?yōu)闄C器1，機器5變?yōu)闄C器2。其變異過程如圖4（a）所示。

圖4 染色體變異操作過程Fig.4 Procedure of chromosome mutation

機器變異：選擇一個父代染色體，隨機生成多個需要進行機器變異的工序位置，在各工序對應加工的機器集里重新選擇機器。例如：選擇工件1的第二道工序的位置進行變異，其可選機器集合為{2，5}，生成該集合長度內的隨機數r，若r=1，則選擇機器2；若r=2，則選擇機器5，其變異過程如圖4（b）所示。

2.4 改進NSGA-Ⅱ算法

（1）多種群參數控制

多種群中的各種群采用不同的以某類指標為主的搜索方式，給不同的種群賦予不同的控制參數，突破NSGA-Ⅱ僅靠單個群體進行遺傳進化的框架。本文目的側重種群進化完成后使得三個目標相對較優(yōu)以及處于第一層級非支配序的解分布均勻，具體操作為，對種群進行二元錦標賽選擇，對第一個種群選擇以非支配排序為主的適合繁殖的父代種群，對第二個種群選擇以完工時間最小為主的適合繁殖的父代種群，對第三個種群選擇以設備總負荷最小為主的適合繁殖的父代種群，對三個種群分別進行交叉變異操作，引入三個種群同時進行優(yōu)化搜索，實現多種群的協同進化。

（2）基于Pareto級的去重精英保留策略

首先將第t代產生的新種群Qt放入新的父代種群Pt+1中，然后對上一代父代種群Pt進行非支配排序，產生一系列非支配集Zi并計算擁擠度，將經過非支配排序以后的最優(yōu)的非支配解存入新的第一層級非支配集Z′1中，再將Z′1中不同的個體放入新的父代種群Pt+1中，即Pt+1=Qt+Z′1。

本文采用的精英保留策略中種群數量不確定，每次迭代只保留第一層級中去掉重復解的個體到下一代中，這樣操作保證最優(yōu)解遺傳到下一代，且能避免傳統隱形精英保留策略在進化過程中大部分非支配解處于第一層級的非支配曲面造成局部收斂的情況。種群進化過程如圖5所示。

圖5 種群進化過程Fig.5 Procedure of population evolution

2.5 算法流程

AGV/機器雙約束下的改進NSGA-Ⅱ算法求解柔性作業(yè)車間調度問題的具體流程如圖6所示。

圖6 算法流程圖Fig.6 Algorithm flowchart

2.6 INSGA-Ⅱ算法時間復雜度分析

假設目標函數個數為M，種群規(guī)模為N，從2.5節(jié)算法流程可以看出，INSGA-Ⅱ算法尋優(yōu)主要由六部分組成：第一部分初始化種群，由單次種群搜索行為分析可知，其時間復雜度約為O(MN)；第二部分計算適應度值，其時間復雜度約為O(N1+N2+N3)=O(N′)，Nk為子群k的規(guī)模；第三部分快速非支配排序，首先二層循環(huán)生成非支配解，該步時間復雜度為O(MN2)，其次訪問集合中每一個非支配解得到非支配面，由于每個解最多由N－1個解支配，所以每個解被訪問的次數最多為N－1次，該步時間復雜度為O(N2)，綜上，快速非支配排序的時間復雜度約為O(MN2)；第四部分擁擠度計算，對每一個體求目標值并找其最大值，其時間復雜度約為O(MNlogN)；第五部分多種群進化，加入三個種群，其時間復雜度約為O(N·3)=O(N)；第六部分精英保留，其時間復雜度約為O(MN)。因此，INSGA-Ⅱ算法的總時間復雜度為：

3 車間調度仿真實例

3.1 案例求解

本文以表3所示的8×8問題實例和表4所示的AGV搬運時間為例，對以最大完工時間、總延期、設備總負荷為優(yōu)化目標的FJSP問題進行驗證。問題規(guī)模設置為工件數n=8，機器數m=8，AGV數V=3。采用Matlab 2018b進行編程實現，實驗在平臺（Intel?Core?i5-6500 CPU@3.20 GHz 3.19 GHz，內存8.00 GB）上進行。算法參數設置為：種群規(guī)模P=200，最大迭代次數M=100，交叉概率Pc=0.8，變異概率Pm=0.1。

表3 具有工件到達時間和交貨期的8×8 FJSP問題實例Table 3 Example of 8×8 FJSP problem with workpiece arrival time and delivery date單位：min

表4 AGV搬運時間Table 4 AGV handling time 單位：min

實驗結果如圖7（a）所示，其中機器加工時間段用工件號、工序號、加工時間構成的字符串進行標記，即p（工件，工序）=加工時間；AGV運輸時間段分為空載和負載兩個階段，分別用虛線框和實線框標記，圖中數字代表各個位置節(jié)點。方案中調度的3個目標最佳值分別為最大完工時間121、總延期13、設備總負荷568。從圖7（a）中可以看出，AGV存在無效運輸時間段，如空載段10-6-6。分析可知此時待運送工件的下一道工序仍在同一機器上加工，不需搬運。因此，增加如下約束：相同工件的不同操作工序在同一臺機器上加工不需要AGV運輸。校正后調度解甘特圖如圖7（b）所示，此時3個目標最佳值分別為最大完工時間112、總延期12、設備總負荷561，獲得了更優(yōu)秀的解。

圖7 8×8案例調度甘特圖Fig.7 8×8 case scheduling Gantt chart

校正后該方案得到AGV的運輸時間矩陣為：

其中，每個矩陣第一列數值表示AGV號，第二列表示AGV位置節(jié)點，第三列表示工件位置節(jié)點，第四列表示工件加工機器位置節(jié)點，第五列表示AGV空載開始時間，第六列表示AGV負載開始時間，第七列表示AGV負載結束時間。含義如下：第八個工件的第一道工序O81開始加工時間為其到達時間0、小車1從入庫區(qū)搬運O81到機器1的運輸時間4之和即4，對應AGV時間矩陣為[1 9 9 1 0 0 4]；小車1負載結束時間為4，由位置1行駛至入庫區(qū)搬運工序O21到機器3上加工，其開始加工時間計算判斷小車到達時間和工件到達時間的大小取最大值，即max（4+4，17）+6=23，對應AGV時間矩陣[1 1 9 3 13 17 23]，以此類推，最終確定調度方案。

針對最大完工時間、總延期以及設備總負荷的3個目標的柔性作業(yè)車間調度問題，用本文改進NSGA-Ⅱ算法求解得到的Pareto前沿如圖8所示，各解相互之間重疊小，解集覆蓋性較好。

3.2 AGV數量與調度目標關系分析

為研究AGV數量變化對調度目標的影響，本文基于8×8算例，取不同數量的AGV，進行獨立測試，分別計算20次取平均值，得到結果如圖9所示。從圖9中可以看出，當AGV數量超過3時，最大完工時間和總延期變化趨于平緩，而由于AGV增加造成AGV空載減少，設備總負荷會相應減少?？偟膩碚f，隨著AGV數量的增加，三個目標函數值會逐漸減小，且減小的幅度會越來越小，即對提高相同任務調度效率的影響隨AGV數量的增加而減小。實際生產過程中，在考慮AGV成本的情況下，選擇相同調度效率下AGV數量少的方案。

圖9 AGV數量對目標函數值的影響Fig.9 Influence of AGV numbers on objective functions values

3.3 算法性能測試

為測試算法求解能力，設置不同AGV數量，在相同規(guī)模問題（8×8算例）下，實驗中AGV數V＜n，種群規(guī)模P=200，最大迭代次數M=100，交叉概率Pc=0.8，變異概率Pm=0.1。

不同AGV規(guī)模案例中，INSGA-Ⅱ算法求解8×8算例的3個目標函數平均收斂曲線分別如圖10所示。由圖10可以看出，隨著AGV數量的增加，算法收斂速度先加快，后不變，3個目標迭代到一定程度時均收斂到最優(yōu)值，可以證明改進的NSGA-Ⅱ算法在求解此類調度問題上具有較強的搜索能力。

圖10 不同AGV數量下目標函數平均收斂曲線圖Fig.10 Average convergence curves of objective functions under different AGV quantities

此外，構建AGV=7案例，選擇多目標粒子群優(yōu)化（multi-objective particle swarm optimization，MOPSO）算法[17]、混合差分進化（hybrid differential evolution，HDE）算法[18]、非支配排序遺傳（non-dominated sorting genetic algorithm-Ⅱ，NSGA-Ⅱ）算法與本文算法進行性能對比。AGV=7時以上3種算法下的目標函數平均收斂曲線如圖11所示。結果可以看出，INSGA-Ⅱ算法克服了MOPSO和HDE求解AGV機器調度問題的過早收斂現象，且較NSGA-Ⅱ有更好的優(yōu)化效果。體現了本文改進算法的可擴展性。

圖11 AGV=7時對比算法下的目標函數平均收斂曲線圖Fig.11 Average convergence curves of objective functions under comparative algorithm at AGV=7

為進一步驗證模型和INSGA-Ⅱ算法及優(yōu)化策略的有效性，分別使用文獻中3×5算例[19]、10×8算例[20]、12×10算例[21]和本文8×8算例數據進行模型和算法測試。文獻算例中未指明的AGV運輸時間采用表4中數據。4種多目標優(yōu)化算法在每組測試數據下分別運行20次取平均值，得到對比結果如表5所示。結果顯示，改進算法均獲得更高質量的解，證明本文INSGA-Ⅱ算法能夠有效求解帶有AGV約束的多目標柔性作業(yè)車間調度問題，且對大規(guī)模問題也更好地優(yōu)化效果。

表5 不同案例算法對比結果Table 5 Comparison results of different case algorithms單位：min

4 結論

針對FJSP中較少考慮運輸過程的不足，本文在加工過程的基礎上增加了運輸資源AGV的調度，考慮多時間因素和一個或多個AGV組成的柔性作業(yè)車間系統，用于解決機器和多個相同AGV的同時調度問題。針對任務分配和AGV調度對模型進行多目標優(yōu)化，設計了改進NSGA-Ⅱ算法，提出了基于AGV分配的貪婪式解碼策略，同時結合多種群和精英保留策略提高算法的搜索能力。通過與其他算法對比實驗，結果證明了本文提出模型的有效性，且改進算法能夠獲得優(yōu)秀的調度結果。在下一步研究工作中，將重點研究模型中隨機因素對FJSP問題的影響以及進一步改善算法求解效率。