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

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

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

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

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

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

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

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

2.1算法設(shè)計

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

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

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

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

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

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

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

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

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

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

（2）初始化時間段，tg=1

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

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

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

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

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

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

3　實例驗證

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

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

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

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

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

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

4　結(jié)語

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

主要參考文獻

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

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

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

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

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

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

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

［7］彭武良，王成恩.關(guān)鍵鏈項目調(diào)度模型及遺傳算法求解［J］.系統(tǒng)工程學報，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)鍵鏈在多項目的整體進度優(yōu)化中作用。崔南方等則對關(guān)鍵鏈緩沖區(qū)的尺寸做了一系列的研究。劉士新等也對關(guān)鍵鏈的緩沖設(shè)定方法進行了研究。

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