基于分布估計(jì)算法的資源受限項(xiàng)目調(diào)度方法.pdf

1、在項(xiàng)目調(diào)度問題中，一個(gè)項(xiàng)目往往包含多個(gè)任務(wù)，每一個(gè)任務(wù)的完成都需要消耗一定的時(shí)間，占用一定的資源。項(xiàng)目調(diào)度的目標(biāo)是安排各個(gè)任務(wù)的執(zhí)行時(shí)間來滿足高效、低消耗的工程要求。資源受限項(xiàng)目調(diào)度問題（Resource-Constrained Project Scheduling Problems，RCPSPs）是在項(xiàng)目調(diào)度的基礎(chǔ)上，規(guī)定資源上限約束以及由于技術(shù)上或其它一些因素導(dǎo)致的任務(wù)之間的時(shí)序約束，在約束范圍內(nèi)優(yōu)化某個(gè)項(xiàng)目調(diào)度目標(biāo)。這一重要的問題

2、模型在眾多領(lǐng)域得到了廣泛的應(yīng)用，擁有較大的工程應(yīng)用背景，主要包括規(guī)劃、管理、設(shè)備機(jī)器制造維護(hù)以及開發(fā)與研究中遇到的與調(diào)度相關(guān)的工作。求解RCPSPs的算法研究是調(diào)度領(lǐng)域的一個(gè)重要研究方向。近年來，考慮到該問題的復(fù)雜性以及RCPSPs模型的多樣性，算法研究方向主要集中在啟發(fā)式方法上。作為進(jìn)化算法的一個(gè)重要分支，待解決問題的復(fù)雜性以及大規(guī)模的變量促進(jìn)了分布估計(jì)算法（Estimation of Distribution Algorithm，E

3、DA）的發(fā)展，這類算法也被稱為基于模型構(gòu)建的遺傳算法或迭代密度估計(jì)進(jìn)化算法，其通過不斷更新概率模型實(shí)現(xiàn)優(yōu)化過程，從無偏差分布開始，逐步優(yōu)化收斂到只生成最優(yōu)解的模型。本論文主要研究如何將EDA應(yīng)用到RCPSPs上，主要工作可總結(jié)為如下三個(gè)方面：
　　（1）首先對RCPSPs的特性進(jìn)行了研究，提出了一種新的方法來分析單模RCPSPs的解空間組態(tài)。通常在多數(shù)求解單模RCPSPs的算法中，RCPSPs有三種解碼方式，分別是前向解碼、后向解

4、碼和混合解碼。我們通過比較這三種解碼方式構(gòu)建的解空間網(wǎng)絡(luò)特性，分別評價(jià)這三種解碼方式。主要工作分為兩個(gè)方面：第一，構(gòu)建單模RCPSPs的局部最優(yōu)解網(wǎng)絡(luò)（Local Optima Network，LON），LON中的節(jié)點(diǎn)表示局部最優(yōu)解，節(jié)點(diǎn)之間的邊表示局部最優(yōu)解之間的轉(zhuǎn)化方向及概率；第二，分析了三種RCPSPs-LON的不同網(wǎng)絡(luò)特性。分析表明RCPSPs-LON結(jié)構(gòu)大致分為三種類型，混合解碼方式構(gòu)建的RCPSPs-LON相比于其它兩種解碼

5、方式具有較好的網(wǎng)絡(luò)特性。
　?。?）基于以上關(guān)于單模RCPSPs解空間的分析，接下來我們提出了求解資源受限項(xiàng)目調(diào)度問題的松散約束分布估計(jì)算法（EDALCS-RCPSPs）。在該算法中，每一個(gè)個(gè)體為一個(gè)滿足時(shí)序約束的活動(dòng)列表，新的個(gè)體由概率模型產(chǎn)生并且從每一次迭代中選取較好的解進(jìn)行特征采樣來更新概率模型。算法采用傳統(tǒng)的前向-后向-前向局部搜索方法（Forward-Backward-Forward Iteration，F(xiàn)BI），除此之

6、外，我們提出了一個(gè)新的局部搜索算子，即松散約束搜索（Loosing Constraint Search，LCS）來增強(qiáng)算法的優(yōu)化強(qiáng)度。通過EDALCS-RCPSPs與已有EDA的對比實(shí)驗(yàn)，說明了LCS的局部搜索能力以及EDA模型的全局搜索能力，表明EDALCS-RCPSPs的性能優(yōu)勢。
　　（3）基于以上對單模RCPSPs分布估計(jì)算法的研究，進(jìn)而提出了一種新的RCPSPs模型——帶時(shí)間窗的資源受限項(xiàng)目調(diào)度問題（Resource-C

7、onstrained Project Scheduling Problems with Time Windows，RCPSPs-TW），并設(shè)計(jì)EDA解決該問題。在RCPSPs-TW中，首先構(gòu)建一個(gè)松散的基準(zhǔn)調(diào)度方案，然后通過向該方案中每個(gè)活動(dòng)添加時(shí)間窗的方式，來產(chǎn)生基準(zhǔn)的時(shí)間窗約束。RCPSPs-TW模型的有效解必須滿足以下三種約束：時(shí)序約束、資源約束、時(shí)間窗約束。針對于這一模型，我們提出了一種新的松散調(diào)度解碼方式（Sparse Dec