多模式資源受限項(xiàng)目調(diào)度問題

1、外文翻譯：譯文字?jǐn)?shù)5515一般情況下，英文:中文字?jǐn)?shù)=1:1.5，英文字?jǐn)?shù):英文字符數(shù)=1:5.5出處（超鏈接直達(dá)原文哦，徹底杜絕沒有pdf原文的煩惱?。〩ybrid Optimization Method for Large-Scale Multimode Resource-Constrained Project Scheduling ProblemR Sonmez, M Gurel - Journal of Management in Engineering, 2016 - 大規(guī)模多模式資源受限項(xiàng)目調(diào)度問題的混合優(yōu)化方法Rifat Sonmez and Mus

2、tafa Gurel摘要：盡管針對(duì)多模式資源受限項(xiàng)目調(diào)度問題（MRCPSP）進(jìn)行了許多研究 工作，但是在解決大型項(xiàng)目的問題上取得的成績(jī)卻很小。在本文中，提出了一種 新的混合優(yōu)化方法，以實(shí)現(xiàn)具有多個(gè)持續(xù)時(shí)間/資源執(zhí)行模式和資源受限的大規(guī) 模建設(shè)項(xiàng)目的最優(yōu)規(guī)劃和調(diào)度的進(jìn)步。提出的方法由一種新穎的啟發(fā)式和獨(dú)特的 遺傳優(yōu)化算法組成。啟發(fā)式設(shè)計(jì)旨在通過動(dòng)態(tài)選擇模式來實(shí)現(xiàn)具有高效資源利用 率的時(shí)間表。將遺傳優(yōu)化算法整合到所提出的優(yōu)化方法中，以進(jìn)一步提高在啟發(fā) 式階段獲得的解決方案的質(zhì)量。計(jì)算實(shí)驗(yàn)結(jié)果表明，新的混合方法優(yōu)于現(xiàn)有技術(shù) 方法，實(shí)現(xiàn)了高質(zhì)量的解決方案，顯著減少了計(jì)算時(shí)間，特別是對(duì)于大型項(xiàng)目。 提出

3、的混合優(yōu)化方法的主要貢獻(xiàn)是通過對(duì)具有多個(gè)持續(xù)時(shí)間/資源執(zhí)行模式和資 源限制的中大規(guī)模建設(shè)項(xiàng)目進(jìn)行最優(yōu)規(guī)劃和調(diào)度，實(shí)現(xiàn)了顯著節(jié)省。關(guān)鍵詞：項(xiàng)目管理，資源管理，施工規(guī)劃，調(diào)度，費(fèi)用，優(yōu)化引言在許多建筑項(xiàng)目中，某些資源的可用性有限。然而，建設(shè)項(xiàng)目調(diào)度中常用的 關(guān)鍵路徑法（CPM）僅考慮優(yōu)先受限條件。因此，在不考慮資源限制的情況下， 由CPM決定的項(xiàng)目持續(xù)時(shí)間通常是不切實(shí)際的（Hegazy et al，2000）。資源受 限項(xiàng)目調(diào)度問題（RCPSP）考慮資源限制以及優(yōu)先受限。一般RCPSP的目標(biāo)是 確定每個(gè)活動(dòng)的開始日期，以滿足優(yōu)先權(quán)和資源受限的方式，并將項(xiàng)目持續(xù)時(shí)間 最小化。盡管資源受限調(diào)度在施工管

4、理中的重要性，但Primavera Project Planner 和Microsoft Project等流行項(xiàng)目調(diào)度軟件在解決RCPSP方面的能力非常有限(Lu 和 Lam 2008; Lu et al，2008; Hegazy and Menesi 2012; Bettemir and Sonmez 2014; Siu et al，2015，2016; Tran et，2015 年)。多模式資源受限項(xiàng)目調(diào)度問題(MRCPSP)是RCPSP的一般化版本，可實(shí) 現(xiàn)多個(gè)具有不同持續(xù)時(shí)間和資源需求的執(zhí)行模式。MRCPSP的目標(biāo)是確定每個(gè) 活動(dòng)的模式和開始日期，使項(xiàng)目持續(xù)時(shí)間最小化，同時(shí)考慮優(yōu)先級(jí)關(guān)

5、系和資源限 制。由于MRCPSP在強(qiáng)大的情況下是非確定性多項(xiàng)式時(shí)間硬(NP hard)，所以 問題的最優(yōu)解只能通過精確的方法來實(shí)現(xiàn)，包括很少的活動(dòng)。因此，許多研究都 集中在開發(fā)用于解決MRCPSP的啟發(fā)式和元啟發(fā)式方法。在早期嘗試解決MRCPSP的過程中，Boctor (1993)評(píng)估了基于21個(gè)優(yōu)先 級(jí)的資源受限調(diào)度啟發(fā)式的性能。為了改進(jìn)基于優(yōu)先級(jí)的啟發(fā)式，Boctor(1996) 開發(fā)了一種啟發(fā)式，它列舉了優(yōu)先級(jí)和資源可行的活動(dòng)組合，并根據(jù)評(píng)估標(biāo)準(zhǔn)選 擇組合。Kolisch和Drexl (1997)提出了一種本地搜索方法，首先找到一個(gè)可行 的解，然后執(zhí)行單個(gè)鄰域搜索來提高解決方案的質(zhì)量。L

6、ova等人(2006)使用 Boctor (1996)生成的問題集分析了 MRCPSP的基于優(yōu)先級(jí)的啟發(fā)式和不同調(diào) 度生成方案的結(jié)果。提出了幾種解決MRCPSP的元啟發(fā)式策略。遺傳算法(GA) (Mori and Tseng 1997; Hartmann2001; Alcaraz 等人 2003; Lova 等人 2009 年;Elloumi 和 Fortemps 2010; Van Peteghem和 Vanhoucke 2010)，粒子群優(yōu)化(PSO) (Zhang et al， 2006)，散射搜索(Ranjbar et al， 2009)，差異演化(Damak 等人 2009)，人造免

7、疫系統(tǒng)(Van Peteghem 和 Vanhoucke 2009)，蟻群優(yōu)化(ACO) (Zhang 2012; Li and Zhang 2013)，洗牌蛙跳算法(Wang and Fang 2011)以及分 布算法的估計(jì)(Wang and Fang 2012)是為MRCPSP提出的元啟發(fā)式方法之一。 很少有研究側(cè)重于具有多個(gè)持續(xù)時(shí)間/資源執(zhí)行模式和資源限制的項(xiàng)目的成本最 小化。Leu 和 Yang (1999)，Chen 和 Weng (2009)和 Ghoddousi 等(2013)采 用基于GA的方法，對(duì)具有多個(gè)持續(xù)時(shí)間/資源執(zhí)行模式和資源限制的建設(shè)項(xiàng)目 進(jìn)行成本最小化。在最近的研究

8、中，Van Peteghem和Vanhoucke (2014)對(duì)不同的元啟發(fā)式解 決方案進(jìn)行了比較，并對(duì)MRCPSP的文獻(xiàn)進(jìn)行了詳細(xì)的回顧。在最近的其他研 究中，Menesi和Hegazy（2014）介紹了 MRCPSP的受限規(guī)劃（CP）方法，也 可以執(zhí)行資源調(diào)配。Cheng和Tran（2015）提出了一種基于混合差分進(jìn)化的方法 來解決MRCPSP。最近的一些研究提出了基于模糊集的MRCPSP方法。Vartouni 和Khanli（2014）提出了一個(gè)考慮MRCPSP模糊活動(dòng)持續(xù)時(shí)間的GA。Gan和 Xu（ 2013）提出了一種混合不確定的多目標(biāo)二維編程模型和一種用于控制 MRCPSP調(diào)度風(fēng)險(xiǎn)

9、的多重差分更新粒子群優(yōu)化方法。對(duì)MRCPSP提出的大多數(shù)啟發(fā)式和元啟發(fā)式方法進(jìn)行了評(píng)估，包括10到 100個(gè)活動(dòng)之間的問題。因此，現(xiàn)有方法中很少有現(xiàn)實(shí)生活中的問題，包括300 多個(gè)活動(dòng)（Liberatore et al，2001）。專注于可以處理大規(guī)模MRCPSP的方法的研 究將使具有多個(gè)持續(xù)時(shí)間/資源執(zhí)行模式和資源受限的現(xiàn)實(shí)生活建設(shè)項(xiàng)目能夠進(jìn) 行最佳規(guī)劃和調(diào)度。在這種情況下，本研究的主要目標(biāo)是通過設(shè)計(jì)和開發(fā)一種新 的混合方法（HM），在合理的計(jì)算時(shí)間內(nèi)實(shí)現(xiàn)高質(zhì)量的解決方案，特別是大規(guī) 模MRCPSP。本文的其余部分組織如下。下一節(jié)將介紹所提出的混合方法。在 下面的部分中給出了計(jì)算實(shí)驗(yàn)。最后，

10、作了總結(jié)?；旌蟽?yōu)化方法新的混合優(yōu)化方法由兩部分組成。在第一部分中，使用一種新穎的啟發(fā)式來 實(shí)現(xiàn)優(yōu)先級(jí)和資源可行的具有高效資源利用率的時(shí)間表。然后在啟發(fā)階段獲得的 時(shí)間表在第二階段通過遺傳優(yōu)化得到改善。為MRCPSP提出的大多數(shù)現(xiàn)有方法 都是基于先驗(yàn)優(yōu)先級(jí)規(guī)則為每個(gè)活動(dòng)選擇一個(gè)執(zhí)行模式。所提出的啟發(fā)式執(zhí)行模式的動(dòng)態(tài)選擇，以啟用具有高效資源利用率的時(shí)間表。 在提出的混合方法的第二部分中，實(shí)現(xiàn)遺傳優(yōu)化，以進(jìn)一步改進(jìn)在啟發(fā)式階段獲 得的高質(zhì)量解決方案。HM被設(shè)計(jì)為實(shí)現(xiàn)向后向前資源受限調(diào)度，以實(shí)現(xiàn)更短的 項(xiàng)目持續(xù)時(shí)間的活動(dòng)開始時(shí)間。李和威利斯（1992）提出了后向調(diào)度方法。后向 前向調(diào)度方法的主要目標(biāo)是

11、通過壓縮資源受限時(shí)間表的活動(dòng)開始時(shí)間來減少項(xiàng) 目持續(xù)時(shí)間。Lova等人（2009）使用后向調(diào)度方法作為GA的局部搜索技術(shù)， 并表明后向調(diào)度改進(jìn)了 MRCPSP的解決方案。在最近的研究中，后向前向調(diào)度 集成優(yōu)化方法優(yōu)于現(xiàn)有技術(shù)方法資源受限多項(xiàng)目調(diào)度問題（Sonmez和Uysal 2014） 和資源受限的離散時(shí)間成本折衷問題（Sonmez等人，2015）。在提出的混合優(yōu)化 方法中，在啟發(fā)式階段使用反向調(diào)度，在遺傳優(yōu)化階段進(jìn)行向前改進(jìn)。本節(jié)介紹 了該方法的啟發(fā)式和遺傳優(yōu)化階段，以及后向前進(jìn)的改進(jìn)。遺傳優(yōu)化在啟發(fā)階段確定的解決方案通過遺傳優(yōu)化得到改進(jìn)。遺傳優(yōu)化是一種基于群 體的搜索方法，基于達(dá)爾文自然

12、選擇原理（Holland 1975）啟發(fā)的進(jìn)化計(jì)算原理。 在遺傳優(yōu)化中，問題的潛在解決方案由稱為染色體的候選解決方案群體表示。每 個(gè)染色體由一組稱為基因的參數(shù)組成。根據(jù)參數(shù)群體大?。╬）確定染色體數(shù)量。 在提出的混合優(yōu)化方法中，通過使用動(dòng)態(tài)模式選擇啟發(fā)式確定初始種群的一定百 分比（pct），而pct是用于遺傳優(yōu)化的參數(shù)。剩余的群體是隨機(jī)創(chuàng)建的，以包括 初始群體的多樣性。染色體編碼方式在提出的HM中，染色體由兩部分組成：第一部分包括活動(dòng)的優(yōu)先事項(xiàng)， 第二部分則包括活動(dòng)的執(zhí)行方式。二進(jìn)制表示用于所提出的方法中的活動(dòng)模式， 以清楚地區(qū)分所選擇的模式。對(duì)于在啟發(fā)階段獲得的解決方案，活動(dòng)的優(yōu)先級(jí)根 據(jù)其

13、在后向調(diào)度中的開始時(shí)間來確定，以實(shí)現(xiàn)后向調(diào)度。在領(lǐng)帶的情況下，選擇 是隨機(jī)的。在案例示例的啟發(fā)式階段獲得的時(shí)間表的染色體表示如圖1所示。前十個(gè)基 因代表活動(dòng)的優(yōu)先事項(xiàng)，剩下的基因代表模式選擇?；顒?dòng)的優(yōu)先次序根據(jù)圖1 給出的開始時(shí)間確定?；顒?dòng)2的最高優(yōu)先級(jí)為10，因?yàn)樗哂凶钤绲拈_始時(shí)間。 活動(dòng)1被分配下一個(gè)最高優(yōu)先級(jí)9,因?yàn)樗哂械诙€(gè)最早的開始時(shí)間。在具有 相同開始日期的活動(dòng)3和活動(dòng)5之間，隨機(jī)選擇活動(dòng)5。剩余活動(dòng)的優(yōu)先事項(xiàng)也 是類似的。模式選擇以二進(jìn)制表示形式進(jìn)行編碼，每種模式選擇替代方案由基因表示。 基因表示為活性選擇的模式被分配基因值1，并且將活性的剩余模式基因賦值為 0.例如圖11中

14、的第十一，第十二和第十三個(gè)基因。7表示活動(dòng)1的模式替代方案。 由于在啟發(fā)階段為此活動(dòng)選擇了第一種模式，所以第十一基因被賦值為1，而第 十二和第十三個(gè)基因被賦值為0.同樣地，作為活性2選擇第三模式，第十四和第 十五基因分配值為0,第十六基因的值為1.活性活性4,活性6和活性7有兩種 模式。因此使用兩個(gè)基因來代表這些活動(dòng)的模式。后向前進(jìn)在遺傳優(yōu)化中，使用正向串行調(diào)度方案（Kelley 1963）來解碼染色體。在正 向串行調(diào)度方案中，根據(jù)優(yōu)先級(jí)列表，最早優(yōu)先安排活動(dòng)和資源可行的開始時(shí)間。 染色體的解碼以及動(dòng)態(tài)模式選擇啟發(fā)式設(shè)計(jì)可實(shí)現(xiàn)后向改進(jìn)。例如，在圖1中給 出的染色體的解碼中。7, 2M 3由于具

15、有最高優(yōu)先級(jí)，所以在第0天首先從前開 始開始（圖8）。1M 1預(yù)定在第0天開始，這是最早的優(yōu)先級(jí)和資源可行的開始 時(shí)間。然后，活動(dòng)5M 1，3M 3，4M 1，8M 3,7M 1,6M 1,9M 3,10M2 以最早的優(yōu) 先級(jí)和資源可行的開始時(shí)間分別轉(zhuǎn)發(fā)，如圖1所示。因此，在啟發(fā)階段獲得的項(xiàng) 目期限由18天減少到16天，通過后向改善。交叉，變異和精英選擇新的染色體是由交叉或變異算子創(chuàng)建的。Hartmann（1998）已經(jīng)表明，兩點(diǎn) 交叉算子比RCPSP的一點(diǎn)和均勻交叉算子更好。因此，在遺傳優(yōu)化中，通過使 用兩點(diǎn)交叉算子來組合兩條染色體。用于遺傳優(yōu)化的兩點(diǎn)交叉算子最初確定染色 體第一部分隨機(jī)的兩

16、個(gè)點(diǎn)，其中保留了活動(dòng)的優(yōu)先級(jí)。然后，交叉算子選擇染色 體第二部分中相同活動(dòng)的模式來保留遺傳識(shí)別。例如，對(duì)于圖1中給出的染色體 7,如果將交叉點(diǎn)確定為第一部分的第三和第五基因，其中包括活性3,活性4 和活性5的優(yōu)先級(jí)，則染色體第二部分的交叉點(diǎn)應(yīng)包括以下基因：保持活動(dòng)3, 活動(dòng)4和活動(dòng)5的模式信息如圖1所示。變異算子首先隨機(jī)選擇一個(gè)活動(dòng)，然后隨機(jī)改變所選活動(dòng)的優(yōu)先級(jí)或者模式。 在下一代生存的染色體由精英選擇方法決定。染色體的前3%自動(dòng)轉(zhuǎn)移到下一代， 剩下的將在下一代生存的染色體由輪盤選擇決定。參數(shù)配置基于實(shí)驗(yàn)配置了所提方法的參數(shù)。在實(shí)驗(yàn)中，考慮了參數(shù)交叉率（cr ）的三 個(gè)水平，并考慮了參數(shù)突變率

17、（mr）,群體大?。╬）,動(dòng)態(tài)模式選擇啟發(fā)式（pct） 創(chuàng)建的初始群體的百分比）和更新（r）（Gurel2015）o對(duì)Menesi和Hegazy（2014 年）的100個(gè)活動(dòng)基準(zhǔn)項(xiàng)目進(jìn)行了 48次實(shí)驗(yàn)，包括參數(shù)水平的所有組合。所提 出的方法選擇的實(shí)驗(yàn)和參數(shù)值總結(jié)在表1中。小型基準(zhǔn)項(xiàng)目提出的HM最初是用小規(guī)模MRCPSP基準(zhǔn)測(cè)試項(xiàng)目測(cè)試的。該項(xiàng)目包括10 個(gè)活動(dòng)，最多3種模式（Zhang 2012），并作為案例（圖1）。基準(zhǔn)項(xiàng)目的上限報(bào) 告為14天（Zhang 2012; Menesi and Hegazy 2014）。第一個(gè)問題的終止標(biāo)準(zhǔn)設(shè)置 為10,000個(gè)時(shí)間表（目標(biāo)函數(shù)評(píng)估）。在所有40

18、個(gè)實(shí)驗(yàn)中，HM能夠確定最為 已知的解決方案，因此在平均計(jì)算時(shí)間（平均計(jì)算時(shí)間）（平均解）（AS）為14.0 天的情況下，實(shí)現(xiàn)了與上限（ADUB）值的平均偏差為0.0% ACT）小于1秒， 如表2所示。在40個(gè)實(shí)驗(yàn)中，粒子群優(yōu)化（PSO）方法（Zhang et al，2006）能 夠?qū)崿F(xiàn)5.0%的ADUB值（Zhang 2012）。類似地，Zhang（2012）的遺傳算法（GA） 成功地達(dá)到了 10.0%的ADUB值，在40個(gè)實(shí)驗(yàn)中，蟻群優(yōu)化（ACO）方法（Zhang 2012）達(dá)到了 2.9%的ADUB值。在具有2.00GHz CPU的臺(tái)式計(jì)算機(jī)上進(jìn)行GA （Zhang 2012），PSO （

19、Zhang et al，2006）和 ACO （Zhang 2012）的實(shí)驗(yàn)。中大規(guī)模基準(zhǔn)項(xiàng)目Menesi和Hegazy （2014）創(chuàng)造了中大規(guī)模通過多次復(fù)制（張2012）基準(zhǔn)項(xiàng) 目，為MRCPSP的基準(zhǔn)項(xiàng)目。項(xiàng)目包括100個(gè);500; 1000; 1500; 2000個(gè)活動(dòng)， 體現(xiàn)了現(xiàn)實(shí)生活建設(shè)項(xiàng)目的規(guī)模。HM的表現(xiàn)為10,000; 50000; 100,000，250,000 500,000;每個(gè)基準(zhǔn)項(xiàng)目報(bào)告了 1,000,000個(gè)時(shí)間表（目標(biāo)函數(shù)評(píng)估）。將HM的 性能與Menesi和Hegazy （2014）的受限規(guī)劃模型的性能進(jìn)行了比較，用于中大 型實(shí)例。HM在平均計(jì)算時(shí)間為2秒內(nèi)實(shí)

20、現(xiàn)了 4.0%的ADUB值，并在第二個(gè)基準(zhǔn)項(xiàng) 目（包括100個(gè)活動(dòng)）的2分鐘ACT內(nèi)，在所有40個(gè)實(shí)驗(yàn)中成功獲得了 140 天最好的解決方案，如表3所示CP模型在1秒內(nèi)達(dá)到了 15.0%的ADUB值，并 在3分鐘內(nèi)獲得了第二個(gè)基準(zhǔn)項(xiàng)目的最佳解決方案。對(duì)于第三個(gè)基準(zhǔn)項(xiàng)目，包括 500個(gè)活動(dòng)，HM在1分鐘的ACT內(nèi)實(shí)現(xiàn)了 5.6%的ADUB值，并在14分鐘內(nèi) 實(shí)現(xiàn)了 1.0%的ADUB值。然而,CP模型在1分鐘內(nèi)獲得了 11.0%的ADUB值， 在20分鐘內(nèi)獲得了 3.6%的ADUB值。CP模型需要2 h的計(jì)算時(shí)間才能達(dá)到1.1 % 的ADUB值。如表4所示，大型基準(zhǔn)項(xiàng)目的HM與CP模式之間的業(yè)績(jī)

21、差距擴(kuò)大。HM在 26秒內(nèi)實(shí)現(xiàn)了 10.7%的ADUB價(jià)值，11分鐘內(nèi)達(dá)到了 10.7%，在第4個(gè)基準(zhǔn)項(xiàng) 目中達(dá)到了 11個(gè)百分點(diǎn)，達(dá)到了 43分鐘，而在1分鐘內(nèi)，CP模式的ADUB價(jià) 值達(dá)到了 18.9%，而在10分鐘內(nèi)達(dá)到10.7% 10分鐘內(nèi)，4.8小時(shí)。對(duì)于第五個(gè) 基準(zhǔn)項(xiàng)目，包括1,500個(gè)活動(dòng)，HM在54秒內(nèi)實(shí)現(xiàn)了 11.5%的ADUB值，9分 鐘內(nèi)達(dá)到7.3%，46分鐘達(dá)到4.0%。CP模型，在1分鐘內(nèi)獲得21.0%的ADUB 值，10分鐘內(nèi)獲得11.0%的ADUB值，在2小時(shí)內(nèi)獲得7.3%的ADUB值。對(duì) 于第六個(gè)基準(zhǔn)項(xiàng)目，包括2000個(gè)活動(dòng)，HM在2分鐘內(nèi)獲得了 11.9%的ADUB 值，16分鐘的7.9%，1小時(shí)的4.6%，而CP模式在1分鐘內(nèi)達(dá)到了 21.6，分別 為11.1%在20分鐘內(nèi)，10.6%在1小時(shí)內(nèi)。計(jì)算結(jié)果表明，與Menesi和Hegazy (2014)的受限規(guī)劃模型相比，新型混 合模型獲得的結(jié)果明顯好于大規(guī)模MRCPSP。所提出的HM成功獲得了在幾分 鐘內(nèi)與上限偏離5-10%的解決方案。HM只通過搜索搜索空間的一小部分來實(shí)現(xiàn) 高質(zhì)量的解決方案。HM的收斂特性如圖1所示。11.對(duì)于包括2,000個(gè)活動(dòng)在內(nèi) 的大規(guī)模項(xiàng)目，CP在前10分鐘內(nèi)從ADUB的11.4億美元(11.4)達(dá)到11.