柔性資源普遍存在于制造業(yè)生產(chǎn)制造的各個環(huán)節(jié)中,提高了資源利用率和生產(chǎn)效益。以柔性資源為研究對象,建立了以最小化項目完成工期為目標的柔性資源受限項目調(diào)度問題的數(shù)學(xué)模型。針對現(xiàn)有標準遺傳算法過早地收斂從而使整個遺傳搜索無法求解出全局最優(yōu)值的缺陷,提出了一種改進的多種群遺傳算法來求解該問題模型。算法對作業(yè)優(yōu)先級列表編碼,引入交叉移民算子實現(xiàn)多種群間的協(xié)同進化,在解碼過程中運用一種啟發(fā)式柔性資源技能分配算法為作業(yè)分配資源,同時通過改進的串行調(diào)度生成方案對作業(yè)調(diào)度。最后通過標準算例庫PSPLIB進行數(shù)值試驗,驗證了所提算法求解該問題的有效性。 

【文章來源】：計算機科學(xué). 2020,47(S1)北大核心

【文章頁數(shù)】：6 頁

【部分圖文】：

汽車移動裝配生產(chǎn)線簡圖

針對MSRCPSP問題,本文設(shè)計了一種以作業(yè)優(yōu)先級列表為編碼方式的改進多種群遺傳算法來求解該問題模型。傳統(tǒng)多種群遺傳算法中的移民操作可能會因為外來優(yōu)秀個體成為種群主導(dǎo)個體從而使得種群多樣性迅速降低,導(dǎo)致無法跳出局部最優(yōu)。因此,本文對傳統(tǒng)的移民操作進行改進,對移民算子進行交叉處理,得到交叉移民算子,再通過精英策略選擇較優(yōu)的個體替換目標種群中的最差個體,從而達到每次交流都使得目標種群引入外來優(yōu)秀個體的部分基因,又保留自身種群個體的部分基因,避免外來優(yōu)秀個體迅速成為主導(dǎo)個體的情況發(fā)生,保證了種群的多樣性。在解碼過程中,針對柔性資源技能分配問題,為避免資源分配時選擇的隨機性,本文提出一種啟發(fā)式柔性資源技能分配算法,并通過作業(yè)—技能—資源映射關(guān)系模型為作業(yè)分配相應(yīng)的資源。同時調(diào)用改進的串行調(diào)度生成機制對作業(yè)進行調(diào)度,通過判斷局部兩作業(yè)位置關(guān)系,根據(jù)不同的情況對作業(yè)進行調(diào)度,最終得到各個作業(yè)的執(zhí)行時間,使得項目完成工期最短。算法流程圖如圖2所示。3.1 改進多種群遺傳算法

本文采用實數(shù)編碼方式對作業(yè)優(yōu)先級列表編碼,則編碼的長度等于作業(yè)的個數(shù)n+1,編碼的位置代表了作業(yè)的優(yōu)先級pj,j∈V,pj越小,優(yōu)先級越高;該位置上的數(shù)字代表了作業(yè)編號。如圖3所示,作業(yè)2的優(yōu)先級p2=1,優(yōu)先級最高;作業(yè)7的優(yōu)先級最低,p7=7;作業(yè)3的優(yōu)先級p3=5等。3.1.2 選擇

【參考文獻】：
期刊論文
[1]多技能資源時間窗約束下可中斷項目調(diào)度的分支定界算法[J]. 劉振元,袁慧濤,周成,畢陽,胡淑芳.  系統(tǒng)工程理論與實踐. 2019(01)
[2]基于多種群遺傳算法的自動化立體庫貨位優(yōu)化[J]. 焦玉玲,張鵬,田廣東,邢小翠,鄒連慧.  吉林大學(xué)學(xué)報(工學(xué)版). 2018(05)
[3]考慮技能水平的多技能資源約束項目調(diào)度[J]. 任逸飛,陸志強,劉欣儀,張猛.  浙江大學(xué)學(xué)報(工學(xué)版). 2017(05)
[4]柔性資源約束下的項目調(diào)度問題雙目標優(yōu)化[J]. 謝芳,徐哲,于靜.  系統(tǒng)工程理論與實踐. 2016(03)
[5]基于交叉親和度評價的多種群遺傳算法[J]. 王東,歸偉夏.  廣西大學(xué)學(xué)報(自然科學(xué)版). 2015(06)
[6]柔性資源約束項目調(diào)度問題的啟發(fā)式求解方法[J]. 賈艷,王致民,張躍剛.  計算機集成制造系統(tǒng). 2015(07)
[7]多技能資源約束項目調(diào)度問題的改進算法[J]. 張猛,陸志強.  計算機集成制造系統(tǒng). 2016(03)
[8]多目標模糊柔性車間調(diào)度中的多種群遺傳算法[J]. 劉愛軍,楊育,邢青松,陸惠,張煜東.  計算機集成制造系統(tǒng). 2011(09)



本文編號：2997895