關(guān)鍵鏈管理法在資源受限多項(xiàng)目調(diào)度中的應(yīng)用

吳超（安徽工業(yè)大學(xué) 管理科學(xué)與工程學(xué)院，安徽 馬鞍山　243032）

關(guān)鍵鏈管理法在資源受限多項(xiàng)目調(diào)度中的應(yīng)用

吳超
（安徽工業(yè)大學(xué) 管理科學(xué)與工程學(xué)院，安徽 馬鞍山243032）

RCMPSP問題主要待解決的問題就是解決資源沖突的問題。關(guān)鍵鏈管理法主要是需找出項(xiàng)目中的制約整個(gè)項(xiàng)目的任務(wù)并將其組成一條關(guān)鍵鏈路，并設(shè)置各種緩沖區(qū)來(lái)保護(hù)關(guān)鍵鏈。本文用關(guān)鍵鏈管理法來(lái)解RCMPSP問題中，設(shè)計(jì)了基于關(guān)鍵鏈的調(diào)度算法。

資源受限；多項(xiàng)目；關(guān)鍵鏈；調(diào)度算法

2　基于關(guān)鍵鏈的資源受限多項(xiàng)目調(diào)度算法

本文采用文獻(xiàn)［7］中為每個(gè)項(xiàng)目任務(wù)設(shè)置一個(gè)優(yōu)先權(quán)系數(shù)的方法來(lái)作為調(diào)度依據(jù)。本文采用粒子群遺傳算法來(lái)求得多項(xiàng)目中各個(gè)任務(wù)的優(yōu)先權(quán)系數(shù)。

2.1算法設(shè)計(jì)

（1）編碼。粒子群算法和遺傳算法都是可以采用整數(shù)編碼的。一個(gè)粒子或染色體就表示一個(gè)優(yōu)先權(quán)列表。

（2）適應(yīng)數(shù)函數(shù)。設(shè)為當(dāng)前種群中第k個(gè)染色體或粒子，則g（uk）是適應(yīng)度函數(shù)值，f（uk）是其 RCMPSP數(shù)學(xué)模型的目標(biāo)函數(shù)值。

（3）粒子群遺傳算法的操作。對(duì)于產(chǎn)生的初始種群，先采用粒子群的兩個(gè)跟新公式來(lái)對(duì)種群進(jìn)行操作。

慣性權(quán)重w體現(xiàn)出了粒子繼承先前的速度的能力，為了平衡算法的全局搜索和局部搜索的能力，本文采用線性遞減的慣性權(quán)重。對(duì)于GA算法的選擇操作，本文采用輪盤賭選擇；對(duì)于交叉操作，采用單點(diǎn)交叉。

2.2關(guān)鍵鏈和非關(guān)鍵鏈的識(shí)別

本文采用基于優(yōu)先權(quán)列表和總時(shí)差相結(jié)合的方法來(lái)識(shí)別關(guān)鍵鏈。方法如下：先計(jì)算出每個(gè)項(xiàng)目中各個(gè)任務(wù)的總時(shí)差，然后將總時(shí)差的任務(wù)為0的任務(wù)選出，從左到右，按照任務(wù)編號(hào)從大到小依次排列上一步所選擇出的任務(wù)，在遇到同時(shí)有兩個(gè)以上的任務(wù)的任務(wù)總時(shí)差為0時(shí)，選擇優(yōu)先權(quán)系數(shù)大的任務(wù)作為關(guān)鍵鏈上的任務(wù)。

2.3基于關(guān)鍵鏈的資源受限多項(xiàng)目調(diào)度算法

本文采用并行調(diào)度方案產(chǎn)生項(xiàng)目的調(diào)度計(jì)劃。根據(jù)進(jìn)度區(qū)分三個(gè)任務(wù)集合：Cg成為已完成集合；Ag為執(zhí)行集合；Dg為候選集合。具體算法如下：

輸入：多項(xiàng)目調(diào)度網(wǎng)絡(luò)G=（V，R）；

（1）初始化任務(wù)集合

（2）初始化時(shí)間段，tg=1

（3）檢查執(zhí)行集合中，是否有執(zhí)行完成的任務(wù)，若是有，則將其移入完成集合中，并更新這兩個(gè)任務(wù)集合

（4）更新資源信息，檢查候選集合中是否有滿足邏輯工序和資源約束的任務(wù)，若是有，將任務(wù)優(yōu)先權(quán)系數(shù)大的任務(wù)調(diào)入執(zhí)行集合中；

（5）重復(fù)第4步，直至候選集合中沒有任務(wù)滿足邏輯工序和資源約束，跟新集合和資源信息；

（6）判斷執(zhí)行集合和候選是否為空集，若是，則退出算法；

（7）tg=tg+1，轉(zhuǎn)入第三步；

輸出基于關(guān)鍵鏈的多項(xiàng)目調(diào)度方案G′=（V′，G′）。

3　實(shí)例驗(yàn)證

3.1關(guān)鍵鏈多項(xiàng)目調(diào)度

采用一個(gè)實(shí)例來(lái)驗(yàn)證該方法的正確性。本文采用的多項(xiàng)目是包含三個(gè)項(xiàng)目。三個(gè)項(xiàng)目共享三種可更新資源R1、R2和R3，可使用的總量分別為：20、20、20。多項(xiàng)目的各個(gè)任務(wù)基本情況如圖3.1。首先采用上述算法求出該多項(xiàng)目各個(gè)任務(wù)的優(yōu)先權(quán)列表：［0-13-26-1-14-18-27-3-31-28-29-4-19-5-30-17-2-6-22-16-33-20-7-23-29-24-32-34-8-9-21-36-10-25-35-37-22-12-38］。接著求出各項(xiàng)目關(guān)鍵鏈，第一個(gè)項(xiàng)目的關(guān)鍵鏈為：1-3-5-6-7-8-10-11-12，非關(guān)鍵鏈為：2、4、9。第二個(gè)項(xiàng)目的關(guān)鍵鏈為：13-14-18-19-22-23-24-25。非關(guān)鍵鏈為：15、17，、16-20、21。第三個(gè)項(xiàng)目的關(guān)鍵鏈為：26-27-28-31-33-34-36-37。非關(guān)鍵鏈為：29-32、30、35。使用調(diào)度算法生成進(jìn)度計(jì)劃，見表1。

表1　關(guān)鍵鏈多項(xiàng)目調(diào)度方案

如表1所示，共有8個(gè)時(shí)間段，其中資源R1的負(fù)荷在各個(gè)時(shí)間段較其他兩個(gè)資源的負(fù)荷是較重的。因此，將R1設(shè)為鼓資源，并為其任務(wù)設(shè)置CCB。由于本文不涉及多項(xiàng)目的各個(gè)緩沖區(qū)尺寸的計(jì)算，計(jì)算方法不在此詳述，圖1為經(jīng)過關(guān)鍵鏈管理法優(yōu)化的多項(xiàng)目網(wǎng)絡(luò)圖。

3.2關(guān)鍵鏈多項(xiàng)目調(diào)度結(jié)果分析

從圖1可以看出，該多項(xiàng)目在未使用關(guān)鍵鏈管理法時(shí)的項(xiàng)目完工工期為154天，而使用基于關(guān)鍵鏈的多項(xiàng)目調(diào)度算法而產(chǎn)生的調(diào)度方案的工期為101.87，加上左后的項(xiàng)目緩沖區(qū)18，17，所以，該多項(xiàng)目最后的工期為120.04。

4　結(jié)語(yǔ)

本文考慮了RCMPSP問題的約束條件，利用關(guān)鍵鏈管理法去解決RCMPSP問題。本文為每個(gè)任務(wù)設(shè)置優(yōu)先權(quán)系數(shù)，并結(jié)合總時(shí)差來(lái)求出關(guān)鍵鏈。在生成進(jìn)度計(jì)劃方案時(shí)，采用并行調(diào)度和優(yōu)先權(quán)列表相結(jié)合的方法來(lái)求出調(diào)度方案。

主要參考文獻(xiàn)

［1］GOLDRATT E M.Critical Chain［M］.Great Barrington，MA：The North River Press，1997.

［2］劉士新，宋健海，唐加福.基于關(guān)鍵鏈的資源受限項(xiàng)目調(diào)度新方法［J］.自動(dòng)化學(xué)報(bào)，2006，32（1）：60-66.

［3］李俊亭，王潤(rùn)孝，楊云濤.關(guān)鍵鏈多項(xiàng)目整體進(jìn)度優(yōu)化［J］.計(jì)算機(jī)集成制造系統(tǒng)，2011，17（8）：1772-1779.

［4］別黎，崔南方.關(guān)鍵鏈多項(xiàng)目管理中能力約束緩沖大小研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2011，17（7）：1534-1540.

圖1　基于關(guān)鍵鏈的多項(xiàng)目調(diào)度網(wǎng)絡(luò)計(jì)劃圖

［5］別黎，崔南方，趙雁，張小明，等.關(guān)鍵鏈多項(xiàng)目調(diào)度中分散式能力約束緩沖設(shè)置法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2013，27（2）：148-152.

［6］劉士新，宋健海，唐加福.資源受限項(xiàng)目調(diào)度中緩沖區(qū)的設(shè)定方法［J］.系統(tǒng)工程學(xué)報(bào)，2006（4）：381-386.

［7］彭武良，王成恩.關(guān)鍵鏈項(xiàng)目調(diào)度模型及遺傳算法求解［J］.系統(tǒng)工程學(xué)報(bào)，2010，25（1）：123-131.

10.3969/j.issn.1673-0194.2016.17.041

TP391

A

1673-0194（2016）17-0087-03

1引言

2016-05-19則研究了關(guān)鍵鏈在多項(xiàng)目的整體進(jìn)度優(yōu)化中作用。崔南方等則對(duì)關(guān)鍵鏈緩沖區(qū)的尺寸做了一系列的研究。劉士新等也對(duì)關(guān)鍵鏈的緩沖設(shè)定方法進(jìn)行了研究。

關(guān)鍵鏈項(xiàng)目管理法（Critical Chain Project Management. CCPM）是約束理論（Theory of Constraints，TOC）在項(xiàng)目管理中的應(yīng)用。關(guān)鍵鏈法考慮到了人的不良行為因素，消除了存在任務(wù)中的大量的安全時(shí)間，并設(shè)置緩沖區(qū)集中保護(hù)任務(wù)的進(jìn)度。劉士新等提出了一種基于啟發(fā)式規(guī)則的關(guān)鍵鏈調(diào)度方法。李俊亭