變擾動強度下柔性裝配作業(yè)車間調(diào)度性能分析

楊小佳，劉建軍，陳慶新，毛 寧

(廣東工業(yè)大學(xué)廣東省計算機(jī)集成制造重點實驗室，廣東 廣州 510006)

0 引言

柔性作業(yè)車間(Flexible Job Shop，F(xiàn)JS)考慮了零件多可選工藝路徑和工序多可選設(shè)備等加工柔性，相對于作業(yè)車間調(diào)度問題(Job-shop Scheduling Problem，JSP)，柔性作業(yè)車間的調(diào)度決策包含了確定各零件的加工設(shè)備(路徑)及在各設(shè)備的加工順序(開完工時間)兩部分[1-3]。鑒于FJS調(diào)度是比JSP更為復(fù)雜的NP-難問題，眾多研究致力于提出各種近似求解算法，其中啟發(fā)式優(yōu)先度規(guī)則與元啟發(fā)式智能優(yōu)化算法是兩類最常見的近似算法[1-6]。

柔性裝配作業(yè)車間(Flexible Assembly Job Shop，F(xiàn)AJS)在FJS的基礎(chǔ)上進(jìn)一步考慮了零件的裝配關(guān)聯(lián)約束。FAJS是裝備制造企業(yè)中一種常見的車間類型，路徑和工時差異化的零件分別進(jìn)行機(jī)加工，待裝配關(guān)聯(lián)零件機(jī)加工完工后才能開始裝配工序。相比于FJS，F(xiàn)AJS生產(chǎn)中協(xié)同裝配關(guān)聯(lián)零件的生產(chǎn)進(jìn)度是生產(chǎn)調(diào)度的關(guān)鍵。這是因為關(guān)聯(lián)零件盡可能同時進(jìn)入裝配車間能夠減少關(guān)聯(lián)零件的裝配等待時間，有利于將產(chǎn)能讓予緊急的零件，進(jìn)而提高車間生產(chǎn)的效率。Nourali等[7-8]最早建立了FAJS的混合整數(shù)規(guī)劃數(shù)學(xué)模型，并在靜態(tài)環(huán)境中以makespan為優(yōu)化目標(biāo)提出一種粒子群算法進(jìn)行求解。

考慮到生產(chǎn)執(zhí)行過程的動態(tài)性，生產(chǎn)調(diào)度不僅需要考慮計算的復(fù)雜度，還需明確執(zhí)行過程中擾動的響應(yīng)策略?，F(xiàn)有的動態(tài)調(diào)度響應(yīng)策略有完全反應(yīng)式調(diào)度、預(yù)測-反應(yīng)式調(diào)度與魯棒性調(diào)度3種[9]。其中，魯棒性調(diào)度需先預(yù)計擾動因素對調(diào)度引起的影響，再生成對擾動因素不敏感的調(diào)度方案[10]，但在帶多種擾動且零件存在裝配關(guān)聯(lián)的車間中，擾動所帶來的影響難以事先做出預(yù)測。完全反應(yīng)式調(diào)度是一種基于事件的實時調(diào)度策略，當(dāng)零件工序完工時，為零件選擇下一道工序的加工設(shè)備，同時為空閑的設(shè)備選擇下一個上機(jī)的待加工零件。為了滿足完全反應(yīng)式的實時調(diào)度需求，一般采用啟發(fā)式優(yōu)先度規(guī)則求解。在柔性車間中，啟發(fā)式優(yōu)先度規(guī)則分為設(shè)備選擇規(guī)則和作業(yè)分派規(guī)則兩類。文獻(xiàn)[11-12]在FJS中，研究了這兩類規(guī)則多種組合在不同環(huán)境下的性能表現(xiàn)，而文獻(xiàn)[13]研究了不同柔性程度對設(shè)備選擇規(guī)則與分派規(guī)則組合性能的影響。但上述研究中并未考慮零件的裝配關(guān)聯(lián)。而預(yù)測-反應(yīng)式調(diào)度策略則是先總體上制定所有零件的預(yù)調(diào)度計劃，當(dāng)執(zhí)行中遇到擾動再修正預(yù)調(diào)度計劃。文獻(xiàn)[14]分別采用優(yōu)先度規(guī)則、整數(shù)規(guī)劃與約束規(guī)劃3種算法求解預(yù)調(diào)度計劃，當(dāng)遇到擾動時再修正計劃。

由上述分析可知，預(yù)測-反應(yīng)式調(diào)度和完全反應(yīng)式調(diào)度是兩種比較適合FAJS的動態(tài)調(diào)度策略。其中，預(yù)測-反應(yīng)式調(diào)度策略從全局上安排各個零件的加工路徑及上機(jī)順序，具有較好的全局優(yōu)度。但是，在存在裝配關(guān)系的生產(chǎn)中，擾動的發(fā)生可能會導(dǎo)致原有計劃性能的下降。因為返修或設(shè)備故障等擾動，需要快速調(diào)整其關(guān)聯(lián)零件的進(jìn)度計劃，否則不僅無法如期開始裝配工序，還會因為提前開工而搶占了產(chǎn)能，反過來又會導(dǎo)致更廣泛的進(jìn)度不協(xié)同問題。而采用優(yōu)先度規(guī)則的完全反應(yīng)式調(diào)度策略，能夠快速求解調(diào)度方案，有利于在動態(tài)環(huán)境中實時協(xié)同裝配關(guān)聯(lián)的零件，但分散的規(guī)則決策，缺乏總體上的優(yōu)化力度。

為研究不同綜合擾動強度對FAJS調(diào)度兩種調(diào)度策略的影響，本文將通過構(gòu)建一類存在多種擾動的仿真模型，分別進(jìn)行兩方面的研究:①分別對完全反應(yīng)式調(diào)度使用的設(shè)備選擇規(guī)則與分派規(guī)則進(jìn)行分析，進(jìn)一步分析兩類規(guī)則之間的組合效果，及其性能隨擾動強度變化的走勢;②實現(xiàn)一種基于遺傳算法的周期性滾動調(diào)度算法作為預(yù)測-反應(yīng)式調(diào)度代表。通過仿真實驗對比完全反應(yīng)式調(diào)度與預(yù)測-反應(yīng)式調(diào)度，分析兩者在多種擾動的環(huán)境下，調(diào)度性能隨著擾動強度變化的性能走勢。

1 研究問題及數(shù)學(xué)模型

柔性裝配作業(yè)車間的生產(chǎn)過程如圖1所示，研究將基于以下說明及假設(shè):

(1)機(jī)加工車間有n個不同工序的加工單元，每個單元中僅負(fù)責(zé)處理一類工序，單元主要包含1個待加工零件的緩存區(qū)、多臺同等能力的設(shè)備和1個質(zhì)檢中心。由于多臺設(shè)備共享同一個待加工零件的緩存區(qū)，不失一般性地將多臺設(shè)備視為1臺增強數(shù)倍加工能力的設(shè)備，后文假定各個加工單元僅有1臺加工設(shè)備。

(2)訂單i隨機(jī)到達(dá)，假定每個訂單僅包含1套產(chǎn)品，產(chǎn)品中包含多個零件的集合為Ji。零件j，j∈Ji的工藝路徑網(wǎng)絡(luò)類型為t，工藝路徑中各工序可選設(shè)備集合與其對應(yīng)的加工時間ptij在訂單到達(dá)后才可獲知。零件具有多工藝路徑與工序多可選設(shè)備的加工柔性，如圖2所示。本文采用網(wǎng)絡(luò)圖表示零件的工藝路徑，使用加工設(shè)備路徑表示零件各工序所有可能的加工設(shè)備選擇組合情況。

(3)不考慮零件原料的準(zhǔn)備時間，即零件j原料的可投產(chǎn)時間為訂單的到達(dá)時間。零件j各工序完工后，需要進(jìn)入質(zhì)檢中心進(jìn)行質(zhì)量檢查。如果質(zhì)量合格則進(jìn)行下一道工序，質(zhì)量不合格則需要返回當(dāng)前工序重新排隊、加工。

(4)裝配工序采用的是完全齊套裝配，即產(chǎn)品i下所有零件j機(jī)加工完成后，裝配工序才開始。由于裝配工序所需時間相對較短且固定，可根據(jù)訂單的交貨期倒推其裝配計劃開工時間。本文著重于機(jī)加工車間的調(diào)度，使得訂單i各零件的完工時間盡量接近裝配計劃開工時間。

(5)每臺加工設(shè)備同一時刻只能加工一個零件，設(shè)備一旦開工便不允許其他零件搶占。如果設(shè)備發(fā)生故障，維修后零件接著原有進(jìn)度繼續(xù)加工。

(6)不考慮物料的運輸時間。因為輸運時間相對于零件工序加工時間而言較小，且運輸設(shè)備的成本遠(yuǎn)小于加工設(shè)備的成本，不存在運輸能力不足的問題，所以忽略零件運輸時間。

(7)從訂單、工序與設(shè)備3方面考慮擾動事件，有以下4種:①訂單隨機(jī)到達(dá);②緊急訂單;③返工返修與;④設(shè)備故障維修/維護(hù)。

為了描述的準(zhǔn)確性，采用一個混合整數(shù)規(guī)劃數(shù)學(xué)模型表達(dá)生產(chǎn)調(diào)度過程。在此之前，先對模型中使用到的符號聲明如下:

i為產(chǎn)品訂單，i∈I;

ati為產(chǎn)品訂單i的到達(dá)時間;

j為產(chǎn)品訂單中的零件，j∈Ji;

k為零件的工序，k∈O;

m為加工設(shè)備，m∈M;

p為零件j中工藝路徑的下標(biāo)，p∈Pij;

Pij為訂單i零件j的工藝路徑集合;

Oijp為訂單i零件j的工藝路徑p中所有工序的集合;

oijpk為訂單i零件j的工藝路徑p中工序k，oijpk∈Oijp，將工藝路徑中第一道工序設(shè)為oijpf，最后一道工序設(shè)為oijpl;

Oij為訂單i零件j所有工序集合;

di為訂單i的交貨期;

Mij為訂單i零件j所有工序可選加工設(shè)備集合;

ptijpkm為訂單i零件j工序k使用加工設(shè)備m所需的加工時間;

apti為訂單i的裝配所屬時間;

L為一個極大的數(shù)。

Sijpkm為訂單i零件j工序k使用加工設(shè)備m的開工時間;

Cijpkm為訂單i零件j工序k使用加工設(shè)備m的完工時間;

Cij為訂單i零件j的完工時間(最后一道工序完工時間);

Wijp為如果訂單i零件j選擇工藝路徑p進(jìn)行加工，則Wijp=1，否則Wijp=0;

Xijpkm為如果訂單i零件j的工序oijpk選擇設(shè)備m進(jìn)行加工，則Xijpkm=1，否則Xijpkm=0;

Yijki'j'k'm為如果訂單i零件j工序k在設(shè)備m的加工順序比訂單i'零件j'工序k'早，則Yijki'j'k'm=1，否則Yijki'j'k'm=0。

約束條件:

其中:約束(1)和約束(2)表示零件僅選擇一條工藝路徑進(jìn)行加工且每道工序只能選擇一臺設(shè)備;約束(3)和約束(4)表示工序在設(shè)備上的開工時間小于或等于該工序在設(shè)備上完工時間，工序的完工時間大于或等于工序的開工時間;約束(5)為同一工藝路徑中工序之間的順序約束，即前道工序的完工時間小于或等于后一道工序的開工時間;約束(6)和約束(7)表示工序可選設(shè)備相同的零件不能同時進(jìn)行加工，即設(shè)備任何時刻加工零件不能超過一個;約束(8)定義了訂單完工的時間為訂單中最后完工零件的時間加上裝配所需時間;約束(9)～約束(11)表示決策變量為0-1變量。

2 動態(tài)調(diào)度求解

2.1 調(diào)度總流程

如圖3所示，生產(chǎn)調(diào)度是在已知訂單、零件與設(shè)備等信息，并在滿足約束的情況下制定出來的。其中，完全反應(yīng)式調(diào)度是一種實時情況的調(diào)度策略，車間整體的調(diào)度可分解為設(shè)備選擇和作業(yè)分派兩種實時的調(diào)度決策，前者是零件投放或零件工序完工時，為零件選擇加工設(shè)備選擇決策;后者是當(dāng)設(shè)備空閑時，選擇待加工隊列零件的上機(jī)分派決策。而預(yù)測-反應(yīng)式調(diào)度策略將制定所有待加工零件整體的預(yù)調(diào)度計劃，當(dāng)擾動發(fā)生時再重新生成或局部修正預(yù)調(diào)度計劃，以適應(yīng)新的車間狀態(tài)。針對所研究的帶多種擾動的柔性裝配作業(yè)車間，考慮到頻繁的完全重調(diào)度將會導(dǎo)致現(xiàn)實執(zhí)行的混亂，采用周期性滾動調(diào)度與局部修正的方式完成調(diào)度。

2.2 優(yōu)先度調(diào)度規(guī)則

2.2.1 設(shè)備選擇規(guī)則

設(shè)備選擇規(guī)則用于為零件選擇加工設(shè)備，盡管存在工藝路徑的柔性，但一旦為零件指派了加工設(shè)備也意味著確定了工藝路徑[6]。在考慮工藝柔性的車間動態(tài)調(diào)度研究中，現(xiàn)有設(shè)備選擇規(guī)則研究主要為局部規(guī)則，其僅從工序的角度作決策，如文獻(xiàn)[12]提出的最小負(fù)荷優(yōu)先SW、最小工時優(yōu)先SP等規(guī)則，局部設(shè)備選擇規(guī)則具有一定的短視性。本文將從零件加工路徑的角度提出兩種全局性規(guī)則與兩種經(jīng)典局部規(guī)則和隨機(jī)設(shè)備選擇規(guī)則RAND(基礎(chǔ)性規(guī)則)進(jìn)行實驗對比。

局部規(guī)則1最小工時優(yōu)先SP(smallest processing)，這是一種考慮工時節(jié)約的規(guī)則，其為零件緊接著的工序選擇一臺加工時間最短的設(shè)備，即選擇的設(shè)備m*需滿足:

式中:p'為零件緊接著的可選工藝路徑，k'為緊接著的下一道工序，M'為工序k'的可選設(shè)備集合。

局部規(guī)則2最小負(fù)荷優(yōu)先SW(smallest workload)，這是一種考慮車間各設(shè)備負(fù)荷均衡的規(guī)則，其為零件緊接著的工序選擇一臺待加工負(fù)荷最小的設(shè)備，即選擇的設(shè)備m*需滿足:

式中wijp'k'm為各可選設(shè)備當(dāng)前時刻的負(fù)荷量，即各待加工零件的當(dāng)前工序在該設(shè)備所需工時總和。

全局規(guī)則1最小加工設(shè)備路徑工時優(yōu)先RSP(routes smallest processing)，該規(guī)則是在SP規(guī)則的基礎(chǔ)上，進(jìn)一步考慮了加工設(shè)備路線的整體總工時，在零件首道工序加工前，為其選擇一條總工時最小的加工設(shè)備路徑q*，即需滿足:

式中:q為零件的設(shè)備加工路徑，Q為所有設(shè)備加工路徑集合，ptijq為加工設(shè)備路徑的工時總和。

全局規(guī)則2最小加工設(shè)備路徑負(fù)荷優(yōu)先RSW(routes smallest workload)，該規(guī)則是在SW規(guī)則的基礎(chǔ)上，考慮了加工設(shè)備路徑整體負(fù)荷情況。在零件首道工序加工前，為其選擇一條各設(shè)備負(fù)荷總和最小的加工設(shè)備路徑q*，即其需滿足:

式中wijq為加工設(shè)備路徑中各設(shè)備當(dāng)前負(fù)荷(零件當(dāng)前工序工時)的總和。

2.2.2 作業(yè)分派規(guī)則

作業(yè)分派規(guī)則作用于各設(shè)備中，當(dāng)零件工序完工時，為空閑的設(shè)備在待加工隊列中選擇下一個上機(jī)加工的零件。分派規(guī)則將根據(jù)設(shè)備與加工任務(wù)的屬性，如當(dāng)前隊列負(fù)荷、任務(wù)交貨期、剩余加工時間等情況，為每個待加工的零件計算一明確的優(yōu)先值，按優(yōu)先值排序再選優(yōu)上機(jī)完成調(diào)度[15-16]。相比普通的作業(yè)車間，本文所研究的柔性裝配作業(yè)車間，在調(diào)度過程需要考慮同屬訂單的各零件間的生產(chǎn)進(jìn)度協(xié)同。本文將對以下4種有代表性的考慮進(jìn)度協(xié)同的規(guī)則，進(jìn)行擾動強度影響實驗:

(1)先到先服務(wù)(First Come First Served，F(xiàn)CFS)。FCFS為基礎(chǔ)性的規(guī)則，在待加工隊列中選擇零件到達(dá)的時間最早的零件上機(jī)加工，各待加工零件的優(yōu)先度

(2)最早交貨期優(yōu)先(Earliest Due Date，EDD)。該規(guī)則以訂單交貨期評定優(yōu)先度，交貨期最緊的加工零件具有最高的優(yōu)先級，交貨期在訂單到達(dá)后不再變更，而同屬訂單中的各零件具有相同的優(yōu)先度，因此該規(guī)則具有靜態(tài)協(xié)同效果，EDD在裝配作業(yè)車間中，在平均拖期量指標(biāo)上表現(xiàn)最好[17]。該規(guī)則下，各待加工零件的優(yōu)先度

(3)裝配關(guān)聯(lián)零件最少總工序數(shù)量優(yōu)先(Total Least OPerations Remaining，TLOPR)。隨著零件加工進(jìn)度的推進(jìn)，各關(guān)聯(lián)零件的工序不斷減少，零件的優(yōu)先度也逐漸提高，從而有利于減少關(guān)聯(lián)零件之間的裝配等待時間、提高齊套性。該規(guī)則為動態(tài)協(xié)同規(guī)則，其優(yōu)先度

式中NOUij為產(chǎn)品i零件j的剩余工序數(shù)量。

(4)重要程度-最早交貨期優(yōu)先(Importance Ratio，IR)-EDD。關(guān)聯(lián)零件中剩余工序數(shù)量最多的零件為關(guān)鍵件，其將制約裝配工序的開工，應(yīng)該優(yōu)先加工。IR值為各零件工序數(shù)量與關(guān)鍵件工序數(shù)量的比值，IR值越大優(yōu)先度越高。如果IR值相同，則使用EDD規(guī)則進(jìn)行再次排序。該規(guī)則也為動態(tài)協(xié)同規(guī)則，其優(yōu)先度

2.3 基于優(yōu)先度的周期性滾動調(diào)度方法

周期性滾動調(diào)度的原理是將長期動態(tài)的生產(chǎn)劃分為多個周期進(jìn)行，將問題轉(zhuǎn)換為周期內(nèi)的靜態(tài)調(diào)度進(jìn)行求解[18-21]。如圖4所示，在周期性調(diào)度觸發(fā)時刻ts+1進(jìn)行周期ΔTs+1的重調(diào)度，制定周期ΔTs+1的零件排產(chǎn)預(yù)調(diào)度計劃。調(diào)度的零件包括在上一個調(diào)度周期s中尚未開工工序的零件以及在上一個調(diào)度周期s中新到達(dá)的零件。從周期性滾動調(diào)度的過程可以看出，其存在兩點不同于靜態(tài)的調(diào)度:①在周期性調(diào)度觸發(fā)時刻設(shè)備可能被上一個調(diào)度周期的零件占用，調(diào)度計劃制定過程需要滿足設(shè)備的最早可使用時間約束;②上一個調(diào)度周期中還有工序尚未開工的零件，如果在調(diào)度時刻正在加工，調(diào)度計劃制定需要滿足零件的最早可加工時間約束。

在各調(diào)度周期預(yù)生產(chǎn)計劃制定過程中，并不考慮周期內(nèi)可能遇到的各種擾動。而生產(chǎn)過程中將遇到設(shè)備故障與零件返修等多種擾動事件，擾動事件的出現(xiàn)使得原排產(chǎn)方案不再有效?？紤]到擾動的頻繁性，對周期內(nèi)的生產(chǎn)計劃采用局部修正的方法。本文采用一種基于優(yōu)先度的預(yù)調(diào)度計劃修正方法:在預(yù)調(diào)度計劃中確定各零件的加工優(yōu)先度，各設(shè)備空閑時將在待加工隊列中選擇優(yōu)先度最高的零件進(jìn)行加工[22]。具體流程如圖5所示，在零件1工序2返修過程中，零件2工序2到達(dá)設(shè)備3，此時設(shè)備3將優(yōu)先加工零件2，而零件1工序3將在零件2工序2完工后再加工。

上述周期性滾動調(diào)度方法，擬采用遺傳算法(Genetic Algorithm，GA)進(jìn)行求解調(diào)度計劃，后文簡稱P-GA方法。遺傳算法是一種經(jīng)典的最優(yōu)解搜索算法，常用于求解組合優(yōu)化問題[22]。首先編碼所有未完工的零件與新到達(dá)的零件，生成初始化種群，再通過交叉、變異等一系列遺傳算子不斷進(jìn)化種群，具體步驟如下:

(1)染色體編碼 采用一種雙層的整數(shù)染色體編碼方式表示一個可行的調(diào)度計劃。前半部分染色體表示各零件的加工優(yōu)先級，染色體基因的順序越靠前表示優(yōu)先度越高;后半部分染色體表示與前半部分對應(yīng)的各零件加工設(shè)備路徑序號。如染色體[2 8 9 1 6 4 3 5 7|3 2 4 2 3 1 1 2 3]表示了9個零件在設(shè)備上的加工優(yōu)先級，其中零件2的優(yōu)先級最高，選擇的加工設(shè)備路徑為3。

(2)種群初始化 初始種群為遺傳算法搜索的起點，為了提高算法搜索的效率，以及分析擾動對預(yù)測-反應(yīng)式調(diào)度與完全反應(yīng)式調(diào)度兩種策略的影響，后續(xù)將結(jié)合設(shè)備選擇規(guī)則與作業(yè)分派規(guī)則對種群進(jìn)行初始化。

(3)適應(yīng)度評估 采用最小化各訂單總拖期量作為周期內(nèi)調(diào)度目標(biāo)，并以此評估各個體染色體的適應(yīng)度，如式(20)所示:

式中:ci為訂單i的完工時間，di為訂單i的交貨期。周期內(nèi)各訂單的拖期量總和越小，代表對應(yīng)的個體染色體的適應(yīng)度越高，即該預(yù)調(diào)度方案越好。

(4)選擇操作 本文采用二元錦標(biāo)賽選擇法進(jìn)行選擇操作，該方法是一種放回抽樣的單元內(nèi)部競賽的方法。每次從種群中隨機(jī)抽取2個個體，再將適應(yīng)度值較大的個體(周期內(nèi)拖期量較小的調(diào)度方案)保留到下一代種群中，并放回另一個個體，重復(fù)抽樣直至達(dá)到種群數(shù)量。此外，為了種群更好地進(jìn)化，將每一代中最優(yōu)的個體保留到下一代。

(5)交叉與變異操作 采用部分映射雜交(Partial-Mapped Crossover，PMX)法對染色體的前半部分(零件優(yōu)先度)進(jìn)行交叉操作。如圖6所示，首先，隨機(jī)選擇兩個父代染色體，并隨機(jī)產(chǎn)生前半部分染色的兩個交叉點Pos1和Pos2兩個父代染色體交換兩交叉點之間的區(qū)域，父代1中的基因1變?yōu)?、6變?yōu)?、4變?yōu)?。交換后重復(fù)的基因則按原交叉區(qū)域的順序逐一替換，父代1中基因2替換為6、9替換為4、7替換為1。最后，根據(jù)父代中各零件原本選擇的加工設(shè)備路徑，還原子代染色體中各零件的設(shè)備加工路徑。

染色體的變異操作分為染色體前半部分零件優(yōu)先度逆轉(zhuǎn)變異算子和染色體后半部分加工設(shè)備路徑的基本位變異算子兩項。零件優(yōu)先度逆轉(zhuǎn)變異為隨機(jī)選擇染色體上的兩個基因(零件)，再逆轉(zhuǎn)兩個零件及其加工設(shè)備路徑的位置。加工設(shè)備路徑基本位變異則為零件隨機(jī)選擇另一條加工設(shè)備路徑。

3 仿真實驗及分析

3.1 仿真模型設(shè)定

車間由8臺單處理機(jī)構(gòu)成，代表8種不同工藝的機(jī)加工設(shè)備。前文已提及裝配過程采用的是完全齊套裝配方式，并假定裝配工序的能力充足，裝配所需時間穩(wěn)定，本文的研究重點為機(jī)加工車間的調(diào)度。產(chǎn)品生產(chǎn)訂單隨機(jī)到達(dá)，每個訂單僅包含1套產(chǎn)品生產(chǎn)需求，其交貨期服從離散均勻分布。每套產(chǎn)品包含的零件數(shù)量服從離散均勻分布[1，6]，各個零件的工藝路徑類型為圖7中的一類，各工藝路徑中的工序節(jié)點可選的加工設(shè)備在訂單到達(dá)后才隨機(jī)生成，各設(shè)備被采用的概率均等，加工設(shè)備數(shù)量為離散均勻分布[1，3]，即不存在長期的加工瓶頸。各工序的工時服從均值為1，方差為0.1小時的埃爾朗分布。仿真模型的設(shè)定總結(jié)如表1所示。

根據(jù)前人研究的歸納，車間生產(chǎn)調(diào)度過程中的擾動可以分為4類[23]:①訂單擾動，動態(tài)到達(dá)、交貨期變更等;②設(shè)備擾動，設(shè)備維護(hù)/維修等;③工序擾動，質(zhì)量事故等;④其他擾動，人員缺勤等。在實際企業(yè)中，常有部分緊急且重要的訂單到達(dá)，需要優(yōu)先處理。此外，零件的返修延誤或設(shè)備故障，需要調(diào)整其關(guān)聯(lián)零件的進(jìn)度計劃，否則它們不僅無法如期開始裝配工序，還會因為提前開工而搶占了產(chǎn)能，反過來又會導(dǎo)致更廣泛的進(jìn)度不協(xié)同問題。而相對設(shè)備資源等昂貴固定資產(chǎn)，人力等變動成本的彈性更大，且人員缺勤對生產(chǎn)調(diào)度所帶來的影響等價于設(shè)備不可加工擾動。因此，本文主要考慮前3類有代表性的擾動，除了訂單隨機(jī)到達(dá)外，還考慮了:①緊急訂單，有一定比例E的訂單為緊急訂單，其在原交貨期的基礎(chǔ)上再乘以緊急系數(shù)U，U=0.6;②設(shè)備維護(hù)/維修，設(shè)備預(yù)防性維護(hù)與故障維修有一定的不可加工時間占比F;③工件返工返修。零件在工序質(zhì)檢后有一定質(zhì)量事故率Q發(fā)生返修，需對當(dāng)前工序進(jìn)行返工。考慮到不同的產(chǎn)品企業(yè)中存到的擾動強度不一，設(shè)置了4種綜合的擾動強度。

仿真模型使用西門子的工廠生產(chǎn)仿真軟件Tecnomatix Plant Simulation 11.3 TR3搭建，并在內(nèi)存8 G，CPU 為Intel?Core(TM)i5-8250U 的個人電腦上進(jìn)行仿真實驗。仿真時間長度為260d(該時長內(nèi)將超過10，000個零件任務(wù)被加工)，重復(fù)執(zhí)行實驗30次。此外，為了避免仿真啟動時所有設(shè)備空閑所帶來的影響，將仿真時長的前60天做為仿真預(yù)熱時間，各指標(biāo)將在預(yù)熱時間后統(tǒng)計。

為了測試調(diào)度的性能，車間調(diào)度性能評價指標(biāo)如表2所示，表中:ci為產(chǎn)品i的完工時間;N為完工訂單的數(shù)量;NT為完工訂單中的拖期數(shù)量;ati為產(chǎn)品i的到達(dá)時間;TWm為各設(shè)備的平均加工時間;T為仿真時長;fi1為產(chǎn)品i中最早完工的零件的完工時間。流水時間類與交貨期類兩類指標(biāo)為車間性能評價指標(biāo)，而輔助統(tǒng)計量為輔助分析指標(biāo)，其中流水時間類指標(biāo)反映了車間在制品庫存的情況。本文假定訂單不可提前交貨，提前完工的產(chǎn)品需待到指定交貨期才能交付，因此，訂單的流水時間與訂單的提前期兩者相等。在按單生產(chǎn)(Make-To-Order，MTO)的生產(chǎn)模式下，交貨期類指標(biāo)的訂單拖期率與訂單拖期量能夠體現(xiàn)企業(yè)的服務(wù)水平，穩(wěn)定有保障的準(zhǔn)時交貨率有利于提高企業(yè)的信用，同時體現(xiàn)了調(diào)度的效率。訂單拖期率與平均拖期量互為對照分析，有利于分析較低的拖期率是否以惡化訂單拖期量為代價，反之分析較低的拖期量是否以訂單大規(guī)模拖期為代價[24]。輔助統(tǒng)計量中的設(shè)備平均稼動率能夠輔助分析設(shè)備選擇規(guī)則對車間設(shè)備稼動率的影響，而裝配等待時間反映了對關(guān)聯(lián)零件生產(chǎn)進(jìn)度的協(xié)同效果。

表1 仿真模型參數(shù)設(shè)定

表2 車間調(diào)度性能評價指標(biāo)

3.2 實驗設(shè)計與結(jié)果分析

下面從以下兩方面進(jìn)行實驗:①優(yōu)先度調(diào)度規(guī)則的組合性能分析。首先分別分析兩類規(guī)則單獨的性能及組合性能，其次分析擾動強度對其性能的影響。②調(diào)度規(guī)則與周期性滾動調(diào)度的性能對比分析。為了更好對比這兩者的性能，采用調(diào)度規(guī)則初始化種群，作為遺傳算法搜索的起點，并進(jìn)一步分析擾動對算法性能的影響。

3.2.1 優(yōu)先度調(diào)度規(guī)則組合性能分析實驗

實驗因素及其水平設(shè)置如表3所示，本實驗為分析調(diào)度規(guī)則的組合分析實驗?？紤]到過緊的交貨期設(shè)定將造成企業(yè)大規(guī)模拖期，不是企業(yè)正常的經(jīng)營狀態(tài)，交貨期設(shè)置為訂單到達(dá)時間加上一個服從[30，60]均分分布的隨機(jī)數(shù)，該設(shè)置將使得在綜合擾動強度1(僅訂單到達(dá)擾動)、隨機(jī)設(shè)備選擇規(guī)則RAND與作業(yè)分派規(guī)則FCFS下，訂單的拖期率大致為30%。性能指標(biāo)將從均值、方差與極大值3個緯度進(jìn)行衡量，方差與極大值能夠評價規(guī)則的惡化程度。對實驗因素各水平設(shè)置進(jìn)行全因素正交實驗，共5×4×1×4=80組實驗，各實驗組進(jìn)行30次重復(fù)實驗。

表3 實驗因素及其水平設(shè)置

表4為各設(shè)備選擇規(guī)則與基礎(chǔ)性作業(yè)分派規(guī)則FCFS的性能結(jié)果，由表可知:①在同一綜合擾動強度下，相較于基礎(chǔ)規(guī)則RAND，各設(shè)備選擇規(guī)則皆能提高車間的調(diào)度性能。SP、RSP規(guī)則能夠從節(jié)省工時的角度降低設(shè)備的平均稼動率，進(jìn)而提升調(diào)度性能。而SW、RSW 規(guī)則能夠從負(fù)荷均衡的角度減少零件的車間流水時間，進(jìn)而提升調(diào)度性能。②在不同的考慮角度下，全局規(guī)則與局部規(guī)則的優(yōu)劣結(jié)果不同。全局規(guī)則RSP優(yōu)于局部規(guī)則SP，這是由于RSP從整體路徑?jīng)Q策比SP從工序決策更節(jié)約工時。而在考慮負(fù)荷均衡的規(guī)則中，局部規(guī)則SW 優(yōu)于全局規(guī)則RSW。這是由于SW 規(guī)則是每道工序完工后進(jìn)行下一道工序的設(shè)備選擇決策，更能夠?qū)崟r考慮到當(dāng)前工序各可選設(shè)備的負(fù)荷，SW 規(guī)則比RSW 規(guī)則更有利于負(fù)荷的平衡。③不同的擾動強度并不影響設(shè)備選擇規(guī)則之間的性能差異。盡管擾動強度的提升劣化了各性能指標(biāo)，但由于各設(shè)備選擇規(guī)則的綜合考慮要素為零件工序的加工工時，擾動對此并無影響。

表4 設(shè)備選擇規(guī)則實驗結(jié)果

表5為各作業(yè)分派規(guī)則與基礎(chǔ)性設(shè)備選擇規(guī)則RAND的性能結(jié)果，由表可知:各規(guī)則皆優(yōu)于基礎(chǔ)規(guī)則FCFS，且擾動強度影響著各分派規(guī)則的性能優(yōu)劣。

在擾動強度1下，規(guī)則EDD能夠最小化訂單的平均拖期量，進(jìn)而優(yōu)化訂單的提前期與拖期率。相比EDD，規(guī)則TLOPR 在裝配等待時間上表現(xiàn)更好，更能協(xié)同各關(guān)聯(lián)零件的生產(chǎn)進(jìn)度，訂單提前期指標(biāo)均值上TLOPR性能表現(xiàn)最佳，但在各指標(biāo)的方差都是最大的，即存在部分訂單嚴(yán)重惡化的情況。規(guī)則IR-EDD在裝配等待時間指標(biāo)上表現(xiàn)最好，最能有效地減少關(guān)聯(lián)零件的裝配等待時間，但其最終車間性能指標(biāo)(訂單提前期與交貨期類指標(biāo))，相比EDD規(guī)則并無明顯優(yōu)勢。

在擾動強度為3與4的情況下，規(guī)則TLOPR在拖期率、拖期量與提前期3個指標(biāo)均值上都取得最好的表現(xiàn)。而且隨著擾動強度的上升，車間各性能的劣化程度明顯小于其他規(guī)則。這是由于TLOPR規(guī)則調(diào)度的原理是關(guān)聯(lián)零件總剩余工序數(shù)量越少的零件其優(yōu)先度越高，這意味著規(guī)則將會挑選總工序數(shù)量較少的訂單優(yōu)先加工，訂單將被提前交付，而這也將導(dǎo)致部分訂單被嚴(yán)重拖期。

表5 作業(yè)分派規(guī)則實驗結(jié)果

表6為各作業(yè)分派規(guī)則與各設(shè)備選擇規(guī)則的組合性能結(jié)果，由結(jié)果可知:組合規(guī)則能取得了更優(yōu)的結(jié)果，且很大程度上集成了兩類規(guī)則各自的性能。其中，RSP+EDD組合在訂單拖期率與平均拖期量指標(biāo)上取得了最好的表現(xiàn)，平均拖期量的極大值與方差也同樣是最小的。SW-TLOPR在訂單提前均值指標(biāo)中取得了最好的表現(xiàn)，但同樣其提前期最大值與方差是最大的，即存在部分訂單嚴(yán)重惡化的情況。

如圖8所示為不同擾動強度下各組合規(guī)則的性能結(jié)果，從圖8的實驗結(jié)果來看，隨著擾動強度的上升，各組合規(guī)則在各指標(biāo)上都逐漸劣化。其中:①在訂單平均拖期量指標(biāo)上，包含SP與RSP的組合規(guī)則，相對較好。RSP+EDD規(guī)則明顯優(yōu)于其他組合規(guī)則在各擾動強度下都能取得比較優(yōu)的結(jié)果。②在訂單拖期率指標(biāo)上，包含RSW 的組合規(guī)則表現(xiàn)最差，而包含TLNOP 的組合規(guī)則表現(xiàn)最好;包含EDD的組合規(guī)則，在擾動強度為1與2的環(huán)境下，表現(xiàn)相對較優(yōu)，但在擾動強度為3與4的環(huán)境下，劣化程度比較大。③在訂單平均提前期指標(biāo)上，SW+TLNOP規(guī)則的性能表現(xiàn)在各擾動強度情況下都取得最好的表現(xiàn)。而包含TLNOP的組合規(guī)則同樣也取得了較好的表現(xiàn)。

表6 組合規(guī)則實驗結(jié)果

續(xù)表6

3.2.2 周期性滾動調(diào)度性能分析實驗

初始種群是遺傳算法搜索的起點，為了分析擾動給周期性滾動方法P-GA 帶來的影響，將使用RSP+EDD組合初始化種群，作為P-GA 方法搜索的起點，也作為分析擾動對P-GA 方法影響的比較基準(zhǔn)。實驗由以下兩部分組成:①在擾動強度為1的情況下(僅存在零件動態(tài)到達(dá))，檢驗P-GA 方法的遺傳算法收斂性，并對比P-GA 方法與RSP+EDD組合規(guī)則調(diào)度的性能;②隨著擾動強度的上升，對比周期性滾動調(diào)度方法P-GA 與RSP+EDD組合規(guī)則的性能劣化程度對比。

通過預(yù)仿真實驗，算法中的參數(shù)設(shè)置如下:種群大小SIZE=20、交叉率Pc=0.55、零件優(yōu)先度逆轉(zhuǎn)變異率Pr=0.15和加工設(shè)備路徑的基本位變異率Pm=0.1。為減少仿真啟動時存在波動的影響，將在仿真時間第100天時檢驗算法的收斂性。如圖9所示，隨著迭代代數(shù)的增加，種群中平均個體與最佳個體的適應(yīng)值逐漸收斂，迭代到第35代左右基本收斂。在后續(xù)實驗中，設(shè)置P-GA 方法的迭代代數(shù)Gen=20代。

P-GA方法最終的性能不僅取決于單周期內(nèi)的結(jié)果，還取決于各周期的之間的疊加效果。后文中滾動調(diào)度周期長度相等，大小為8 h。分析擾動對P-GA方法影響實驗因素及其水平設(shè)置如表7所示。為了更好地分析兩種調(diào)度方法的性能差異，設(shè)置了3種交貨期松緊情況。

表8 為擾動強度1 時，P-GA 方法與RSP+EDD組合規(guī)則的性能比較結(jié)果。由表可知:①在訂單提前期指標(biāo)上，盡管P-GA方法比RSP+EDD組合規(guī)則在設(shè)備稼動率指標(biāo)上更高，但P-GA 在訂單平均提前期指標(biāo)上表現(xiàn)更好。由此可以看出，P-GA方法增加了各零件工序所需的工時，卻更能好地安排各零件的進(jìn)度，縮短零件在車間的流水時間。②在拖期率與拖期量指標(biāo)上，在交貨期設(shè)置為松的情況下，P-GA方法并無優(yōu)勢。但隨著交貨期設(shè)置越來越緊，P-GA方法的優(yōu)勢逐漸明顯。這是由于交貨期越緊，訂單越容易拖期，具有較大的優(yōu)化空間。

表7 實驗因素及其水平設(shè)置

表8 周期性滾動調(diào)度實驗結(jié)果

圖10與圖11為不同擾動強度下，P-GA 方法與RSP+EDD組合規(guī)則的性能比較結(jié)果。其中，圖10為不同交貨期設(shè)置下的，訂單拖期量和拖期率兩指標(biāo)的結(jié)果。由于交貨期的設(shè)置對訂單平均提前期指標(biāo)影響并不大，圖10僅呈現(xiàn)一種交貨期設(shè)置下訂單提前期性能結(jié)果。

由圖10a可知，在交貨期設(shè)置為緊的情況下，在拖期率指標(biāo)上，P-GA 調(diào)度方法在各擾動強度下都優(yōu)于RSP+EDD 組合規(guī)則。在拖期量指標(biāo)上，PGA最初具有一定的優(yōu)勢，但隨著擾動強度的上升，P-GA劣化程度明顯，RSP+EDD 組合規(guī)則更具明顯優(yōu)勢。

由圖10b和圖10c可知，在交貨期設(shè)置為中的情況下，擾動強度為1時，P-GA比RSP+EDD組合規(guī)則在拖期率指標(biāo)上有一定優(yōu)勢，但隨著擾動強度的上升，RSP+EDD 組合規(guī)則逐漸優(yōu)于P-GA 規(guī)則。在拖期量指標(biāo)上，RSP+EDD組合規(guī)則都優(yōu)于P-GA方法。而在交貨期設(shè)置為松的情況下，RSP+EDD 組合規(guī)則在拖期率和拖期量指標(biāo)上皆取得更好的結(jié)果。

由圖11可知，在訂單平均提前期指標(biāo)上，P-GA方法在擾動1和2的情況下，具有一定優(yōu)勢。而在高擾動的情況下，RSP+EDD組合規(guī)則更具優(yōu)勢。

綜上可知，在交貨期較緊且擾動強度不高的情況下，P-GA方法具有更好的優(yōu)化力度，能取得更好的車間性能。而在交貨期較松且擾動強度高的情況下，實時決策的RSP+EDD組合規(guī)則更適合。

4 結(jié)束語

完全反應(yīng)式調(diào)度與預(yù)測-反應(yīng)式調(diào)度是柔性裝配作業(yè)車間兩種常見的動態(tài)調(diào)度策略，而實際生產(chǎn)中存在的返工返修、設(shè)備故障等擾動給調(diào)度性能帶來一定的影響。本文圍繞著不同擾動強度對兩種不同調(diào)度策略的影響，展開了以下兩方面的研究:

(1)完全反應(yīng)式調(diào)度的優(yōu)先度規(guī)則研究 分析了設(shè)備選擇規(guī)則和作業(yè)分派規(guī)則兩類規(guī)則的單一性能和組合性能，及擾動強度所帶來的影響。本文從考慮工時節(jié)約和負(fù)荷均衡的角度選擇了兩則代表性的設(shè)備選擇規(guī)則SP和SW，并提出了對應(yīng)的兩則全局性規(guī)則RSP和RSW。而作業(yè)分派規(guī)則選擇了4則經(jīng)典的裝配作業(yè)車間協(xié)同規(guī)則。結(jié)果表明:考慮工時節(jié)約與負(fù)荷均衡的設(shè)備選擇規(guī)則皆能提高車間調(diào)度性能，而設(shè)備選擇與作業(yè)分派的組合性能更優(yōu)，且組合規(guī)則的性能很大程集合了兩者的特點，其中RSP+EDD 組合規(guī)則在交貨期類指標(biāo)上具有良好且穩(wěn)定的性能表現(xiàn)。

(2)基于遺傳算法的周期性滾動調(diào)度方法 提出一種基于遺傳算法的周期性滾動調(diào)度方法P-GA作為預(yù)測-反應(yīng)式調(diào)度的代表。周期性滾動將生產(chǎn)劃分為多個周期進(jìn)行，在各周期初采用遺傳算法求解預(yù)調(diào)度計劃，并在周期內(nèi)使用基于優(yōu)先度局部修正預(yù)調(diào)度計劃的擾動響應(yīng)方式。RSP+EDD 組合規(guī)則為遺傳算法初始化種群并作為對照基準(zhǔn)，通過實驗對比分析了擾動對P-GA 和RSP+EDD 兩者的影響，結(jié)果表明:在交貨期較緊且擾動強度不高的情況下，P-GA方法具有更好的優(yōu)化力度，能取得更好的車間性能。而在交貨期較松且擾動強度高的情況下，實時決策的RSP+EDD 組合規(guī)則調(diào)度更適合。

針對研究中加工環(huán)境與調(diào)度規(guī)則較為單一等不足，未來將從以下2方面作進(jìn)一步的研究:①考慮非同等能力處理機(jī)、零件加工準(zhǔn)備時間等更為復(fù)雜情況;②構(gòu)建規(guī)則動態(tài)選用機(jī)制，不同的調(diào)度規(guī)則有不同的優(yōu)化偏向，根據(jù)車間當(dāng)前的狀態(tài)從規(guī)則庫中動態(tài)地選用最適合的規(guī)則組合;③研究建立更高效的預(yù)測-反應(yīng)式調(diào)度算法。