第 1 章  緒論

1.1 選題背景及意義

1.1.1  選題背景

隨著科學技術的進步，社會科學的發(fā)展，生產的規(guī)模性逐漸加大，生產技術復雜性也越來越高，對企業(yè)尤其是制造型企業(yè)的生產監(jiān)控提出了更高的要求。企業(yè)只有通過最有效的方式并不斷縮短加工時間才能生產出符合顧客滿意的產品。與此同時，企業(yè)自身也需要不斷降低生產成本從而保證利潤最大化，長此以往，才能不斷獲得十足的發(fā)展動力。因此出現了以項目為中心的活動開展方式。

項目是組織進行的一個暫時性的活動，在一定的規(guī)定時間內，運用事先確定的資源，以產出一個獨特的且可以事先約定俗成的結果為目標所進行的時效為一次性的活動。項目管理，簡稱（PM）就是指項目經理人，在現有的、有限的資源約束下，運用系統(tǒng)論的觀點、方法和其他相關理論，對項目中的全部任務進行有效地統(tǒng)籌管理。從項目的生命周期來講，就是從項目的決策開始到項目結束的整個過程進行計劃、組織、指揮、協調、控制和評價，以實現項目的既定目標。項目管理是在組織整體活動上，運用管理的知識、技術和手段來達成解決項目的問題或達成項目的需求。項目管理的概念最早由美國提出，是 20 世紀 40 年代發(fā)展起來的具有重大革新意義的管理技術之一。

而項目調度問題是項目管理中的一個經典問題，它主要研究的是一系列具有相關性的項目完成的邏輯順序，從而實現所規(guī)定的項目指標達到最優(yōu)化的效果。項目調度問題是各種加工行業(yè)、制造業(yè)和交通運輸業(yè)等領域中普遍存在的問題，根據所規(guī)定任務的開始順序不同，所得到的結果往往差別是很大的。如果可以將調度理論和方法恰當地運用到工業(yè)生活中進行生產活動的調度，往往極有可能使得項目目標達到最優(yōu)化或者讓人滿意的效果。在項目管理領域，資源受限項目調度問題（RCPSP)又是項目調度中被深入研究的一個經典問題。典型的資源受限型項目調度問題是以確定的工期、給定的資源和單一條件約束下的總工期最小為目標。自從 RCPSP 問題被提出以來，就受到項目經理人和廣大研究人員的長久的廣泛的關注。人們對不同約束條件下的 RCPSP 問題的研究分別做了大量的工作，還將其大致劃分為單目標資源受限項目調度問題、多目標資源受限項目調度問題、多模式資源受限項目調度問題、模糊資源受限項目調度問題、資源受限項目的魯棒優(yōu)化問題。

........................

1.2 相關研究現狀評析

1.2.1 傳統(tǒng)項目調度的研究現狀

傳統(tǒng)項目調度問題，即經典 PCPSP 問題，是假設項目的完工時間和資源的使用是一個確定的值，以項目總工期最小為目標函數，同時滿足三個約束條件：一是要滿足任務之間的單一時序邏輯約束條件，即緊前約束或者緊后約束；二是要滿足完成任務的資源約束條件，每項任務的完成都需要消耗一定數量的資源，這里提到的資源只考慮可更新資源；三是要滿足時間約束條件，假定項目中每項任務的持續(xù)時間是事先已知的，并且假設項目中的每一項任務一旦開始就不能被中斷（即不允許可搶占）。

用于求解經典 RCPSP 問題的算法有精確算法和啟發(fā)式算法兩大類，精確算法一般在規(guī)定時間內對小規(guī)模問題能夠求得最優(yōu)解，由于此問題屬于 NP-hard問題，對于超過 60 個任務的項目此類算法則無法實施。啟發(fā)式算法則適合于中大規(guī)模問題求解，但無法保證所求結果為最優(yōu)解。

自從凱利提出調度產生方案(SGS)的概念后，人們陸續(xù)地提出了其他不同的啟發(fā)式算法。對于規(guī)模較大的項目而言，啟發(fā)式算法雖然不能保證求得目標函數的最優(yōu)解，但其優(yōu)勢在于計算速度快，同時還可以兼顧計算質量和計算效率兩方面。啟發(fā)式算法的類型主要包括基于優(yōu)先規(guī)則的簡單算法；分離弧的概念；局部搜索技術；智能優(yōu)化算法等。近年來人們發(fā)現用啟發(fā)式搜索算法求解經典的RCPSP  問題的有效性，啟發(fā)式搜索算法主要包括以遺傳算法（GA）；模擬退火（SA）；禁忌搜索（TS）為典型代表的智能優(yōu)化算法。Boctor（1996）提出用模擬退火算法求解經典 RCPSP 問題。該方法采用任務鏈表編碼，運用串行調度產生方案進行解碼，采用插入式的鄰域函數。Kim 等人（2003）提出了一種帶有模糊控制器的混合遺傳算法，此算法可以大大加快遺傳算法的收斂速度，并能保留遺傳算法的現有優(yōu)點。

1.2.2 項目模糊調度的研究現狀傳統(tǒng)項目調度問題將項目中每項任務的持續(xù)時間和所占用的資源看成確定值的前提下進行求解的，而在實際的生產或者工程類問題中，由于企業(yè)生存的內外環(huán)境的不斷變化，以及供給資源的不確定等不確定因素的存在，使得企業(yè)受到一系列不確定因素的影響。對于這些不確定因素，通常的處理方法有兩種，一是把這些確定因素看成是確定值進行求解，這種方法會使得問題模型發(fā)生變化，從而求得的問題解也會產生偏差，而且求的解的形式不符合傳統(tǒng)的表達。二是運用概率學理論描述參數的分布，目前針對概率函數，多用隨機優(yōu)化的方法來解決不確定約束下的項目調度問題。這種處理方法要求參數的數據是已知的，但是項目具有非重復性，并且項目采用的新技術降低了項目經驗數據的可靠程度。另外，由于各項活動執(zhí)行時間的概率分布是未知的，所以應用隨機優(yōu)化方法是十分困難的。在這種情況下，采用模糊數來表示活動執(zhí)行時間比采用隨機數更符合實際情況。

..........................

第 2 章  相關理論基礎

2.１ 多目標優(yōu)化理論概述

在同一個系統(tǒng)內，在給定的區(qū)域上優(yōu)化兩個或者兩個以上問題叫做多目標優(yōu)化問題，多目標優(yōu)化問題提出之后就獲得了強烈地關注，已經廣泛應用到學術理論研究和工程實踐以及工業(yè)生產等領域。比如，我們在解決項目調度問題時，必須考慮許多因數，產品的可制作性，產品的可靠性，產品的安全性，產品的可控成本，以及產品的模糊交貨期和模糊工期等等。但是這些目標之間又往往存在著很大的矛盾，如果保證成本最低，那么產品的可靠性和安全性又無法保證，若同時保證成本最低，可靠性最大，安全性最高的話，交貨日期和工期又很難保證。在求解上述問題時，無論是目標函數和目標函數之間，還是各種不同的約束條件之間往往都存在著各種錯綜復雜的關系，所以，僅僅依靠簡單的單目標優(yōu)化并不能很好地解決所有問題，因此必須從多目標優(yōu)化思路進行考慮。

區(qū)分單目標優(yōu)化問題和多目標優(yōu)化問題在本質的地方在于多目標優(yōu)化問題的解是一個解集的形式，它里面可能包含多個最優(yōu)解，并不存在唯一的全集最優(yōu)解，這個集合被稱為 Pareto 最優(yōu)解。所謂的 Pareto 最優(yōu)可以解釋為，在對一個或者一個以上的目標進行優(yōu)化之后，不存在其余的目標可以不朝著更壞的方向退化的更理想解的形式。也就是說，在對其中的某一個或者某幾個目標函數進行優(yōu)化的同時，勢必會削弱其他目標函數保持最優(yōu)的趨勢。對全部的目標函數來說，Pareto 最優(yōu)解集中的各個元素相互之間是可以進行比較的。而單目標優(yōu)化問題，則必須通過對單目標函數的求解優(yōu)化操作得到全局的最優(yōu)解或者是滿意解。

2.2.1 多目標優(yōu)化問題的數學模型

要求解多目標優(yōu)化問題，首先應當建立數學模型。建立數學模型不僅是求解問題提供必要的前提，同時也是進行對  優(yōu)化問題進行定性研究的一種重要方法。建立數學模型，既可以從理論角度進行分析，又可以給具體的實踐活動提供適當的計算方法，從而從更大范圍給實踐活動或者生產活動作出相應的指導。

......................

2.2單目標項目模糊調度描述與模型

2.2.1 單目標項目模糊調度問題描述

項目決策者在項目周期的初始計劃階段無法獲得各項活動的準確執(zhí)行時間，所以需要根據以往經驗給定各項活動一個估計時間，本文假定完工時間是一個模糊值，稱之為模糊完工時間。同時，一個企業(yè)在一段時間內所擁有的資源是固定的，同一資源又可能同時被多項活動所占用，因此各項活動的資源消耗量的大小和資源在項目中每個任務的可用時間也具有了不確定性，資源的可用時間也變?yōu)橐粋�估計的模糊值。正是由于這種外在因素的不確定性，導致了項目原定計劃的不準確，因此在執(zhí)行過程中項目原有調度極有可能會被多次更改，從而導致成本增加，施工時間增加，這就有可能會導致項目不能按時完工。這就要求項目決策者在項目計劃階段，必須合理安排各項活動的所占用資源的時間，并確保項目中的各項活動都滿足前后邏輯約束關系，以項目完工時間的最小化作為現代調度中的首要性能指標。

遺傳算法是一種基于全局所進行的隨機優(yōu)化算法，它的算法原理主要是模擬了達爾文的進化論中提到的自然界生物進化的適者生存的過程。在運用遺傳算法進行項目調度問題的優(yōu)化求解，第一步要做的是把項目調度優(yōu)化模型中目標函數的運算和約束條件中所涉及到的參數指標通過編碼操作而轉化成程序語言，得到我們接下來要進行遺傳操作的染色體。接著需要做的是通過不同染色體之間的遺傳操作（包括交叉和變異兩個過程），從而達到在被編碼的染色體遺傳空間進行高效迭代搜索尋求最優(yōu)解的目的。迭代次數達到之前所設定的最大值時終止算法流程，對所得到的染色體解進行解碼和評價，從而可以保證解空間朝著更優(yōu)化的方向進化。

染色體編碼的實質是在算法進行過程中主要是在編碼空間中對染色體進行多次重復的遺傳交叉和遺傳變異操作，從而達到種群向著更優(yōu)化進化的目的。解碼過程則是把遺傳空間中所挑選出的染色體再重新翻譯成解空間中的特征解的形式，然后對解空間中所得的特征解進行評價和選擇。用遺傳算法來解決項目調度問題時，需要重復地在搜索空間和解空間中進行反復交替操作，如圖 3.1 所示。

...........................

第 3 章 單目標項目模糊調度算法設計 ....................... 21

3.1 單目標項目模糊調度描述與模型 ....................... 21

3.1.1 單目標項目模糊調度問題描述 ..................... 21

第 4 章 多目標項目模糊調度算法設計 ....................... 37

4.1 多目標項目模糊調度描述和模型構建 ................... 38

4.1.1 多目標項目模糊調度問題描述 ..................... 38

第 5 章 結論及展望 ........ 51

5.1  研究結論 ............ 51

5.2 研究展望 ......... 52

第 4 章  多目標項目模糊調度算法設計

在項目進行的過程中，往往不只是對一個方面進行約束，而是同時對多個條件加以限制，要求在各方面都達到最好的前提條件下來解決項目調度問題。因此就出現了多目標項目調度問題。多目標問題往往由于所構成目標函數的不同而出現不同的求解方法，常見的目標函數包括項目工期最小、成本最小，項目拖期/完工的最小化，，常見的項目調度問題中對以上單個目標都做出比較深入的研究，但是在現實的求解項目調度問題，往往需要綜合考慮多個目標函數，單憑其中一項目標函數的求解很難進行調度結果的好壞評價，而這些指標之間通常又不具有可比性，有些指標往往還是呈現負相關的聯系。因此，怎么在這些指標之間進行權衡比較和篩選，從而找到一個解決問題的平衡點。求解這類問題叫做多目標項目調度問題（MOCPSP)。舉一個具體例子，比如增加資源的投入量，可以縮短項目的完工時間，但是同時還會是得項目資源成本增大。對于項目決策者而言，他們當然希望盡可能地縮短項目的總工期，但與此同時，他們也不愿意項目資源成本過大，這就需要在項目完工時間和項目資源成本之間進行權衡，從而找到最佳的平衡點。

4.1 多目標項目模糊調度描述和模型構建

4.1.1 多目標項目模糊調度問題描述

項目多目標模糊項目調度（FRCPSMOOP）是對經典資源受限項目調度問題的進一步拓展，是對第三章項目單目標模糊調度問題的進一步深入展開。首先從模型來說，本文所研究的多目標問題是在第三章以項目工期為目標函數的基礎上，又引入了項目資源成本這一目標，從而將其轉化成項目多目標模糊調度優(yōu)化模型。通過這一模型，希望能在項目完工時間和資源都是不確定的條件下，運用三角模糊數的理論，能夠同時優(yōu)化項目完工時間和資源成本及分配。在算法設計方面，延續(xù)了第三章對單目標項目模糊調度的求解的遺傳算法的基本步驟，并對其進行了改進，使得算法更具有效性。

.......................

第 5 章  結論及展望

5.1  研究結論

資源受限型項目調度問題（RCPSP）是項目調度問題中的一類非常重要的問題，一直以來受到人們的廣為關注和系統(tǒng)研究。本文通過對傳統(tǒng) RCPSP問題的論述和總結前人的研究成果，從中找出傳統(tǒng) RCPSP 問題在求解不確定資源約束條件下的項目調度問題中存在的不足。而企業(yè)實際的生產過程中往往會出現許多不確定因素，比如各項任務工期的不確定，資源需求的不確定。為盡量減少這些不確定因素對項目調度的影響，我們首先從隨機優(yōu)勢的角度來考慮這些因素的建模。但由于我們是通過以往的經驗判斷各任務的概率值，使得結論非常不具有客觀性和通用性。然后我們又考慮將模糊數學的理論引入到資源受限型項目調度問題中，形成一種全新的調度問題——項目模糊調度問題，并建立相應的數學模型，并運用模糊數學、多目標優(yōu)化等理論，相應地給出不確定資源約束條件下針對單目標問題和多目標問題的不同的求解方法，并得出以下結論：

1.本文在解決項目調度問題時引入模糊數學的理論，運用三角模糊數來表示項目的模糊最大完工時間和模糊資源使用量，將確定的任務持續(xù)時間和日均資源使用量轉化為資源使用量的下界、中值和上界的形式，從而結果變成可持續(xù)的一組區(qū)間值，使結果具有一定的靈活性和機動性。

2.本文首先求解了項目單目標模糊項目調度問題，在問題描述方面，將項目模糊完工時間作為需要求解的目標函數，給出其他約束條件，給出項目單目標模糊項目調度問題的優(yōu)化模型。在求解算法方面，首先使用的是傳統(tǒng)的遺傳算法，包括對編碼和解碼方案的設計、產生第一代種群、確定適應度函數，進行輪盤賭選擇、單點交叉和變異等操作。然后由于遺傳算法的某些局限性，本文考慮對傳統(tǒng)的遺傳算法進行改進，在遺傳算法的基礎上，引入模擬退火步驟，將原算法改進為遺傳-模擬退火算法，并對其他方面同時進行改進，具體體現在將原來的二進制編碼變?yōu)楦窭拙幋a方案，產生初始種群時由原有的輪盤賭選擇改進為混沌遍歷搜索的辦法，適應度函數的設計更加數值化，變異操作也由單點變異改進為兩點變異。通過一個對具體實例的數值實驗，可以看出改進的遺傳-模擬退火方法比傳統(tǒng)的遺傳算法更加有效。

本文第四章在第三章的基礎上，將項目單目標模糊調度優(yōu)化問題拓展為項目多目標模糊調度優(yōu)化問題。首先在問題描述方面，將模糊資源成本從約束條件中拿出來，與模糊最大完工時間一起作為目標函數，同時對兩個目標函數進行最小化，從而建立起項目多目標模糊調度優(yōu)化模型，在算法的設計方面，以基于非支配性排序的多目標遺傳算法（NSGA-II)為基礎，并引入基于模式、任務雙鏈表，設計了求解該問題的算法，包括算法的編碼與解碼方案設計，種群初始化的方案，適應度函數值的計算，以及傳統(tǒng)遺傳算法的選擇操作、交叉操作和變異操作等。最后通過一個具體的案例求解，驗證了本文提出的項目多目標模糊調度優(yōu)化模型以及所設計的 NSGA-II 算法同時求解模糊完工時間和模糊資源成本兩個目標函數的合理性和有效性。

參考文獻（略）