【摘要】：帶有資源故障的資源受限多項目調(diào)度問題是經(jīng)典資源受限多項目調(diào)度問題(RCMPSP)的擴展問題,并且在實踐中普遍存在。由于這類問題通常比較復(fù)雜而且模型多樣,所以很難建立統(tǒng)一的問題模型去求解,目前相關(guān)研究較少。本文以某一實際生產(chǎn)場景為背景,建立問題模型并研究求解算法,主要研究內(nèi)容如下:首先,建立了一個帶有計劃型故障的資源受限多項目調(diào)度問題模型(RCMPSP-PRU),問題目標是最小化項目的最大完工時間。RCMPSP-PRU在經(jīng)典RCMPSP的基礎(chǔ)上,增加了一些新概念,如工位、可移動資源、不可移動資源、計劃型故障等,并綜合考慮了多種復(fù)雜約束關(guān)系。其次,對串行進度生成機制做了改進,并根據(jù)問題特征設(shè)計了調(diào)度優(yōu)先級規(guī)則,進而提出了基于優(yōu)先級規(guī)則的改進串行進度生成算法ISSPR。實驗結(jié)果表明,ISSPR可以快速給出合理可行的調(diào)度計劃。然后,針對ISSPR算法中影響調(diào)度計劃的工件換位順序和計劃型故障兩個重要因素,分別提出了兩個單因素優(yōu)化算法:工件換位順序的遺傳算法GAJTO和計劃型故障的禁忌搜索算法TSPRU。實驗結(jié)果表明,算法GAJTO和TSPRU對ISSPR解的質(zhì)量均有明顯的優(yōu)化效果。但算法GAJTO存在收斂速度慢,耗時長的問題。最后,為解決算法GAJTO耗時長的問題,提出了針對工件換位順序的遺傳-粒子群混合優(yōu)化算法JTO-PSOGA。實驗結(jié)果表明,JTO-PSOGA可以在保證GAJTO優(yōu)化效果的同時明顯提升求解效率。然后,在單因素優(yōu)化算法JTO-PSOGA和TSPRU的基礎(chǔ)上,提出了基于遺傳-粒子群和禁忌搜索的優(yōu)化算法JP-PSOGATS。在JP-PSOGATS中,遺傳-粒子群混合算法用來優(yōu)化工件換位順序,禁忌搜索算法用來解決計劃型故障。實驗結(jié)果表明,JP-PSOGATS可取得較本文其他優(yōu)化算法更好的優(yōu)化效果,但同時需要更多的求解時間。結(jié)合本文的問題特征,并權(quán)衡求解質(zhì)量與求解效率的關(guān)系后,認為較本文其他優(yōu)化算法而言,JP-PSOGATS的優(yōu)化效果最理想。
【圖文】：

開始－結(jié)束型（ｓｔａｒｔ－ｆｉｎｉｓｈ）邐ＳＦ邐工序Ｂ在工序Ａ開始之前不可以結(jié)束逡逑圖１－２工序ＡＯＮ網(wǎng)絡(luò)示意圖逡逑Ｆｉｇｕｒｅ邋１－２邋Ｔｈｅ邋ＡＯＮ邋ｏｆ邋ｔｈｅ邋ｏｐｅｒａｔｉｏｎｓ：邋ａｎ邋ｅｘａｍｐｌｅ逡逑１．１．２經(jīng)典ＲＣＭＰＳＰ模型簡介逡逑ＲＣＭＰＳＰ是指在一個總項目中包含多個并行的子項目和一個資源庫。在每個逡逑子項目中，存在多個任務(wù)需要完成。完成這些任務(wù)需要一定的資源和時間，，各項逡逑目之間除共享同一個資源庫外，其他均獨立。資源之間以及各任務(wù)之間均存在約逡逑束關(guān)系。ＲＣＭＰＳＰ的最終目的就是在滿足資源及其他一系列約束條件的情況下，逡逑４逡逑

Ｂ—ｙ逡逑圖１－１工序之間關(guān)系不意圖逡逑Ｆｉｇｕｒｅ邋１－１邋Ｔｈｅ邋ｒｅｌａｔｉｏｎｓｈｉｐ邋ｂｅｔｗｅｅｎ邋ｏｐｅｒａｔｉｏｎｓ逡逑表１－１工序之間約束關(guān)系類型及含義逡逑Ｔａｂｅｌ邋１－１邋Ｔｈｅ邋ｒｅｌａｔｉｏｎｓｈｉｐ邋ｂｅｔｗｅｅｎ邋ｏｐｅｒａｔｉｏｎｓ邋ａｎｄ邋ｔｈｅ邋ｃｏｒｒｅｓｐｏｎｄｉｎｇ邋ｍｅａｎｉｎｇ逡逑約束關(guān)系類型邐邐逡逑結(jié)束－開始型（ｆｉｎｉｓｈ＿ｓｔａｒｔ）邐ＦＳ邐工序Ｂ必須在工序Ａ結(jié)束后才可開始逡逑結(jié)束－結(jié)束型（ｆｉｎｉｓｈ－ｆｉｎｉｓｈ）邐ＦＦ邐工序Ｂ必須在工序Ａ結(jié)束后才可結(jié)束逡逑開始＿開始型（ｓｔａｒｔ－ｓｔａｒｔ）邐ＳＳ邐工序Ａ在開始之前工序Ｂ不可以開始逡逑開始－結(jié)束型（ｓｔａｒｔ－ｆｉｎｉｓｈ）邐ＳＦ邐工序Ｂ在工序Ａ開始之前不可以結(jié)束逡逑圖１－２工序ＡＯＮ網(wǎng)絡(luò)示意圖逡逑Ｆｉｇｕｒｅ邋１－２邋Ｔｈｅ邋ＡＯＮ邋ｏｆ邋ｔｈｅ邋ｏｐｅｒａｔｉｏｎｓ：邋ａｎ邋ｅｘａｍｐｌｅ逡逑１．１．２經(jīng)典ＲＣＭＰＳＰ模型簡介逡逑ＲＣＭＰＳＰ是指在一個總項目中包含多個并行的子項目和一個資源庫。在每個逡逑子項目中，存在多個任務(wù)需要完成。完成這些任務(wù)需要一定的資源和時間，各項逡逑目之間除共享同一個資源庫外，其他均獨立。資源之間以及各任務(wù)之間均存在約逡逑束關(guān)系。ＲＣＭＰＳＰ的最終目的就是在滿足資源及其他一系列約束條件的情況下，逡逑４逡逑
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2019
【分類號】：TP18

【參考文獻】

相關(guān)期刊論文 前5條

1 王軍強;張松飛;陳劍;張映鋒;孫樹棟;;一種求解資源受限多項目調(diào)度問題的分解算法[J];計算機集成制造系統(tǒng);2013年01期

2 田文迪;崔南方;;關(guān)鍵鏈項目管理中關(guān)鍵鏈和非關(guān)鍵鏈的識別[J];工業(yè)工程與管理;2009年02期

3 丁海利;王芳;高成修;;旅行商問題的交叉粒子群優(yōu)化算法[J];數(shù)學(xué)雜志;2008年01期

4 王超學(xué);崔杜武;王竹榮;費蓉;;一種求解TSP的高效遺傳算法[J];西安理工大學(xué)學(xué)報;2006年01期

5 吉根林;遺傳算法研究綜述[J];計算機應(yīng)用與軟件;2004年02期

本文編號：2630781