張沙清 陳新度 陳慶新 陳 新

廣東工業(yè)大學(xué)，廣州，510006

基于改進(jìn)多目標(biāo)微粒群算法的模具多項(xiàng)目反應(yīng)調(diào)度

張沙清 陳新度 陳慶新 陳 新

廣東工業(yè)大學(xué)，廣州，510006

針對(duì)模具多項(xiàng)目執(zhí)行過程中由于可再生資源發(fā)生故障、任務(wù)拖期以及隨機(jī)插入新項(xiàng)目而導(dǎo)致的調(diào)度計(jì)劃變更問題，提出了一種反應(yīng)調(diào)度算法。利用生滅過程理論對(duì)可再生資源的不確定性進(jìn)行分析，并采用基于優(yōu)先規(guī)則的拓?fù)渑判蚍椒?gòu)建初始調(diào)度計(jì)劃，建立了以調(diào)度計(jì)劃變更產(chǎn)生的附加費(fèi)用最小以及項(xiàng)目加權(quán)工期之和最小為目標(biāo)的多目標(biāo)反應(yīng)調(diào)度模型，并提出一種改進(jìn)的多目標(biāo)微粒群算法進(jìn)行模型求解。最后，通過仿真計(jì)算分析了反應(yīng)調(diào)度算法的可行性與有效性。

任務(wù)拖期；資源不確定；反應(yīng)調(diào)度；多目標(biāo)微粒群算法

0 引言

在模具項(xiàng)目執(zhí)行過程中經(jīng)常會(huì)出現(xiàn)各種突發(fā)事件，如資源發(fā)生故障、任務(wù)拖期、隨機(jī)插入新項(xiàng)目、工程與生產(chǎn)變更等，結(jié)果導(dǎo)致開始制訂的項(xiàng)目計(jì)劃被破壞。只有采取科學(xué)的多項(xiàng)目動(dòng)態(tài)調(diào)度與協(xié)同監(jiān)控手段，才能有效地應(yīng)對(duì)突發(fā)事件，確保項(xiàng)目順利進(jìn)行。目前，專門研究風(fēng)險(xiǎn)性和不確定環(huán)境下項(xiàng)目調(diào)度理論與方法的文獻(xiàn)較少。對(duì)現(xiàn)有文獻(xiàn)進(jìn)行初步歸類，可以大致分為兩大類：第一類將項(xiàng)目網(wǎng)絡(luò)圖的結(jié)構(gòu)假設(shè)為確定的，而將項(xiàng)目中的其他參數(shù)，如任務(wù)工期等作為不確定性變量，對(duì)項(xiàng)目調(diào)度方案的制訂展開研究，文獻(xiàn)［1］全面地綜述了這類研究工作，認(rèn)為主要存在四種不同的調(diào)度方法，即反應(yīng)性調(diào)度、隨機(jī)性調(diào)度、模糊調(diào)度和前攝魯棒性調(diào)度；第二類將項(xiàng)目網(wǎng)絡(luò)圖的結(jié)構(gòu)假設(shè)為隨機(jī)的，研究項(xiàng)目調(diào)度計(jì)劃與控制方法，文獻(xiàn)［2－3］介紹了這類研究工作。

就模具項(xiàng)目調(diào)度而言，文獻(xiàn)［4］對(duì)確定條件下的多個(gè)模具項(xiàng)目的工期費(fèi)用規(guī)劃作了初步研究，文獻(xiàn)［5－6］在單個(gè)模具項(xiàng)目的工期與費(fèi)用的不確定性規(guī)劃方面作了大量的研究，文獻(xiàn)［7］研究了具有工件約束的模具零件制造的動(dòng)態(tài)調(diào)度問題，文獻(xiàn)［8－9］考慮了任務(wù)工時(shí)、費(fèi)用、質(zhì)量、是否返修等不確定因素，基于Markov理論，研究了基于啟發(fā)式策略仿真和Q學(xué)習(xí)算法的多模具制造過程的隨機(jī)調(diào)度問題，但針對(duì)不確定環(huán)境下多個(gè)模具項(xiàng)目的分析、設(shè)計(jì)、制造過程的動(dòng)態(tài)調(diào)度研究，國(guó)內(nèi)外文獻(xiàn)并不多見。

本文從多目標(biāo)優(yōu)化的角度出發(fā)，研究在可再生資源（以下簡(jiǎn)稱資源）發(fā)生故障、任務(wù)拖期、隨機(jī)插入新項(xiàng)目等多種不確定因素影響下的模具多項(xiàng)目反應(yīng)調(diào)度算法。

1 問題描述

一個(gè)典型完整的模具項(xiàng)目的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1所示，其中每個(gè)節(jié)點(diǎn)（圓圈表示）表示一個(gè)任務(wù)，共有16個(gè)任務(wù)，各任務(wù)名稱及其對(duì)資源的需求如表1所示。由于模具項(xiàng)目的分析、設(shè)計(jì)與制造的工藝流程大致相同，因此它們的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)也大體相同，因此可以把多個(gè)模具的網(wǎng)絡(luò)結(jié)構(gòu)圖采用并行連接的方法合并為一個(gè)網(wǎng)絡(luò)圖G＝（N，A），首尾加兩個(gè)虛擬節(jié)點(diǎn)，并對(duì)各節(jié)點(diǎn)重新編號(hào)，其中，N為網(wǎng)絡(luò)中的節(jié)點(diǎn)（包括虛擬的開始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)），A為任務(wù)之間的緊前約束關(guān)系集合，即若任務(wù)i為任務(wù)j的前驅(qū)，則?。╥，j）∈A。圖2為三個(gè)模具項(xiàng)目的網(wǎng)絡(luò)結(jié)構(gòu)圖，其中0、49號(hào)節(jié)點(diǎn)分別表示虛擬的開始任務(wù)和結(jié)束任務(wù)，工期為0，也不需要任何資源。

圖1 模具項(xiàng)目網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

表1 任務(wù)資源需求表

圖2 三個(gè)模具項(xiàng)目的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

模具生產(chǎn)過程中，首先需要制訂一個(gè)初始調(diào)度計(jì)劃，然后執(zhí)行該初始計(jì)劃。在項(xiàng)目執(zhí)行過程中，當(dāng)可用資源數(shù)量不足、任務(wù)拖期或隨機(jī)插入新項(xiàng)目導(dǎo)致正在執(zhí)行的調(diào)度計(jì)劃St－1無法繼續(xù)執(zhí)行時(shí)，則進(jìn)行反應(yīng)調(diào)度，產(chǎn)生一個(gè)新的調(diào)度計(jì)劃St。本文提出的反應(yīng)調(diào)度的優(yōu)化目標(biāo)為：①St與St－1的偏差最小，通常用因反應(yīng)調(diào)度產(chǎn)生的計(jì)劃變更而帶來的附加費(fèi)用來衡量這種偏差［10-11］，附加費(fèi)用越小則偏差越小；②St的項(xiàng)目加權(quán)工期之和最小，從而減少由于項(xiàng)目拖期而造成的高額罰款。上述優(yōu)化目標(biāo)可用如下模型進(jìn)行描述：式中，n 為G 中非虛 擬任務(wù)的 個(gè) 數(shù)、分 別為St、St－1中任務(wù)i的計(jì)劃開始時(shí)間為St中任務(wù)i的工期；wi為任務(wù)i的權(quán)重，表示反應(yīng)調(diào)度后任務(wù)i開始時(shí)間每變更一個(gè)時(shí)間單位所產(chǎn)生的附加費(fèi)用的相對(duì)大小，假設(shè)其大小符合一個(gè)離散的三角分布，即wi＝z的概率P由下式確定［12］：P（wi＝z）＝（21－2z）%，z∈ ｛1，2，…，10｝；g 為項(xiàng)目個(gè)數(shù)（包括可能隨機(jī)插入的新項(xiàng)目）為St中項(xiàng)目q的計(jì)劃完成時(shí)間；γq為項(xiàng)目q的重要性權(quán)重；rik為任務(wù)i每個(gè)時(shí)段所需的資源k的數(shù)量；Ωτ為時(shí)間段τ正在執(zhí)行的任務(wù)的集合；a′kτ為τ時(shí)段資源k的可用數(shù)量。

式（1）、式（2）表示多目標(biāo)優(yōu)化模型的兩個(gè)優(yōu)化目標(biāo)，式（3）表示任務(wù)之間的緊前約束條件（即任意一個(gè)任務(wù)必須在其所有前驅(qū)任務(wù)完成之后才可以開始），式（4）表示資源約束條件（即任意一個(gè)時(shí)段正在執(zhí)行的任務(wù)所需要的各類資源數(shù)量不能超過該時(shí)段各類資源的可用數(shù)量）。

對(duì)于上述多目標(biāo)優(yōu)化模型，有以下定義：

2 初始調(diào)度計(jì)劃的構(gòu)建

2.1 基于生滅過程的資源不確定性分析

通常，機(jī)器發(fā)生故障的時(shí)間間隔與機(jī)器的修復(fù)時(shí)間均服從一定參數(shù)的指數(shù)分布。如果工作人員（如前述的設(shè)計(jì)員、程序員、工藝員、采購(gòu)員）因各種原因而發(fā)生缺勤的時(shí)間間隔，以及人員缺勤的時(shí)間也服從指數(shù)分布，則可用生滅過程來分析資源的不確定性。為方便起見，將機(jī)器故障與人員缺勤統(tǒng)一描述為資源故障，而將機(jī)器修復(fù)與人員復(fù)工統(tǒng)一描述為資源修復(fù)。

設(shè)項(xiàng)目執(zhí)行共需要K類資源，t＝0時(shí)資源k（k∈K）的總量為ak，資源k的平均故障時(shí)間間隔為TF，k，平均修復(fù)時(shí)間為TR，k。任意時(shí)段t的系統(tǒng)狀態(tài)jk表示故障資源k的個(gè)數(shù)為jk（為了描述方便，暫時(shí)省去下標(biāo)k）。若生滅過程在時(shí)段t處于狀態(tài)j，則該過程的狀態(tài)轉(zhuǎn)變服從如下兩個(gè)定理。

定理1［15］在時(shí)段t和t＋Δt之間出現(xiàn)“生”的概率為λjΔt＋ο（Δt），“生”使系統(tǒng)狀態(tài)增加1，成為j＋1，變量λj稱為狀態(tài)j下的出生率；在時(shí)段t和t＋Δt之間出現(xiàn)“滅”的概率為μjΔt＋ο（Δt），“滅”使系統(tǒng)狀態(tài)減少1，成為j－1，變量μj稱為狀態(tài)j下的滅亡率，μ0＝0必須成立，否則可能出現(xiàn)負(fù)狀態(tài)。

定理2［15］“生”和“滅”彼此獨(dú)立。

顯然，本文中的“生”指資源發(fā)生故障，“滅”指資源被修復(fù)。因此，有λj＝ （a－j）／TF，μj＝j(luò)／TR。狀態(tài)j的穩(wěn)態(tài)概率πj可以通過求解如下的流量平衡方程而得到［15］：

2.2 基于拓?fù)渑判虻某跏颊{(diào)度計(jì)劃構(gòu)建

初始調(diào)度計(jì)劃的構(gòu)建為典型的資源受限項(xiàng)目調(diào)度問題（resource constrained project scheduling problem，RCPSP），目前的解法主要有精確算法和啟發(fā)式算法兩大類。對(duì)于規(guī)模較大的RCPSP問題主要采用后者進(jìn)行求解。本文中令資源k單位時(shí)段的可用數(shù)量為E（ak），采用一種基于優(yōu)先規(guī)則的拓?fù)渑判蚍▉懋a(chǎn)生一個(gè)項(xiàng)目加權(quán)工期之和最小的初始調(diào)度計(jì)劃［16］。

3 基于改進(jìn)多目標(biāo)微粒群算法的反應(yīng)調(diào)度

3.1 反應(yīng)調(diào)度算法描述

設(shè)S0表示時(shí)間t＝0時(shí)執(zhí)行的調(diào)度計(jì)劃，則本文提出的反應(yīng)調(diào)度算法流程如下：①初始化，t＝0，St＝S0；②若時(shí)間t所有任務(wù)全部完成，則調(diào)度結(jié)束，否則轉(zhuǎn)向步驟③；③若時(shí)間t出現(xiàn)資源不足、任務(wù)拖期或插入新項(xiàng)目的情況，則轉(zhuǎn)向步驟④，否則St＝St－1，轉(zhuǎn)向步驟⑤；④將當(dāng)前正在執(zhí)行的調(diào)度計(jì)劃St－1中計(jì)劃完成時(shí)間不小于t的任務(wù)及其時(shí)序關(guān)系組成新調(diào)度的項(xiàng)目網(wǎng)絡(luò)圖，并采用改進(jìn)的多目標(biāo)微粒群算法求出新的調(diào)度計(jì)劃St；⑤開始執(zhí)行St中所有開始時(shí)間為t的任務(wù)；⑥t←t＋1，返回步驟 ②。

上述算法步驟④中，對(duì)于在t時(shí)段正在執(zhí)行的任務(wù)，進(jìn)行反應(yīng)調(diào)度時(shí)通常有兩種處理模式，即所謂的Preempt－repeat模式和Preempt－resume模式。前者指的是在t之前的工作完全損失，反應(yīng)調(diào)度時(shí)該任務(wù)需要從頭開始執(zhí)行，而后者指的是在t之前的工作不會(huì)損失，反應(yīng)調(diào)度時(shí)該任務(wù)從中斷處繼續(xù)開始執(zhí)行。本文采用Preempt－repeat模式，同時(shí)假設(shè)在沒有出現(xiàn)資源不足、任務(wù)拖期或插入新項(xiàng)目的情況下，正在執(zhí)行的任務(wù)所使用的資源不能被強(qiáng)占，即任務(wù)不能被中斷（簡(jiǎn)稱為不可強(qiáng)占資源）。

3.2 改進(jìn)的多目標(biāo)微粒群算法

文獻(xiàn)［17］提出利用微粒群優(yōu)化算法解決多目標(biāo)優(yōu)化問題，在理論研究和實(shí)際應(yīng)用中都取得了大量的成果。多目標(biāo)優(yōu)化的多重任務(wù)要求整個(gè)群體既要向Pareto最優(yōu)前端逼近，又要能維持群體的多樣性與均勻性，因此在更新微粒位置與速度時(shí)，往往面臨著一定的矛盾。本文借鑒文獻(xiàn)［18］的最優(yōu)解評(píng)估選取方法，將孤立點(diǎn)搜索策略與精英歸檔策略相結(jié)合，提出采用一種改進(jìn)的多目標(biāo)微粒群算法（improved multi－objective particle swarm optimization，IMOPSO）來求解反應(yīng)調(diào)度時(shí)的新計(jì)劃。算法流程描述如下：

（1）初始化，設(shè)定算法的各參數(shù)（種群規(guī)模為M，最大迭代次數(shù)為Imax，慣性權(quán)重為ω，學(xué)習(xí)因子分別為c1、c2、c3，精英集的容量大小為Selite）。隨機(jī)產(chǎn)生每個(gè)微粒的位置向量X（i）和速度向量V（i）（i＝ 1，2，…，M），X（i）為對(duì)應(yīng)任務(wù)的優(yōu)先權(quán)，為［0，1］之間的隨機(jī)數(shù)，微粒速度為［－0.9，0.9］之間的隨機(jī)數(shù)。分別隨機(jī)產(chǎn)生每個(gè)微粒i在目標(biāo)函數(shù)f1、f2下的最優(yōu)位置向量Pbest1（i）、Pbest2（i），以及全局最優(yōu)位置向量Gbest1、Gbest2，置當(dāng)前迭代次數(shù)m＝1。

（2）對(duì)每個(gè)微粒i，利用修改后的串行調(diào)度生成方案［16］產(chǎn)生一個(gè)調(diào)度計(jì)劃，分別用目標(biāo)函數(shù)f1、f2計(jì) 算 調(diào) 度 計(jì) 劃 的 適 應(yīng) 值 f1（X（i））和f2（X（i））。

（3）分別求得每個(gè)微粒i在目標(biāo)函數(shù)f1、f2下的最優(yōu)位置向量，即

（6）計(jì)算每個(gè)微粒的稀疏度，并得到稀疏度最大的微粒，其位置向量記為X（l）。

（7）更新每個(gè)微粒的速度向量和位置向量：

（8）將當(dāng)前種群中的非劣解加入精英集，并更新精英集（更新算法見3.3節(jié)）。

（9）m ←m＋1，若m≤Imax，則返回步驟（2）；否則，轉(zhuǎn)向步驟（10）。

（10）在精英集中選擇一個(gè)最優(yōu)折中解（見3.4節(jié)），算法結(jié)束。

算法步驟（6）中的稀疏度表示種群中個(gè)體周圍的稀疏程度，它等價(jià)于在個(gè)體周圍包含個(gè)體本身但是不包含其他個(gè)體的最大的長(zhǎng)方形?！跋∈瓒取痹酱蟮膫€(gè)體與其周圍鄰近的個(gè)體的平均距離越大，因而該個(gè)體周圍顯得越稀疏，“稀疏度”最大的個(gè)體稱為孤立點(diǎn)。在解空間進(jìn)行搜索時(shí)，使微粒朝著群體分布最為稀疏的區(qū)域飛行，有利于提高解的分布均勻性。分別將微粒按照目標(biāo)函數(shù)f1、f2排序，則微粒i的“稀疏度”可按下式計(jì)算［19］：

式中，β為（0，1）之間的隨機(jī)數(shù)。

3.3 精英集更新算法

（3）求RN數(shù)組中值為1與RE數(shù)組中值為1的元素所對(duì)應(yīng)的非劣解的并集。

簡(jiǎn)單的聚類方法（如K均值聚類）一般需要事先給定聚類的數(shù)目，具有較強(qiáng)的主觀性，而且對(duì)于高維數(shù)據(jù)（通常認(rèn)為超過16維即為高維）的聚類效果較差；另外，算法實(shí)現(xiàn)過程中往往需要對(duì)數(shù)據(jù)集進(jìn)行反復(fù)聚類，計(jì)算效率較低。本文采用一種高性能的層次聚類算法（clusters optimization on preprocessing stage，COPS）對(duì)微粒位置向量進(jìn)行聚類分析。COPS的原理與主要過程是［20］：①將每個(gè)數(shù)據(jù)點(diǎn)看作為一個(gè)單獨(dú)的簇；②自底向上層次式地構(gòu)造出數(shù)據(jù)集所有合理的劃分組合，進(jìn)而生成一條關(guān)于不同劃分的聚類質(zhì)量曲線；③抽取出對(duì)應(yīng)曲線極小值點(diǎn)的劃分來計(jì)算數(shù)據(jù)集的最佳聚類數(shù)目；④根據(jù)最佳聚類數(shù)目確定每個(gè)類中的樣本個(gè)數(shù)及其中心。若n′、d分別表示數(shù)據(jù)集的數(shù)據(jù)個(gè)數(shù)與維度，則COPS的時(shí)間復(fù)雜度僅為O（dn′log2n′），計(jì)算效率較高。

3.4 選擇最優(yōu)折中解

由于多目標(biāo)優(yōu)化算法得到的解是一組Pareto解集，故項(xiàng)目管理者需要從Pareto解集中選擇一個(gè)解作為反應(yīng)調(diào)度的結(jié)果。本文應(yīng)用模糊隸屬度函數(shù)來分別表示每個(gè)Pareto解中各個(gè)目標(biāo)函數(shù)對(duì)應(yīng)的滿意度［21］。設(shè)分別表示Pareto解集中目標(biāo)函數(shù)i的最大值與最小值表示Pareto解集中第k個(gè)解的目標(biāo)函數(shù)i的值，則Pareto解集中第k個(gè)解的目標(biāo)函數(shù)i對(duì)應(yīng)的滿意度定義如下：

4 仿真實(shí)驗(yàn)

4.1 算例介紹與算法參數(shù)設(shè)置

某模具廠同時(shí)開始三個(gè)模具項(xiàng)目，其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖2所示，其中編號(hào)為46、47、48的任務(wù)所在的項(xiàng)目分別為項(xiàng)目1、2、3，其項(xiàng)目重要性權(quán)重γ1、γ2、γ3分別為0.35、0.37、0.28。項(xiàng)目所需的各類資源的初始總量、平均故障時(shí)間間隔TF、平均修復(fù)時(shí)間TR如表3所示，項(xiàng)目各任務(wù)的權(quán)重如表4所示，任務(wù)估算工期與資源需求如表5所示。

表3 資源名稱及其相關(guān)數(shù)據(jù)

表4 任務(wù)編號(hào)與其權(quán)重

表5 任務(wù)估算工期與資源需求

設(shè)有一個(gè)新項(xiàng)目在第10～15天、第16～25天、第26～35、第36～45天插入的概率分別為10%、20%、40%、30%，其重要性權(quán)重為1。新插入項(xiàng)目的各任務(wù)的估算工期、資源需求以及任務(wù)權(quán)重如表6所示。

表6 新插入項(xiàng)目各任務(wù)估算工期、資源需求與權(quán)重

設(shè)各任務(wù)（包括新插入項(xiàng)目的任務(wù)）發(fā)生拖期的概率為15%，任務(wù)拖期的天數(shù)為其估算工期的20%～40%。

微粒群種群規(guī)模M＝50，最大迭代次數(shù)Imax＝60，精英集容量大小Selite＝120，學(xué)習(xí)因子c1＝c2＝2，c3＝0.5，慣性權(quán)重ω＝exp（－15×（Ic／Imax）10）（Ic為當(dāng)前迭代次數(shù)）。

采用MATLAB7編寫應(yīng)用程序，在配置為Intel（R）Xeon（R）CPU E5335＠2.00GHz 3GB內(nèi)存的服務(wù)器上進(jìn)行仿真實(shí)驗(yàn)。

4.2 仿真結(jié)果分析

通常情況下，主要是從解的質(zhì)量方面評(píng)價(jià)多目標(biāo)進(jìn)化算法的優(yōu)劣。Zitzler等［22］提出了一系列非劣解的評(píng)價(jià)指標(biāo)，然而這些評(píng)價(jià)指標(biāo)都是在真實(shí)Pareto最優(yōu)解已知的情況下建立的，稱之為理論型評(píng)價(jià)指標(biāo)。但是，實(shí)際問題的真實(shí)Pareto最優(yōu)解集往往并不知道，理論型評(píng)價(jià)指標(biāo)存在一定的局限性。因此，本文用算法實(shí)際求得的非劣解集合（近似Pareto最優(yōu)解集）替代真實(shí)的Pareto最優(yōu)解集，主要采用如下兩種應(yīng)用型評(píng)價(jià)指標(biāo)來進(jìn)行算法優(yōu)劣的比較：

（1）修正距離Dm［23］。該指標(biāo)反映算法所得非劣解逼近近似Pareto最優(yōu)解的程度，定義為

其中，n″為算法求得的非劣解的個(gè)數(shù)，di為第i個(gè)非劣解到近似Pareto最優(yōu)前端的最小距離。Dm越小，則算法所得非劣解越靠近近似Pareto最優(yōu)前端，反之亦然。若Dm＝0，則說明非劣解完全落在近似Pareto最優(yōu)前端。

求得初始調(diào)度計(jì)劃后，對(duì)項(xiàng)目執(zhí)行過程進(jìn)行了100次隨機(jī)仿真（從開始執(zhí)行初始調(diào)度計(jì)劃到各項(xiàng)目全部完成稱為一次仿真）。每次仿真過程中，由于資源故障、任務(wù)拖期或插入新項(xiàng)目的影響，將出現(xiàn)若干次反應(yīng)調(diào)度。分別采用本文提出的IMOPSO算法和文獻(xiàn)［18］、文獻(xiàn)［24］中的算法（種群規(guī)模、最大迭代次數(shù)、學(xué)習(xí)因子、慣性權(quán)重的設(shè)置同IMOPSO）進(jìn)行反應(yīng)調(diào)度，則100次仿真共進(jìn)行反應(yīng)調(diào)度的次數(shù)分別為1659、1684、1662，多次反應(yīng)調(diào)度的Dm平均值平均值如表7所示。

表7 算法性能比較

由表7可知，本文提出的IMOPSO算法性能優(yōu)于文獻(xiàn)［18］和文獻(xiàn)［24］中的算法。另外，由于IMOPSO算法和文獻(xiàn)［24］中的算法均采用了精英歸檔策略，所以兩種算法所得解全部都是非劣解，而文獻(xiàn)［18］算法未采用精英歸檔策略，結(jié)果平均只有74.6%的解為非劣解。

從計(jì)算時(shí)間上看，IMOPSO算法耗時(shí)最長(zhǎng)，文獻(xiàn)［18］算法次之，文獻(xiàn)［24］算法耗時(shí)最短，三者的平均反應(yīng)調(diào)度時(shí)間依次約為261s、108s、52s。這主要是因?yàn)镮MOPSO算法的精英歸檔策略中的聚類算法增加了計(jì)算復(fù)雜度，而文獻(xiàn)［24］中的算法執(zhí)行流程相對(duì)簡(jiǎn)單，所以耗時(shí)最短。

5 結(jié)束語

本文分析了資源不確定、任務(wù)拖期以及隨機(jī)插入新項(xiàng)目等不確定因素對(duì)模具多項(xiàng)目調(diào)度的影響，建立了以調(diào)度計(jì)劃變更產(chǎn)生的附加費(fèi)用最小以及項(xiàng)目加權(quán)工期之和最小為優(yōu)化目標(biāo)的多目標(biāo)反應(yīng)調(diào)度模型，并提出了一種改進(jìn)的多目標(biāo)微粒群算法IMOPSO進(jìn)行模型求解。IMOPSO采用一種最優(yōu)解評(píng)估選取方法，并將孤立點(diǎn)搜索策略與精英歸檔策略相結(jié)合，增加了非劣解的多樣性與均勻性。通過仿真計(jì)算，并分別與文獻(xiàn)［18］和文獻(xiàn)［24］中的算法進(jìn)行對(duì)比和分析，表明IMOPSO具有良好的性能，能夠有效解決模具多項(xiàng)目的動(dòng)態(tài)調(diào)度問題。

本文的研究是在Preempt－repeat模式下，以不能強(qiáng)占資源為前提展開的，取得了初步的研究成果。對(duì)Preempt－resume模式和可強(qiáng)占資源條件下的模具多項(xiàng)目動(dòng)態(tài)調(diào)度的研究將是我們下一步的主要工作。

［1］Herroelen W，Leus R.Project Scheduling under Uncertainty：Survey and Research Potentials［J］.European Journal of Operation Research，2005，65（2）：289－306.

［2］Neumann K.Scheduling of Projects with Stochastic Evolution Structure［M］／／Jozefowska J，Weglarz J.Project Scheduling－Recent Models，Algorithms and Applications.Boston，Mass.，USA：Kluwer Academic Publishers，1999.

［3］Neumann K，Steinhardt U.GERT Networks and the Time－oriented Evaluation of Projects（Lecture Notes in Economics and Mathematical Systems）［M］.New York：Springer－Verlag，1979.

［4］廖仁.模具虛擬企業(yè)項(xiàng)目調(diào)度研究［D］.廣州：廣東工業(yè)大學(xué)，2003.

［5］蘇志龍，陳慶新，陳新，等.CPC環(huán)境下的模具虛擬企業(yè)項(xiàng)目粗規(guī)劃［J］.機(jī)械工程學(xué)報(bào)，2003，39（1）：38－45.

［6］李英杰，陳慶新，陳新度，等.多屬性虛擬企業(yè)部分并行協(xié)商項(xiàng)目規(guī)劃［J］.計(jì)算機(jī)集成制造系統(tǒng)，2005，11（6）：810－817，850.

［7］王延斌，王剛，趙立忠，等.基于蟻群算法的模具制造動(dòng)態(tài)調(diào)度研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2006，12（7）：1028－1036.

［8］張沙清，陳新度，陳慶新，等.不確定環(huán)境下模具制造項(xiàng)目群隨機(jī)調(diào)度研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2009，15（7）：1389－1396.

［9］張沙清，陳新度，陳慶新，等.基于多步Q學(xué)習(xí)的模具制造項(xiàng)目群隨機(jī)調(diào)度算法［J］.中國(guó)機(jī)械工程，2009，20（12）：1439－1445.

［10］程序，吳澄.粒子群優(yōu)化算法求解多模式項(xiàng)目再調(diào)度問題［J］.計(jì)算機(jī)集成制造系統(tǒng)，2009，15（1）：97－101.

［11］Lambrechts O，Demeulemeester E，Herroelen W.Proactive and Reactive Strategies for Resourceconstrained Project Scheduling with Uncertain Resource Availabilities［J］.Journal of Scheduling，2008，2（11）：121－136.

［12］Vonder S，Demeulemeester E，Herroelen W，et al.The Trade－off between Stability and Makespan in Resource－constrained Project Scheduling［J］.International Journal of Production Research，2006，44（2）：215－236.

［13］Veldhuizen D，Lamont G.Multi－objective Evolutionary Algorithms：Analyzing the State－ofthe－art［J］.IEEE Transactions on Evolutionary Computation，2000，18（2）：125－147.

［14］李中凱，譚建榮，馮毅雄，等.基于擁擠距離排序的多目標(biāo)粒子群優(yōu)化算法及其應(yīng)用［J］.計(jì)算機(jī)集成制造系統(tǒng)，2008，14（7）：1329－1336.

［15］Wayne L.運(yùn)籌學(xué)概率模型應(yīng)用范例與解法［M］.李乃文，崔群法，林細(xì)財(cái)，等，譯.4版.北京：清華大學(xué)出版社，2006.

［16］張沙清，陳新度，陳慶新，等.資源不確定環(huán)境下模具多項(xiàng)目預(yù)測(cè)－反應(yīng)式調(diào)度算法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2010，16（12）：2688－2696.

［17］Coello C，Salzzar M.MOPSO：A Proposal for Multiple Objective Particle Swarm Optimization［C］／／IEEE Proceedings of 2002 Congress on Evolutionary Computation.Washington D.C.，USA：IEEE，2002：1051－1056.

［18］張利彪，周春光，馬銘，等.基于粒子群算法求解多目標(biāo)優(yōu)化問題［J］.計(jì)算機(jī)研究與發(fā)展，2004，41（7）：1286－1291.

［19］趙志剛，李陶深，楊林峰.求多目標(biāo)優(yōu)化問題的粒子群優(yōu)化算法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45（29）：37－40.

［20］陳黎飛，姜青山，王聲瑞.基于層次劃分的最佳聚類數(shù)確定方法［J］.軟件學(xué)報(bào)，2008，19（1）：62－72.

［21］Abido M A.Environmental／Economic Power Dispatch Using Multi－objective Evolutionary Algorithms［J］.IEEE Transactions on Power Systems，2003，18（4）：1529－1537.

［22］Zitzler E，Deb K，Thiele L.Comparison of Multiobjective Evolutionary Algorithms：Empirical Results［J］.Evolutionary Computation，2000，8（2）：173－195.

［23］周劉喜，張興華，李緯.一種改進(jìn)的多目標(biāo)粒子群優(yōu)化算法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45（33）：38－41.

［24］王輝，錢鋒.基于擁擠度與變異的動(dòng)態(tài)微粒群多目標(biāo)優(yōu)化算法［J］.控制與決策，2008，23（11）：1238－1242，1248.

Reactive Scheduling for Multiple Mould and Die Projects Based on Improved Multi－objective Particle Swarm Optimization

Zhang Shaqing Chen Xindu Chen Qingxin Chen Xin
Guangdong University of Technology，Guangzhou，510006

This paper proposed a reactive scheduling algorithm for multiple mould and die projects to deal with multiple stochastic disruptions during projects execution including uncertain renewable resources infeasibilities due to breakdowns，multiple tasks taking longer time than planning and random arrivals of new projects.Firstly，uncertain renewable resources availabilities were analyzed with the theory of birthdead process，and an initial schedule was constructed by using topological sorting method based on priority rules.Then，a multi－objective reactive scheduling model with the optimization objects of minimizing the weighted sum duration of projects and the disruptions cost，defined as the weighted sum of the deviations between the executing schedule before reactive scheduling and a new schedule after reactive scheduling was built，and an improved multi－objective particle swarm optimization was proposed to solve it.Finally，the feasibility and reliability of the reactive scheduling algorithm were analyzed by simulations.

task duration enlarging；uncertain resource availability；reactive scheduling；multi－objective particle swarm optimization

TH166

1004—132X（2011）10—1173—07

2010—10—11

國(guó)家高技術(shù)研究發(fā)展計(jì)劃（863計(jì)劃）資助項(xiàng)目（2006AA04Z132）；國(guó) 家 自 然 科 學(xué) 基 金 資 助 項(xiàng) 目 （50675039，50875051）；廣東工業(yè)大學(xué)青年基金資助項(xiàng)目（20062014）

（編輯 袁興玲）

張沙清，男，1973年生。廣東工業(yè)大學(xué)機(jī)電工程學(xué)院博士研究生。主要研究方向?yàn)樯a(chǎn)計(jì)劃與控制、網(wǎng)絡(luò)化制造與信息系統(tǒng)。發(fā)表論文10余篇。陳新度，男，1967年生。廣東工業(yè)大學(xué)機(jī)電工程學(xué)院教授。陳慶新，男，1963年生。廣東工業(yè)大學(xué)機(jī)電工程學(xué)院教授、博士研究生導(dǎo)師。陳 新，男，1960年生。廣東工業(yè)大學(xué)機(jī)電工程學(xué)院教授、博士研究生導(dǎo)師。