不同再調(diào)度周期下的柔性作業(yè)車間動(dòng)態(tài)調(diào)度

汪雙喜，張超勇+，劉 瓊，饒運(yùn)清，尹 勇

（1.華中科技大學(xué) 機(jī)械學(xué)院數(shù)字制造裝備與技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074；2.武漢理工大學(xué) 湖北省數(shù)字制造重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074）

0 引言

柔性作業(yè)車間調(diào)度問題（Flexible Job-shop Scheduling Problem，F(xiàn)JSP）是經(jīng)典作業(yè)車間調(diào)度問題（Job shop Scheduling Problem，JSP）的擴(kuò)展，它不但考慮機(jī)器上待加工工序的加工順序，而且考慮各個(gè)工序是由哪臺(tái)機(jī)器進(jìn)行加工，更符合實(shí)際生產(chǎn)的需要。然而，F(xiàn)JSP 減少了機(jī)器約束，擴(kuò)大了可行解的搜索范圍，增加了問題的求解難度，是比JSP更為復(fù)雜的NP-hard問題。鑒于此，人們將研究目標(biāo)轉(zhuǎn)向各種啟發(fā)式方法。在眾多的研究與探索中，通過模擬自然界中生物和人類行為過程中所表現(xiàn)出的某些特點(diǎn)而發(fā)展的群體智能算法，如遺傳算法、粒子群優(yōu)化算法、蟻群優(yōu)化算法、差分進(jìn)化（Differential Evolution，DE）算法等，在包括調(diào)度問題在內(nèi)的組合優(yōu)化問題求解領(lǐng)域中，受到越來越普遍的關(guān)注。近年來，大量學(xué)者對(duì)FJSP 進(jìn)行了研究，Bagheri等［1］使用人工免疫算法求解FJSP，Wang 等［2-3］分別使用人工蜂群算法和分布估計(jì)算法求解FJSP，在求解過程中平衡了局部搜索和全局搜索過程。其中DE算法由Storn和Price［4］于1997年提出，是最新的基于種群的進(jìn)化算法之一，其最初的設(shè)想是用于解決連續(xù)性問題。由于DE 算法具有思路簡(jiǎn)單、容易實(shí)現(xiàn)、收斂速度快和穩(wěn)定性好等優(yōu)點(diǎn)，近年來被廣泛應(yīng)用于解決復(fù)雜優(yōu)化問題，如人工神經(jīng)元網(wǎng)絡(luò)、化工、電氣和經(jīng)濟(jì)學(xué)等，但對(duì)于調(diào)度問題這種典型的離散型問題研究得還不多，尤其對(duì)于FJSP 問題，少有學(xué)者用DE算法進(jìn)行研究。

實(shí)際環(huán)境下的FJSP 不但具有計(jì)算復(fù)雜性，而且有多目標(biāo)和動(dòng)態(tài)性特征，具體表現(xiàn)為：①生產(chǎn)過程是動(dòng)態(tài)的，各個(gè)工件依次進(jìn)入待加工狀態(tài)，進(jìn)入系統(tǒng)接受加工，同時(shí)完成加工的工件又不斷離開過程；②調(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)鍵問題，經(jīng)典調(diào)度的研究忽略了生產(chǎn)需求的動(dòng)態(tài)性和生產(chǎn)過程的健壯性與穩(wěn)定性，造成了理論研究距離實(shí)際應(yīng)用有相當(dāng)?shù)牟罹唷?/p>

Nelson等［5］在1977年最早提出了動(dòng)態(tài)調(diào)度問題，它將動(dòng)態(tài)調(diào)度過程分成多個(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)度；潘全科等［6］研究了待加工工件的選取原則和再調(diào)度周期的確定方法；Branke等［7］研究了工件隨機(jī)到達(dá)的動(dòng)態(tài)調(diào)度，以合并早期空閑時(shí)間的方法來提高調(diào)度效率；Chryssolouris等［8］用遺傳算法對(duì)動(dòng)態(tài)作業(yè)車間調(diào)度問題（Dynamic Job-shop Scheduling Problem，DJSP）進(jìn)行了求解，并考慮了兩個(gè)目標(biāo)，進(jìn)而說明多目標(biāo)調(diào)度在動(dòng)態(tài)調(diào)度中的可行性；Rangsaritrasamee等9提出了一種同時(shí)考慮效率與穩(wěn)定性的多目標(biāo)優(yōu)化策略，其采用加權(quán)的方式將兩目標(biāo)合成為單目標(biāo)問題進(jìn)行研究；劉愛軍等［10］提出一種自適應(yīng)遺傳算法的多目標(biāo)柔性動(dòng)態(tài)調(diào)度算法，基于事件和周期驅(qū)動(dòng)的混合再調(diào)度策略來求解實(shí)際的調(diào)度問題。

群體智能算法可以在一次運(yùn)行中得到多個(gè)Pareto解，非常適合求解多目標(biāo)優(yōu)化問題。國(guó)內(nèi)外學(xué)者目前在這方面做了大量研究，提出了多種多目標(biāo)進(jìn)化算法（Multi-Objective Evolutionary Algorithm，MOGA），如非支配排序遺傳算法（Non-dominated Sorting Genetic Algorithm，NSGA-Ⅱ）等，其中多目標(biāo)差分進(jìn)化有較好的收斂性和分布性，越來越受到國(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òng)態(tài)調(diào)度問題描述與轉(zhuǎn)化

為了研究不同再調(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á)時(shí)間模擬

許多研究顯示：在一定時(shí)間，內(nèi)車間中工件隨機(jī)到達(dá)的個(gè)數(shù)服從泊松分布，設(shè)泊松分布的參數(shù)為λ，表示工件的平均到達(dá)率，則任意兩個(gè)先后到達(dá)的工件之間的時(shí)間間隔服從參數(shù)為λ的指數(shù)分布。Karisiti等［11］在研究作業(yè)車間調(diào)度問題時(shí)提出一個(gè)關(guān)于到達(dá)率的計(jì)算公式，

式中：λ表示工件的平均到達(dá)率；U表示車間利用率（shop utilization）；m表示車間的機(jī)器數(shù)量；μp表示工序的平均加工時(shí)間；μg表示每個(gè)工件的平均工序數(shù)。

工件隨機(jī)到達(dá)的示意圖如圖1所示，任意兩個(gè)先后到達(dá)的工件之間的時(shí)間差服從參數(shù)為λ的幾何分布。通過模擬一組服從幾何分布的隨機(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 動(dòng)態(tài)調(diào)度策略與調(diào)度區(qū)間劃分

對(duì)于動(dòng)態(tài)調(diào)度問題，通常采用周期和事件驅(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í)間稱為再調(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)度的工件包括：①在上一個(gè)調(diào)度區(qū)間中進(jìn)行了調(diào)度但在當(dāng)前再調(diào)度時(shí)刻還未加工完成的工件；②在上一個(gè)再調(diào)度時(shí)刻與當(dāng)前再調(diào)度時(shí)刻期間到達(dá)的新工件。通過這種策略對(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)度問題進(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)生過程如圖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還沒有加工完成的工件（去除當(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還未開始加工，即工件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ī)器只能加工完成上述工序后才能開始加工調(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)度問題轉(zhuǎn)化為連續(xù)的調(diào)度區(qū)間上的靜態(tài)調(diào)度問題。在每個(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)度問題采用優(yōu)化算法進(jìn)行求解。

2 調(diào)度區(qū)間上的多目標(biāo)調(diào)度

2.1 調(diào)度區(qū)間上的問題描述

調(diào)度區(qū)間上的調(diào)度問題相當(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)度問題描述如下：該調(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ī)器加工，其中Mi′，j?M；工序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è)工件的每道工序一旦開始加工就不能中斷。

（7）不同工件的工序之間沒有先后約束，同一工件的工序之間有先后約束。

（8）忽略各機(jī)器設(shè)備的啟動(dòng)時(shí)間和各工序的運(yùn)輸時(shí)間。

2.2 優(yōu)化指標(biāo)

與傳統(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等［9］最早在作業(yè)車間動(dòng)態(tài)調(diào)度問題中同時(shí)考慮了這兩個(gè)指標(biāo)，F(xiàn)attahi等［12］將前者提出的兩個(gè)目標(biāo)進(jìn)行了擴(kuò)展，引入柔性作業(yè)車間動(dòng)態(tài)調(diào)度問題中，但是兩者對(duì)待雙目標(biāo)問題都是采用加權(quán)將雙目標(biāo)問題轉(zhuǎn)化為一個(gè)合成的單目標(biāo)問題進(jìn)行優(yōu)化。

本文將上述兩個(gè)目標(biāo)引入柔性作業(yè)車間動(dòng)態(tài)調(diào)度問題中，并在模擬求解過程中采用基于Pareto解的多目標(biāo)算法進(jìn)行優(yōu)化，最后再通過Pareto解決策出每個(gè)調(diào)度區(qū)間中的最優(yōu)調(diào)度方案，作為對(duì)應(yīng)調(diào)度區(qū)間上的實(shí)際調(diào)度方案。

2.3 優(yōu)化算法

DE算法是一種群體進(jìn)化搜索算法，具有思路簡(jiǎn)單、容易實(shí)現(xiàn)、收斂速度快和穩(wěn)定性好等優(yōu)點(diǎn)。它具有記憶個(gè)體最優(yōu)解和種群內(nèi)信息共享的特點(diǎn)，即通過種群內(nèi)個(gè)體間的合作與競(jìng)爭(zhēng)實(shí)現(xiàn)對(duì)優(yōu)化問題的求解。

Yuan Yuan等［13］在研究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)化問題。同樣在用差分進(jìn)化算法進(jìn)行單目標(biāo)優(yōu)化時(shí)，新種群通過選擇操作產(chǎn)生，同樣不適用于多目標(biāo)優(yōu)化問題。本文針對(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 多目標(biāo)變異操作

對(duì)于多目標(biāo)DE 算法，采用基于Pareto解的方法時(shí)，在每一代種群中會(huì)得到一個(gè)非支配解集DG（non-dominated solutions），G=0，1，…，Gmax，其中G表示種群的代數(shù)；同時(shí)也可以得到一個(gè)進(jìn)化到當(dāng)前代數(shù)為止的一個(gè)全局的非支配解集D。本文針對(duì)Xue Feng等［14］提出的多目標(biāo)變異算子進(jìn)行相應(yīng)改進(jìn)，使得變異操作能夠充分利用到全局的非支配解集D，得到式（4）所示的變異操作：

在Xue Feng等［14］提出的算子中，是否被支配以及都是基于當(dāng)前父代種群中的非支配解集DG考慮的。本文采用全局的非支配解集D進(jìn)行操作，如果，則說明不能被支配，否則從全局的非支配解集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(xiàn)為縮放因子，λ∈［0，1］表示的是貪婪因子。λ越靠近1，差分基向量中所占的比重就越大；λ越靠近0，在差分基向量中所占的所比重就越大。

如果在當(dāng)前調(diào)度區(qū)間不存在需要再調(diào)度的工件，即待調(diào)度工件全是新到達(dá)的工件，如第一個(gè)調(diào)度區(qū)間，則該調(diào)度區(qū)間上將不存在穩(wěn)定性指標(biāo)的優(yōu)化，公式中的變異算子將退化（如式（5）），與Yuan Yuan等［13］采用的單目標(biāo)變異算子保持一致。

2.3.2 新種群產(chǎn)生策略

父代種群Pt（t表示種群的代數(shù)）中的每個(gè)個(gè)體經(jīng)過變異、交叉操作后得規(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 Pareto解決策

在調(diào)度區(qū)間中，采用基于Pareto解的優(yōu)化算法進(jìn)行調(diào)度后最終會(huì)得到一個(gè)Pareto非支配解集，而進(jìn)行加工時(shí)只能有一個(gè)可行的調(diào)度方案，因此必須要從當(dāng)前的非支配集合中選擇出一個(gè)滿意的調(diào)度方案，并以此調(diào)度方案作為下個(gè)調(diào)度區(qū)間的基準(zhǔn)。在進(jìn)行Pareto解決策時(shí)，本文采用文獻(xiàn)［9］的推薦比例，效率（Efficiency）和穩(wěn)定性（Stability）權(quán)重分析設(shè)為5和1，依據(jù)式（6）計(jì)算結(jié)果選擇滿意解，實(shí)際操作中可以根據(jù)具體情況設(shè)定其他合適的決策方案。

3 實(shí)例設(shè)置

3.1 工件的加工時(shí)間模擬

在柔性作業(yè)車間中，各個(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說明工序Pi，j不能在機(jī)器Mk上加工。

3.2 工件到達(dá)時(shí)間仿真

根據(jù)式（1）所示的工件的平均到達(dá)率，本文設(shè)定實(shí)例的相關(guān)參數(shù)為：加工機(jī)器數(shù)量m=10，車間利用率U=0.9，每個(gè)工件包含15 道工序，即μg=15。平均加工時(shí)間μp是一個(gè)與加工車間的實(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 工件交貨期模擬

本文采用的效率目標(biāo)由調(diào)度區(qū)間上的完工時(shí)間和拖期共同確定，為了計(jì)算各工件的拖期值，必須要針對(duì)其交貨期進(jìn)行設(shè)置。很多學(xué)者就工件交貨期的設(shè)定進(jìn)行了研究，其中Baker等［15］提出的TWK（total work content）規(guī)則得到了很多學(xué)者的引用。本文針對(duì)柔性作業(yè)車間調(diào)度環(huán)境的特殊性，將此模型進(jìn)行了相應(yīng)的修改，得到

式中：DDi表示工件Ji的交貨期；ai表示工 件Ji的到達(dá)時(shí)間表示工件Ji的第j道工序Oi，j在各個(gè)可加工機(jī)器上加工時(shí)間的均值；K表示松緊因子，在Blocher等［16］給出的推薦值中，該值最小取2，本文取K=2。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 算法參數(shù)設(shè)置

在各個(gè)調(diào)度區(qū)間上，本文采用Yuan Yuan等［13］針對(duì)FJSP提出的實(shí)數(shù)編碼方案，采用DE 算法進(jìn)行求解，并針對(duì)多目標(biāo)優(yōu)化問題就變異算子以及新種群的產(chǎn)生策略進(jìn)行調(diào)整，另外增加了Pareto解決策的操作，但總體上依然采用DE 算法的框架，算法對(duì)應(yīng)的參數(shù)也沿襲了Yuan Yuan等［13］測(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 測(cè)試結(jié)果與分析

本文在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所示。

表1 不同再調(diào)度周期ΔT 下對(duì)500個(gè)先后到達(dá)的工件進(jìn)行動(dòng)態(tài)調(diào)度得到的各項(xiàng)指標(biāo)

4.2.1 再調(diào)度周期ΔT對(duì)總完工時(shí)間和總拖期的影響

不同再調(diào)度周期ΔT下的總完工時(shí)間和總拖期如圖4所示。從圖4中可以看出，隨著再調(diào)度周期ΔT的增加，總完工時(shí)間相應(yīng)增加，再調(diào)度周期ΔT每增加100個(gè)時(shí)間單位，總完工時(shí)間大約增加5%～6%，而總拖期大約增加100%?？梢娫僬{(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ì)總效率和總穩(wěn)定性的影響

不同的再調(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的過程中，總穩(wěn)定性值逐次降低，且降幅比較明顯；但再調(diào)度周期ΔT從300 增加到400的過程中，總穩(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)度周期ΔT對(duì)調(diào)度區(qū)間的影響

由于每個(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)增加。

表2 再調(diào)度周期ΔT＝200時(shí)各調(diào)度區(qū)間上的工件工序構(gòu)成

表3 再調(diào)度周期ΔT＝300時(shí)各調(diào)度區(qū)間上的工件工序構(gòu)成

續(xù)表3

通過在不同再調(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)減少，即對(duì)應(yīng)的調(diào)度區(qū)間數(shù)量會(huì)減小，從而使總的穩(wěn)定性相應(yīng)減少，因?yàn)橹挥性僬{(diào)度才會(huì)產(chǎn)生穩(wěn)定性值的增加。但是當(dāng)再調(diào)度周期ΔT取值過大時(shí)，調(diào)度區(qū)間中屬于再調(diào)度類型的工序數(shù)增多，兩次再調(diào)度區(qū)間之間的時(shí)間間隔（等于）變大，使得需要再調(diào)度的工序經(jīng)常被安排在下一個(gè)，甚至下下一個(gè)調(diào)度區(qū)間中才能加工，從而增大了每個(gè)被再調(diào)度的工序所產(chǎn)生的穩(wěn)定性值，也相應(yīng)地提高了總的穩(wěn)定性。

5 結(jié)束語(yǔ)

本文采用概率的方法模擬了各個(gè)工件的到達(dá)時(shí)間，并針對(duì)這些先后到達(dá)的工件，采用周期性再調(diào)度的調(diào)度策略進(jìn)行調(diào)度加工，將動(dòng)態(tài)調(diào)度問題轉(zhuǎn)化為多個(gè)連續(xù)的調(diào)度區(qū)間上的靜態(tài)調(diào)度問題進(jìn)行求解。在每個(gè)調(diào)度區(qū)間上，采用基于多目標(biāo)DE 算法，以效率和穩(wěn)定性為優(yōu)化目標(biāo)進(jìn)行調(diào)度優(yōu)化。采用該方法對(duì)先后到達(dá)的500個(gè)工件在不同的再調(diào)度周期ΔT下進(jìn)行調(diào)度加工，并對(duì)最后得到的總完工時(shí)間、總拖期、總效率和總穩(wěn)定性進(jìn)行了分析與比較，得到以下結(jié)論：

（1）再調(diào)度周期ΔT增大，總完工時(shí)間依次增大，但增幅較小，總拖期和總效率依次增大，且增幅較大?？紤]到本文的效率指標(biāo)是通過完工時(shí)間和拖期加權(quán)得到的，而拖期的變化隨著調(diào)度周期的變化非常明顯，調(diào)度周期越長(zhǎng)，總拖期越大，總完工時(shí)間的變化相對(duì)較小。因此在實(shí)際生產(chǎn)中當(dāng)拖期指標(biāo)很重要時(shí)，通常應(yīng)當(dāng)減小再調(diào)度周期。

（2）再調(diào)度周期ΔT逐漸增大時(shí)，總穩(wěn)定性依次減?。ǚ€(wěn)定性越好），且降幅明顯；但當(dāng)再調(diào)度周期ΔT太大時(shí)，總穩(wěn)定性反而增大（穩(wěn)定性變差）。在實(shí)際生產(chǎn)中，應(yīng)當(dāng)根據(jù)實(shí)際的調(diào)度加工環(huán)境適當(dāng)設(shè)置再調(diào)度周期，以滿足對(duì)穩(wěn)定性指標(biāo)的要求。

（3）在實(shí)際生產(chǎn)中，效率和穩(wěn)定性通常會(huì)表現(xiàn)出一定的矛盾，即不存在使兩個(gè)都變優(yōu)的方案。因此，應(yīng)當(dāng)根據(jù)實(shí)際需要以及對(duì)應(yīng)優(yōu)化目標(biāo)的重要程度進(jìn)行特定優(yōu)化，以確定最合適的再調(diào)度周期ΔT。

柔性作業(yè)車間動(dòng)態(tài)調(diào)度是生產(chǎn)調(diào)度中一個(gè)復(fù)雜的研究方向，比較符合制造車間中的實(shí)際情況，對(duì)其開展進(jìn)一步深入研究顯得十分必要，項(xiàng)目組在本文研究的基礎(chǔ)上，將在未來開展以下工作：

（1）研究不同調(diào)度周期下在每個(gè)調(diào)度區(qū)間中已完成加工的工序數(shù)與未開始加工（即需要再調(diào)度的工序）的工序數(shù)之間的比例關(guān)系，并在采用算法求解時(shí)針對(duì)這一數(shù)據(jù)進(jìn)行相應(yīng)優(yōu)化。

（2）研究考慮機(jī)器故障等動(dòng)態(tài)事件下的柔性作業(yè)車間動(dòng)態(tài)調(diào)度問題。

［1］BAGHERI A，ZANDIEH M，MAHDAVI I，et al.An artificial immune algorithm for the flexible job-shop scheduling problem［J］.Future Generation Computer Systems，2010，26（4）：533-541.

［2］WANG L，ZHOU G，XU Y，et al.An effective artificial bee colony algorithm for the flexible job-shop scheduling problem［J］.The International Journal of Advanced Manufacturing Technology，2012，60（1-4）：303-315.

［3］WANG L，WANG S，XU Y，et al.A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem［J］.Computers &Industrial Engineering，2012，62（4）：917-926.

［4］STORN R，PRICE K.Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces［J］.Journal of Global Optimization，1997，11（4）：341-359.

［5］HOLLOWAY C A，NELSON R T.Job shop scheduling with due dates and variable processing times［J］.Management Science，1974，20（9）：1264-1275.

［6］PAN Quanke，ZHU Jianying.Rolling time horizon Job Shop scheduling strategy in dynamic environment［J］.Journal of Nanjing University of Aeronautics &Astronautics，2005，37（2）：262-268（in Chinese）.［潘全科，朱劍英.作業(yè)車間動(dòng)態(tài)調(diào)度研究［J］.南京航空航天大學(xué)學(xué)報(bào)，2005，37（2）：262-268.］

［7］BRANKE J，MATTFELD D C.Anticipation and flexibility in dynamic scheduling［J］.International Journal of Production Research，2005，43（15）：3103-3129.

［8］CHRYSSOLOURIS G，SUBRAMANIAM V.Dynamic scheduling of manufacturing job shops using genetic algorithms［J］.Journal of Intelligent Manufacturing，2001，12（3）：281-293.

［9］RANGSARITRATSAMEE R，F(xiàn)ERRELL J R W G，KURZ M B.Dynamic rescheduling that simultaneously considers efficiency and stability［J］.Computers &Industrial Engineering，2004，46（1）：1-15.

［10］LIU Aijun，YANG Yu，XING Qingsong，et al.Dynamic scheduling on multi-objective flexible Job Shop［J］.Compyter Integrated Manufacturing Systems，2011，17（12）：2629-2637（in Chinese）.［劉愛軍，楊 育，邢青松，等.柔性作業(yè)車間多目標(biāo)動(dòng)態(tài)調(diào)度［J］.計(jì)算機(jī)集成制造系統(tǒng)，2011，17（12）：2629-2637.］

［11］KARSITI M N，CRUZ JR J B，MULLINGAN J R J.Simulation studies of multilevel dynamic job shop scheduling using heuristic dispatching rules［J］.Journal of Manufacturing Systems，1992，11（5）：346-358.

［12］FATTAHI P，SAIDI MEHRABAD M，JOLAI F.Mathematical modeling and heuristic approaches to flexible job shop scheduling problems［J］.Journal of Intelligent Manufacturing，2007，18（3）：331-342.

［13］YUAN Y，XU H.Flexible job shop scheduling using hybrid differential evolution algorithms［J］.Computers &Industrial Engineering，2013，65（2）：246-260.

［14］XUE F，SANDERSON A C，GRAVES R J.Pareto-based multi-objective differential evolution［C］／／Proceedings of the 2003Congress on Evolutionary Computation.Washington，D.C.，USA：IEEE，2003：862-869.

［15］BAKER K R.Sequencing rules and due-date assignments in a job shop［J］.Management Science，1984，30（9）：1093-1104.

［16］BLOCHER J D，CHHAJED D，LEUNG M.Customer order scheduling in a general job shop eEnvironment［J］.Decision Sciences，1998，29（4）：951-981.