張沙清 陳新度 陳慶新 陳 新

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

基于改進多目標微粒群算法的模具多項目反應調(diào)度

張沙清 陳新度 陳慶新 陳 新

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

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

任務拖期；資源不確定；反應調(diào)度；多目標微粒群算法

0 引言

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

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

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

1 問題描述

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

圖1 模具項目網(wǎng)絡拓撲結(jié)構(gòu)圖

表1 任務資源需求表

圖2 三個模具項目的網(wǎng)絡拓撲結(jié)構(gòu)圖

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

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

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

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

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

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

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

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

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

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

2.2 基于拓撲排序的初始調(diào)度計劃構(gòu)建

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

3 基于改進多目標微粒群算法的反應調(diào)度

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

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

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

3.2 改進的多目標微粒群算法

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

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

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

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

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

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

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

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

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

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

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

3.3 精英集更新算法

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

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

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

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

4 仿真實驗

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

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

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

表4 任務編號與其權(quán)重

表5 任務估算工期與資源需求

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

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

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

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

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

4.2 仿真結(jié)果分析

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

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

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

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

表7 算法性能比較

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

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

5 結(jié)束語

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

本文的研究是在Preempt－repeat模式下，以不能強占資源為前提展開的，取得了初步的研究成果。對Preempt－resume模式和可強占資源條件下的模具多項目動態(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è)項目調(diào)度研究［D］.廣州：廣東工業(yè)大學，2003.

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

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

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

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

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

［10］程序，吳澄.粒子群優(yōu)化算法求解多模式項目再調(diào)度問題［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］李中凱，譚建榮，馮毅雄，等.基于擁擠距離排序的多目標粒子群優(yōu)化算法及其應用［J］.計算機集成制造系統(tǒng)，2008，14（7）：1329－1336.

［15］Wayne L.運籌學概率模型應用范例與解法［M］.李乃文，崔群法，林細財，等，譯.4版.北京：清華大學出版社，2006.

［16］張沙清，陳新度，陳慶新，等.資源不確定環(huán)境下模具多項目預測－反應式調(diào)度算法［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］張利彪，周春光，馬銘，等.基于粒子群算法求解多目標優(yōu)化問題［J］.計算機研究與發(fā)展，2004，41（7）：1286－1291.

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

［20］陳黎飛，姜青山，王聲瑞.基于層次劃分的最佳聚類數(shù)確定方法［J］.軟件學報，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］周劉喜，張興華，李緯.一種改進的多目標粒子群優(yōu)化算法［J］.計算機工程與應用，2009，45（33）：38－41.

［24］王輝，錢鋒.基于擁擠度與變異的動態(tài)微粒群多目標優(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

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

（編輯 袁興玲）

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