基于排隊論的動態(tài)多項目資源配置方法研究

黃小榮，杜百崗，戴 偉

(1湖北理工學(xué)院經(jīng)濟與管理學(xué)院，湖北黃石435003;2武漢理工大學(xué)機電工程學(xué)院，湖北武漢430073)

0 引言

隨著制造企業(yè)的生產(chǎn)方式從大規(guī)模批量生產(chǎn)轉(zhuǎn)變?yōu)榇笠?guī)模定制生產(chǎn)，表明現(xiàn)代制造企業(yè)的戰(zhàn)略已經(jīng)從以產(chǎn)品為中心轉(zhuǎn)向以顧客為中心［1］。在這樣的環(huán)境下，一方面，產(chǎn)品的多樣性增加、生命周期變短;另一方面，顧客對產(chǎn)品的交貨期、質(zhì)量、成本提出了更高的要求。這些原因使得企業(yè)傳統(tǒng)的管理方式不再有效。隨著項目管理理論與應(yīng)用的發(fā)展，許多企業(yè)在大規(guī)模定制生產(chǎn)中引入了項目管理的方法［2］，按項目對產(chǎn)品的售前、設(shè)計、采購、制造、售后等全過程進行管理。管理的項目化使得許多企業(yè)面臨多項目管理的挑戰(zhàn)。資源是項目執(zhí)行過程中的重要組成部分，其在多項目之間的競爭與共享是多項目管理中的核心問題。如何配置資源、提高項目的執(zhí)行效率以降低成本、減少工期是項目管理中的一個重要課題，即資源受限項目調(diào)度問題(Resource Constrained Project Scheduling Problem，RCPSP)，該問題研究在滿足項目活動關(guān)系及資源約束的前提下，如何合理地配置資源、安排項目的各個活動，使得管理目標(biāo)最優(yōu)化［3］。

鑒于RCPSP 本身重要的學(xué)術(shù)意義和應(yīng)用價值，學(xué)者們對其進行了大量的研究，研究內(nèi)容主要集中于問題的模型和求解算法上，文獻(xiàn)［4］對此進行了總結(jié)。由于RCPSP 的最初研究對象是工程類項目，在模型的構(gòu)建上有一個重要假設(shè)即項目的靜態(tài)性，項目的開工時間已知、固定，多個項目同時到達(dá)或隨機到達(dá)聚集后再集中規(guī)劃;對于執(zhí)行過程中項目完成時間與資源的動態(tài)關(guān)系，則采用多模式方法建模［5］，而多模式不足以反映項目全過程的動態(tài)性。在大規(guī)模定制企業(yè)中，一份訂單即可看作一個項目，故項目具有較強的動態(tài)性、不確定性，項目到達(dá)具有流水性以及項目之間具有關(guān)聯(lián)復(fù)雜性、差異性。上述原因使得經(jīng)典的RCPSP 模型的應(yīng)用受到了限制。

因此，針對項目動態(tài)性的上述特點，研究動態(tài)環(huán)境下多項目資源配置方法對縮短產(chǎn)品交期、降低成本、提高現(xiàn)代制造企業(yè)的市場競爭力和經(jīng)濟效益具有重要的理論意義和實際應(yīng)用價值?；诖?，針對制造企業(yè)多項目的動態(tài)性、不確定性、隨機性和流水性，本文考慮將資源看作服務(wù)臺，而項目看作服務(wù)對象，建立動態(tài)多項目的排隊論模型。首先對項目的到達(dá)時間及資源的服務(wù)時間進行統(tǒng)計，然后根據(jù)這些規(guī)律改進企業(yè)多項目的資源配置，使得資源既能滿足多項目的需要，又能使費用最低或項目交期最優(yōu)。

1 動態(tài)多項目資源配置問題描述

多項目并行以及項目的動態(tài)性增加了項目管理的復(fù)雜性，給現(xiàn)代企業(yè)的管理帶來了極大的挑戰(zhàn)，項目的動態(tài)性主要表現(xiàn)在以下幾個方面。

1)項目資源的動態(tài)性。一般來說，項目資源的動態(tài)性包括對資源需求的動態(tài)性和資源自身的動態(tài)性。前者表現(xiàn)為未知項目對資源需求的不確定性和現(xiàn)有項目對需求描述的模糊性等。后者主要指資源故障的不確定性，一般與其固有可靠性和參與條件有關(guān)，這類不確定性往往會影響項目調(diào)度的有效性和調(diào)度性能。

2)項目執(zhí)行過程中的動態(tài)性。當(dāng)企業(yè)接到客戶的產(chǎn)品需求后，采用項目管理的方式，對產(chǎn)品立項、建立研發(fā)小組，設(shè)計并確認(rèn)后小批量試產(chǎn)、批量生產(chǎn)，最后交付，項目管理涵蓋了銷售、研發(fā)、采購、質(zhì)量控制、制造等各個環(huán)節(jié)。項目執(zhí)行過程中各環(huán)節(jié)資源工作效率的變化、各活動提前期估算不準(zhǔn)、項目優(yōu)先級臨時變化等動態(tài)性因素削弱了項目按時完工的能力。

3)項目外部環(huán)境的動態(tài)性。項目外部環(huán)境的動態(tài)性是指由環(huán)境、條件、技術(shù)、工藝以及市場行情變化所引起的不確定因素。主要包括供給動態(tài)性和需求的動態(tài)性。前者來自于供應(yīng)商無法滿足市場需求，比如原材料供應(yīng)是否充足、外協(xié)生產(chǎn)加工的不確定性等;后者來自于最終市場需求與客戶訂單之間的差距，比如取消訂單或者緊急插入新訂單等。

動態(tài)多項目資源配置問題可以從以下幾個方面進行描述。

1)項目類別。根據(jù)產(chǎn)品的設(shè)計變動量可以將項目分為多類，同類項目之間的相似度高，不同類別的項目包括的任務(wù)不同。比如一個全新的產(chǎn)品其項目包括全部的產(chǎn)品研發(fā)任務(wù)，而只有某個零部件改變的產(chǎn)品則只包括少部分產(chǎn)品的研發(fā)任務(wù)。

2)項目到達(dá)速度。不同類別的項目隨訂單隨機到達(dá)，具有普通性、有限性、平穩(wěn)性和無后效性，因此可假設(shè)各類項目的到達(dá)均服從泊松分布。

3)項目任務(wù)。根據(jù)工作分解結(jié)構(gòu)(Work Breakdown Structure，WBS)［6］將項目分解為工作包(Work Package，WP)，WP 即為項目任務(wù)，項目任務(wù)不可再分，具有原子性，在項目中不同的項目任務(wù)所需的資源不同，各類項目中的同類任務(wù)資源需求相同。

4)資源約束。企業(yè)滿足所有項目任務(wù)的各類資源有限，所有資源總價之和有限。

5)目標(biāo)。在資源有限的情況下將其合理地配置到為各項目任務(wù)服務(wù)的服務(wù)臺中，優(yōu)化的目標(biāo)主要是項目評價工期最短、成本最低。

2 動態(tài)多項目資源配置模型

由于項目具有動態(tài)性、相似性、流水性等特點，項目隨機到達(dá)，企業(yè)的資源依次為各類項目任務(wù)服務(wù)，因而可將資源看做服務(wù)臺，項目看做顧客。同一類項目任務(wù)和為其服務(wù)的資源可以看做一個基本的排隊系統(tǒng)，“項目任務(wù)－資源”構(gòu)成的基本排隊系統(tǒng)如圖1所示。對于該系統(tǒng)，可以認(rèn)為:①顧客到達(dá)服從泊松分布;②排隊規(guī)則為等待制且容量無限;③至少有一個服務(wù)臺，且先到先服務(wù)，服務(wù)時間無記憶性且服從負(fù)指數(shù)分布。這說明“項目任務(wù)－資源”構(gòu)成的基本排隊系統(tǒng)即為M/M/c 或M/M/1 模型，服務(wù)臺數(shù)為資源的數(shù)量，項目任務(wù)的工期為平均逗留時間Ws。

圖1 “項目任務(wù)－資源”構(gòu)成的基本排隊系統(tǒng)

整個項目的執(zhí)行過程是由這些基本的排隊系統(tǒng)串聯(lián)或并聯(lián)在一起構(gòu)成了排隊網(wǎng)絡(luò)。

由文獻(xiàn)［7］中的Burke 定理可知，在排隊網(wǎng)絡(luò)中各類項目在各節(jié)點中的到達(dá)速度與離開速度相同，均等于該類項目到達(dá)系統(tǒng)的速度，即均為相同參數(shù)的泊松分布。由泊松分布的可加性［8］可知，所有項目到達(dá)排隊網(wǎng)絡(luò)中某一節(jié)點的泊松分布參數(shù)為各類項目的泊松分布參數(shù)之和。由文獻(xiàn)［9］中的Jackson 定理可知，在計算整個項目的工期時，可將“任務(wù)項目－資源”排隊網(wǎng)絡(luò)分解為各自獨立的“項目任務(wù)－資源”排隊系統(tǒng)，各排隊系統(tǒng)平均逗留時間之和即為整個項目工期。

基于排隊論的動態(tài)多項目資源配置模型建立流程，具體描述如下。

步驟1:對企業(yè)項目進行歸集，根據(jù)WBS對項目任務(wù)進行分解，按照項目內(nèi)任務(wù)數(shù)量對項目進行分類，根據(jù)各類項目建立網(wǎng)絡(luò)計劃圖模型，并尋找出關(guān)鍵路徑與非關(guān)鍵路徑。

步驟2:按照統(tǒng)計資料確定各類項目的到達(dá)速度，即確定泊松分布參數(shù)λ，同時，根據(jù)總的網(wǎng)絡(luò)計劃圖模型確定項目到達(dá)各服務(wù)臺的到達(dá)速度;對服務(wù)于同一類項目任務(wù)的資源進行抽象，定義資源的服務(wù)時間、資源單位等特征，其中服務(wù)時間為服從參數(shù)μ 的負(fù)指數(shù)分布，資源單位統(tǒng)一可折算為費用。通過對服務(wù)臺、顧客的抽象，確定“項目任務(wù)－資源”排隊系統(tǒng)模型。

步驟3:通過各個節(jié)點排隊系統(tǒng)與網(wǎng)絡(luò)圖模型建立排隊網(wǎng)絡(luò)模型。

步驟4:確定資源配置目標(biāo)，尋找約束。資源配置的目標(biāo)可以是成本最低或項目的平均完工時間最短，排隊網(wǎng)絡(luò)模型中項目的完工時間由各節(jié)點配置的服務(wù)臺數(shù)量決定。約束包括資源總價約束、項目關(guān)鍵路徑約束與非關(guān)鍵路徑的匯入約束［10］等。

步驟5:建立動態(tài)多項目資源配置數(shù)學(xué)模型。

步驟6:對模型進行求解，若資源配置不合理則轉(zhuǎn)向步驟2。

步驟7:輸出資源配置計劃。

綜上所述，完整模型表述如下:

在該模型中，式(1)表示配置目標(biāo)費用最低，其中fn(xn)表示資源費用函數(shù)，xn表示服務(wù)節(jié)點n 的服務(wù)臺數(shù)量，即第n 類資源的分配數(shù)量，N 表示資源的最大種類數(shù)。式(2)表示配置目標(biāo)項目的評價完工時間最短，Tz表示第z 類項目的完工時間，Pz表示第z 類項目關(guān)鍵路徑上的任務(wù)總數(shù)，ws表示任務(wù)的執(zhí)行時間，即任務(wù)在服務(wù)節(jié)點上的逗留時間。式(3)表示匯入約束，即非關(guān)鍵路徑節(jié)點上的服務(wù)時間之和不得大于關(guān)鍵路徑節(jié)點上的服務(wù)時間之和，排隊網(wǎng)絡(luò)模型中存在1～Q 個匯入約束，Ki表示第i 個匯入約束的非關(guān)鍵路徑節(jié)點數(shù)，Mi則表示第i 個匯入約束的關(guān)鍵路徑節(jié)點數(shù)。式(4)表示各節(jié)點的逗留時間。式(5)為排隊模型相關(guān)參數(shù)的計算公式。

3 求解

在上述模型中，各節(jié)點分配的資源數(shù)量決定了項目的完工時間，該模型可看作如何分配各節(jié)點資源數(shù)量以使成本最低、項目的完工時間最短，因此可將該模型近似地看作多目標(biāo)背包問題(Knapsack Problem)［11］。作為一種經(jīng)典的組合優(yōu)化問題，背包問題有著十分廣泛的工程應(yīng)用背景。由于該問題是一種NP(Non－deterministic Polynomial)完全問題，對其求解較為困難，而多目標(biāo)更加劇了問題的復(fù)雜性。由于各目標(biāo)之間存在沖突，模型不存在全局最優(yōu)解，只能對多個目標(biāo)進行折中處理，尋找Parato非支配解(Non－dominated solutions)［12］。常見的折中方法主要有加權(quán)求和法、約束法、最大－最小法等［12］。對于本文提出的問題，考慮到問題的實際背景，即客戶會對產(chǎn)品要求一個相對固定的交期，故采用約束法折中，對項目的工期目標(biāo)進行限定。

背包問題的求解方法可分為精確算法和進化算法。隨著問題的規(guī)模增大，精確算法的求解效果并不理想。近年來，進化算法特別是遺傳算法在求解該問題時越來越有效［13－14］，因此，本文采用遺傳算法對問題進行求解。

由于基本遺傳算法(Simple Genetic Algorithm，SGA)存在早熟收斂、局部搜索能力差、無方向性等缺點，對SGA 可從編碼、初始群體、適應(yīng)度函數(shù)、遺傳算子、控制參數(shù)等方面進行改進。針對本文問題的特點，采用自適應(yīng)遺傳算法(Adaptive Genetic Algorithms，AGA)主要對遺傳算子和控制參數(shù)進行改進。對于選擇算子，采用最優(yōu)保存策略以保證優(yōu)秀基因不被破壞，同時為避免“早熟”現(xiàn)象，配合使用入侵選擇策略。對于交叉與變異算子，SGA 采用固定的策略與控制參數(shù)無法滿足不同進化時期的動態(tài)要求，本文主要采用文獻(xiàn)［15］中給出的方法進行改進。

下面給出AGA 算法的設(shè)計步驟:

步驟1:編碼，隨機產(chǎn)生初始種群Popsize。為反映所求問題的結(jié)構(gòu)特征，滿足積木塊編碼原則，本文采用多參數(shù)級聯(lián)編碼方法，多參數(shù)級聯(lián)編碼染色體結(jié)構(gòu)如圖2所示。由圖2 可知，染色體R 長度為n，采用整數(shù)編碼，順序值為節(jié)點編號，基因值xn為節(jié)點服務(wù)臺數(shù)量，其數(shù)值大于等于1，表示服務(wù)臺的數(shù)量至少為1，xn決定著該節(jié)點的平均服務(wù)時間。在給定的λ 和μ 下，節(jié)點服務(wù)臺數(shù)量xn與節(jié)點平均服務(wù)時間t 之間的關(guān)系如圖3所示。由圖3 可知，節(jié)點上資源數(shù)目增加到Rmax時，節(jié)點上的平均服務(wù)時間趨于一定，因此xn的取值范圍為［1－Rmax］。根據(jù)基因的取值范圍隨機產(chǎn)生初始種群Popsize。

圖2 多參數(shù)級聯(lián)編碼染色體結(jié)構(gòu)

圖3 節(jié)點服務(wù)臺數(shù)量xn 與平均服務(wù)t 之間的關(guān)系

步驟2:算法終止判斷。由于目標(biāo)函數(shù)的最小值難以確定，所以終止條件為最大迭代次數(shù)Gen，算法到達(dá)預(yù)測迭代次數(shù)時，取種群中適應(yīng)度最高的染色體表示的資源配置組合，退出算法，否則轉(zhuǎn)下一步。

步驟3:解碼，計算個體的適應(yīng)度值。由于目標(biāo)函數(shù)是求最小值問題，令:

Cmax為最大完工時間，定義為:

適應(yīng)值越大表明越接近最優(yōu)解。

步驟4:選擇算子。設(shè)num 為新增個體數(shù)量。首先更新迄今為止的最優(yōu)個體，用最優(yōu)個體取代當(dāng)前種群適應(yīng)度值最低的個體。若此時已經(jīng)連續(xù)多代最優(yōu)個體未更新，則將num 增加△num，當(dāng)有最優(yōu)個體更新時，再將num 值調(diào)回初始值。然后去除當(dāng)前種群適應(yīng)度最低的num 個個體。

步驟5:交叉算子。計算被選入交叉操作的個體適應(yīng)度指標(biāo)，根據(jù)式(8)算出當(dāng)前交叉概率pc，采用兩點交叉算子對種群進行交叉配對。

式(8)中k 的取值范圍為(0，+∞)，Cmax為種群最大適應(yīng)度值，C－＇為種群平均適應(yīng)度值，pc∈［0.4，0.9］。當(dāng)種群趨于收斂時，pc減小;反之，pc增大，種群產(chǎn)生新個體能力增強。

在執(zhí)行交叉運算后，新生成的個體中基因值xn可能會超出其范圍，對于這種情況需要對2 個父代重新選擇交叉點進行交叉。若重新選擇后仍然超出其范圍，則直接將2 個父代補充到下一代。

步驟6:變異算子。采用單點變異操作，以變異概率pm在個體中隨機選擇變異節(jié)點，若染色體第x 位基因被選中，則在該基因值域范圍內(nèi)隨機生成一個整數(shù)，代替原來的基因。若多代最優(yōu)個體未更新，則將變異概率增加△pm，反之將pm調(diào)回初始值。

步驟7:形成下一代群體，轉(zhuǎn)向步驟2。在算法開始前需要收集并整理出如下數(shù)據(jù):①各類項目到達(dá)速率RC;②網(wǎng)絡(luò)中各節(jié)點服務(wù)速率RS;③資源種類數(shù)N;④各資源費用系數(shù)CostForXp、各資源上限Rmax;⑤各類項目的非關(guān)鍵路徑條數(shù)NonKey;⑥各類項目的非關(guān)鍵路徑位置矩陣nonKetStr;⑦各類項目的關(guān)鍵路徑節(jié)點數(shù)P;⑧各類項目完工時間限制T;⑨遺傳算法相關(guān)參數(shù)Gen、Popsize、k、pm、△pm、num、△num、Cmax。

4 實驗仿真

案例企業(yè)為某汽車零部件制造公司，該公司向國內(nèi)外多家知名汽車主機廠供應(yīng)汽車零部件，產(chǎn)品型號多達(dá)數(shù)百種，屬于典型的多品種小批量生產(chǎn)企業(yè)，對此，企業(yè)采用項目方式對訂單進行全程管理，并對項目按照產(chǎn)品設(shè)計的新舊程度進行分類。為減少問題的復(fù)雜程度，不失一般性，將這些項目分為2 類:新產(chǎn)品項目和既有產(chǎn)品項目。每類項目流程高度相似，對項目流程及資源特點進行分析抽象后，得到項目網(wǎng)絡(luò)圖如圖4所示，項目網(wǎng)絡(luò)圖基本數(shù)據(jù)如表1所示，項目數(shù)據(jù)及相關(guān)資源特征如表2～3所示，其中新產(chǎn)品研發(fā)時間約束為20，產(chǎn)品生產(chǎn)時間約束為80。遺傳算法進化曲線如圖5所示。

算法求得最優(yōu)個體為3，1，1，1，1，1，1，1，1，3，3，4，4，2，2，3，5，2，1，2，4，2，2，1，1;資源費用為227，跟原始費用相比，優(yōu)化后的資源費用大大降低。

圖4 項目網(wǎng)絡(luò)圖

表1 項目網(wǎng)絡(luò)圖基本數(shù)據(jù)

表2 項目數(shù)據(jù)表

表3 資源數(shù)據(jù)表

圖5 遺傳算法進化曲線

5 結(jié)束語

多項目并行與項目的動態(tài)性增加了項目資源配置問題的復(fù)雜性，對傳統(tǒng)的RCPSP 的研究雖已較好地解決了多項目資源配置問題，但對于項目的動態(tài)性問題考慮較少。本文基于排隊論的動態(tài)多項目資源配置模型，從排隊論的角度考慮了企業(yè)資源服務(wù)項目的問題，該模型考慮了項目隨機聚散現(xiàn)象和資源隨機服務(wù)項目工作過程中的特點，利用排隊論的數(shù)學(xué)理論和方法可以較好地處理項目資源配置中的動態(tài)性問題。給出的案例首先對項目及資源進行了簡單的抽象，表明該模型可以在滿足時間約束的情況下對資源進行優(yōu)化配置。但在實際中，項目及其任務(wù)的聚集、項目的優(yōu)先級、資源的服務(wù)時間、資源的共享等情況更加復(fù)雜，因此如何建立項目及其資源的相關(guān)模型以及模型的驗證將是下一步研究的重點。

［1］祁國寧，顧新建，李仁旺.大批量定制及其模型的研究［J］.計算機集成制造系統(tǒng)，2000，6(2):41－45.

［2］邱進冬，顧新建.面向大規(guī)模定制的項目管理研究［J］.成組技術(shù)與生產(chǎn)現(xiàn)代化，2003，20(1):34－37.

［3］劉士新.項目優(yōu)化調(diào)度理論與方法［M］.北京:機械工業(yè)出版社，2006:1－10.

［4］方晨，王凌.資源約束項目調(diào)度研究綜述［J］.控制與決策，2010，25(5):641－650.

［5］程序，吳澄.粒子群優(yōu)化算法求解多模式項目再調(diào)度問題［J］.計算機集成制造系統(tǒng)，2009，15(1):97－101.

［6］項目管理協(xié)會(美)編.項目管理知識體系指南［M］.王勇，張斌，譯.北京:電子工業(yè)出版社，2009:80－87.

［7］Burke P J.The output of a queueing system［J］.Operations Research，1956，4(6):699－704.

［8］徐懷，唐玲.復(fù)合泊松過程的可加性［J］.大學(xué)數(shù)學(xué)，2006，22(6):114－117.

［9］Jackson J R.networks of waiting lines［J］.Operations Research，1957，5(4):518－521.

［10］劉瓊，林魁，張超勇，等.基于關(guān)鍵鏈多項目魯棒調(diào)度［J］.計算機集成制造系統(tǒng)，2012，18(4):813－820.

［11］熊小華，寧愛兵，馬良.基于多交換鄰域搜索的多維0/1 背包問題競爭決策算法［J］.系統(tǒng)工程理論與實踐，2010，30(8):1448－1456.

［12］馬小姝，李宇龍，嚴(yán)浪.傳統(tǒng)多目標(biāo)優(yōu)化方法和多目標(biāo)遺傳算法的比較綜述［J］.電氣傳動自動化，2010(3):48－50.

［13］Lin F.Solving the knapsack problem with imprecise weight coefficients using genetic algorithms［J］.European Journal of Operational Research，2008，185(1):133－145.

［14］劉西奎，李艷，許進.背包問題的遺傳算法求解［J］.華中科技大學(xué)學(xué)報(自然科學(xué)版)，2002，30(6):89－90.

［15］李濟民.基于遺傳算法的軌道精調(diào)系統(tǒng)的設(shè)計與應(yīng)用［D］.武漢:武漢理工大學(xué)，2012:37－40.