基于改進匈牙利算法的航空企業(yè)動態(tài)調度方法研究

王晉，王鵬，郭豐赫

(1.西安航空學院 機械工程學院，西安 710077)(2.西北工業(yè)大學 現(xiàn)代設計與集成制造技術教育部重點實驗室，西安 710072)

0 引 言

航空零件的加工是一個復雜的制造過程，零件結構多樣，標準化程度低，工藝復雜，一個零件需要在多個機器上加工才能完全加工成型。不同種類的航空零件，在每個機器上加工的時間不同。此外，在航空零件加工過程中，需要將各個航空零件合理地分配給最優(yōu)的機器，并確定機器加工零件的順序，從而達到合理利用產品制造資源、更好地完成飛機組裝線需求的目的。因此，研究航空制造企業(yè)的生產調度模型和方法具有一定的理論意義和工程應用價值。

生產調度在提高車間生產率中扮演著重要的角色。近幾十年來，生產調度問題受到廣泛關注，尤其是作業(yè)車間調度問題(Job Shop Scheduling Problem，簡稱JSSP)。1976年，M.R.Garey等[1]證明了JSSP是一個NP難問題。在JSSP中，所有工件在不同的機器上進行加工，每個工件由連續(xù)的多道工序組成，每道工序在指定的一臺機器上加工，并且每道工序的可加工機器只有一臺。和JSSP不同的是，柔性作業(yè)車間調度問題(Flexible Job Shop Scheduling Problem，簡稱FJSSP)允許每道工序可在多臺機器上進行加工。以至于FJSSP相對JSSP來說，變得更加復雜和難以解決。通常，柔性作業(yè)車間調度需要同時解決兩個問題：將每道工序分配到可用的機器上和將每臺機器上的工序進行排序并加工。

由于柔性作業(yè)車間調度的復雜性，研究人員提出了許多不同的算法來解決此類問題。例如基于規(guī)則的調度方法[2]、變鄰域搜索方法[3]、人工神經網(wǎng)絡方法[4]、禁忌搜索算法[5]、遺傳算法[6]和粒子群算法[7]等。然而，上述算法都是用來解決靜態(tài)的FJSSP，即在進行車間調度時，只要在初始時刻生成調度，那么在生產過程中所有的工件以及機器數(shù)量是不可變的，并且工序只要被分配到機器上就肯定會被加工。但是，在實際生產中，車間內經常發(fā)生一些不可預知的異常事件。例如，新的緊急訂單的加入、機器故障的發(fā)生、工人的缺勤等等，這些都會導致先前生成的調度不再適合新的調度環(huán)境。因此，柔性作業(yè)車間動態(tài)調度(Flexible Job Shop Dynamic Scheduling，簡稱FJSDS)問題受到越來越多的關注。M.Gholami等[8]通過一種集成仿真和遺傳算法的方法來解決隨機機器故障的FJSDS問題；A.Rajabinasab等[9]利用信息素方法，通過建立相應的多代理調度系統(tǒng)，來解決一種工件隨機到達、機器故障等異常事件發(fā)生的FJSDS問題；T.Ning等[10]提出了一種仿真模型，應用改善混合多相粒子群算法來解決FJSDS問題。

盡管針對FJSDS問題已有諸多研究，但對于航空制造企業(yè)來說，航空零件具有生產工藝復雜、生產周期長、單件小批量的生產特點，現(xiàn)有的粗放式生產管理方式嚴重制約著我國航空制造業(yè)的發(fā)展。雖然企業(yè)資源規(guī)劃、MES等系統(tǒng)已在多數(shù)航空加工企業(yè)中得到應用，但是航空企業(yè)使用傳統(tǒng)的FJSDS方法，通常由于調度結果難以解決復雜問題而不能滿足需求。具體表現(xiàn)在以下兩個方面：

(1) 傳統(tǒng)的FJSDS方法優(yōu)化多目標問題主要應用的方法有兩種：帕累托優(yōu)化和基于權重的優(yōu)化。在帕累托優(yōu)化中，會生成一些可行解供決策者選擇[11]，但決策者從大量的可行解中選取合適的解是一件不容易的事。而在基于權重的多目標優(yōu)化中，目前多是將各個目標的權重賦予一個固定的值[12]，即各個目標的權重是固定不變的，并不能隨著車間的實時狀況或者管理者需求的變化而變化。

(2) 在傳統(tǒng)FJSDS問題中，優(yōu)化目標很少考慮生產中的能耗。眾所周知，全球性的氣候問題使人們對環(huán)境的關注度越來越高，制造企業(yè)作為能源的主要消耗者，各國政府已經陸續(xù)制定強制措施，要求制造企業(yè)節(jié)能減排，以應對全球性的環(huán)境污染問題。

因此，基于上述分析以及航空制造企業(yè)的特殊性，本文提出一種新的動態(tài)調度方法對工序進行實時分配。在此方法中，應用基于“窮盡成對比較”技術的多目標權重參數(shù)調節(jié)方法來調節(jié)動態(tài)調度時目標參數(shù)的權重。此外，通過對航空企業(yè)動態(tài)調度過程的分析，將最大完工時間、生產加工成本以及能耗作為優(yōu)化目標，給出一種基于改進匈牙利算法的FJSDS方法。最后，通過仿真實驗驗證系統(tǒng)的有效性和可行性。

1 FJSDS的數(shù)學模型

1.1 FJSDS描述

一般的，F(xiàn)JSSP分為完全柔性作業(yè)車間調度和部分柔性作業(yè)車間調度。在完全柔性作業(yè)車間調度中，每個工序可以在任何一個機器上進行加工。而部分柔性作業(yè)車間調度中，至少有一個工序不能在任意一個機器上進行加工。對于航空制造企業(yè)來說，航空零件的加工屬于部分柔性作業(yè)車間調度。因此，本文研究部分柔性作業(yè)車間調度問題。

部分柔性作業(yè)車間調度模型如下：有n個航空工件J={J1,J2,…,Jn}在m臺機器M={M1,M2,…,Mm}上加工。每個航空工件Ji有ni道工序{Oi1,Oi2,…,Oini}。按照航空工件的工藝路線要求，每個航空工件的工序具有順序約束。調度的任務就是將所有工序分配到相應的加工機器并確定工序的開始加工時間，使得優(yōu)化的目標達到最優(yōu)。為了建立數(shù)學模型，對一些符號和變量定義如表1所示。

表1 符號和變量定義

航空工件加工過程中一般滿足以下條件：

(1) 每臺機器在同一時刻最多只能加工一道工序；

(2) 每道工序同一時刻最多只能被一臺機器加工；

(3) 航空工件的加工過程需符合預先給定的工藝路線要求，同一個航空工件的不同工序不能同時加工；

(4) 工序一旦開始加工不能中斷，直至加工完成，除非機器發(fā)生故障；

(5) 各個航空工件之間相互獨立，不存在順序約束，相互之間沒有優(yōu)先級差別；

(6) 在零時刻，所有機器的初始狀態(tài)均為空閑可用。

1.2 數(shù)學建模

本文從航空制作企業(yè)生產實際和“綠色制造”出發(fā)，分別從最大完工時間、生產加工成本、生產能耗三個方面建立優(yōu)化目標。

(1) 最小化最大完成時間

F1=minf1=CM=Makespan=maxCijk
(i∈[1,n],j∈[1,ni],k∈[1,m])

(1)

(2) 最小化加工成本

(2)

(3) 最小化生產能耗

(3)

并滿足約束條件：

Ci,j,k≤Ci,j+1,k-ti,j+1,k(j=1,2,…,ni-1)

(4)

Ci,j,k≥0 (i=1,2,…,n)

(5)

(6)

式(1)～式(3)為動態(tài)調度優(yōu)化的三個目標，其中F1的單位為小時，F(xiàn)2的單位為百元，F(xiàn)3的單位為千瓦時；式(4)保證同一個工件的相鄰工序在前一道工序加工完后才能加工下一道工序；式(5)表明每道工序的加工時間都大于零；式(6)保證一道工序只能在一臺機器上進行加工。

上述優(yōu)化目標和約束函數(shù)可保證動態(tài)調度結果的可行性及有效性，為“綠色生產”提供技術支持。此外，通過基于權重的調度方法，將多目標優(yōu)化問題轉化為單目標優(yōu)化問題。

即優(yōu)化總目標為

(7)

2 FJSDS的調度方法

2.1 FJSDS方法流程

本文提出一種針對航空制造企業(yè)的基于改進匈牙利算法的FJSDS方法流程，如圖1所示。在調度時刻t，根據(jù)每一個目標的重要程度計算F中各個目標權重的參數(shù)；根據(jù)上述各目標權重參數(shù)，計算動態(tài)調度系統(tǒng)中可加工工序與可用機器進行匹配時的成本，即總目標F，然后采用改進匈牙利算法尋找工序與機器的最優(yōu)分配結果。在t+1時刻，重復上述過程直到航空工件加工完成。

圖1 基于改進匈牙利算法的柔性作業(yè)車間動態(tài)調度方法流程

2.2 FJSDS的策略

在FJSDS系統(tǒng)中，機器的狀態(tài)有兩種：可用與不可用；而工序的狀態(tài)有三種：正在加工、已加工、未加工。在真實的航空制造車間，由于不可預知異常事件的發(fā)生，前一調度時刻的分配在當前時刻不再最優(yōu)。并且伴隨著機器和工件數(shù)量的增多，使得調度計算的復雜度不斷增加。因此，本文提出一種動態(tài)調度策略對工序進行實時分配，其過程如圖2所示。在某一時刻t，將所有未加工工序中的可加工工序放入任務池中；同時，將機器集中、可用機器挑出，則在t時刻的調度問題就是如何將任務池中的工序分配到相應的可用機器上。本文應用“窮極成對比較”技術來實現(xiàn)多目標權重的選擇，并利用改進匈牙利算法對任務池中的工序進行分配。

圖2 動態(tài)調度的策略

3 基于“窮盡成對比較”技術的多目標權重參數(shù)調節(jié)方法

在進行動態(tài)調度時，首先需要確定三個目標Fz在總目標F中的權重關系。一般對于基于權重的多目標優(yōu)化，大都會將權重ωz設為固定值，但是此種方法不適用于動態(tài)環(huán)境下的柔性作業(yè)車間調度系統(tǒng)優(yōu)化。為了應對在實際航空制造過程中異常事件的發(fā)生，使調度系統(tǒng)可以根據(jù)車間中環(huán)境的實時變化而對生產目標進行實時的調整，本文研究一種基于“窮盡成對比較”技術的多目標權重參數(shù)調節(jié)方法。

設有目標集合{f1,f2,…,fp,…,fq,…,fs}，且設fpq表示目標fp與目標fq的重要性的比較，則

此處，為了避免某一目標的權重為零，在目標集合中添加一個虛擬目標fs+1，則新的目標集合為{f1,f2,…,fp,…,fq,…,fs,fs+1}。

所有的原目標與虛擬目標進行比較，則fp,s+1=1 (p=1,2,…,s)。

可得出所有目標比較值之和：

(8)

各個目標的權重為

(9)

在本文所提出的三個優(yōu)化目標中，通過式(7)可將三個優(yōu)化目標轉化為一個單目標問題。則：

因此，決策者可根據(jù)航空制造企業(yè)車間中的實時狀態(tài)，通過本文提出的基于“窮盡成對比較”技術的多目標權重參數(shù)調節(jié)方法來調節(jié)各個目標的權重參數(shù)，使得在進行動態(tài)調度時滿足車間中管理者的需求，更好地應對未知異常事件。

4 基于改進匈牙利算法的FJSDS方法

4.1 基于改進匈牙利算法的動態(tài)調度問題目標描述

使用基于匈牙利算法的FJSDS目的在于減少航空工件完工時間，提高生產效率，降低航空制造企業(yè)成本，同時在動態(tài)調度的過程中兼顧對環(huán)境的影響。設在FJSDS系統(tǒng)中，在時刻t車間中有x個可加工工序和y臺可用機器，則該t時刻動態(tài)調度系統(tǒng)的優(yōu)化目標為

(10)

式中：X為匹配系數(shù)矩陣，當機器j加工工件i時，Xij=1，否則為0；C為動態(tài)調度的目標F匹配矩陣；cij為工件i被機器j加工時的目標F的值。

4.2 算法步驟

式(10)的求解問題可轉化為一個二部賦權圖的最佳匹配問題，而khun-Munkres(KM)算法可用來求解二部賦權圖，其本質是一種基于匈牙利算法的標號方法。

利用KM算法求解FJSDS問題時，在某一調度時刻t，有以下三種情況：

(1) 當可用機器和可加工工序相同時，直接根據(jù)模型進行求解；

(2) 當可用機器大于可加工工序時，則設置虛擬可加工工序，使得可加工工序與可用機器數(shù)量相同。由于實際上該調度不會執(zhí)行，則設置虛擬加工工序的目標F值為零；

(3) 當可用機器小于可加工工序時，則設置虛擬可用機器，使可用機器與可加工工序數(shù)量相同。

通過以上變換后，即可將二部賦權圖轉變?yōu)橥陚涠抠x權圖，通過完備二部賦權圖求得最佳匹配。

本文提出的改進匈牙利算法是在KM算法上進行改進，在t時刻，算法具體步驟如下：

Step1 對于一個完備的二部賦權圖G=(X,Y)中，X和Y分別表示可用機器集和可加工工序集。對于X和Y的頂點都賦予一個標號，分別記為L(x)和L(y)。通過式(11)，取L為G的初始可行點，并執(zhí)行匈牙利算法，得出M為GL的一個匹配。

(11)

Step2 若X的每個點都是飽和的，則M為所求的最小權完美匹配；否則取M的非飽和點u∈X，令S={u},T≠φ，轉向Step3。

Step3 記NL(s)={v|u∈S,uv∈GL}。若NL(s)=T，則GL沒有完美匹配，轉向Step4，否則轉向step5。

Step4 調整標記，計算aL=min{L(x)+L(y)-C(xy)x∈S,y∈Y-T}，得到一個新的可行點H(v)。令L=H,GL=GH，重新給出一個GL的一個匹配M，轉向Step1。

Step5 取y∈NL(s)-T，若y是M的飽和點，轉向Step6，否則轉向Step7。

Step6 設xy∈M，則令S=S∪{x},T=T∪{y}，轉向Step2。

Step7 在GL中的u-y路是M-增廣路，設為P，并令M=M⊕P，轉向Step1。

Step8 若工序與機器的最優(yōu)匹配不止一個，也即存在多個最優(yōu)匹配時，選取一個目標值F為最小的匹配。

Step9 在下一個t=t+1時刻，重復Step1～Step8，直到所有工序加工完成。

基于改進匈牙利算法的工序分配方法如圖3所示。

t時刻 調度優(yōu)化總目標可用機器可加工工序最大完成時間因素加工成本因素生產總能耗因素 F=ω1f1+ω2f2+ω3f3↓ 最佳匹配矩陣 目標函數(shù)匹配矩陣 CBM=1…0???0…0n×n←———C=c11…c1y…cij…cx1…cxy

圖3 基于改進匈牙利算法的工序分配方法

Fig.3ProcessallocationmethodbasedonimprovedHungaryalgorithm

5 算法實例仿真實驗與分析

5.1 實例仿真

針對某航空企業(yè)某車間實際的原始數(shù)據(jù)，經過整理后，給出一個8×8的調度問題，如表2所示。在此例子中，J9作為車間中的異常事件(緊急加單)。符號“-”表示機器不具備加工對應工序的能力。因此，給出的數(shù)據(jù)為一個部分柔性作業(yè)車間的加工數(shù)據(jù)。為了簡化調度問題，本文將符號“-”轉變?yōu)?99。通過此方法，部分柔性問題就轉變?yōu)橐粋€完全柔性問題。在表2中，行MK和列Oij旁邊的三個數(shù)字(x, y, z)表示第i個工件的第j個工序在機器k上的費用成本是“x”，切削時間是“y”，切削功率是“z”。

某航空企業(yè)某車間每一個機器在開機狀態(tài)且未加工時的空閑功率如表3所示。

表2 加工信息

表3 機器空閑時的功率

為了說明本文在有異常事件發(fā)生時動態(tài)調度的過程，假設四種異常事件的發(fā)生：機器故障、緊急加單、訂單取消以及質量問題。具體描述如下：(1) 機器5在t1(t1=3)時刻發(fā)生故障，維修好的時間為t2(t2=6)；(2) 工件9加入在t3(t3=6)時刻，作為緊急加單加入到未加工工序隊列；(3) 工件6在t4(t4=3)時刻被取消加工；(4) O22在加工完成后被檢測出有質量問題，需要重新加工。則通過本文提出的動態(tài)調度方法進行動態(tài)調度的結果如圖5所示。

(a) 異常事件-機器故障

(b) 異常事件-緊急加單

(c) 異常事件-訂單取消

5.2 實驗結果比較及分析

(1) 動態(tài)調度過程中無異常事件發(fā)生

為了驗證本文提出的動態(tài)調度方法在無異常事件發(fā)生時的有效性，將本文提出的方法與現(xiàn)有傳統(tǒng)調度方法進行比較，其中包括基于權重的優(yōu)化方法：AL+CGA[13]、PSO+TS[14]；以及基于帕累托的優(yōu)化方法：混合排序免疫模擬算法(HSISAT)[15]。動態(tài)調度結果如表4所示。

表4 各種方法調度結果比較

從表4可以看出：對于A目標，本文提出的方法優(yōu)于AL+CGA和PSO+TS兩種算法，相對這兩種方法，本文提出的方法能夠節(jié)省生產加工成本最大為5.3%，最小為3.6%；雖然本文提出的方法得出的CM比其他幾種方法稍大，但是本文提出方法得出的E為114.56，意味著相比其他三種方法最大提高為5.5%，最小提高2.6%。表明本文提出的基于改進匈牙利算法的動態(tài)調度方法在車間生產過程無異常事件發(fā)生時是有效的。

(2) 動態(tài)調度過程中有異常事件發(fā)生

為了驗證本文提出的動態(tài)調度方法在有異常事件發(fā)生時的有效性，將本文的方法與現(xiàn)有傳統(tǒng)的動態(tài)調度方法進行比較，包括遺傳算法+周期性策略調度方法[16]、基于啟發(fā)式規(guī)則調度方法[17]。在啟發(fā)式規(guī)則算法中，工序有兩種常用的優(yōu)先權分配規(guī)則，包括最短加工時間(SPT)和最大工序剩余(MOPNR)規(guī)則。此外，考慮兩種機器分配規(guī)則(MARs)：第一種是將工序分配到具有最小加工時間的機器上(MAR1)；第二種是將工序分配到當前機器負荷最小的機器上(MAR2)。為了說明動態(tài)調度的過程，設定四種異常事件的發(fā)生： M1,M3,M6和M8在時刻t1=4、t2=5、t3=6、t4=7分別發(fā)生機器故障，在時刻t5=6、t6=7、t7=8、t8=9四臺機器分別開始可用。通過計算，得出對于四種異常事件發(fā)生時各個動態(tài)調度方法給出的動態(tài)調度結果，如表5所示。

表5 異常事件發(fā)生時動態(tài)調度結果比較

從表5可以看出：使用傳統(tǒng)動態(tài)調度方法所得CM的最大值和最小值分別為37和22h，意味著本文提出的方法可以將最大完成時間提高最大43.2%、最小4.8%；本文方法得出的生產加工成本為52.3百元，傳統(tǒng)的動態(tài)調度方法得出的最好值是76.4百元，最壞的值為100.5百元；此外，本文方法得出的E為135.67kW·h，能耗值明顯低于傳統(tǒng)動態(tài)調度方法。

因此，基于以上仿真數(shù)據(jù)以及對比實驗數(shù)據(jù)可以得出，本文提出的基于改進匈牙利算法的柔性作業(yè)車間動態(tài)調度方法對于航空企業(yè)提高生產率，降低生產成本以及減少能耗是有效、可行的。

6 結 論

改進的匈牙利算法能夠解決航空制造企業(yè)中的動態(tài)調度問題，可有效地提高企業(yè)的生產效率，通過仿真實驗證明，該方法在航空制造車間動態(tài)調度中具有有效性和可行性。

目前，對于在航空企業(yè)中的動態(tài)調度研究主要集中在應用啟發(fā)式算法進行調度的優(yōu)化，而對分布式的實時調度研究很少。后續(xù)研究的主要方面有：(1) 優(yōu)化模型，添加模型中未考慮的某些因素，例如“綠色生產”中碳排放問題；(2) 研究車間中的基于實時數(shù)據(jù)的動態(tài)調度問題，例如運用實時數(shù)據(jù)進行車間的動態(tài)優(yōu)化。