王晉，王鵬，郭豐赫

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

0 引 言

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

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

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

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

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

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

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

1 FJSDS的數(shù)學(xué)模型

1.1 FJSDS描述

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

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

表1 符號(hào)和變量定義

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

(1) 每臺(tái)機(jī)器在同一時(shí)刻最多只能加工一道工序；

(2) 每道工序同一時(shí)刻最多只能被一臺(tái)機(jī)器加工；

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

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

(5) 各個(gè)航空工件之間相互獨(dú)立，不存在順序約束，相互之間沒(méi)有優(yōu)先級(jí)差別；

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

1.2 數(shù)學(xué)建模

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

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

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

(1)

(2) 最小化加工成本

(2)

(3) 最小化生產(chǎn)能耗

(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)為動(dòng)態(tài)調(diào)度優(yōu)化的三個(gè)目標(biāo)，其中F1的單位為小時(shí)，F(xiàn)2的單位為百元，F(xiàn)3的單位為千瓦時(shí)；式(4)保證同一個(gè)工件的相鄰工序在前一道工序加工完后才能加工下一道工序；式(5)表明每道工序的加工時(shí)間都大于零；式(6)保證一道工序只能在一臺(tái)機(jī)器上進(jìn)行加工。

上述優(yōu)化目標(biāo)和約束函數(shù)可保證動(dòng)態(tài)調(diào)度結(jié)果的可行性及有效性，為“綠色生產(chǎn)”提供技術(shù)支持。此外，通過(guò)基于權(quán)重的調(diào)度方法，將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題。

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

(7)

2 FJSDS的調(diào)度方法

2.1 FJSDS方法流程

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

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

2.2 FJSDS的策略

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

圖2 動(dòng)態(tài)調(diào)度的策略

3 基于“窮盡成對(duì)比較”技術(shù)的多目標(biāo)權(quán)重參數(shù)調(diào)節(jié)方法

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

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

此處，為了避免某一目標(biāo)的權(quán)重為零，在目標(biāo)集合中添加一個(gè)虛擬目標(biāo)fs+1，則新的目標(biāo)集合為{f1,f2,…,fp,…,fq,…,fs,fs+1}。

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

可得出所有目標(biāo)比較值之和：

(8)

各個(gè)目標(biāo)的權(quán)重為

(9)

在本文所提出的三個(gè)優(yōu)化目標(biāo)中，通過(guò)式(7)可將三個(gè)優(yōu)化目標(biāo)轉(zhuǎn)化為一個(gè)單目標(biāo)問(wèn)題。則：

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

4 基于改進(jìn)匈牙利算法的FJSDS方法

4.1 基于改進(jìn)匈牙利算法的動(dòng)態(tài)調(diào)度問(wèn)題目標(biāo)描述

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

(10)

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

4.2 算法步驟

式(10)的求解問(wèn)題可轉(zhuǎn)化為一個(gè)二部賦權(quán)圖的最佳匹配問(wèn)題，而khun-Munkres(KM)算法可用來(lái)求解二部賦權(quán)圖，其本質(zhì)是一種基于匈牙利算法的標(biāo)號(hào)方法。

利用KM算法求解FJSDS問(wèn)題時(shí)，在某一調(diào)度時(shí)刻t，有以下三種情況：

(1) 當(dāng)可用機(jī)器和可加工工序相同時(shí)，直接根據(jù)模型進(jìn)行求解；

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

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

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

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

Step1 對(duì)于一個(gè)完備的二部賦權(quán)圖G=(X,Y)中，X和Y分別表示可用機(jī)器集和可加工工序集。對(duì)于X和Y的頂點(diǎn)都賦予一個(gè)標(biāo)號(hào)，分別記為L(zhǎng)(x)和L(y)。通過(guò)式(11)，取L為G的初始可行點(diǎn)，并執(zhí)行匈牙利算法，得出M為GL的一個(gè)匹配。

(11)

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

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

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

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

Step6 設(shè)xy∈M，則令S=S∪{x},T=T∪{y}，轉(zhuǎn)向Step2。

Step7 在GL中的u-y路是M-增廣路，設(shè)為P，并令M=M⊕P，轉(zhuǎn)向Step1。

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

Step9 在下一個(gè)t=t+1時(shí)刻，重復(fù)Step1～Step8，直到所有工序加工完成。

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

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

圖3 基于改進(jìn)匈牙利算法的工序分配方法

Fig.3ProcessallocationmethodbasedonimprovedHungaryalgorithm

5 算法實(shí)例仿真實(shí)驗(yàn)與分析

5.1 實(shí)例仿真

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

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

表2 加工信息

表3 機(jī)器空閑時(shí)的功率

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

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

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

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

5.2 實(shí)驗(yàn)結(jié)果比較及分析

(1) 動(dòng)態(tài)調(diào)度過(guò)程中無(wú)異常事件發(fā)生

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

表4 各種方法調(diào)度結(jié)果比較

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

(2) 動(dòng)態(tài)調(diào)度過(guò)程中有異常事件發(fā)生

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

表5 異常事件發(fā)生時(shí)動(dòng)態(tài)調(diào)度結(jié)果比較

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

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

6 結(jié) 論

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

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