熱門關鍵詞:
位置:首頁 > 機械學術資料 > 機械工廠、車間
基于蟻群算法的資源受限多項目調度問題研究
  • 該文件為pdf格式
  • 文件大小:0.25M
  • 下載次數
  • 文件評級
  • 更新時間:2015-01-29
  • 發 布 人忘川秋水
  • 文件介紹:
  • 該文件為 pdf 格式,下載需要 1 積分
  • 工程百科資料庫,工百科。歡迎訪問 GongBaike.com

    中圖法分類號 :TH186 doi:10.3963/j.issn.2095-3844.2013.01.043目前對資源受限的項 目調度問題(resource-constrained proj ect scheduling problem,RCPSP)的研究主要集中于單項 目的研究上,對于資源受限 的 多 項 目調 度 問 題 (resource-constrainedmulti-project scheduling problem,RCMPSP)通常的處理方式有單項 目方式和多項 目方式 2種[1].前者是通過人為加入開始”和結束”的虛擬活動將多個項 目綜合轉變為單個項 目求解,而后者則把項目看成獨立的.由于單項目方式忽略了資源在多個項目間的分配與在單個項目內部各活動間的分配的區別,因此存在理論缺陷 ]。

    對于多項目方式的研究,研究者從不同的角度,應用不同的技術對該問題進行研究.文獻[3-6]運用遺傳算法進行網絡資源調度,能有效的改進項 目調度方案,但是其搜索效率具有-定的隨機性,且在作業數量較大時,會使算法的搜索空間急劇擴大,造成遺傳算法的性能下降 ].文獻[8]提出-種排序方案,但是該研究沒有提及如何處理作業之間的時序邏輯關系.文獻E9]提出運用粒子群算法的方案,但是當項 目任務多時,該算法對于離散的優化可能導致較大的誤差,容易陷入局部最優.文獻[103提出針對 RCMPSP的最大-最小蟻群優化算法,并結合禁忌表能夠很好的防止收稿日期:2012-09-29高 金(1986-):男,碩士生,主要研究領域為通信與信息系統蟻群算法的停滯現象。

    本文基于實際工作背景,分析 RCMPSP的特點,結合文獻[11]的案例建立以各項 目完成時間最短為目標的數學模型.由于文獻[11]用到的是遺傳算法的思想,因此存在遺傳算法的各種弊端。

    因此本文根據資源上作業間的時序關系和項 目內部任務的緊前關系組成的項目網絡圖,提出運用蟻群算法和串行調度生產機制[ 相結合的方法對該問題求解,并運用禁忌搜索來提高算法的局部搜索能力.為使算法具有實用性,給出算法的基本步驟。

    結合實例對算法進行測試,通過實例表明,算法能有效的解決資源約束下的多項目調度問題。

    1 問題描述據典型的RCMPSP的描述,本文研究的 RC-MPSP共包含 N 個獨立的子項 目.各子項 目之間沒有必然的聯系,但可能需要占用同-種資源。

    每個子項目包含 個任務;其任務按照 1到J進行編碼,其中第 1和第 .,個任務為子項 目的虛擬起始任務和最終任務,均不占資源和時間;用A,表示第 i個子項目的第J( 1,2,,J)個任務,其工期為 d 任務的開始時間記為 ST 完成· 184 · 武漢理工大學學報(交通科學與工程版) 2O13年 第 37卷時間記為 F丁 且所有任務-旦開始就不可中斷.子項 目的各任務之間存在緊前關系,即各任務只有在其所有緊前任務都結束之后才能開始;任務A,的緊前任務集合記為P 所有項 目共享 K種可更新資源,其中第 k種資源的供應量為R ;任務A 對第k種資源的需求量為r 。

    則 RCMPSP可以表示為如下數學模型min maxF州 (1)S.t.ST ≥ FT ,V h∈ P V i, (2)>:r ≤R ,V k,t (3)A-l E fST ≥ 0,V i,J (4)式中:F 為第i個項目的最終完成時間,由于所有項 目均從時間 0開始 ,則 maxF ,)為整個項目組的總工期.式(1)即為 RCMPSP的目標函數 ,最小 的項 目工期;式 (2)表示項 目內部各任務之 間的緊前關系;式(3)表示在任意時刻所有當前任務對資源的總需求不得超過該資源的供應量。

    2 基于 RCMPSP的蟻群算法2.1 混合蟻群算法的設計由于無資源約束下每個項目活動都有各自的最早開始時間ST 和工期d 則根據串行調度生N 成機制,能夠得到 >:J 個階段,每個階段都有-個可行集 D ,在局部可行集中運用蟻群算法的思想,從而實現對 RCMPSP的求解.下面對算法的具體求解過程進行說明。

    步驟 1 初始化數據,包括初始化螞蟻的信息素矩陣、算法的啟發式矩陣。

    步驟 5 螞蟻根據轉移規則從可行任務集D 中選擇下-結點,即任務.將選擇任務加入禁忌表中,并更新可行任務集 D 和資源擁有量R .其中轉移規則,采用輪盤賭選擇規則;可行任務集 DA表示在.,階段 k資源上可行的任務集合,根據項目活動的計劃開始時間和完成時間以及任務A ,占用的資源數r 決定。

    步驟6 判斷可行任務集 D々A是否為空.若非空,則轉至步驟 5;否則執行步驟 7。

    步驟 8 如果螞蟻走完所有項目的所有任務,記錄螞蟻的路徑,執行步驟 9;否則返回步驟4。

    步驟 9 如果 M 只螞蟻都走完所有項目的所有任務,執行步驟 10;否則返回到步驟 3。

    步驟 10 將 M 只螞蟻的M 條路徑的信息素進行揮發,對這 M 條路徑中完成時間最短 的路徑進行信息素增強.且保證所有的信息素濃度在范圍[ ,Z'max]中。

    步驟 11 判斷迭代是不是滿足終止條件,若滿足,則迭代結束;否則返回至步驟 2。

    2.2 狀態轉移規則由算法流程可知螞蟻都從起始點開始直到他們走完所有的節點,即螞蟻走完所有項目的所有任務.由于在某-時間內可能存在多個項 目任務同時占用某-資源 ,但資源不能 同時滿足所有項目任務的需求時,如何選擇優先執行是算法的關鍵.由蟻群算法的思想可知螞蟻會根據隨機選擇規則進行選擇.計算公式為pJ - 如 A∈D; (5)rA。批A∈D;式中: l,A為階段J選擇活動A的概率;r/, 為階段J活動A 的啟發信息由式(6)計算;r, 為階段 J活動A 的信息素濃度,由信息素更新機制得到;Du為螞蟻在資源k上階段 .,的可行集 ,由串行調度生成機制得到。

    1- ㈣ A ED.stA式中:st 為活動 A 的開始時 問;D,為階段 ,的可行集。

    2.3 信息素更新規則當所有螞蟻都遍歷完所有 的項 目任務,所有的項 目任務的信息素將發生更新.根據實際的螞蟻可知,信息素的更新方式主要包括信息素揮發和信息素加強.首先當螞蟻遍歷所有項目任務時,信息素會按照-定的比例進行信息素揮發,揮發量由下式給出rJA- (1- p)rJA (7)式中:J0為揮發強度,0%p%1。

    在迭代中,為了突出螞蟻的最佳路徑在下次迭代中被選擇概率,只對最佳路徑上的信息素濃度進行加強,即最佳的項 目調度的信息素得到加強.加強方式如下第 1期 高 金,等:基于蟻群算法的資源受限多項目調度問題研究 ·185 ·FJA - rJa △ (8)式中:酶 為迭代中最佳的項目調度增加的信息素。

    n △ - (9)L,式中:Q為螞蟻的信息素總量,為-常數; 為最佳路徑的距離,這里表示項目調度中,最短的完成時間。

    然而,由于在-次迭代中可能存在所有的螞蟻都選擇同-種調度方案,從而導致這個調度方案的信息素增加太快,以致發生停滯現象,影響最優解的求得.為了避免這種現象的發生,本文采用最大最小蟻群算法,將信息素濃度控制在[ 。 ,rm ]中。

    2.4 可行任務集 D.,由算法流程圖可知,可行任務集 D 是算法的重要參數,它的擴展包含了整個項 目調度的所有的解空間,如何求可行任務集 D 是算法的重點.根據Keley的串行調度生成機制,對于包含NN個項 目的RCMPSP來說,-共包含 ., 個任務,- 1因此對于 RCMPSP的串行調度生成機制,需要N :J 個階段.在每-階段中,首先要確定可行集i 1D ,根據-定的優先規則從 p,中選取任務,并在滿足式(2)、(3)的條件下進行調度.通過局部擴展,逐步更新可行集,從而得到整個項目的進度安排。

    由于每個項 目都有各 自的計劃開始時間,于是將各項目任務按計劃開始時間分配到對應資源k上,如圖 1所示 3個項 目活動在資源 k上的計劃進度安排.由圖可知項目 1和項 目2最早開始發生資源沖突,則在此沖突持續時間段內的所有項 目任務即為此階段的可行任務集 D 。

    1.1項目l:項目2:項目3:I e圖 1 資源沖突3 實例仿真與分析實例模型采用文獻El1]的模具生產項目,即3個具有相同結構的并行執行項 目,網絡結構見圖 2.每個項 目有 16個任務,-共 48個任務,占用 9種資源,且每個項目任務只占用-種資源,不同的項 目任務的執行時間不同.項 目任務在無資源約束下的計劃開始時間、工期和占用資源數量見表 1。

    圖 2 項 目網絡 圖表 1 項 目活動無資源約束下 的開始 時間和工期及 占用資源數量任務 資源 項目1 項目2 項 目3號 種類 Rd ST DT Rd ST DT Rd ST DT注:Rd為占用資源數量;ST為無資源約束下的計劃開始時間,d;DT為項 目任務的工期,d。

    根據設計的蟻群算法 的思想,在迭代次數NC100,揮發系數 P-0.1,偏重因子 口-0.3,口-8的設置下可以得到-個可行的調度計劃,見表 2.由表 2可知,項 目組的總的完成時間為 61d,比文獻[11]少 1 d,說明此算法的設計在資源受限的多項 目調度方面存在-定的優勢,能夠提高企業的項 目調度效率。

    4 結 束 語針對資源受限的多項 目調度問題的特征,運用串行進度生產機制和蟻群算法的基本思想,設計出-種混合的蟻群算法.為了避免蟻群算法的停滯現象,該算法采用最大最小蟻群算法中對信息素的濃度進行限制的方法,從而有效的提高算4 6 1 4 3 6 3 2 1 2 3 3 4 4 5 3 O 4 0 O O O 6 9 6 9 9 1 4 6 9 3 1 1 1 1 l 1 1 1 1 2 2 2 2 3 6 8 9 7 5 4 8 9 8 7 9 6 5 6 6 8 5 6 2 3 2 6 6 3 1 2 3 4 2 4 3 3 O 5 l 1 1 1 7 3 7 3 3 6 O 2 6 9 1 1 1 1 1 2 1 2 2 2 3 3 3 3 4 6 7 7 6 6 7 5 6 5 7 3 7 3 7 6 4 3 2 4 3 5 4 2 1 2 4 3 3 2 3 4 O 4 7 7 7 7 2 6 2 6 6 8 1 4 6 9 1 1 1 1 1 1 2 2 2 2 8 5 6 6 3 8 7 6 5 4 5 8 9 5 8 3 1 1 4 1 3 2 1 2 7 6 7 5 6 7 8 9 1 2 3 4 5 6 7 8 9 O 1 2 3 4 5 6 l · l86 · 武漢理工大學學報(交通科學與工程版) 2013年 第 37卷表 2 資源約束下的調 度計 劃 d法較優解的選取.通過實例的演算與分析發現此算法能夠較好的解決 RCMPSP問題。

    ...
    工程百科資料庫,工百科。歡迎訪問 GongBaike.com
發表評論
驗證碼 驗證碼加載失敗
Playboy黄金电子游艺
趣操盘 30选5基本走势图2元网 1分11选5走势图 258足彩竞彩比分直播 体彩排列三最大遗漏 欢乐麻将辅助2018 qq麻将16番胡牌技巧 钱掌柜配资 黑龙江11选5 湖北十一选五 下载山东11选5 竞彩比分直播新浪旧版 188比分直播吧 陕西省十一选五开奖 湖南麻将游戏大全 竞彩足球比分旧版下载