《专案排程模型课件.ppt》由会员分享，可在线阅读，更多相关《专案排程模型课件.ppt（73页珍藏版）》请在三一办公上搜索。
1、1,CHAPTER 5,專案排程模型Project Scheduling Models,2,專案(project)昰一組必須完成的工作組合，目標是以最少的時間或最低之成本來完成專案排程的目標(p.323)藉由計算各活動開始及完成的最早與最晚時間，儘早完成專案計算一個專案在某一期間內完成之可能性.發現在某一日期能以最小成本完成之專案排程控制專案進度是否按時進行，並在預算以內,5.1 介紹(p.322),3,專案排程的目標(p.323)調查某些活動得延誤如何影響一個專案整體的完成時間調整整個專案期間之資源分配專案中工作(Tasks)稱為”活動”(activities).每個活動皆有預估的完成時間(
2、Estimated completion time)活動完成時與投入該活動之資源多寡有關,5.1 介紹,4,5.2 確定專案中之活動,為了決定最佳排程，我們需要確定所有專案中之活動決定活動之先後順序(precedence)藉由這些資訊，我們便可以發展專案管理之方法,5,確定專案活動範例(p.323325)科隆電腦公司(KLONE COMPUTERS,INC.),KLONE Computers 製造個人電腦KLONE Computers需要設計、製造對其產品Klonepalm 2000進行行銷活動三個主要的工作:製造新電腦訓練員工與銷售員代表.廣告行銷 KLONE需要發展先後順序流程圖來顯示各活
3、動間之先後順序關係,6,活動敘述 A設計原型(Prototype model)B材料購買製造活動C原型製造 D設計修正E 第一次生產,F員工訓練訓練活動G員工對產品原型之建議H銷售人員訓練,廣告活動 I生產前廣告活動 J生產後廣告活動,科隆電腦公司活動敘述(p.324),7,由前頁之活動敘述表中,我們可以決定每個活動之前置活動(immediate predecessors).,科隆電腦公司,8,活動前後關係表(表5.3)(p.325)(Precedence Relationships Chart),科隆電腦公司,9,科隆電腦公司 PERT/CPM網路,A90,B15,C5,F25,I30,G1
4、4,D20,E21,H28,J45,10,5.3 專案排程的PERT/CPM 方法,專案排程的PERT/CPM 方法為網路表達方式反應出各個活動之間的先後關係活動完成時間PERT/CPM 方法之目標是希望專案完成時間為最短,11,科隆電腦公司-續,科隆電腦公司管理者希望安排活動計劃使得專案完成時間為最短管理者希望知道:(p.326)此專案之最早完成時間在此日期之下，每個活動之最早與最晚開始時間(earliest and latest start times)在此日期之下，每個活動之最早與最晚結束時間(earliest and latest finish times)找出可能被延遲卻不影響專案完
5、成時間的活動,12,最早開始時間/最早完成時間(p.327),以順向進行(Forward Pass)之方式檢視網路:先由無立即前置活動之活動開始評估(如：科隆電腦公司中之活動A)令此活動之最早開始時間 ES=0.令此活動之最早完成時間 EF為活動時間.當某活動之所有立即前置活動的ES值都確定後，計算該活動的ES值ES=所有立即前置活動的ES值之最大值EF=ES+該活動之活動時間.重複此程序直到所有活動皆被評估為止最後活動之EF值為該專案之最早完成時間,13,最早開始時間/最早完成時間 順向進行,A90,B15,C5,F25,I30,G14,D20,E21,H28,J45,90,105,90,1
6、15,90,120,105,110,110,124,115,129,129,149,149,170,149,177,120,165,149,194,170,194,177,(ES,EF),14,最晚開始時間/最晚完成時間,以反向進行(Forward Pass)之方式檢視網路:(p.328)由沒有後向活動之所有活動開始評估.(如：科隆電腦公司中之活動E,H,J)該活動之最晚完成時間 LF=最小專案完成時間(say 194)該活動之最晚開始時間 LS=LF-活動時間.計算某活動之LF值若該活動之所有立即後置活動之LS值已決定.LF=所有立即後置活動的LS值之最小值LS=LF-活動時間.重複此程序直
7、到所有活動皆被評估為止.,15,B,F,C,A,I,E,D,G,H,H28,166,194,J,J45,149,194,E21,173,194,90,105,90,115,90,120,105,110,115,129,129,149,149,170,149,177,149,194,153,173,146,166,194,129,149,0,90,129,149,D20,129,149,129,149,129,149,129,149,129,149,129,149,129,149,G14,115,129,I30,119,149,29,119,C5,110,115,B15,95,110,5,95,
8、F25,90,115,0,90,A90,最晚開始時間/最晚完成時間-反向進行,16,專案完成過程中，計劃中的或不可預見延遲(Delay)都會影響活動之開始與完成時間。有些活動之延遲會影響整體之完成時間為了解此中延遲之效應，我們計算寬鬆時間(slack time),並決定要徑(critical path).,寬鬆時間(Slack Times),17,寬鬆時間 昰指某活動之ES可以在不致影響整個方案預期完成時間之下可以延遲的時間量.,寬鬆時間=LS-ES=LF-EF,寬鬆時間 Slack Times,ES,EF,LS,LF,Slack,Slack,18,重要活動(Critical Activiti
9、es)必須嚴格按計畫執行,科隆電腦公司專案活動的寬鬆時間,19,要徑為一組無寬鬆時間(Slack=0)的活動所組成,此要徑連結 START活動至 FINISH活動.專案網路中至少存在一條要徑要徑昰網路中最長之路徑要徑上所有活動完成時間之總合為計劃最小完成時間,要徑 The Critical Path,20,B,F,C,A,I,E,D,G,H,H28,166,194,J,J45,149,194,E21,173,194,90,105,90,115,90,120,105,110,115,129,129,149,149,170,149,177,149,194,D20,0,90,129,149,G14,
10、115,129,I30,119,149,A90,C5,110,115,B15,95,110,F25,90,115,0,90,要徑 The Critical Path,21,可能延遲之類型:單一延遲(Single delays).多重延遲(Multiple delays).,可能延遲分析(p.332),22,單一要徑活動(critical activity)之延遲，將造成整個專案產生相同之延遲時間，如活動D(要徑活動)延遲6天，整個專案將延遲6天非要徑活動之延遲(non-critical activity)只會造成整體專案落後該延遲超過其寬鬆時間之量，少於寬鬆時間之延遲不會影響專案完成之時間如活
11、動C(非要徑活動)有5天之寬鬆時間，故延遲4天不會影響專案完成之時間若延遲7天，整個專案將延遲7-5=2天,單一延遲 Single delays,23,LS=119,A90,J45,H28,E21,D20,I30,G14,F25,C5,B15,ES=149,LS=173,DELAYED START=149+15=164,ES=90,DELAYED START=90+15=105,活動 E與 I 個別延遲15天.,整個專案不受影響，不會延遲,FINISH,多重延遲於非要徑活動:範例 1:活動於不同路徑上,24,甘特圖呈現活動“I”與“E”各延遲15天後，對整個專案並無影響,Activity I,
12、I,30,E,21,Activity E,25,A,90,B,15,C,5,F,25,I,30,G,14,D,20,E,21,H,28,J,45,FINISH,ES=149,LS=173,DELAYED START=149+15=164,ES=90,DELAYED START=90+4=94,LS=95,整個專案不受影響，不會延遲,多重延遲於非要徑活動:範例 2:活動於相同路徑上,且被要徑分隔,活動 B延遲 4天,活動 E延遲15天,26,A,90,B,15,C,5,F,25,I,30,G,14,D,20,E,21,H,28,J,45,FINISH,DELAYED START=,109+4=1
13、13;,ES=90,DELAYED START=94,DELAYED FINISH=,94+15=109,LS=110,整個計劃延遲3天,活動 B延遲 4天,活動 C延遲4天,整個計劃延遲3天,多重延遲於非要徑活動:範例 3:活動於相同路徑上,且未被要徑分隔,LS=105,27,5.4 PERT/CPM 線性規劃法,變數Xi=活動開始時間 i=A,B,C,JX(FIN)=計劃完成時間目標函數以最少時間完成專案.限制式對於每個弧 為一個限制式，表示M活動的開始時間不能比前置活動 L的完成時間來的早,M,L,28,線性規劃法,定義 X(FIN)=專案完成時間，目標函數為,Minimize X(FI
14、N),29,X(FIN)XE+21 X(FIN)XH+28X(FIN)XJ+45 XD XG+14 XE XD+20 XG XC+5 XH XD+20 XG XF+25 XJ XD+20 XI XD+90XJ XI+30 XF XA+90XC XB+15 XD XG+14 XB XA+90,G,C5,F25,All X s are nonnegative,Minimize X(FIN)ST,線性規劃法(see p.330 圖5.3),30,Minimize XA+XB+XJ此目標函數確定各活動ES值之最佳解.Xj=ES EF=Xj+活動時間因此整個專案之活動時間為最小,線性規劃法,31,5.5
15、 使用Excel以獲得結果,32,5.6 甘特圖 Gantt Charts(p.337),甘特圖(Gantt charts)昰一種用來展示及監督專案進度的工具甘特圖 為圖形表示法:橫軸代表時間，縱軸代表各個活動，活動之完成時間以長條表示.最早時間之甘特圖，長條開始於某活動之於某活動之最早開始進行之時間.,33,科隆電腦公司之最早時間甘特圖,34,甘特圖可以用來監控各個活動之進度做法昰在以完成之部份就其所佔之比例在長條上畫上陰影.管理者可以檢視此圖就可以了解專案是否按時間完成,甘特圖-監控專案進度,35,A,90,B,15,F,25,I,30,C,5,G,14,D,20,E,21,H,28,J,
16、45,135,監控專案進度,陰影部份長條代表進行135天後完成之工作,36,優點 容易製作可決定最早完成時間.提供一個能符合專案之最早開始與完成時間之活動排程缺點甘特圖只提供一個可能之會早活動排程無法辨識專案進度是否落後未顯示活動之先後順序關係，由甘特圖無法明顯看出某活動之延遲如何影響另一活動之開始時間.,甘特圖之優缺點(p.339),37,5.7 資源均分法(略),38,5.8 專案排程機率法(p.345)The Probability Approach to Project Scheduling,活動之完成時間很少能100%正確估算，經常發生變動，故活動完成時間可視為隨機變數視活動完成時間
17、為隨機變數之專案排程技術稱為PERT.PERT 中用來表示完成時間變動性之方法稱為三種時間估計法(Three Time Estimate approach),39,三種時間估計法提供每個活動之完成時間估計.使用符號(notation):a=執行該活動之樂觀時間.m=執行該活動之最可能時間.b=執行該活動之悲觀時間.,機率法 三種時間估計法,40,在只有(a,m,b)存在之情形下很難預測其機率分配對於活動完成時間平均數與標準差之近似值可以用Beta 分配估計(see p.346,圖5.13),活動分配，平均數與標準差,41,為了計算專案完成時間之平均數與標準差，我們有以下之假設.,專案完成時間之
18、機率分配-假設,42,假設2完成某活動之時間與完成另外一個活動之時間無關.假設3要徑上有足夠之活動，故專案之完成時間可以用常態分配來估計,專案完成時間之機率分配-假設(p.347),假設1要徑，可用活動之平均完成時間來決定.專案平均完成時間為要徑上各活動之平均完成時間總和來決定.,43,平均數(Mean)=要徑上平均完成時間之總合,此三個假設可以暗示，整個專案之完成時間近似一個常態分配 N(,2)。,專案完成時間之機率分配(p.349),變異數(Variance)2=要徑上個活動完成 時間變異數之總合標準差(Standard deviation)=Variance,44,機率分配 科隆電腦公司
19、,45,科隆管理階層對下列問題有興趣.專案在194天內完成之機率專案在180天內完成之機率.專案超過210天完成之機率.,機率分配 科隆電腦公司(p.349),46,mA=(a+4m+b)/6=76+4(86)+120/6=90sA=(b-a)/6=(120-76)/6=7.33sA2=(7.33)2=53.78,s2,科隆電腦公司 計算活動之平均數與變異數(P.350),47,所有活動之平均時間與PERT/CPM問題相同因此，要徑為A-F-G-D J.平均完成時間=mA+mF+mG+mD+mJ=194.專案之變異數=sA2+sF2+sG2+sD2+sJ2=85.66專案之標準差=9.255,
20、s2,科隆電腦公司 計算要徑平均數與變異數,s2,48,令X=專案完成時間則 X N(194,9.255),機率分配,近似,專案於194天內完成之機率為=,49,95%信賴區間為,機率分配,95%信賴區間為=194 1.96(9.255)175,213 天.也就是說，完工時間為 175,213天之機率為 0.95.,50,XZ,1940,180天內完工之機率=,P(X 180)=P(Z-1.51)=0.5-0.4345=0.0655,180-1.51,0.0655,機率分配,51,超過210以上之完工機率為,.4582,0.0418,機率分配,52,專案幾乎確定如期完成(假設僅能有1%延遲)，
21、則專案必須於何時完成?,機率分配,P(XX0)=0.01,or P(Z(X0 m)/s=P(Z Z0)=.01P(Z 2.33)=0.01;X0=m+Z0s=194+2.33(9.255)=215.56 days.,由分配圖知，有 99%機率專案將於 215.56天內完成.,53,NORMDIST(194,194,9.255,TRUE),NORMINV(.025,194,9.255)NORMINV(.975,194,9.255),NORMDIST(180,194,9.255,TRUE),1-NORMDIST(210,194,9.255,TRUE),NORMINV(.99,194,9.255),
22、機率分配 使用試算表作機率分析,See P.41說明,54,使用試算表作要徑分析(PERT Input)(p.349),55,使用試算表作要徑分析(PERT Output),56,5.9 使用期望值法進行成本分析(略),57,5.10 使用要徑法(CPM)進行成本分析(p.356),要徑法(CPM)為一種專案計畫之明確方法計畫之完成時間牽涉到每個活動所分配到的金錢資源.以額外之金錢來降低活動所需時間之過程成為趕工“crashing.”,58,每種活動有兩種重要的完成時間.正常完成時間(TN).趕工完成時間(TC),最小可能完成時間.,趕工時間Crash time/趕工成本Crash cost,
23、每種活動有兩種重要的成本正常成本(CN),若活動於TN時間內完成.趕工成本(CC),若活動於TC 時間內完成.,TC TN,CC CN,59,趕工時間/趕工成本CPM 線性假設,R=TN TC=某活動最大可能減少時間E=CC CN=達到最大可能減少時間所需之趕工成本若某個介於(CN,CC)之間之金額被用於一活動上，則活動減少之時間與成本之增加成正比,60,時間(天),成本($100),2018161412108642,5 10 15 20 25 30 35 40 45,正常CN=$2000TN=20 days,於正常成本外加入趕工成本,省下之完工時間,於正常成本外加入更多趕工成本,趕工CC=$
24、4400TC=12 days,省下更多之完工時間,CPM線性假設,61,邊際成本(M)=,加入趕工之額外成本(E)趕工所減少之時間(R),=(4400-2000)/(20-12)=$300 per day,M=,E R,趕工時間/趕工成本CPM 線性假設(p.357),62,若一專案無法於正常時間之期限(Dead_Line)完成，則需要使用額外資源與費用於趕工活動上其目的為以最小額外成本達到期限要求,趕工活動 以最小成本達到期限要求,63,芭茄餐廳(BB)為墨西哥是速食餐廳，該餐廳希望於19週中設立一家新的餐廳管理者希望 評估此計畫之可能性了解計劃是否可以在19週之期限內完成,芭茄餐廳範例(p
25、.358),64,芭茄餐廳範例,Determined by the PERT.xls template,65,A,D,C,B,E,F,G,I,H,芭茄餐廳 網路圖形,L,O,J,N,M,K,P,66,芭茄餐廳 邊際成本,67,芭茄餐廳 啟發式演算法求解,啟發式演算法需考慮下列三種結果：只有在要徑上之活動被縮減時，專案時間才可以被縮減.每個活動之最大縮減時間是有限的另一非要徑路線,可能在縮減時間之過程中成為另一條要徑要徑上某活動可以被縮減之數量是有限的,小型演算法可以用啟發式演算法求解,68,線性規劃模式變數Xj=第i個活動之開始時間.Yj=第i個活動之被縮減之量.目標函數極小化趕工需要花費的額
26、外總費用.限制式所有活動不可超過最大允許的縮減量每個活動之開始時間不可以早於所有前置活動的完成時間專案完成時間必須在期限(deadline date)D完成.,芭茄餐廳 趕工之線性規劃模式,69,Min 5.5YA+10YB+2.67YC+4YD+2.8YE+6YF+6.67YG+10YH+5.33YI+12YJ+4YK+5.33YL+1.5YN+4YO+5.33YP,Minimize 總趕工成本,芭茄餐廳 趕工之線性規劃模式,70,Min 5.5YA+10YB+2.67YC+4YD+2.8YE+6YF+6.67YG+10YH+5.33YI+12YJ+4YK+5.33YL+1.5YN+4YO+
27、5.33YP,最大時間縮減限制式,滿足期限,線性規劃模式,71,Min 5.5YA+10YB+2.67YC+4YD+2.8YE+6YF+6.67YG+10YH+5.33YI+12YJ+4YK+5.33YL+1.5YN+4YO+5.33YP,XBXA+(5 YA),A,XA+5-YA,A,XA+5,線性規劃模式,每個活動之開始時間不可以早於所有前置活動的完成時間,72,XBXA+(5 YA)XCXA+(5 YA)XDXA+(5 YA)XeXA+(5 YA)XFXA+(5 YA)XBXB+(1 YB)XFXC+(3 YC)XGXF+(1 YF)X(FIN)XN+(3 YN)X(FIN)XO+(4 YO)X(FIN)XP+(4 YP),Min 5.5YA+10YB+2.67YC+4YD+2.8YE+6YF+6.67YG+10YH+5.33YI+12YJ+4YK+5.33YL+1.5YN+4YO+5.33YP,每個活動必須於所有前置活動完成完成後才能開始,.,線性規劃模式,73,芭茄餐廳 Deadline 試算表,
