《系統(tǒng)網(wǎng)絡(luò)技術(shù)》PPT課件.ppt

系統(tǒng)工程原理,主講：顏兆林 副教授 單 位：信息系統(tǒng)與管理學(xué)院系統(tǒng)工程系一室 E-mail： 電 話：84573540(O)2,第十章 系統(tǒng)網(wǎng)絡(luò)技術(shù),3,引例1：夫妻共度周末，17:00起要做幾件事情： 洗衣服，單獨(dú)一人需3小時完成； 做晚飯，單獨(dú)一人需1小時； 吃晚飯，需0.5小時。 由于已買好電影票，須在19:30前離家去電影院。二人應(yīng)如何安排上述事情？,系統(tǒng)網(wǎng)絡(luò)技術(shù),關(guān)鍵是洗衣服的工作，誤時最長，須設(shè)法改進(jìn)： 串行工作改并行工作； 改變資源分配，支援關(guān)鍵工作； 在關(guān)鍵工作中投入新設(shè)備或搞技術(shù)革新。,4,引例2：某空軍航校有100名學(xué)員要在規(guī)定時間內(nèi)，完成某階段飛訓(xùn)任務(wù)(含多個科目)。訓(xùn)練飛機(jī)有限，天氣狀況也是影響飛行訓(xùn)練的重要因素，使飛行訓(xùn)練完成時間只能是一個區(qū)間估計?，F(xiàn)要制定一個計劃，合理安排各種資源，回答按時完成任務(wù)的概率？ 引例3：安排學(xué)校每學(xué)期的課程計劃表(資源有教室、班級、人數(shù)、課程關(guān)系等)。 引例4：編制一個建筑工程的建設(shè)(施工)計劃。,系統(tǒng)網(wǎng)絡(luò)技術(shù),5,5,1、定義,（1）它把工程開發(fā)過程當(dāng)作一個系統(tǒng)來處理，將組成這個系統(tǒng)的各項具體工作和各個階段按照先后順序，通過網(wǎng)絡(luò)圖的形式，統(tǒng)籌規(guī)劃，全面安排，并對整個系統(tǒng)進(jìn)行科學(xué)的組織、協(xié)調(diào)和控制，以實(shí)現(xiàn)最有效地利用資源，并用最少的時間來完成系統(tǒng)的預(yù)期目標(biāo)。,（2）所謂系統(tǒng)網(wǎng)絡(luò)技術(shù)，就是用網(wǎng)絡(luò)作為數(shù)學(xué)模型來描述系統(tǒng)，以求解系統(tǒng)中的各種實(shí)際問題，達(dá)到用最少的費(fèi)用和時間完成系統(tǒng)的預(yù)期目標(biāo)。,系統(tǒng)網(wǎng)絡(luò)技術(shù),6,系統(tǒng)網(wǎng)絡(luò)技術(shù),儲油罐工程施工計劃甘特圖,7,甘特圖的優(yōu)點(diǎn)：簡單明了；便于檢查施工進(jìn)度。 甘特圖的缺點(diǎn)： 不能清楚表示各項工作間的制約關(guān)系； 關(guān)鍵工作不明了； 難以判斷計劃方案的好壞； 施工條件變化后，修改計劃需要重新繪圖； 不易上機(jī)運(yùn)算。 甘特圖適于簡單工程，對大型復(fù)雜工程難以適用。,系統(tǒng)網(wǎng)絡(luò)技術(shù),2、產(chǎn)生與發(fā)展,8,8,1957年，Dupout 公司開發(fā) CPM ( Critical Path Method )，民用，主要考慮節(jié)約費(fèi)用。,1958年，RAND公司創(chuàng)造PERT(Program Evaluation and Review Technique ) ，軍用，主要著眼于縮短時間。,我們所講的系統(tǒng)網(wǎng)絡(luò)技術(shù) CPM + PERT ，是既要降低成本，又要縮短時間，即最有效地利用資源。,系統(tǒng)網(wǎng)絡(luò)技術(shù),2、產(chǎn)生與發(fā)展,9,9,我國早在60年代初即引進(jìn)了PERT，國防部五院在東風(fēng)導(dǎo)彈型號研制中已成功運(yùn)用并取得了很好的效果。,我國航天總投資只及日本的1/10、法國的1/20、美國的1/300、前蘇聯(lián)的1/480，而如今能穩(wěn)坐世界航天大國的第三把交椅，原因固然是多方面的，但是采用了SE的組織管理方法卻是功不可沒的。,系統(tǒng)網(wǎng)絡(luò)技術(shù),2、產(chǎn)生與發(fā)展,10,10,廣泛應(yīng)用在時間進(jìn)度的科學(xué)安排、資源的合理分配以及費(fèi)用的優(yōu)化等方面。特別適用于一次性的大型科研、生產(chǎn)和工程建設(shè)項目。例如新產(chǎn)品的研制、油田或礦山開發(fā)、建設(shè)施工管理、編制長遠(yuǎn)發(fā)展規(guī)劃等。,凡是越復(fù)雜、越龐大、頭緒眾多、協(xié)調(diào)頻繁、協(xié)作單位多、時間緊迫的工程任務(wù)，使用系統(tǒng)網(wǎng)絡(luò)技術(shù)的作用就越大，效果越顯著。,系統(tǒng)網(wǎng)絡(luò)技術(shù),3、應(yīng)用范圍,11,主要內(nèi)容,10.1 網(wǎng)絡(luò)圖的組成及繪制 10.2 網(wǎng)絡(luò)圖的參數(shù)與計算 10.3 任務(wù)按期完成的概率分析與計算 10.4 網(wǎng)絡(luò)圖的調(diào)整與優(yōu)化,12,主要內(nèi)容,10.1 網(wǎng)絡(luò)圖的組成及繪制 10.1.1 網(wǎng)絡(luò)圖的組成 10.1.2 繪制網(wǎng)絡(luò)圖的基本規(guī)則 10.1.3 網(wǎng)絡(luò)圖繪制步驟 10.1.4 作業(yè)時間的確定,13,10.1.1 網(wǎng)絡(luò)圖的組成,14,10.1.1 網(wǎng)絡(luò)圖的組成,例10-1 組織戰(zhàn)斗的計劃網(wǎng)絡(luò)圖,15,10.1.1 網(wǎng)絡(luò)圖的組成,作業(yè),事項,例10-1 組織戰(zhàn)斗的計劃網(wǎng)絡(luò)圖,16,幾個概念：,1、作業(yè)（工序）泛指需要消耗人力、物力、時間的具體活動。在網(wǎng)絡(luò)圖中用箭桿“ ”表示。,作業(yè)名稱 完成時間,2、事項（結(jié)點(diǎn)）是作業(yè)開始或完工的瞬間階段點(diǎn)，不消耗人力、物質(zhì)、時間，在圖中是前后箭桿的連接點(diǎn)，用“ i ”表示并編上序號。,3、線路 沿箭桿方向順序地連接起、終點(diǎn)事項的通路稱為線路?！奥烽L”指一條線路上各作業(yè)時間之和?！瓣P(guān)鍵線路”(CP)是網(wǎng)絡(luò)圖中路長最長的線路。,4、虛箭桿虛作業(yè)，描述作業(yè)間緊前或緊后關(guān)系。,10.1.1 網(wǎng)絡(luò)圖的組成,17,10.1.2 網(wǎng)絡(luò)圖的繪圖規(guī)則,1、不出現(xiàn)循環(huán)回路； 2、只能有一個起點(diǎn)和一個終點(diǎn)；,18,3、作業(yè)順序的表示：借助虛箭桿,a完工后就可開始c；a、b都完工后，才可開始d。,a,b都完工后就可同時開始c,d。,10.1.2 網(wǎng)絡(luò)圖的繪圖規(guī)則,19,3、作業(yè)順序的表示：借助虛箭桿,a、b、c均完成后，d才可開工。而b、c完工后，e即可開工，所以d、e的開工條件不同，這完全是靠 、 兩點(diǎn)間的虛箭桿幫助實(shí)現(xiàn)的。,4,5,10.1.2 網(wǎng)絡(luò)圖的繪圖規(guī)則,20,10.1.2 網(wǎng)絡(luò)圖的繪圖規(guī)則,4、不出現(xiàn)編號相同的箭桿（即一對結(jié)點(diǎn)之間只能有一條箭桿或虛箭桿）；,21,5、交叉作業(yè)的表示,例如，有三件相同的產(chǎn)品，要求通過a作業(yè)后才能進(jìn)行b作業(yè)，可以有以下兩種安排方法：,交叉作業(yè)：比方法(1)節(jié)約時間。,10.1.2 網(wǎng)絡(luò)圖的繪圖規(guī)則,22,7、網(wǎng)絡(luò)圖應(yīng)盡量采用平行箭桿，以減少箭桿的相互交叉；若交叉實(shí)在不可避免時:,6、應(yīng)嚴(yán)格控制虛箭桿的使用 保證網(wǎng)絡(luò)圖中沒有多余的虛箭桿。,暗橋,斷線,10.1.2 網(wǎng)絡(luò)圖的繪圖規(guī)則,23,8、網(wǎng)絡(luò)圖的分層：復(fù)雜網(wǎng)絡(luò)圖應(yīng)用分級遞階的辦法處理，避免一張圖過分復(fù)雜。,總圖,分圖,10.1.2 網(wǎng)絡(luò)圖的繪圖規(guī)則,24,8、網(wǎng)絡(luò)圖的分層：復(fù)雜網(wǎng)絡(luò)圖應(yīng)用分級遞階的辦法處理，避免一張圖過分復(fù)雜。,網(wǎng)絡(luò)圖的組合,10.1.2 網(wǎng)絡(luò)圖的繪圖規(guī)則,25,10.1.3 網(wǎng)絡(luò)圖的繪制步驟,1、任務(wù)分解,把一個工程分解成若干作業(yè)，并確定作業(yè)間關(guān)系。作業(yè)間的關(guān)系共四種，如圖。,1,2,3,4,5,6,7,先行作業(yè),P1,并行作業(yè),中途作業(yè),P2,后續(xù)作業(yè),任務(wù)分解后列成任務(wù)清單，標(biāo)明作業(yè)名稱、代號、順序及所需時間等。,26,2、畫圖 從初始作業(yè)起，按任務(wù)清單所定順序一支接一支箭桿地從左至右繪制，直到末尾作業(yè)止，并在箭桿分界處畫一個圓圈作為事項。,10.1.3 網(wǎng)絡(luò)圖的繪制步驟,27,3、編號,從起點(diǎn)開始，從左至右，從小至大，到終點(diǎn)為止，依次編號，并且不得出現(xiàn)重復(fù)的編號。,10.1.3 網(wǎng)絡(luò)圖的繪制步驟,28,例10-2將下表所示的熱力管道維修任務(wù)畫成一個網(wǎng)絡(luò)圖。,10.1.3 網(wǎng)絡(luò)圖的繪制步驟,29,1,2,3,4,5,6,7,8,A 3,B 2,C 5,D 3,E 2,F 1,G 1,H 1,10.1.3 網(wǎng)絡(luò)圖的繪制步驟,30,由作業(yè)時間表繪制網(wǎng)絡(luò)圖,網(wǎng)絡(luò)圖？,練習(xí),31,10.1.4 作業(yè)時間的確定,作業(yè)時間估計方法： 一時估計法 三時估計法 平均值法,1、一時估計法 正常情況下，有同類作業(yè)所需時間作參考，可依據(jù)經(jīng)驗估計出一個時間，用t(i, j)表示。,32,2、三時估計法 無可靠資料和經(jīng)驗來確定一個作業(yè)時間，可用下列三種時間的平均值為作業(yè)平均時間tm(i, j)。,a 樂觀時間，順利情況下完成該作業(yè)所需時間；,b 悲觀時間，極不順利情況下完成該作業(yè)所需時間；,c 最可能時間，一般情況下完成該作業(yè)所需時間。,10.1.4 作業(yè)時間的確定,33,3、平均值法,如某任務(wù)進(jìn)行過多次，知其過去的作業(yè)時間分別是a1，a2， ，an，則用算術(shù)平均值 作為本次作業(yè)時間。,10.1.4 作業(yè)時間的確定,34,主要內(nèi)容,10.2 網(wǎng)絡(luò)圖的參數(shù)與計算 10.2.1 結(jié)點(diǎn)的參數(shù)與計算 10.2.2 作業(yè)的時間參數(shù)與計算 10.2.3 關(guān)鍵路線與時差的關(guān)系 10.2.4 網(wǎng)絡(luò)圖參數(shù)的計算方法,35,10.2 網(wǎng)絡(luò)圖的參數(shù)與計算,兩類參數(shù) 事項（結(jié)點(diǎn)）的時間參數(shù)：3個 作業(yè)的時間參數(shù)：6個,36,10.2.1 事項(結(jié)點(diǎn))的時間參數(shù)與計算,1、結(jié)點(diǎn)早始（最早開始）時間 tE(j),從起點(diǎn)到本結(jié)點(diǎn)j的最長時間之和，此前事項不能開始。 起點(diǎn)1：tE(1)=0 其余各結(jié)點(diǎn)均按下式計算：,37,2、結(jié)點(diǎn)遲完（最遲完成）時間tL(i),指結(jié)點(diǎn)i最遲必須完成（結(jié)束）的時間，否則將影響其后續(xù)作業(yè)按時開工。,終點(diǎn)：tL(n)=任務(wù)的總工期（有規(guī)定時） 或 tL(n)=tE(n) （無規(guī)定時） 其余各點(diǎn)按下式計算：,10.2.1 事項(結(jié)點(diǎn))的時間參數(shù)與計算,38,3、結(jié)點(diǎn)的時差S(i),結(jié)點(diǎn)的最遲完成時間減去最早開始時間。,10.2.1 事項(結(jié)點(diǎn))的時間參數(shù)與計算,39,1,2,3,4,5,6,7,B , 5,E , 2,A , 2,C , 3,D 2,F , 3,G , 5,H , 2,I , 4,例10-3計算以下網(wǎng)絡(luò)圖各節(jié)點(diǎn)時間參數(shù),10.2.1 事項(結(jié)點(diǎn))的時間參數(shù)與計算,40,i,j,t(i, j),h,t(h, i),k,t(j, k),10.2.2 作業(yè)的時間參數(shù)與計算,約定：,41,（1）通過其先行作業(yè)計算，從左至右直至終點(diǎn)。,（2）通過其箭尾結(jié)點(diǎn)的早始時間計算。,1、作業(yè)的早始時間tES(i, j),表示該作業(yè)最早何時可開始顯然須等到其先行作業(yè)完工之后才能開始。 兩種計算方法：,10.2.2 作業(yè)的時間參數(shù)與計算,42,2、作業(yè)的早完時間tEF(i, j),表示該作業(yè)最早何時可完成顯然等于最早開始時間加上本作業(yè)所需時間。 兩種計算方法：,10.2.2 作業(yè)的時間參數(shù)與計算,43,3、作業(yè)的遲始時間tLS(i, j),為不影響其后續(xù)作業(yè)如期開始，則每個作業(yè)須有一個最遲開始時間。 兩種計算方法：,10.2.2 作業(yè)的時間參數(shù)與計算,44,4、作業(yè)的遲完時間tLF( i, j ),該作業(yè)最遲應(yīng)何時完成等于最遲開始時間加上本作業(yè)所需時間。 兩種計算方法：,10.2.2 作業(yè)的時間參數(shù)與計算,45,繪制以下作業(yè)清單的網(wǎng)絡(luò)圖:,課堂練習(xí)：網(wǎng)絡(luò)圖的繪制,46,答案：,課堂練習(xí)：網(wǎng)絡(luò)圖的繪制,47,結(jié)點(diǎn)時間參數(shù)： 早始（最早開始）時間 tE(j) 結(jié)點(diǎn)遲完（最遲完成）時間tL(i) 結(jié)點(diǎn)的時差S(i),回顧：結(jié)點(diǎn)的時間參數(shù)與計算,48,作業(yè)時間參數(shù)： 作業(yè)的早始時間tES(i,j) 作業(yè)的早完時間tEF(i,j) 作業(yè)的遲始時間tLS(i,j) 作業(yè)的遲完時間tLF(i,j),回顧：作業(yè)的時間參數(shù)與計算,49,作業(yè)時間參數(shù)： 作業(yè)的早始時間tES(i,j) 作業(yè)的早完時間tEF(i,j) 作業(yè)的遲始時間tLS(i,j) 作業(yè)的遲完時間tLF(i,j),回顧：作業(yè)的時間參數(shù)與計算,50,作業(yè)時間參數(shù)： 作業(yè)的早始時間tES(i,j) 作業(yè)的早完時間tEF(i,j) 作業(yè)的遲始時間tLS(i,j) 作業(yè)的遲完時間tLF(i,j),回顧：作業(yè)的時間參數(shù)與計算,51,作業(yè)時間參數(shù)： 作業(yè)的早始時間tES(i,j) 作業(yè)的早完時間tEF(i,j) 作業(yè)的遲始時間tLS(i,j) 作業(yè)的遲完時間tLF(i,j),回顧：作業(yè)的時間參數(shù)與計算,52,5、作業(yè)的總時差 R(i , j),作業(yè)(i, j)，如在tES(i, j)開始，耗時t(i, j)，則定能在tEF(i, j)時完成；作業(yè)(i, j)又有一個tLF(i, j)，只要不超過tLF(i, j)完工就不會拖延總工期。故作業(yè)(i, j)的安排有一定回旋余地，即作業(yè)的總時差:,10.2.2 作業(yè)的時間參數(shù)與計算,53,10.2.2 作業(yè)的時間參數(shù)與計算,54,i,j,作業(yè) A,k,作業(yè) B,tES tLS A tEF tLF,tES tLS B tEF tLF,R(A),R(B),10.2.2 作業(yè)的時間參數(shù)與計算,R(i, j)=0時，稱作業(yè) (i, j)為“關(guān)鍵作業(yè)”。,55,R(i, j)0時，作業(yè) (i, j)可作兩種機(jī)動即其“時差調(diào)用”兩種方式： （1）適當(dāng)推遲開工時間：只要不超過遲始時間； （2）適當(dāng)放慢進(jìn)度延長作業(yè)時間：增量不超過R(i, j). 記調(diào)用量為(i, j)，調(diào)用原則為 (i, j)R(i, j),10.2.2 作業(yè)的時間參數(shù)與計算,56,r(i, j)：不影響后續(xù)作業(yè)早始時間的前提下，本作業(yè)(i , j) 可自由利用的機(jī)動時間范圍。,6、作業(yè)的單時差,i,j,作業(yè) A,k,作業(yè) B,tES tLS A tEF tLF,tES tLS B tEF tLF,r(A),10.2.2 作業(yè)的時間參數(shù)與計算,57,r(i, j)：不影響后續(xù)作業(yè)早始時間的前提下，本作業(yè)(i , j) 可自由利用的機(jī)動時間范圍。,6、作業(yè)的單時差,10.2.2 作業(yè)的時間參數(shù)與計算,58,r(i, j)與R(i, j)的關(guān)系：,i,j,作業(yè) A,k,作業(yè) B,tES tLS A tEF tLF,tES tLS B tEF tLF,R(A),r(A),10.2.2 作業(yè)的時間參數(shù)與計算,59,（1）關(guān)鍵結(jié)點(diǎn)(事項)：時差為0的結(jié)點(diǎn)（事項）； （2）關(guān)鍵作業(yè) ：總時差為0的作業(yè)； （3）關(guān)鍵路線 (CP)：從起點(diǎn)到終點(diǎn)，由關(guān)鍵作業(yè)連成的通路。常用粗線、雙線或紅色線表示。,10.2.3 關(guān)鍵路線與時差的關(guān)系,1、幾個定義,60,關(guān)鍵路線(CP)的意義： 要縮短總工期須減少CP上作業(yè)時間，因CP上作業(yè)時間之和決定了總工期。 網(wǎng)絡(luò)圖的CP 可能有多條，CP越多，表明各項作業(yè)的周期都很緊張。故須加強(qiáng)管理、嚴(yán)格控制，才能保證任務(wù)按期完成。,10.2.3 關(guān)鍵路線與時差的關(guān)系,61,2、CP與時差關(guān)系的三定理,【定理1】 的前提下，對網(wǎng)絡(luò)圖的所有作業(yè)均有： 且當(dāng) 為關(guān)鍵結(jié)點(diǎn)時， 特別地，有,10.2.3 關(guān)鍵路線與時差的關(guān)系,62,【定理2】CP上全部結(jié)點(diǎn)的時差為零，反之不真。,2、CP與時差關(guān)系的三定理,這個定理只是提供確定CP的必要條件，而非充分必要條件。這是對美國和國內(nèi)以往部分教科書的一個重要的原則性的修正。,10.2.3 關(guān)鍵路線與時差的關(guān)系,63,上世紀(jì)80年代中期前的美國教科書曾經(jīng)錯誤指出：“時差為零的結(jié)點(diǎn)連成的通路就是CP”。受此影響，我國也有不少教科書重復(fù)了這個錯誤。,中國人大的管理SEP.201：“時差為零的事項是關(guān)鍵事項，將其串聯(lián)起來就是所求的CP?！?清華的運(yùn)籌學(xué)P.342：“由事項時差為零的那些 事項所組成的路線就是CP?！?1990年再版時已糾正) 南京大學(xué)的工業(yè)企業(yè)生產(chǎn)管理P.98：“將時差為 0的事項串聯(lián)起來就可得到CP?！?哈工大姚德明主編的管理SEP.179：“CP即為各關(guān)鍵結(jié)點(diǎn)的連線。”,10.2.3 關(guān)鍵路線與時差的關(guān)系,64,2、CP與時差關(guān)系的三定理,【定理3】在CP上，全部作業(yè)的總時差均為零，反之亦真。,10.2.3 關(guān)鍵路線與時差的關(guān)系,65,兩種計算方法 圖上計算法 ：用公式計算結(jié)點(diǎn)和作業(yè)時間參數(shù)，將結(jié)果用適當(dāng)?shù)姆枠?biāo)注在圖上。 表格計算法：用作業(yè)關(guān)系列表計算時間參數(shù)。,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,66,【例10-4】圖上計算法 某工程由A，B， ，I共9道作業(yè)組成，作業(yè)的前后關(guān)系和時間估計值如下表所示，請畫出該工程的網(wǎng)絡(luò)圖并確定其CP。,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,67,時間單位：天,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,例10-4,68,1,2,3,4,5,6,7,B,E,A,C,D,F,G,H,I,解： （1）畫出網(wǎng)絡(luò)圖如下：,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,69,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,（2）用三時估計法計算作業(yè)的平均時間 tm,70,1,2,3,4,5,6,7,B , 5,E , 2,A , 2,C , 3,D 2,F , 3,G , 5,H , 2,I , 4,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,71,（3）計算 tE(j),利用公式,從起點(diǎn) 開始，從左向右，逐個結(jié)點(diǎn)地計算，直至終點(diǎn) 為止，計算結(jié)果填入結(jié)點(diǎn)近旁所畫符號 內(nèi)。,1,7,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,72,1,2,3,4,5,6,7,B , 5,E , 2,A , 2,C , 3,D 2,F , 3,G , 5,H , 2,I , 4,節(jié)點(diǎn)的早始時間,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,73,（4）計算 tL(i),利用公式,從終點(diǎn) 開始，從右向左，逐點(diǎn)計算，直至起點(diǎn) 為止，其計算結(jié)果填入結(jié)點(diǎn)近旁所畫的符號 內(nèi)。,7,1,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,74,1,2,3,4,5,6,7,B , 5,E , 2,A , 2,C , 3,D 2,F , 3,G , 5,H , 2,I , 4,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,75,（5）計算 R(i , j),利用公式,對每個作業(yè)進(jìn)行計算，并將結(jié)果標(biāo)注在箭桿近旁所畫的符號 內(nèi)。,這種計算也可形象化地表示為,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,76,1,2,3,4,5,6,7,0,0,B , 5 0,E , 2 5,A , 2 2,C , 3 2,0 D 2,F , 3 0,G , 5 2,H , 2 5,I , 4 0,7,7,14,14,2,4,5,5,7,12,10,10,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,77,（6）計算 r( i , j),利用公式,對每個作業(yè)進(jìn)行計算，并將結(jié)果標(biāo)注在箭桿近旁所畫的符號（ ）內(nèi)。 此計算也可形象化地表示為,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,78,1,2,3,4,5,6,7,0,0,B , 5 0,E , 2 5,A , 2 2,C , 3 2,0 D 2,F , 3 0,G , 5 2,H , 2 5,I , 4 0,7,7,14,14,2,4,5,5,7,12,10,10,(0),(0),(2),(0),(0),(0),(2),(5),(0),10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,79,（7）將R(i , j)0的作業(yè)全部加粗或用紅線串聯(lián)起來形成通路，就得到CP為,1,2,3,4,5,6,7,0,0,B , 5 0 (0),E , 2 5 (0),A , 2 2 (0),C , 3 2 (2),0 D (0) 2,F , 3 0 (0),G , 5 2 (2),H , 2 5 (5),I , 4 0 (0),7,7,14,14,2,4,5,5,7,12,10,10,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,80,圖上計算法流程,開始 tE(1)=0,j=n ?,i=1 ?,CP: R(i , j)=0的作業(yè)連線,否,是,否,是,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,81,1,2,3,4,5,6,7,0,0,B , 5 0 (0),E , 2 5 (0),A , 2 2 (0),C , 3 2 (2),0 D (0) 2,F , 3 0 (0),G , 5 2 (2),H , 2 5 (5),I , 4 0 (0),7,7,14,14,2,4,5,5,7,12,10,10,對前述三定理的驗證： （1）所有作業(yè)均有 0 r(i, j)R(i, j)，且關(guān)鍵作業(yè)B、D、F、I 均滿足：r(i, j)R(i, j)0,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,82,1,2,3,4,5,6,7,0,0,B , 5 0 (0),E , 2 5 (0),A , 2 2 (0),C , 3 2 (2),0 D (0) 2,F , 3 0 (0),G , 5 2 (2),H , 2 5 (5),I , 4 0 (0),7,7,14,14,2,4,5,5,7,12,10,10,（2）CP上全部結(jié)點(diǎn)時差均為0，反之不真。如由關(guān)鍵結(jié)點(diǎn) 1 3 4 7 連成的通路并非CP。,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,83,1,2,3,4,5,6,7,0,0,B , 5 0 (0),E , 2 5 (0),A , 2 2 (0),C , 3 2 (2),0 D (0) 2,F , 3 0 (0),G , 5 2 (2),H , 2 5 (5),I , 4 0 (0),7,7,14,14,2,4,5,5,7,12,10,10,（3）CP上全部作業(yè)的總時差均為0，反之亦真。（即由關(guān)鍵作業(yè)連成的通路一定是CP）,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,84,例10-5表格法,解： （1）作一個規(guī)范的表格,1 2 3 4 5 6 7 8 9,作業(yè),i,j,作業(yè) 時間 t(i,j),早始 時間 tES,早完 時間 tEf,遲始 時間 tLS,遲完 時間 tLF,總時差 R,單時差 r,關(guān)鍵 作業(yè),3+2,5+2,5-3,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,（2）填表格：按順序自上而下逐行填寫表格的第1、2列,1 2 3 4 5 6 7 8 9,作業(yè),i,j,作業(yè) 時間 t(i,j),早始 時間 tES,早完 時間 tEF,遲始 時間 tLS,遲完 時間 tLF,總時差 R,單時差 r,關(guān)鍵 作業(yè),3+2,5+2,5-3,1,2,1,3,2,4,3,4,3,5,4,6,4,7,5,7,6,7,2 5 3 2 2 3 5 2 4,86,（3）在表上計算參數(shù) （a）計算tES和tEF：第3、4列由上至下一行一行地計算。先算第3列，第4列的數(shù)字是第3列和第2列的同行數(shù)字之和。 （b）計算tLS和tLF：第5列計算從終點(diǎn)算起，由下往上逐個進(jìn)行。第6列是第2列與第5列之和。 （c）計算R和r：第7列的R由各作業(yè)的第5列數(shù)字與第3列數(shù)字相減求得。第8列的作業(yè)單時差r由后續(xù)作業(yè)的早始時間減去所算作業(yè)的早完時間而求得的。 （d）標(biāo)出關(guān)鍵作業(yè)：將第7列中R為0的作業(yè)標(biāo)在第9列中，串聯(lián)第9列的作業(yè)構(gòu)成關(guān)鍵路線。,10.2.4 網(wǎng)絡(luò)圖時間參數(shù)的計算方法,（3）在表上計算參數(shù),1 2 3 4 5 6 7 8 9,作業(yè),i,j,作業(yè) 時間 t(i,j),早始 時間 tES,早完 時間 tEf,遲始 時間 tLS,遲完 時間 tLF,總時差 R,單時差 r,關(guān)鍵 作業(yè),3+2,5+2,5-3,1,2,1,3,2,4,3,4,3,5,4,6,4,7,5,7,6,7,2 5 3 2 2 3 5 2 4,0 0 2 5 5 7 7 7 10,2 5 5 7 7 10 12 9 14,2 0 4 5 10 7 9 12 10,4 5 7 7 12 10 14 14 14,2 0 2 0 5 0 2 5 0,0 0 2 0 0 0 2 5 0,1,3,3,4,4,6,6,7,88,課堂練習(xí),據(jù)以下任務(wù)清單確定工程的關(guān)鍵路線（單位：周）,89,課堂練習(xí),90,課堂練習(xí),91,結(jié)點(diǎn)時間參數(shù)： 早始（最早開始）時間 tE(j) 結(jié)點(diǎn)遲完（最遲完成）時間tL(i) 結(jié)點(diǎn)的時差S(i),回顧：結(jié)點(diǎn)的時間參數(shù)與計算,92,作業(yè)時間參數(shù)： 作業(yè)的早始時間tES(i,j) 作業(yè)的早完時間tEF(i,j) 作業(yè)的遲始時間tLS(i,j) 作業(yè)的遲完時間tLF(i,j),回顧：作業(yè)的時間參數(shù)與計算,93,作業(yè)時間參數(shù)： 作業(yè)的早始時間tES(i,j) 作業(yè)的早完時間tEF(i,j) 作業(yè)的遲始時間tLS(i,j) 作業(yè)的遲完時間tLF(i,j),回顧：作業(yè)的時間參數(shù)與計算,94,作業(yè)時間參數(shù)： 作業(yè)的早始時間tES(i,j) 作業(yè)的早完時間tEF(i,j) 作業(yè)的遲始時間tLS(i,j) 作業(yè)的遲完時間tLF(i,j),回顧：作業(yè)的時間參數(shù)與計算,95,作業(yè)時間參數(shù)： 作業(yè)的早始時間tES(i,j) 作業(yè)的早完時間tEF(i,j) 作業(yè)的遲始時間tLS(i,j) 作業(yè)的遲完時間tLF(i,j),回顧：作業(yè)的時間參數(shù)與計算,96,5、作業(yè)的總時差 R(i , j),作業(yè)(i, j)，如在tES(i, j)開始，耗時t(i, j)，則定能在tEF(i, j)時完成；作業(yè)(i, j)又有一個tLF(i, j)，只要不超過tLF(i, j)完工就不會拖延總工期。故作業(yè)(i, j)的安排有一定回旋余地，即作業(yè)的總時差:,10.2.2 作業(yè)的時間參數(shù)與計算,97,10.2.2 作業(yè)的時間參數(shù)與計算,98,i,j,作業(yè) A,k,作業(yè) B,tES tLS A tEF tLF,tES tLS B tEF tLF,R(A),R(B),10.2.2 作業(yè)的時間參數(shù)與計算,R(i, j)=0時，稱作業(yè) (i, j)為“關(guān)鍵作業(yè)”。,99,總時差與單時差的關(guān)系：,i,j,作業(yè) A,k,作業(yè) B,tES tLS A tEF tLF,tES tLS B tEF tLF,R(A),r(A),回顧,100,（1）關(guān)鍵作業(yè) ：總時差為0的作業(yè)； （2）關(guān)鍵路線 (CP)：從起點(diǎn)到終點(diǎn)，由關(guān)鍵作業(yè)連成的通路。 （3）總時差與關(guān)鍵路線關(guān)系的三個定理。,回顧,101,主要內(nèi)容,10.3 任務(wù)按期完成的概率分析與計算 10.3.1 任務(wù)完成時間近似符合正態(tài)分布規(guī)律 10.3.2 任務(wù)按期完成的概率計算,102,“中心極限定理”： 凡是由許多微小的、相互獨(dú)立的變量之和構(gòu)成的隨機(jī)變量，可當(dāng)作正態(tài)分布來處理。,10.3.1 任務(wù)完成時間近似符合正態(tài)分布,103,Liapunov中心極限定理 隨機(jī)變量X1，Xn相互獨(dú)立，有期望和方差：,記,則在一定條件下，隨機(jī)變量,近似服從標(biāo)準(zhǔn)正態(tài)分布N(0,1)。,10.3.1 任務(wù)完成時間近似符合正態(tài)分布,104,據(jù)此，可認(rèn)為計劃完工時間服從標(biāo)準(zhǔn)正態(tài)分布。只要計算每個作業(yè)預(yù)計完工時間的均值和方差，給出整個工程任務(wù)是否按期完成的概率，分析計劃的可行性。,10.3.1 任務(wù)完成時間近似符合正態(tài)分布,105,是作業(yè)的平均時間，與三個估計時間參數(shù)有關(guān)；,1、作業(yè)時間的平均值,2、作業(yè)時間的標(biāo)準(zhǔn)差與方差,標(biāo)準(zhǔn)差 方差,10.3.1 任務(wù)完成時間近似符合正態(tài)分布,106,3、任務(wù)完成時間,據(jù)“中心極限定理” ，任務(wù)最后完成時間是一個平均值為 標(biāo)準(zhǔn)差為 的正態(tài)分布。,10.3.1 任務(wù)完成時間近似符合正態(tài)分布,107,10.3.2 任務(wù)按期完成的概率計算,1、計算方法,為計算概率，需引入一個概率因子 z ，以便查正態(tài)分布表。概率,式中：tL為終點(diǎn)的遲完時間； tE為終點(diǎn)的早始時間； CP是關(guān)鍵路線上方差和的平方根，也稱終點(diǎn)的標(biāo)準(zhǔn)差。 是關(guān)鍵路線上各作業(yè)的方差。,108,若規(guī)定了計劃完成時間，則終點(diǎn)的 tL就用此時間。因 tE 已知， CP 可以計算出來，故概率因子可用 算到。有z后查正態(tài)分布表就可得相應(yīng)概率 p(z) 。,10.3.2 任務(wù)按期完成的概率計算,109,2、應(yīng)用舉例,例10-6某工程由A 、B 、 、H 8道作業(yè)組成，作業(yè)的前后關(guān)系和時間估計值如下表所示。 （1）計算該工程按時完工的概率。 （2）如規(guī)定工期20.8 周，計算完工概率。 （3）如要求完工概率為72，工期應(yīng)定多少周？ （4）如要求工期17.2 周，計算完工概率。,10.3.2 任務(wù)按期完成的概率計算,110,作業(yè)代號 A B C D E F G H,先行作業(yè) B A C A , D E , F,悲觀時間 2 8 8 11 8 14 10 10,最可能時間 2 2 4 4 7 7 8 6,樂觀時間 2 2 3 3 6 6 6 5,時間單位：周,10.3.2 任務(wù)按期完成的概率計算,111,作業(yè)代號 A B C D E F G H,先行作業(yè) B A C A , D E , F,悲觀時間 2 8 8 11 8 14 10 10,最可能時間 2 2 4 4 7 7 8 6,樂觀時間 2 2 3 3 6 6 6 5,平均時間 2 3 4.5 5 7 8 8 6.5,解： 1.三時估計法算作業(yè)平均時間 tm 。,10.3.2 任務(wù)按期完成的概率計算,112,2.畫出該工程的網(wǎng)絡(luò)圖如下。得到CP為 ，可知按時完工時間 tL(7)=19 周。,A , 2 3.5,B , 3 3,C , 4.5 0,D , 5 3,E , 6 3.5,F , 8 0,G , 8 3,H , 6.5 0,0,0,3,6,2,5.5,4.5,4.5,8,11,12.5,12.5,19,19,10.3.2 任務(wù)按期完成的概率計算,113,3.計算CP上各作業(yè)的方差和e2 與標(biāo)準(zhǔn)離差CP,作業(yè)代號 C F H,悲觀時間 8 14 10,最可能時間 4 7 6,樂觀時間 3 6 5,10.3.2 任務(wù)按期完成的概率計算,114,(1)計算按時完工的概率,查正態(tài)分布表得p=0.50，即按時完工的概率為50.,10.3.2 任務(wù)按期完成的概率計算,115,(2)20.8周完工的概率計算,以 tL=20.8 代入得,查正態(tài)分布表得 p=0.8413 ，即完工的可能性為84.13 。,10.3.2 任務(wù)按期完成的概率計算,116,(3)如要求完工概率為72 查正態(tài)分布表得 z= 0.58 ，則 tL= tE+ z CP = 19 + 0.581.8=20（周） 即此時應(yīng)規(guī)定總工期為20周。,10.3.2 任務(wù)按期完成的概率計算,117,(4)若規(guī)定總工期為17.2周，即以 tL=17.2 代入得,可見，此時完工的概率只有 15.87 。,10.3.2 任務(wù)按期完成的概率計算,118,3、任務(wù)按時完成的討論,若時差tL- tE =0，則 z=0，p=0.5 ，完成任務(wù)的概率為50；,tL- tE 0，則完成任務(wù)的概率大于50 ；,tL- tE =3CP，則按時完工的概率為99.9 ；,tL- tE -3CP，則按時完工的概率為0.1 ；,管理者可根據(jù)時差和標(biāo)準(zhǔn)差來判斷按時完成任務(wù)的可能性。,10.3.2 任務(wù)按期完成的概率計算,119,3、任務(wù)按時完成的討論,一般當(dāng)任務(wù)在指定日期完成的概率 p(z) 滿足： 0.3 p(z) 0.7,則表示按此網(wǎng)絡(luò)執(zhí)行計劃在指定日期完成是可能的，比較合適。計劃定得既先進(jìn)又留有充分余地，說明此時網(wǎng)絡(luò)計劃工作已完成，可以組織實(shí)施。,10.3.2 任務(wù)按期完成的概率計算,120,原定義：用確定性作業(yè)時間，再用“作業(yè)總時差為0”的標(biāo)準(zhǔn)確定關(guān)鍵路線，其相當(dāng)于在以1/2的概率按期完成任務(wù)的條件下，確定的關(guān)鍵路線。,確切提法：給定預(yù)計完成日期，在所有線路中，依預(yù)計日期完成的可能性最小的才是關(guān)鍵路線。,關(guān)鍵路線定義的重新評價,121,課堂練習(xí),某工程由A,I九道作業(yè)組成，其關(guān)系及作業(yè)時間估計值如下。繪出該工程的計劃網(wǎng)絡(luò)圖，求工期不遲于50天的概率，及比期望工期提前4天的概率。,期望工期：tL(8)=45天 要求不遲于50天完工，z=1.67,P=0.9525,提前4天， P=0.0918,124,教材P274，第3、4題,作業(yè),125,回顧,網(wǎng)絡(luò)圖的繪制 結(jié)點(diǎn)和作業(yè)時間參數(shù)的計算 關(guān)鍵路線的確定 完工的可行性分析,126,引子,編制工作計劃時，一般很難在最初方案中得到完全合理的指標(biāo)，用系統(tǒng)網(wǎng)絡(luò)技術(shù)也如此。通常初始方案制定后，需進(jìn)行調(diào)整和優(yōu)化，使計劃符合要求。,127,引子,網(wǎng)絡(luò)圖調(diào)整和優(yōu)化的主要內(nèi)容： 工期優(yōu)化：縮短計劃工期； 資源優(yōu)化：工期不變，減少資源(人、物、財)； 資源均衡：降低資源需要量高峰，使其均衡； 成本優(yōu)化：縮短工期且使費(fèi)用增加最少。,128,主要內(nèi)容,10.4 網(wǎng)絡(luò)圖的調(diào)整與優(yōu)化 10.4.1 縮短網(wǎng)絡(luò)計劃工期 10.4.2 時間-費(fèi)用分析與優(yōu)化 10.4.3 時間-資源優(yōu)化,129,縮短工期的手段： 在CP上找最有利的作業(yè)縮短其時間。 技術(shù)革新、增加資源投入，縮短作業(yè)時間。 從非關(guān)鍵路線上調(diào)用時差，縮短CP時間。 可能時用平行作業(yè)或交叉作業(yè)來縮短工期。,10.4.1 縮短網(wǎng)絡(luò)計劃工期,130,10.4.2 時間-費(fèi)用分析與優(yōu)化,在時間進(jìn)度優(yōu)化中，重點(diǎn)在于如何縮短工期。 工期的縮短與費(fèi)用是密切相關(guān)。 網(wǎng)絡(luò)計劃的優(yōu)化中，應(yīng)考慮不同的完工時間所對應(yīng)的工程費(fèi)用。 找到工程費(fèi)用最低的完工時間(最低成本日程)。,131,時間,費(fèi)用,趕工時間,正常時間,直接費(fèi)用,間接費(fèi)用,最優(yōu)完 工時間,工程總費(fèi)用,10.4.2 時間-費(fèi)用分析與優(yōu)化,132