柔性作業(yè)車(chē)間的周期性再調(diào)度優(yōu)化研究

柔性作業(yè)車(chē)間的周期性再調(diào)度優(yōu)化研究

0fjp的求解柔性工作流（fjp）是jp的一個(gè)經(jīng)典工作流（jp）擴(kuò)展問(wèn)題。它不僅考慮了機(jī)械零件的加工順序，還考慮了每個(gè)加工序列是哪個(gè)機(jī)器加工的過(guò)程，以滿(mǎn)足實(shí)際生產(chǎn)的需要。然而,FJSP減少了機(jī)器約束,擴(kuò)大了可行解的搜索范圍,增加了問(wèn)題的求解難度,是比JSP更為復(fù)雜的NP-hard問(wèn)題。鑒于此,人們將研究目標(biāo)轉(zhuǎn)向各種啟發(fā)式方法。在眾多的研究與探索中,通過(guò)模擬自然界中生物和人類(lèi)行為過(guò)程中所表現(xiàn)出的某些特點(diǎn)而發(fā)展的群體智能算法,如遺傳算法、粒子群優(yōu)化算法、蟻群優(yōu)化算法、差分進(jìn)化(DifferentialEvolution,DE)算法等,在包括調(diào)度問(wèn)題在內(nèi)的組合優(yōu)化問(wèn)題求解領(lǐng)域中,受到越來(lái)越普遍的關(guān)注。近年來(lái),大量學(xué)者對(duì)FJSP進(jìn)行了研究,Bagheri等使用人工免疫算法求解FJSP,Wang等分別使用人工蜂群算法和分布估計(jì)算法求解FJSP,在求解過(guò)程中平衡了局部搜索和全局搜索過(guò)程。其中DE算法由Storn和Price于1997年提出,是最新的基于種群的進(jìn)化算法之一,其最初的設(shè)想是用于解決連續(xù)性問(wèn)題。由于DE算法具有思路簡(jiǎn)單、容易實(shí)現(xiàn)、收斂速度快和穩(wěn)定性好等優(yōu)點(diǎn),近年來(lái)被廣泛應(yīng)用于解決復(fù)雜優(yōu)化問(wèn)題,如人工神經(jīng)元網(wǎng)絡(luò)、化工、電氣和經(jīng)濟(jì)學(xué)等,但對(duì)于調(diào)度問(wèn)題這種典型的離散型問(wèn)題研究得還不多,尤其對(duì)于FJSP問(wèn)題,少有學(xué)者用DE算法進(jìn)行研究。實(shí)際環(huán)境下的FJSP不但具有計(jì)算復(fù)雜性,而且有多目標(biāo)和動(dòng)態(tài)性特征,具體表現(xiàn)為:(1)生產(chǎn)過(guò)程是動(dòng)態(tài)的,各個(gè)工件依次進(jìn)入待加工狀態(tài),進(jìn)入系統(tǒng)接受加工,同時(shí)完成加工的工件又不斷離開(kāi)過(guò)程;(2)調(diào)度優(yōu)化決策不僅包括時(shí)間、成本等靜態(tài)指標(biāo),還包括魯棒性和穩(wěn)定性等動(dòng)態(tài)指標(biāo),各個(gè)指標(biāo)之間通常互相沖突和耦合,需要對(duì)多個(gè)目標(biāo)同時(shí)進(jìn)行優(yōu)化與決策。多目標(biāo)和動(dòng)態(tài)性是當(dāng)今制造系統(tǒng)必須解決的一個(gè)關(guān)鍵問(wèn)題,經(jīng)典調(diào)度的研究忽略了生產(chǎn)需求的動(dòng)態(tài)性和生產(chǎn)過(guò)程的健壯性與穩(wěn)定性,造成了理論研究距離實(shí)際應(yīng)用有相當(dāng)?shù)牟罹唷elson等在1977年最早提出了動(dòng)態(tài)調(diào)度問(wèn)題,它將動(dòng)態(tài)調(diào)度過(guò)程分成多個(gè)連續(xù)的靜態(tài)區(qū)間,然后對(duì)上述調(diào)度區(qū)間進(jìn)行優(yōu)化以達(dá)到每個(gè)區(qū)間內(nèi)最優(yōu),從而適應(yīng)動(dòng)態(tài)環(huán)境;張超勇研究了原材料延期到達(dá)、加工時(shí)間延誤、緊急工件加入等情況下的動(dòng)態(tài)調(diào)度;潘全科等研究了待加工工件的選取原則和再調(diào)度周期的確定方法;Branke等研究了工件隨機(jī)到達(dá)的動(dòng)態(tài)調(diào)度,以合并早期空閑時(shí)間的方法來(lái)提高調(diào)度效率;Chryssolouris等用遺傳算法對(duì)動(dòng)態(tài)作業(yè)車(chē)間調(diào)度問(wèn)題(DynamicJob-shopSchedulingProblem,DJSP)進(jìn)行了求解,并考慮了兩個(gè)目標(biāo),進(jìn)而說(shuō)明多目標(biāo)調(diào)度在動(dòng)態(tài)調(diào)度中的可行性;Rangsaritrasamee等提出了一種同時(shí)考慮效率與穩(wěn)定性的多目標(biāo)優(yōu)化策略,其采用加權(quán)的方式將兩目標(biāo)合成為單目標(biāo)問(wèn)題進(jìn)行研究;劉愛(ài)軍等提出一種自適應(yīng)遺傳算法的多目標(biāo)柔性動(dòng)態(tài)調(diào)度算法,基于事件和周期驅(qū)動(dòng)的混合再調(diào)度策略來(lái)求解實(shí)際的調(diào)度問(wèn)題。群體智能算法可以在一次運(yùn)行中得到多個(gè)Pareto解,非常適合求解多目標(biāo)優(yōu)化問(wèn)題。國(guó)內(nèi)外學(xué)者目前在這方面做了大量研究,提出了多種多目標(biāo)進(jìn)化算法(Multi-ObjectiveEvolutionaryAlgorithm,MOGA),如非支配排序遺傳算法(Non-dominatedSortingGeneticAlgorithm,NSGA-Ⅱ)等,其中多目標(biāo)差分進(jìn)化有較好的收斂性和分布性,越來(lái)越受到國(guó)內(nèi)外學(xué)者的關(guān)注。本文運(yùn)用概率方法模擬各個(gè)工件的到達(dá)時(shí)間,采用周期性再調(diào)度的調(diào)度策略將各工件劃分到對(duì)應(yīng)的調(diào)度區(qū)間進(jìn)行求解。在每個(gè)調(diào)度區(qū)間上,以穩(wěn)定性和效率為優(yōu)化目標(biāo),設(shè)計(jì)基于Pareto解的多目標(biāo)差分進(jìn)化算法進(jìn)行求解,并研究不同的再調(diào)度周期對(duì)調(diào)度性能的影響,從而有效地指導(dǎo)生產(chǎn)。1到達(dá)時(shí)間和動(dòng)態(tài)調(diào)度為了研究不同再調(diào)度周期對(duì)調(diào)度性能的影響,本文采用概率方法模擬了各工件的到達(dá)時(shí)間,并針對(duì)這些先后到達(dá)的工件進(jìn)行動(dòng)態(tài)調(diào)度。動(dòng)態(tài)調(diào)度采用周期性再調(diào)度策略,將各工件依其到達(dá)的時(shí)間劃入相應(yīng)的調(diào)度區(qū)間中,進(jìn)而在各調(diào)度區(qū)間進(jìn)行多目標(biāo)優(yōu)化。1.1工件到達(dá)率的計(jì)算許多研究顯示:在一定時(shí)間,內(nèi)車(chē)間中工件隨機(jī)到達(dá)的個(gè)數(shù)服從泊松分布,設(shè)泊松分布的參數(shù)為λ,表示工件的平均到達(dá)率,則任意兩個(gè)先后到達(dá)的工件之間的時(shí)間間隔服從參數(shù)為λ的指數(shù)分布。Karisiti等在研究作業(yè)車(chē)間調(diào)度問(wèn)題時(shí)提出一個(gè)關(guān)于到達(dá)率的計(jì)算公式,式中:λ表示工件的平均到達(dá)率;U表示車(chē)間利用率(shoputilization);m表示車(chē)間的機(jī)器數(shù)量;μp表示工序的平均加工時(shí)間;μg表示每個(gè)工件的平均工序數(shù)。工件隨機(jī)到達(dá)的示意圖如圖1所示,任意兩個(gè)先后到達(dá)的工件之間的時(shí)間差服從參數(shù)為λ的幾何分布。通過(guò)模擬一組服從幾何分布的隨機(jī)數(shù)列,將數(shù)列中的各值依次作為先后到達(dá)的兩個(gè)工件的到達(dá)時(shí)間差,然后累計(jì)得到各個(gè)工件的實(shí)際到達(dá)時(shí)間。設(shè)工件Ji的到達(dá)時(shí)間為ai,數(shù)列b1,b2,…,bn為模擬得到的服從幾何分布的數(shù)列,t0為模擬的第一個(gè)工件J1的到達(dá)時(shí)間,即a1=t0,則工件Jn的到達(dá)時(shí)間an可由式(2)得到:為了方便研究,本文設(shè)第一個(gè)工件的到達(dá)時(shí)間t0=0。1.2調(diào)度區(qū)間上的靜態(tài)調(diào)度問(wèn)題對(duì)于動(dòng)態(tài)調(diào)度問(wèn)題,通常采用周期和事件驅(qū)動(dòng)再調(diào)度的調(diào)度策略。本文主要探討不同再調(diào)度周期對(duì)調(diào)度性能的影響,進(jìn)而采用周期性再調(diào)度的調(diào)度策略。在不同的再調(diào)度周期下對(duì)先后到達(dá)的相同數(shù)量的工件進(jìn)行調(diào)度,并對(duì)最后的性能指標(biāo)進(jìn)行比較和分析。在周期性再調(diào)度模型中,將每一次進(jìn)行再調(diào)度的時(shí)間稱(chēng)為再調(diào)度時(shí)刻,每進(jìn)行一次再調(diào)度即產(chǎn)生一個(gè)調(diào)度區(qū)間,該調(diào)度區(qū)間的長(zhǎng)度為上一次再調(diào)度時(shí)刻與當(dāng)前再調(diào)度時(shí)刻之間的長(zhǎng)度(在再調(diào)度周期ΔT不變時(shí)即為一個(gè)再調(diào)度周期的時(shí)間長(zhǎng)度)。每個(gè)調(diào)度區(qū)間上需要進(jìn)行調(diào)度的工件包括:(1)在上一個(gè)調(diào)度區(qū)間中進(jìn)行了調(diào)度但在當(dāng)前再調(diào)度時(shí)刻還未加工完成的工件;(2)在上一個(gè)再調(diào)度時(shí)刻與當(dāng)前再調(diào)度時(shí)刻期間到達(dá)的新工件。通過(guò)這種策略對(duì)先后到達(dá)的工件進(jìn)行動(dòng)態(tài)調(diào)度時(shí),可以將各個(gè)工件依其到達(dá)時(shí)間劃分到對(duì)應(yīng)的調(diào)度區(qū)間中,進(jìn)而將動(dòng)態(tài)調(diào)度轉(zhuǎn)化為多個(gè)連續(xù)的調(diào)度區(qū)間上的靜態(tài)調(diào)度問(wèn)題進(jìn)行求解。工件所屬的調(diào)度區(qū)間為式中:hi表示工件Ji初次進(jìn)行調(diào)度所屬的調(diào)度區(qū)間;ai表示工件Ji的到達(dá)時(shí)間;ΔT表示再調(diào)度的調(diào)度周期。因?yàn)楣ぜ﨡1在0時(shí)刻到達(dá),而它應(yīng)在第一個(gè)調(diào)度區(qū)間進(jìn)行調(diào)度,所以修改得h1=1。周期性再調(diào)度策略以及調(diào)度區(qū)間的產(chǎn)生過(guò)程如圖2所示。在圖2的示例中,ΔT為再調(diào)度的周期,t1,t2和t3為三個(gè)連續(xù)的再調(diào)度時(shí)刻,其中t2=t1+ΔT,t3=t2+ΔT。調(diào)度區(qū)間A和調(diào)度區(qū)間B為兩個(gè)相鄰的調(diào)度區(qū)間。調(diào)度區(qū)間B是在t2再調(diào)度時(shí)刻產(chǎn)生的,該調(diào)度區(qū)間中需要進(jìn)行調(diào)度的工件包括調(diào)度區(qū)間A在當(dāng)前再調(diào)度時(shí)刻t2還沒(méi)有加工完成的工件(去除當(dāng)前正在加工的工序以后還有未加工工序)和在上一個(gè)再調(diào)度時(shí)刻t1與當(dāng)前再調(diào)度時(shí)刻t2之間新到達(dá)的工件。調(diào)度區(qū)間B中各機(jī)器的加工狀態(tài)需要根據(jù)調(diào)度區(qū)間A上的實(shí)際調(diào)度方案確定。設(shè)調(diào)度區(qū)間A上的實(shí)際調(diào)度方案甘特圖如圖3所示,則調(diào)度區(qū)間B上的各機(jī)器狀態(tài)可按如下方法確定:在圖3中,依據(jù)調(diào)度區(qū)間A上的最終調(diào)度方案,在再調(diào)度時(shí)刻t2到達(dá)時(shí),工序O33,O52和O62正在進(jìn)行加工,工序O53和O63還未開(kāi)始加工,即工件J5和J6在t2時(shí)刻還未加工完成,因此要并入下一個(gè)調(diào)度區(qū)間B進(jìn)行再調(diào)度。機(jī)器M1,M2和M4正在在加工工序O52,O62和O33,則在調(diào)度區(qū)間B中,對(duì)應(yīng)的機(jī)器只能加工完成上述工序后才能開(kāi)始加工調(diào)度區(qū)間B中的工件,在t2時(shí)刻處于“忙碌”狀態(tài),而機(jī)器M3在t2時(shí)刻空閑。調(diào)度區(qū)間B是再調(diào)度時(shí)刻t2產(chǎn)生的,該調(diào)度區(qū)間上各機(jī)器的最早可用時(shí)間為t2(如機(jī)器M3,在t2時(shí)刻空閑)或?yàn)楫?dāng)前正在加工工序的完工時(shí)間(如機(jī)器M1,M2和M4)。本文研究了不同再調(diào)度周期對(duì)相同數(shù)量工件進(jìn)行調(diào)度時(shí)的性能指標(biāo)差異。在本文的研究實(shí)例中,第一個(gè)工件J1的到達(dá)時(shí)刻a1=0,即在0時(shí)刻只有一個(gè)工件,為了方便研究,并保證各機(jī)器不論調(diào)度區(qū)間ΔT為多少,第一個(gè)調(diào)度區(qū)間均在當(dāng)前調(diào)度時(shí)刻可用,令第一個(gè)再調(diào)度時(shí)刻為ΔT而不是0時(shí)刻。第一個(gè)調(diào)度區(qū)間上的工件包括從0時(shí)刻~ΔT時(shí)刻到達(dá)的新工件,該調(diào)度區(qū)間中各機(jī)器均在ΔT時(shí)刻可用,各機(jī)器的最早可加工時(shí)間均為ΔT。以后每隔ΔT的時(shí)刻進(jìn)行再調(diào)度,產(chǎn)生新的調(diào)度區(qū)間,直到所有的工件都被調(diào)度加工完成為止。按照上述再調(diào)度策略和調(diào)度區(qū)間的劃分方法,可以將動(dòng)態(tài)調(diào)度問(wèn)題轉(zhuǎn)化為連續(xù)的調(diào)度區(qū)間上的靜態(tài)調(diào)度問(wèn)題。在每個(gè)調(diào)度區(qū)間上,根據(jù)上一個(gè)調(diào)度區(qū)間的實(shí)際調(diào)度方案得到各機(jī)器在當(dāng)前再調(diào)度時(shí)刻的可用狀態(tài),合并該調(diào)度區(qū)間上新到達(dá)的工件和需要再調(diào)度的工件得到所有待調(diào)度工件集合,進(jìn)而對(duì)該調(diào)度區(qū)間上的調(diào)度問(wèn)題采用優(yōu)化算法進(jìn)行求解。2在規(guī)劃范圍內(nèi)實(shí)現(xiàn)多目標(biāo)規(guī)劃2.1工件的加工類(lèi)型及條件調(diào)度區(qū)間上的調(diào)度問(wèn)題相當(dāng)于一個(gè)靜態(tài)的FJSP,為了區(qū)別調(diào)度區(qū)間上的第i個(gè)工件和按照模擬得到的到達(dá)時(shí)間第i個(gè)到達(dá)的工件,用Ji′表示前者,Ji表示后者。進(jìn)而調(diào)度區(qū)間上的調(diào)度問(wèn)題描述如下:該調(diào)度區(qū)間上有n′個(gè)工件需要進(jìn)行調(diào)度,對(duì)應(yīng)的待加工集合為J′={J1,J2,…,Jn′};共有m臺(tái)機(jī)器加工這些工件,對(duì)應(yīng)的機(jī)器集合為M={M1,M2,…,Mm};工件Ji′由ni′道工序構(gòu)成,各工序按照次序Oi′,1,Oi′,2,…,Oi′,ni′依次加工;工件Ji′的第j道工序Oi′,j可以被其可加工機(jī)器集合Mi′,j中的任意機(jī)器加工,其中工序Oi′,j的加工時(shí)間因其加工機(jī)器不同而各不相同。為了使研究更具可操作性,本文設(shè)定以下假設(shè)條件:(1)各機(jī)器在當(dāng)前再調(diào)度時(shí)刻的可用狀態(tài)由上一個(gè)調(diào)度區(qū)間的實(shí)際調(diào)度方案確定。(2)該調(diào)度區(qū)間所有新到達(dá)的調(diào)度工件均在當(dāng)前再調(diào)度時(shí)刻可被加工。(3)該調(diào)度區(qū)間上所有需要進(jìn)行再調(diào)度的工件,可被加工的最早時(shí)間為當(dāng)前再調(diào)度時(shí)刻與該工件已經(jīng)被加工的最后一道工序的完工時(shí)間中的較大值。(4)一臺(tái)機(jī)器一次只能加工一道工序。(5)同一工件的同一道工序在同一時(shí)刻只能被一臺(tái)機(jī)器加工。(6)每個(gè)工件的每道工序一旦開(kāi)始加工就不能中斷。(7)不同工件的工序之間沒(méi)有先后約束,同一工件的工序之間有先后約束。(8)忽略各機(jī)器設(shè)備的啟動(dòng)時(shí)間和各工序的運(yùn)輸時(shí)間。2.2柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題與傳統(tǒng)的靜態(tài)調(diào)度不同,動(dòng)態(tài)調(diào)度不僅需要考慮調(diào)度效率(Efficiency)指標(biāo),還要考慮一個(gè)重要的指標(biāo)———調(diào)度的穩(wěn)定性(Stability),即再調(diào)度偏離初始調(diào)度的程度。Rangsaritratsamee等最早在作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題中同時(shí)考慮了這兩個(gè)指標(biāo),Fattahi等將前者提出的兩個(gè)目標(biāo)進(jìn)行了擴(kuò)展,引入柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題中,但是兩者對(duì)待雙目標(biāo)問(wèn)題都是采用加權(quán)將雙目標(biāo)問(wèn)題轉(zhuǎn)化為一個(gè)合成的單目標(biāo)問(wèn)題進(jìn)行優(yōu)化。本文將上述兩個(gè)目標(biāo)引入柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題中,并在模擬求解過(guò)程中采用基于Pareto解的多目標(biāo)算法進(jìn)行優(yōu)化,最后再通過(guò)Pareto解決策出每個(gè)調(diào)度區(qū)間中的最優(yōu)調(diào)度方案,作為對(duì)應(yīng)調(diào)度區(qū)間上的實(shí)際調(diào)度方案。2.3編碼解碼方案DE算法是一種群體進(jìn)化搜索算法,具有思路簡(jiǎn)單、容易實(shí)現(xiàn)、收斂速度快和穩(wěn)定性好等優(yōu)點(diǎn)。它具有記憶個(gè)體最優(yōu)解和種群內(nèi)信息共享的特點(diǎn),即通過(guò)種群內(nèi)個(gè)體間的合作與競(jìng)爭(zhēng)實(shí)現(xiàn)對(duì)優(yōu)化問(wèn)題的求解。YuanYuan等在研究FJSP時(shí),提出一種基于實(shí)數(shù)的編碼與解碼方法,采用DE算法進(jìn)行了求解,并對(duì)求解性能與結(jié)果進(jìn)行了比較和分析。結(jié)果顯示,算法收斂性較好,求解結(jié)果也比較理想?？紤]到DE算法的優(yōu)點(diǎn),本文采用原作者提出的編碼解碼方案,并同樣采用DE算法進(jìn)行求解。原作者采用的DE算法僅對(duì)完工時(shí)間該單目標(biāo)進(jìn)行了優(yōu)化,單目標(biāo)DE算法中的變異算子不適用于本文的多目標(biāo)優(yōu)化問(wèn)題。同樣在用差分進(jìn)化算法進(jìn)行單目標(biāo)優(yōu)化時(shí),新種群通過(guò)選擇操作產(chǎn)生,同樣不適用于多目標(biāo)優(yōu)化問(wèn)題。本文針對(duì)上述兩個(gè)操作進(jìn)行了相應(yīng)改進(jìn),設(shè)計(jì)了多目標(biāo)變異算子和新種群的產(chǎn)生策略。在調(diào)度區(qū)間上采用基于Pareto解的多目標(biāo)優(yōu)化策略,最后得到一個(gè)非支配解集D。在本課題的研究中,必須從D中進(jìn)行Pareto解決策,選出一個(gè)調(diào)度方案作為該調(diào)度區(qū)間的實(shí)際調(diào)度方案,并以此判定哪些工件需要在下一個(gè)調(diào)度區(qū)間進(jìn)行再調(diào)度,以及各機(jī)器在下個(gè)調(diào)度區(qū)間再調(diào)度時(shí)刻的可用狀態(tài)。2.3.1異算子的變異操作對(duì)于多目標(biāo)DE算法,采用基于Pareto解的方法時(shí),在每一代種群中會(huì)得到一個(gè)非支配解集DG(non-dominatedsolutions),G=0,1,…,Gmax,其中G表示種群的代數(shù);同時(shí)也可以得到一個(gè)進(jìn)化到當(dāng)前代數(shù)為止的一個(gè)全局的非支配解集D。本文針對(duì)XueFeng等提出的多目標(biāo)變異算子進(jìn)行相應(yīng)改進(jìn),使得變異操作能夠充分利用到全局的非支配解集D,得到式(4)所示的變異操作:在XueFeng等提出的算子中,是否被支配以及珤Xbest都是基于當(dāng)前父代種群中的非支配解集DG考慮的。本文采用全局的非支配解集D進(jìn)行操作,如果則說(shuō)明不能被支配,否則從全局的非支配解集D中隨機(jī)選擇一個(gè)作為進(jìn)行對(duì)應(yīng)操作。在測(cè)試中發(fā)現(xiàn),當(dāng)前種群的非支配解集DG中的個(gè)體往往能被全局的非支配解集D支配。因此用D替換DG進(jìn)行變異操作可以在一定程度上提高解的質(zhì)量,也加大找到新的全局非支配集的機(jī)會(huì)。是不同于的兩個(gè)不同的向量,兩者之差表示差分向量,F為縮放因子,λ∈[0,1]表示的是貪婪因子。λ越靠近1,差分基向量中所占的比重就越大;λ越靠近在差分基向量中所占的所比重就越大。如果在當(dāng)前調(diào)度區(qū)間不存在需要再調(diào)度的工件,即待調(diào)度工件全是新到達(dá)的工件,如第一個(gè)調(diào)度區(qū)間,則該調(diào)度區(qū)間上將不存在穩(wěn)定性指標(biāo)的優(yōu)化,公式中的變異算子將退化(如式(5)),與YuanYuan等采用的單目標(biāo)變異算子保持一致。2.3.2試驗(yàn)向量集合和群體pt、rt構(gòu)造組合父代種群Pt(t表示種群的代數(shù))中的每個(gè)個(gè)體經(jīng)過(guò)變異、交叉操作后得規(guī)模大小同樣為Np(Np表示種群規(guī)模)的試驗(yàn)向量集合。集合中的每一個(gè)試驗(yàn)向量都表示一個(gè)可行的調(diào)度方案。此時(shí)將所有的試驗(yàn)向量并入大小為Np的試驗(yàn)種群Qt,然后將群體Pt和Qt合并到Rt中,針對(duì)Rt構(gòu)造邊界集,根據(jù)需要計(jì)算某個(gè)邊界集中所有個(gè)體的聚集距離,并建立偏序集;然后從偏序集依次選取個(gè)體進(jìn)入Pt+1,直至Pt+1的規(guī)模為Np,這樣得到的Pt+1即為下一代種群。2.3.3優(yōu)化調(diào)度方案在調(diào)度區(qū)間中,采用基于Pareto解的優(yōu)化算法進(jìn)行調(diào)度后最終會(huì)得到一個(gè)Pareto非支配解集,而進(jìn)行加工時(shí)只能有一個(gè)可行的調(diào)度方案,因此必須要從當(dāng)前的非支配集合中選擇出一個(gè)滿(mǎn)意的調(diào)度方案,并以此調(diào)度方案作為下個(gè)調(diào)度區(qū)間的基準(zhǔn)。在進(jìn)行Pareto解決策時(shí),本文采用文獻(xiàn)的推薦比例,效率(Efficiency)和穩(wěn)定性(Stability)權(quán)重分析設(shè)為5和1,依據(jù)式(6)計(jì)算結(jié)果選擇滿(mǎn)意解,實(shí)際操作中可以根據(jù)具體情況設(shè)定其他合適的決策方案。3示例配置3.1加工時(shí)間在柔性作業(yè)車(chē)間中,各個(gè)工序可以在多臺(tái)機(jī)器上加工,且加工時(shí)間相互獨(dú)立。由于可選機(jī)器集中的機(jī)器加工速率不同等因素,完成同一工序所需要的加工時(shí)間也不同。在本文的測(cè)試實(shí)例中,設(shè)工序Oi,j在各機(jī)器上的加工時(shí)間Pi,j,k服從均勻分布,Pi,j,k~U(0,9)。Pi,j,k=0說(shuō)明工序Pi,j不能在機(jī)器Mk上加工。3.2加工時(shí)間的p根據(jù)式(1)所示的工件的平均到達(dá)率,本文設(shè)定實(shí)例的相關(guān)參數(shù)為:加工機(jī)器數(shù)量m=10,車(chē)間利用率U=0.9,每個(gè)工件包含15道工序,即μg=15。平均加工時(shí)間μp是一個(gè)與加工車(chē)間的實(shí)際情況相關(guān)的經(jīng)驗(yàn)值,其值往往小于本文設(shè)定的對(duì)應(yīng)工序的可加工機(jī)器上的加工平均時(shí)間5(本文采用的是0~9的均勻分布,期望值為5,由于0表示不能加工,實(shí)際可加工時(shí)間為1~9)。在本文設(shè)定的調(diào)度環(huán)境中,測(cè)試得到當(dāng)m=10和μg=15時(shí),μp=1.76,其值小于5是因?yàn)樵趯?shí)際調(diào)度中,各個(gè)工件的每道工序通常是在其加工時(shí)間比較短的機(jī)器上加工。為了方便本課題的研究,使工件的到達(dá)更頻繁,本文測(cè)試實(shí)例在μp原值的基礎(chǔ)上乘以一個(gè)系數(shù),設(shè)定μp=1.76×0.7。3.3柔性作業(yè)車(chē)間調(diào)度環(huán)本文采用的效率目標(biāo)由調(diào)度區(qū)間上的完工時(shí)間和拖期共同確定,為了計(jì)算各工件的拖期值,必須要針對(duì)其交貨期進(jìn)行設(shè)置。很多學(xué)者就工件交貨期的設(shè)定進(jìn)行了研究,其中Baker等提出的TWK(totalworkcontent)規(guī)則得到了很多學(xué)者的引用。本文針對(duì)柔性作業(yè)車(chē)間調(diào)度環(huán)境的特殊性,將此模型進(jìn)行了相應(yīng)的修改,得到式中:DDi表示工件Ji的交貨期;ai表示工件Ji的到達(dá)時(shí)間;珚Pi,j表示工件Ji的第j道工序Oi,j在各個(gè)可加工機(jī)器上加工時(shí)間的均值;K表示松緊因子,在Blocher等給出的推薦值中,該值最小取2,本文取K=2。4結(jié)果與分析4.1de算法測(cè)試在各個(gè)調(diào)度區(qū)間上,本文采用YuanYuan等針對(duì)FJSP提出的實(shí)數(shù)編碼方案,采用DE算法進(jìn)行求解,并針對(duì)多目標(biāo)優(yōu)化問(wèn)題就變異算子以及新種群的產(chǎn)生策略進(jìn)行調(diào)整,另外增加了Pareto解決策的操作,但總體上依然采用DE算法的框架,算法對(duì)應(yīng)的參數(shù)也沿襲了YuanYuan等測(cè)試得出的較好參數(shù),其中包括:縮放因子F=0.1,交叉概率Cr=0.3。對(duì)于多目標(biāo)變異因子中的貪婪因子λ,本文經(jīng)測(cè)試取λ=0.5。另外,在每個(gè)調(diào)度區(qū)間上都要對(duì)該調(diào)度區(qū)間上的待調(diào)度工件進(jìn)行調(diào)度優(yōu)化,而每個(gè)調(diào)度區(qū)間上的待調(diào)度工件數(shù)均不相同,為了測(cè)試方便,文中各個(gè)調(diào)度區(qū)間的種群規(guī)模和進(jìn)化代數(shù)都設(shè)置為相同值,其中:種群規(guī)模Np=500,最大進(jìn)化代數(shù)Gmax=200。4.2節(jié)點(diǎn)調(diào)度加工模擬本文在m=10,U=0.9,μg=15,μp=1.76×0.7情況下,對(duì)先后到達(dá)的500個(gè)工件在調(diào)度周期ΔT分別為100,200,300,400和500的情況下進(jìn)行調(diào)度加工模擬,分別得到不同調(diào)度周期下的總完工時(shí)間(500個(gè)工件全部加工完成的完工時(shí)間)、總拖期(500個(gè)工件的拖期值求和)、總效率(由每個(gè)調(diào)度區(qū)間中選擇的調(diào)度方案對(duì)應(yīng)的效率值求和得到)以及總穩(wěn)定性(由各個(gè)調(diào)度區(qū)間的穩(wěn)定性值求和得到)的結(jié)果,具體數(shù)據(jù)如表1所示。4.2.1對(duì)再調(diào)度周期t的影響不同再調(diào)度周期ΔT下的總完工時(shí)間和總拖期如圖4所示。從圖4中可以看出,隨著再調(diào)度周期ΔT的增加,總完工時(shí)間相應(yīng)增加,再調(diào)度周期ΔT每增加100個(gè)時(shí)間單位,總完工時(shí)間大約增加5%~6%,而總拖期大約增加100%?？梢?jiàn)再調(diào)度周期ΔT的增加對(duì)最后的總完工時(shí)間的影響相對(duì)較小,但對(duì)總拖期有較大影響。增大再調(diào)度周期ΔT,則在ΔT的時(shí)間內(nèi)會(huì)有更多的新工件到達(dá),從而增加了每個(gè)調(diào)度區(qū)間上的待調(diào)度工件總數(shù),也增加了各工件從到達(dá)到進(jìn)行調(diào)度的等待時(shí)間,進(jìn)而增大了相應(yīng)的總拖期。4.2.2不同再調(diào)度周期t對(duì)總效率的影響不同的再調(diào)度周期ΔT對(duì)總效率和總穩(wěn)定性的影響如圖5所示。由于效率目標(biāo)(efficiency)由各個(gè)調(diào)度區(qū)間中的完工時(shí)間和拖期加權(quán)得到,隨著再調(diào)度周期ΔT的增加,對(duì)拖期的影響非常顯著,進(jìn)而對(duì)總效率的影響也非常顯著。對(duì)于總穩(wěn)定性,在再調(diào)度周期ΔT從100逐漸增加到300的過(guò)程中,總穩(wěn)定性值逐次降低,且降幅比較明顯;但再調(diào)度周期ΔT從300增加到400的過(guò)程中,總穩(wěn)定性的變化非常微小,在再調(diào)度周期ΔT為300時(shí)總穩(wěn)定性的基礎(chǔ)上增加大約2%;再調(diào)度周期ΔT從400增加到500時(shí),總穩(wěn)定性比再調(diào)度周期ΔT為400時(shí)有稍大的增加,增幅大約為16%。4.2.3工件再調(diào)度加工由于每個(gè)調(diào)度區(qū)間的長(zhǎng)度等于再調(diào)度周期ΔT的長(zhǎng)度,當(dāng)對(duì)同樣數(shù)目的先后到達(dá)工序進(jìn)行動(dòng)態(tài)調(diào)度時(shí),不同的再調(diào)度周期ΔT下需要進(jìn)行調(diào)度的次數(shù)不同,每個(gè)調(diào)度區(qū)間上的工件構(gòu)成也不同。對(duì)500個(gè)先后到達(dá)的工件進(jìn)行動(dòng)態(tài)調(diào)度,再調(diào)度周期ΔT=200的各調(diào)度區(qū)間上的工件構(gòu)成情況如表2所示,ΔT=300時(shí)再調(diào)度周期如表3所示。經(jīng)簡(jiǎn)單計(jì)算可以得到不同的再調(diào)度周期ΔT下,對(duì)500個(gè)先后到達(dá)的工件進(jìn)行調(diào)度加工,調(diào)度區(qū)間在下一個(gè)再調(diào)度時(shí)刻到達(dá)時(shí)加工完成的平均工序數(shù),具體如圖6所示。從圖6中可以看出,每個(gè)調(diào)度區(qū)間內(nèi)加工完成的工序數(shù)和再調(diào)度周期ΔT呈正相關(guān)。再調(diào)度周期ΔT增加,調(diào)度區(qū)間內(nèi)的待調(diào)度工序數(shù)增加,同時(shí)調(diào)度區(qū)間中能夠在下次在調(diào)度時(shí)刻到達(dá)時(shí)加工完成的工序數(shù)也相應(yīng)增加。通過(guò)在不同再調(diào)度周期ΔT下,分析同樣數(shù)量的先后到達(dá)的工件進(jìn)行調(diào)度加工需要進(jìn)行的調(diào)度次數(shù)以及各調(diào)度區(qū)間上的工件工序構(gòu)成,可以得到總穩(wěn)定性值隨著再調(diào)度周期ΔT的增加先減小后增大的原因。對(duì)先后到達(dá)的同樣數(shù)量的工件進(jìn)行動(dòng)態(tài)調(diào)度,再調(diào)度周期ΔT增加,再調(diào)度的次數(shù)會(huì)相應(yīng)減少,