發(fā)布時(shí)間：2020-04-17 10:49

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

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

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

【參考文獻(xiàn)】

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

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

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

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

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

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

本文編號(hào)：2630781