試談PERT網(wǎng)絡(luò)圖的計(jì)算

1、運(yùn)籌學(xué)劉東南第二節(jié)第二節(jié) PERT網(wǎng)絡(luò)圖的計(jì)算網(wǎng)絡(luò)圖的計(jì)算v 例例1：某：某PERT網(wǎng)絡(luò)圖如下：網(wǎng)絡(luò)圖如下：v 四條路線四條路線v 1-2-3-5-8：13v 1-2-4-6-7-8：17v 1-2-6-7-8：12v 1-2-3-4-6-7-8：21關(guān)鍵線路決定工期，各項(xiàng)工作有輕重緩急之分。關(guān)鍵線路決定工期，各項(xiàng)工作有輕重緩急之分。158236474523421342運(yùn)籌學(xué)劉東南一、作業(yè)時(shí)間一、作業(yè)時(shí)間t(i,j)的確定的確定 完成某一工序所需要的時(shí)間完成某一工序所需要的時(shí)間（1）確定型）確定型 資源確定，時(shí)間可確定計(jì)算資源確定，時(shí)間可確定計(jì)算（2）概率型（三點(diǎn)時(shí)間估計(jì)）概率型（三點(diǎn)時(shí)間估計(jì)

2、）樂觀時(shí)間：在順利情況下，完成工序所樂觀時(shí)間：在順利情況下，完成工序所需要的最少時(shí)間，常用符號(hào)需要的最少時(shí)間，常用符號(hào)a表示；表示；最可能時(shí)間：在正常情況下，完成工序最可能時(shí)間：在正常情況下，完成工序所需要的時(shí)間，常用符號(hào)所需要的時(shí)間，常用符號(hào)m表示；表示；悲觀時(shí)間：在不順利情況下，完成工序悲觀時(shí)間：在不順利情況下，完成工序所需要的最多時(shí)間，常用符合所需要的最多時(shí)間，常用符合b表示。表示。運(yùn)籌學(xué)劉東南二、事項(xiàng)時(shí)間參數(shù)二、事項(xiàng)時(shí)間參數(shù)(1)事項(xiàng)最早時(shí)間事項(xiàng)最早時(shí)間(后面工作的最早可能開工后面工作的最早可能開工時(shí)間時(shí)間)tE(i)：與事項(xiàng)：與事項(xiàng)j相鄰的各緊前事項(xiàng)的最早時(shí)相鄰的各緊前事項(xiàng)的最早時(shí)間

3、。間。tE(n)=總最早完工期?？傋钤缤旯て?。從前向后計(jì)算，取大值從前向后計(jì)算，取大值(1)0Et( ) ( )( , )maxEEitjtit i j運(yùn)籌學(xué)劉東南（2）事項(xiàng)最遲時(shí)間）事項(xiàng)最遲時(shí)間(后面工作的最遲必須開后面工作的最遲必須開工時(shí)間工時(shí)間) tL(j)：與事項(xiàng)：與事項(xiàng)i相鄰的各緊后事項(xiàng)的最遲時(shí)間。相鄰的各緊后事項(xiàng)的最遲時(shí)間。確定工期，從右向左計(jì)算取小值。確定工期，從右向左計(jì)算取小值。 ( )( )LEtntn 總工期或( ) ( )( , )minLLjtitjt i j運(yùn)籌學(xué)劉東南三、工作的時(shí)間參數(shù)三、工作的時(shí)間參數(shù)1.最早可能開工時(shí)間與最早可能完工時(shí)間。最早可能開工時(shí)間與最早可

4、能完工時(shí)間。 tES(i,j)（i事項(xiàng)最早時(shí)間）事項(xiàng)最早時(shí)間）， tEF(i,j)(1, )0( , )max( , )( , )( , )( , )( , )ESESESEFEStjti jtk it k iti jti jt i j1.所有從總開工事項(xiàng)出發(fā)的工作所有從總開工事項(xiàng)出發(fā)的工作(1,j),其最早可能開工時(shí)間其最早可能開工時(shí)間=0；2.任一工作任一工作(i,j)其最早可能開工時(shí)間其最早可能開工時(shí)間,要與它的所有的緊前工要與它的所有的緊前工作（作（k,i）的最早開工時(shí)間決定；）的最早開工時(shí)間決定；3.工作工作(i,j)其最早完工時(shí)間等于其最早開工時(shí)間與工時(shí)之和。其最早完工時(shí)間等于其最

5、早開工時(shí)間與工時(shí)之和。運(yùn)籌學(xué)劉東南2.最遲必須開工時(shí)間與最遲必須完工時(shí)間。最遲必須開工時(shí)間與最遲必須完工時(shí)間。 tLS(i,j)， tLF(i,j)(j事項(xiàng)最遲時(shí)間事項(xiàng)最遲時(shí)間)( , )( , )( , )min( , )( , )( , )( , )( , )LFEFLSLSLFLSti nti nti jtj kt i jti jti jt i j或總完工期1. 總完工事項(xiàng)的工作總完工事項(xiàng)的工作(i,n),其最遲完工時(shí)間其最遲完工時(shí)間=預(yù)定總工期或者預(yù)定總工期或者等于這個(gè)工作的最早可能完工時(shí)間；等于這個(gè)工作的最早可能完工時(shí)間；2.任一工作任一工作(i,j)其最遲必須開工時(shí)間其最遲必須開工

6、時(shí)間,要與它的所有的緊后工要與它的所有的緊后工作（作（j,k）的最遲開工時(shí)間決定；）的最遲開工時(shí)間決定；3.工作工作(i,j)其最遲完工時(shí)間等于其最遲開工時(shí)間與工時(shí)之和。其最遲完工時(shí)間等于其最遲開工時(shí)間與工時(shí)之和。運(yùn)籌學(xué)劉東南四、時(shí)差：工作的機(jī)動(dòng)時(shí)間或富裕時(shí)間四、時(shí)差：工作的機(jī)動(dòng)時(shí)間或富裕時(shí)間（1）工作總時(shí)差）工作總時(shí)差 不影響總工期的最多機(jī)動(dòng)時(shí)間。某工作可以不影響總工期的最多機(jī)動(dòng)時(shí)間。某工作可以延遲其開工時(shí)間的最大幅度。延遲其開工時(shí)間的最大幅度。（2）工作單時(shí)差）工作單時(shí)差 不影響緊后工作的最早開工時(shí)間。不影響緊后工作的最早開工時(shí)間。( , )( , )( , )( , )( , )LFEF

7、LSESR i jti jti jti jti j( , )( , )( , )( )( , )( , )( , )( , )( , )ESEFEESESESr i jtj kti jtjt i jti jtj kti jt i j運(yùn)籌學(xué)劉東南 工作及時(shí)差關(guān)系工作及時(shí)差關(guān)系工作工作AES工作工作A的緊后工作的緊后工作ESEFLFLFEFLSLS總時(shí)差總時(shí)差單時(shí)差單時(shí)差(自由浮動(dòng)自由浮動(dòng))運(yùn)籌學(xué)劉東南v五、時(shí)間參數(shù)的圖上計(jì)算法五、時(shí)間參數(shù)的圖上計(jì)算法運(yùn)籌學(xué)劉東南v 例例2189723106544683223825100410182023232531323231262323201810400441

8、01820232323232531010041513182029232324263110tEStLSRr001100000013611001100006130100( , )( , )( , )( )( , )( , )( , )( , )( , )ESEFEESESESr i jtj kti jtjt i jti jtj kti jt i j運(yùn)籌學(xué)劉東南六、表上計(jì)算法六、表上計(jì)算法見下表見下表 原則：原則：工作的排列應(yīng)嚴(yán)格按照箭尾事項(xiàng)工作的排列應(yīng)嚴(yán)格按照箭尾事項(xiàng)編號(hào)由小到大的順序排列，箭尾事項(xiàng)相編號(hào)由小到大的順序排列，箭尾事項(xiàng)相同的工作，按其箭頭事項(xiàng)有小到大排列。同的工作，按其箭頭事項(xiàng)有小到

9、大排列。運(yùn)籌學(xué)劉東南工作工作工作工時(shí)工作工時(shí)t(i,j)最早開工最早開工tES(i,j)最早完工最早完工tEF(i,j)最遲開工最遲開工tLS(i,j)最遲完工最遲完工tLF(i,j)總時(shí)差總時(shí)差R(i,j)單時(shí)差單時(shí)差r(i,j)關(guān)鍵工作關(guān)鍵工作箭尾箭尾i箭頭箭頭j1234567891041063823022851040104104 71018 18 20 2023 23 23 23 25 23 25 23 3125 3031323231312631232624312923232320201818101815104231340013011000061010013011000060010*運(yùn)籌學(xué)劉東南關(guān)鍵線路的確定關(guān)鍵線路的確定 圖上標(biāo)注法圖上標(biāo)注法15387642AHELKGDFCB60451810204015302535060708010