基于信號驅(qū)動的多批處理綜合調(diào)度算法

基于信號驅(qū)動的多批處理綜合調(diào)度算法

1基于動態(tài)關(guān)鍵路徑的批量綜合調(diào)度算法隨著社會對產(chǎn)品個性化需求的增加，大量小批量產(chǎn)品和特別是單件產(chǎn)品的訂單越來越多，公司越來越需要一個基于合適路徑的整體設(shè)計方案。為了實現(xiàn)產(chǎn)品的內(nèi)部結(jié)構(gòu)，產(chǎn)品的內(nèi)部加工和安裝可以同時平行，縮短產(chǎn)品加工的總時間，本文提出了基于目標(biāo)路徑的方案。該算法為解決多產(chǎn)品加工和配置的綜合方案提供了好的解決方案，但該算法重視產(chǎn)品的豎向結(jié)構(gòu)，尤其是對布局結(jié)果的影響，忽視了不同路徑上的不同設(shè)備序列可以并行處理的事實?？紤]到此問題，本文提出了一種優(yōu)先、短用、長路景策略的規(guī)劃算法。由于文獻(xiàn)算法重視其他路徑中不同設(shè)備的聯(lián)合處理，考慮到長路景過程的規(guī)劃，文獻(xiàn)算法優(yōu)于文獻(xiàn)算法。雖然文獻(xiàn)是最好的，但如果強(qiáng)調(diào)橫向策略，產(chǎn)品的布局主要基于縱向。因此，文獻(xiàn)提出了基于文獻(xiàn)優(yōu)勢的基于動態(tài)路徑的布局算法，并以橫向為主布局。動態(tài)路徑法首先確定訂單的布局順序，然后將訂單插入設(shè)備的適當(dāng)距離，這不僅使設(shè)備有很多差距，而且要找到合適的距離需要很多的比較操作。由于事件的需要，預(yù)算編制順序不需要提前確定，因此文獻(xiàn)提出了基于設(shè)備休閑驅(qū)動的綜合方案。由于該算法不涉及訂單的休如操作，這不僅提高了設(shè)備的利用率，而且在設(shè)備上的操作時間也容易確定。目前批處理在單機(jī)調(diào)度、網(wǎng)絡(luò)組播調(diào)度、實時動態(tài)任務(wù)分配方面已有一些研究成果,但存在批處理設(shè)備的綜合調(diào)度問題的研究才剛剛開始.雖然基于文獻(xiàn)的批量綜合調(diào)度算法考慮了存在批處理設(shè)備的一般和動態(tài)綜合調(diào)度問題,但該算法還存在兩個方面問題:(1)可以批量調(diào)度的工序其緊前工序數(shù)不大于2;(2)批量調(diào)度的工序數(shù)量不大于2.而以上兩點(diǎn)弊端將嚴(yán)重限制該批量調(diào)度算法在實際生產(chǎn)調(diào)度中的應(yīng)用.為了避免上述的兩類問題,本文提出通過建立設(shè)備和調(diào)度2個子系統(tǒng),并通過相互間傳遞的信號進(jìn)行驅(qū)動的批綜合調(diào)度算法.該算法利用文獻(xiàn)算法的優(yōu)點(diǎn),設(shè)備信號通過設(shè)備驅(qū)動實現(xiàn);以“多批處理”命名,以區(qū)別以往的限制加工批量為2的調(diào)度算法;將工藝樹葉子節(jié)點(diǎn)工序中未加工的工序定義為可調(diào)度工序,緊前工序均處于加工狀態(tài)的工序定義為準(zhǔn)可調(diào)度工序,當(dāng)可調(diào)度工序與準(zhǔn)可調(diào)度工序批處理時,實現(xiàn)批處理不受緊前工序個數(shù)限制;通過信號驅(qū)動激活可調(diào)度工序,并判斷其是否與準(zhǔn)可調(diào)度工序滿足批組合策略,如果可批處理,將該工序的加工時間延遲至準(zhǔn)可調(diào)度工序的開始時間;當(dāng)已形成的可批處理工序組開始加工時,如果該工序組還可與其它準(zhǔn)可調(diào)度工序繼續(xù)組合形成更大的批處理工序組,可實現(xiàn)加工批量無限制.2多批處理條件下工序約束關(guān)系加工和裝配一同處理的綜合調(diào)度是將加工工序和裝配工序統(tǒng)一定義為加工工序,加工設(shè)備和裝配設(shè)備統(tǒng)一定義為加工設(shè)備,工序和設(shè)備統(tǒng)一調(diào)度,一般要求是:①每道工序的加工設(shè)備唯一.②同一加工設(shè)備在同一時刻只能加工一道工序.③每道工序必須在其所有緊前工序均已加工完畢,或沒有緊前工序時才可以在其加工設(shè)備上開始加工.④最后一道工序加工完畢時間為產(chǎn)品的總加工時間.設(shè)產(chǎn)品由N道工序組成,在M臺設(shè)備上加工,n(1≤n≤N)為工序編號,m(1≤m≤M)為設(shè)備編號.設(shè)End(n)為工序n的加工完畢時間,則產(chǎn)品加工總時間E=max[End(n)],于是一般綜合調(diào)度問題目標(biāo)函數(shù)為E=min{max{End(n)}}.根據(jù)加工工序是否存在緊前工序,將工序劃分為可調(diào)度工序和不可調(diào)度工序.其中不可調(diào)度工序為緊前工序未加工完畢的工序,即非葉子節(jié)點(diǎn)工序;可調(diào)度工序為無緊前工序或緊前工序均已加工完畢的工序,即為動態(tài)樹狀模型中的葉子節(jié)點(diǎn).定義1.多批處理設(shè)備.可以批量加工多個(≥2)工序的設(shè)備.多批處理對一般綜合問題的擴(kuò)展要求是:⑤同一加工設(shè)備在同一時刻可以加工多道工序,工序的數(shù)量受設(shè)備的批加工量限制,同時開始的工序結(jié)束時間相同.通過與一般綜合調(diào)度問題的要求比較可知,多批處理擴(kuò)展了約束②,即一般綜合調(diào)度問題是多批處理問題的特例.為了說明多批處理條件下工序的約束關(guān)系,有關(guān)符號說明和分析如下:(1)不同的設(shè)備可以在同一時刻加工完畢,設(shè)tk為設(shè)備加工完畢并產(chǎn)生空閑的時刻,其中k≥0(t0為開始時刻).(2)tm,k為設(shè)備m加工完畢并產(chǎn)生空閑的時刻.(3)fm,k為tm,k時刻在設(shè)備m上剛加工完畢的某一工序.(4)Fm,k為tm,k時刻在設(shè)備m上剛加工完畢的工序集合,Fm,k={fm,k}.(5)Fk為tk時刻剛加工完畢工序構(gòu)成的集合Fk=F1,k∪F2,k∪…∪Fm,k.(6)Xk為tk時刻已加工完畢工序構(gòu)成的集合;Xk=Xk-1∪Fk.設(shè)pre(n)代表工序n的緊前工序,有關(guān)工序表示如下:(1)Ok為tk時刻可調(diào)度工序集合:(?n)({pre(n)}?Xk)→(n∈Ok).(2)Cm,k為tk時刻空閑設(shè)備m選擇加工的工序集合,Cm,k?Ok,Cm,k中各元素的開始時間均為tk,Cm,k中元素個數(shù)大于1,則Cm,k為批處理工序組.(3)Ck為tk時刻設(shè)備資源選擇的工序集合,Ck=C1,k∪C2,k∪…∪Cm,k,Ck?Ok.多批處理的約束條件⑤表示如下:(?n)(n∈Cm,k)→(End(n)=tm,k+1).3系統(tǒng)模型的設(shè)計3.1加工開始信號和加工開始信號根據(jù)綜合調(diào)度的實際情況,將多批處理系統(tǒng)劃分為調(diào)度子系統(tǒng)(SchedulingManagementSubsystem,SS)和設(shè)備子系統(tǒng)(DeviceManagementSubsystem,DS).其中SS有兩個主要內(nèi)容:(1)采用組合策略確定批處理工序組;(2)利用最大并行性選擇策略為空閑設(shè)備分配可調(diào)度工序或工序組,發(fā)送加工開始信號.DS負(fù)責(zé)接收SS傳遞來的可調(diào)度工序信息,鎖定相應(yīng)加工設(shè)備資源并在加工完畢時釋放設(shè)備資源,發(fā)送加工完畢信號.定義2.加工完畢信號(Sig_F).DS釋放設(shè)備資源時向SS發(fā)送的信號,該信號包含了加工結(jié)束的工序號和設(shè)備號.定義3.加工開始信號(Sig_B).SS選擇為空閑設(shè)備分配可調(diào)度工序后,利用該信號通知DS鎖定設(shè)備資源及具體的加工工序.SS與DS的交互過程如圖1所示,其中信號Sig_F和信號Sig_B發(fā)送時伴隨著設(shè)備資源的轉(zhuǎn)移.系統(tǒng)加工的初始時刻t0,先由SS采用組合策略確定批處理工序組,此時所有設(shè)備資源均為SS所有,SS再為所有空閑設(shè)備進(jìn)行可調(diào)度工序的選擇,將被選擇的工序和設(shè)備信息通過Sig_B傳遞到DS,此時DS鎖定加工工序和設(shè)備資源,在設(shè)備加工完畢時釋放設(shè)備資源并發(fā)送信號Sig_F,SS在收到新的設(shè)備資源信息后再進(jìn)行新一輪的設(shè)備選擇.SS與DS通過信號Sig_F和信號Sig_B的循環(huán)傳遞完成整體加工任務(wù).若某一不可調(diào)度工序的所有緊前工序均被選擇,則將該工序加入準(zhǔn)可調(diào)度集合.3.2準(zhǔn)可調(diào)度狀態(tài)加工任務(wù)從開始到結(jié)束的過程中,各個加工工序狀態(tài)會經(jīng)歷一系列狀態(tài)變化,其定義如下.定義4.加工狀態(tài).可調(diào)度工序在其加工設(shè)備上加工時的狀態(tài).定義5.完畢狀態(tài).工序加工完畢時所處的狀態(tài).定義6.可調(diào)度狀態(tài).可調(diào)度工序所處的狀態(tài).定義7.準(zhǔn)可調(diào)度狀態(tài).不可調(diào)度工序中緊前工序均處于加工狀態(tài)的工序.定義8.非調(diào)度狀態(tài).不可調(diào)度工序中非準(zhǔn)可調(diào)度工序所處的狀態(tài).其中處于準(zhǔn)可調(diào)度狀態(tài)和非調(diào)度狀態(tài)的工序均為不可調(diào)度工序.圖2為某一時刻加工任務(wù)工藝樹,葉子節(jié)點(diǎn)F6和F7在設(shè)備上加工處于加工狀態(tài),無緊前工序的葉子節(jié)點(diǎn)F8和F9處于可調(diào)度狀態(tài);其中非葉子結(jié)點(diǎn)均為不可調(diào)度工序,例如F3的所有緊前工序(F6)處于加工狀態(tài),因此F3處于準(zhǔn)可調(diào)度狀態(tài);F4緊前工序中,只有F7處于加工狀態(tài),因此F4處于非調(diào)度狀態(tài),tk時刻各工序狀態(tài)如表1所示.SS發(fā)送信號Sig_B時,某一工序(組)的狀態(tài)由可調(diào)度狀態(tài)變?yōu)榧庸顟B(tài),其后續(xù)工序可能會變成為準(zhǔn)可調(diào)度狀態(tài).DS發(fā)送信號Sig_F時,某一工序(組)由加工狀態(tài)變?yōu)橥戤厾顟B(tài),其后續(xù)工序可能會變成為可調(diào)度狀態(tài).因此各工序狀態(tài)變化以信號Sig_F和信號Sig_B為驅(qū)動.圖3為某一工序從開始到結(jié)束所經(jīng)歷各種狀態(tài),其狀態(tài)變化隨著信號Sig_F、Sig_B的產(chǎn)生有序地變化.定義9.信號驅(qū)動時刻.某一工序加工完畢的時刻,此時DS發(fā)送驅(qū)動信號Sig_F,進(jìn)行新一輪調(diào)度.下面介紹當(dāng)信號驅(qū)動時刻到來時,SS對可多批處理工序的調(diào)度策略.4ss的組合策略由于SS內(nèi)部分別為可調(diào)度工序和準(zhǔn)可調(diào)度工序建立集合,因此SS內(nèi)部結(jié)構(gòu)如圖4所示.當(dāng)收到信號Sig_F時,SS先對所有工序的狀態(tài)進(jìn)行一次更新,然后SS利用組合策略將可批處理工序組合成工序組,再按文獻(xiàn)中最大并行性選擇策略選擇可調(diào)度工序(組),將被選擇工序號及設(shè)備資源信息通過Sig_B發(fā)送到DS.4.1tqa和tqb工序是否進(jìn)行批處理組合的組合策略設(shè)計和分析如下.定義10.組合工序.將可同時在一臺設(shè)備上加工的多個工序虛擬成為一道工序,這道虛擬工序稱為組合工序,組合工序在調(diào)度時與正常工序一樣.根據(jù)多批處理問題的約束條件⑤,可以批量處理的工序是相同的工序,其加工時間相同,因此,組合后的工序加工時間不變.由于SS工序集中批處理工序分為可調(diào)序批處理工序(A)和準(zhǔn)可調(diào)度批處理工序(B).組合類型分為兩種:A與A組合和A與B組合.對于AA類型,當(dāng)可批處理調(diào)度的工序數(shù)小于設(shè)備批處理量時,此時所有可批處理工序一同批處理;當(dāng)可批處理調(diào)度的工序數(shù)大于設(shè)備批處理量時,考慮工序并行加工,按設(shè)備批處理量,選擇路徑長的工序組合為工序PAA.對于AB類型,由于加工工藝約束,組合后工序A推遲開始加工時間與B同步并形成組合工序PAB.PAB縮短了單一設(shè)備的總加工時間,但推遲了工序A的后續(xù)工序,為此,有必要研究是否進(jìn)行AB類型工序組合的判斷策略.為方便闡述問題,現(xiàn)利用代數(shù)式說明條件之間的關(guān)系.設(shè)信號驅(qū)動時刻T時,可批處理工序A與B的加工時間為Tp,準(zhǔn)可調(diào)度工序B轉(zhuǎn)變?yōu)榭烧{(diào)度狀態(tài)的時刻為TB.工序A和工序B的父路徑工序序列為QA和QB,路徑長度為TQA和TQB.理想條件下QA在A加工結(jié)束時開始加工,即T+Tp時刻;QB在B加工結(jié)束時開始加工,即TB+Tp時刻.當(dāng)T+Tp≤TB時,AB的關(guān)系如圖5(a)所示,準(zhǔn)可調(diào)度工序B可以開始加工時,工序A已加工完畢,若對AB進(jìn)行組合,其結(jié)果如圖5(b)所示,此時,不僅批處理設(shè)備在時間段(T,TB)處于空閑,而且還要推遲QA的開始時間,影響調(diào)度結(jié)果.因此,當(dāng)T+Tp≤TB時不對AB工序進(jìn)行組合.當(dāng)T+Tp>TB時,AB及其后續(xù)工序的關(guān)系如圖6(a)所示,若不對AB進(jìn)行組合,則AB在批處理設(shè)備上串行加工,此時需要推遲B及其后續(xù)工序的開始時間,調(diào)度結(jié)果如圖6(b)所示;若對AB進(jìn)行組合,由于B的開始時間晚于當(dāng)前時刻T,此時需要推遲A及其后續(xù)工序的開始時間,調(diào)度結(jié)果如圖6(c)所示,AB組合后的工序為PAB.由于AB的后續(xù)部分QA和QB可以并行加工,其路徑長度TQA和TQB是決定AB組合后整體效率問題的關(guān)鍵因素,因此下面將根據(jù)TQA和TQB的情況,對AB是否組合進(jìn)行分析.對于圖6(b)所示的情況(AB不組合),設(shè)總加工時間為S1,對于圖6(c)所示的情況(AB組合),設(shè)總加工時間為S2.理想條件下QB與QA可在不同的設(shè)備上并行加工.當(dāng)AB不組合,B、QB與QA并行加工,其并行時間為max(Tp+TQB,TQA),S1=T+Tp+max(Tp+TQB,TQA);當(dāng)AB組合,QB與QA并行加工,其并行時間為max(TQB,TQA),S2=TB+max(TQB,TQA).為了實現(xiàn)目標(biāo)函數(shù),需要選擇S1和S2中較小的方案,即當(dāng)S1>S2時,對AB進(jìn)行組合.下面對選擇組合的條件進(jìn)行分析.根據(jù)上式中的各種取大可能進(jìn)行以下4種情況分析:???????????Tp+TQB>TQA,TQB>TQATp+TQB>TQA,TQB<TQATp+TQB<TQA,TQB>TQATp+TQB<TQA,TQB<TQA①②③④{Τp+ΤQB>ΤQA,ΤQB>ΤQA①Τp+ΤQB>ΤQA,ΤQB<ΤQA②Τp+ΤQB<ΤQA,ΤQB>ΤQA③Τp+ΤQB<ΤQA,ΤQB<ΤQA④由此得出4種情況的首要條件:①TQB>TQA,該條件即工序B的父節(jié)點(diǎn)路徑長度大于工序A的父節(jié)點(diǎn)路徑長度.②TQA>TQB>TQA-Tp,該條件即工序B的父節(jié)點(diǎn)路徑長度小于工序A的父節(jié)點(diǎn)路徑長度,且大于工序A的父節(jié)點(diǎn)路徑長度與B的加工時間之差.③TQB>TQA>TQB+Tp矛盾.④TQA-Tp>TQB,該條件即工序B的父節(jié)點(diǎn)路徑長度小于工序A的父節(jié)點(diǎn)路徑長度與B的加工時間之差.在合理的3種條件下,S1-S2>0還需滿足如下條件:①②④?T+2Tp?TB?TQB>0T+2Tp?TB?TQA>0T+Tp?TB>0?2Tp?(TB?T)>TQB2Tp?(TB?T)>TQAT+Tp?TB>0①Τ+2Τp-ΤB-ΤQB>02Τp-(ΤB-Τ)>ΤQB②?Τ+2Τp-ΤB-ΤQA>0?2Τp-(ΤB-Τ)>ΤQA④Τ+Τp-ΤB>0Τ+Τp-ΤB>0組合時間變化如圖6(c)所示,Tp為AB的加工時間,TB-T為A推遲的時間.情況①時,發(fā)生合并的條件可以表述為:AB的加工時間的2倍與A推遲時間之差大于B的父路徑長;情況②時,發(fā)生合并的條件可以表述為:AB的加工時間的2倍與A推遲時間之差大于A的父路徑長;情況④時,AB組合的條件T+Tp-TB>0與AB批處理前提條件一致,因此情況④在滿足首要條件即TQA-Tp>TQB時可直接對AB進(jìn)行組合.組合后,PAA工序為可調(diào)度工序且開始時間不變;PAB工序為準(zhǔn)可調(diào)度工序且開始時間為TB.理想狀態(tài)下組合后的父路徑工序充分并行后形成的父路徑長度為QA和QB的最大值.根據(jù)以上分析,多批綜合調(diào)度的組合策略如下:①對于AA類型的批處理工序,根據(jù)設(shè)備加工容量(批處理量)和文獻(xiàn)選擇工序路徑長的進(jìn)行組合.②對于AB類型的批處理,在滿足設(shè)備加工容量的前提下,批處理工序需按序滿足以下條件:{2Tp?(TB?T)>TQBT+Tp?TB>0{2Τp-(ΤB-Τ)>ΤQBΤ+Τp-ΤB>0或{2Tp?(TB?T)>TQAT+Tp?TB>0{2Τp-(ΤB-Τ)>ΤQAΤ+Τp-ΤB>0或TQA-Tp>TQB.該組合策略可循環(huán)使用,形成多批量綜合調(diào)度,圖7為組合策略的簡要流程圖.4.2父控制路徑最大可并行性選擇策略就是在信號驅(qū)動時刻,當(dāng)空閑設(shè)備尋找可調(diào)度工序時,如果可調(diào)度工序不唯一,選擇父結(jié)點(diǎn)路徑長的工序;如果存在父結(jié)點(diǎn)最長路徑相同的工序,選擇用時短的工序.由于該策略可以使得待加工工序有更多的并行處理時間,所以本文在可加工工序數(shù)多于設(shè)備批加工容量的情況下,采用最大可并行性選擇策略,在多個可加工工序中選取部分工序批加工.5段算法的設(shè)計與復(fù)雜分析5.1ss的發(fā)送調(diào)度系統(tǒng)分為調(diào)度算法的實現(xiàn)系統(tǒng)SS和設(shè)備的驅(qū)動系統(tǒng)DS.某一加工狀態(tài)的工序加工完畢時,DS向SS發(fā)送信號Sig_F,該信號激活SS進(jìn)行一次調(diào)度;SS調(diào)度完畢后向DS發(fā)送信號Sig_B,該信號激活DS對分配的工序執(zhí)行加工.(1)pid[i]加工數(shù)據(jù)的生成一次調(diào)度時可對不同空閑設(shè)備資源分配不同的可調(diào)度工序,不同的加工工序可能在同一時刻加工完畢,因此信號Sig_F與信號Sig_F需要記錄多個加工工序號及其設(shè)備號,因此為信號設(shè)置如下數(shù)據(jù)結(jié)構(gòu).以上兩個結(jié)構(gòu)中DID數(shù)組與PID數(shù)組的每一項相對應(yīng),即工序PID[i]的加工設(shè)備號為DID[i],其加工時間為workTime[i].(2)sigb->pid①DS等待SS傳來的信號Sig_B.②對Sig_B->DID中的設(shè)備加鎖,鎖定時間為Sig_B->workTime.③等待某一工序加工完畢,將加工完畢工序的工序號、加工設(shè)備號和加工時間記錄在Sig_F中,并釋放加工完畢的設(shè)備資源.④向SS發(fā)送Sig_F.若發(fā)送的Sig_F->PID與根節(jié)點(diǎn)工序的工序號相同則結(jié)束.(3)ss集與準(zhǔn)可調(diào)度集ds為簡化后續(xù)調(diào)度工序滿足最大并行性選擇策略和AA類型批處理工序組工序的選擇,初始時將工序集中所有工序按父結(jié)點(diǎn)路徑長度由長到短排序.①初始時刻,記錄當(dāng)前時刻t0.②更新可調(diào)度工序集與準(zhǔn)可調(diào)度集.③利用組合策略對滿足批處理條件的工序進(jìn)行組合.④根據(jù)SS現(xiàn)有的設(shè)備資源,利用最大并行性選擇策略,對可調(diào)度工序進(jìn)行選擇,將被選擇工序的工序號、加工設(shè)備號和加工時間,記錄在Sig_B中,并將該工序從可調(diào)度集中刪除.⑤向DS發(fā)送Sig_B.⑥等待DS傳來的信號Sig_F.⑦收到信號Sig_F時,若Sig_F->PID與根節(jié)點(diǎn)工序的工序號相同,轉(zhuǎn)⑧,否則轉(zhuǎn)②.⑧記錄當(dāng)前時刻tn=Sig_F->currentTime,加工任務(wù)結(jié)束,產(chǎn)品加工總時間E=tn-t0.圖8為DS和SS子系統(tǒng)的簡要流程圖.5.2多批處理調(diào)度算法復(fù)雜度分析本算法復(fù)雜之處在于,信號驅(qū)動時刻,SS利用組合策略對多批處理工序的組合判斷和設(shè)備利用最大可并行策略對可調(diào)度工序的選擇.由于本算法考慮最大并行性選擇策略,對所有工序按其父路徑長度排序,可調(diào)度工序按加工設(shè)備進(jìn)行分組,從而保證了該算法有較低的復(fù)雜度,具體分析如下:設(shè)多批處理調(diào)度系統(tǒng)中工序集中工序總數(shù)為n,設(shè)備集中設(shè)備總數(shù)為m,下面分析其兩個子系統(tǒng)的算法復(fù)雜度.(1)ds算法的復(fù)雜度設(shè)備加工一個工序時,先接收信號Sig_B并在加工結(jié)束時發(fā)送信號Sig_F,n個工序需進(jìn)行2n次信號操作,因此DS算法的復(fù)雜度為O(n).(2)多批處理調(diào)度系統(tǒng)算法的復(fù)雜度①調(diào)度系統(tǒng)初始時,對工序集中所有工序按其父結(jié)點(diǎn)路徑長度由長到短排序,按Quick-Sort快速排序法排序,復(fù)雜度為O(nlogn).②利用組合策略先對2個可批處理工序進(jìn)行判斷,根據(jù)組合判斷流程圖7知,對2個工序進(jìn)行批處理的判斷次數(shù)最多為5.由于批處理工序組可由2個工序最多擴(kuò)展為n個,所以形成一個批處理工序組最多判斷5n次,即形成一個批處理工序組的復(fù)雜度為O(n).系統(tǒng)中最多形成n個批處理工序組,所以組合策略的復(fù)雜度為O(n2).③利用最大并行性選擇策略對可調(diào)度工序進(jìn)行選擇,由于工序已按最大并行性選擇策略的比較算法排序,每個工序只需1步選擇操作,因此,該過程最多進(jìn)行n次操作,復(fù)雜度為O(n).④SS以接收信號Sig_F作為一次調(diào)度的開始和以發(fā)送信號Sig_B作為一次調(diào)度的結(jié)束,n個工序需進(jìn)行2n次信號操作.因此,SS信號接收和發(fā)送的復(fù)雜度為O(n).綜上所述,本文提出的多批處理調(diào)度系統(tǒng)算法的復(fù)雜度為O(n2).6工序調(diào)度結(jié)果分析圖9為滿足樹狀加工模型的加工任務(wù),如其中P6/3/15表示:加工工序號PID=6、加工設(shè)備號DID=3和加工時間Tp=15,設(shè)備號為1的設(shè)備是多批處理設(shè)備,批處理工序P2、P5、P7、P10和P11的加工時間Tp=30.其它設(shè)備為普通設(shè)備,即加工批量為1的設(shè)備.當(dāng)M1的批處理量為1,即為一般綜合調(diào)度問題,此時利用文獻(xiàn)算法調(diào)度,工序調(diào)度次序為P4、P13、P8、P12、P9、P2、P10、P11、P5、P7、P6、P1、P3、P0,結(jié)果如圖10所示,加工總用時為205;利用文獻(xiàn)算法調(diào)度,工序調(diào)度次序為{P4、P11、P12}、P8、P9、P7、P2、{P1、P10}、P5、P6、P3、P0,結(jié)果如圖11所示,加工總用時為180.文獻(xiàn)之所以比文獻(xiàn)調(diào)度效果好,是因為文獻(xiàn)算法在調(diào)度工序時先確定調(diào)度次序,次序靠后的工序只能在剩余的空閑時間段中尋找合適的位置,由此會產(chǎn)生不可被利用的