某电脑公司专案排程模型

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,*,CHAPTER5,專案,排,排程,模,模型,ProjectSchedulingModels,1,專案,(project),昰一,組,組必,須,須完,成,成的,工,工作,組,組合,，,，目,標,標是,以,以最,少,少的,時,時間,或,或最,低,低之,成,成本,來,來完,成,成,專案,排,排程,的,的目,標,標,(p.323),藉由,計,計算,各,各活,動,動,開,開始,及,完,成,成,的,的,最,最早,與,最,晚,晚,時,時間,，,，儘,早,早完,成,成專,案,案,計算,一,一個,專,專案,在,在某,一,一期,間,間內,完,完成,之,之可,能,能性,.,發現,在,在某,一,一日,期,期能,以,以最,小,小成,本,本完,成,成之,專,專案,排,排程,控制,專,專案,進,進度,是,是否,按,按時,進,進行,，,，並,在,在預,算,算以,內,內,5.1,介紹,(p.322),2,專案,排,排程,的,的目,標,標,(p.323),調查,某,某些,活,活動,得,得延,誤,誤如,何,何影,響,響一,個,個專,案,案整,體,體的,完,完成,時,時間,調整,整,整個,專,專案,期,期間,之,之資,源,源分,配,配,專案,中,中工,作,作,(,Tasks),稱為,”,活動,”(activities).,每個,活,活動,皆,皆有,預,預估,的,的完,成,成時,間,間,(Estimatedcompletiontime),活動,完,完成,時,時與,投,投入,該,該活,動,動之,資,資源,多,多寡,有,有關,5.1,介紹,3,5.2,確定,專,專案,中,中之,活,活動,為了,決,決定,最,最佳,排,排程,，,，我,們,們需,要,要,確定,所,所有,專,專案,中,中之,活,活動,決定,活,活動,之,之先,後,後順,序,序,(precedence),藉由,這,這些,資,資訊,，,，我,們,們便,可,可以,發,發展,專,專案,管,管理,之,之方,法,法,4,確定,專,專案,活,活動,範,範例,(p.323325),科隆,電,電腦,公,公司,(KLONECOMPUTERS,INC.),KLONEComputers,製造,個,個人,電,電腦,KLONEComputers,需要,設,設計,、,、製,造,造對,其,其產,品,品,Klonepalm2000,進行,行,行銷,活,活動,三個,主,主要,的,的工,作,作,:,製造,新,新電,腦,腦,訓練,員,員工,與,與銷,售,售員,代,代表,.,廣告,行,行銷,KLONE,需要,發,發展,先,先後,順,順序,流,流程,圖,圖來,顯,顯示,各,各活,動,動間,之,之先,後,後順,序,序關,係,係,5,活動,敘述,A,設計,原,原型,(Prototypemodel),B,材料,購,購買,製造,活,活動,C,原型,製,製造,D,設計,修,修正,E,第一,次,次生,產,產,F,員工,訓,訓練,訓練,活,活動,G,員工,對,對產,品,品原,型,型之,建,建議,H,銷售,人,人員,訓,訓練,廣告,活,活動,I,生產,前,前廣,告,告活,動,動,J,生產,後,後廣,告,告活,動,動,科隆,電,電腦,公,公司,活,活動,敘,敘述,(p.324),6,由前,頁,頁之,活,活動,敘,敘述,表,表中,我們,可,可以,決,決定,每,每個,活,活動,之,之前,置,置活,動,動,(immediatepredecessors).,活動,A (Activity A),為活動,B,的一個之前置活動,(immediate predecessor),，因為活動,A,必須在活動,B,開始之前完成,A,B,科隆,電,電腦,公,公司,7,活動,前,前後,關,關係,表,表,(,表,5.3)(p.325),(PrecedenceRelationshipsChart),科隆,電,電腦,公,公司,8,科隆,電,電腦,公,公司,PERT/CPM,網路,A,90,B,15,C,5,F,25,I,30,G,14,D,20,E,21,H,28,J,45,B,15,I,F,25,C,5,G,14,D,20,E,21,H,28,J,45,9,5.3,專案,排,排程,的,的,PERT/CPM,方法,專案,排,排程,的,的,PERT/CPM,方法,為,為網,路,路表,達,達方,式,式,反應,出,出各,個,個活,動,動之,間,間的,先,先後,關,關係,活動,完,完成,時,時間,PERT/CPM,方法,之,之目,標,標是,希,希望專案,完,完成,時,時間為最,短,短,10,科隆,電,電腦,公,公司,-,續,科隆,電,電腦,公,公司,管,管理,者,者希,望,望安,排,排活,動,動計,劃,劃使,得,得專,案,案完,成,成時,間,間為,最,最短,管理,者,者希,望,望知,道,道,:(p.326),此專,案,案之,最,最早,完,完成,時,時間,在此,日,日期,之,之下,，,，每,個,個活,動,動之,最,最早,與,與最,晚,晚開,始,始時,間,間,(earliestandlateststarttimes),在此,日,日期,之,之下,，,，每,個,個活,動,動之,最,最早,與,與最,晚,晚結,束,束時,間,間,(earliestandlatestfinishtimes),找出,可,可能,被,被延,遲,遲卻,不,不影,響,響專,案,案完,成,成時,間,間的,活,活動,11,最早,開,開始,時,時間,/,最早,完,完成,時,時間,(p.327),以順,向,向進,行,行,(ForwardPass),之方,式,式檢,視,視網,路,路,:,先由,無,無立,即,即前,置,置活,動,動之,活,活動,開,開始,評,評估,(,如：,科隆,電,電腦,公,公司,中,中之,活,活動,A),令此,活,活動,之,之最,早,早開,始,始時,間,間,ES=0.,令此,活,活動,之,之最,早,早完,成,成時,間,間,EF,為活,動,動時,間,間,.,當某,活,活動,之,之所,有,有立,即,即前,置,置活,動,動的,ES,值都,確,確定,後,後，,計,計算,該,該活,動,動的,ES,值,ES=,所有,立,立即,前,前置,活,活動,的,的,ES,值之,最,最大,值,值,EF=ES+,該活,動,動之,活,活動,時,時間,.,重複,此,此程,序,序直,到,到所,有,有活,動,動皆,被,被評,估,估為,止,止,最後,活,活動,之,之,EF,值為,該,該專,案,案之,最,最早,完,完成,時,時間,12,最早,開,開始,時,時間,/,最早,完,完成,時,時間,順向,進,進行,A,90,B,15,C,5,F,25,I,30,G,14,D,20,E,21,H,28,J,45,90,105,90,115,90,120,105,110,110,124,115,129,129,149,149,170,149,177,120,165,149,194,170,194,A,90,0,90,B,15,I,30,F,25,C,5,G,14,D,20,E,21,H,28,J,45,177,194,最早完成時間,(ES,EF),13,最晚,開,開始,時,時間,/,最晚完成,時,時間,以反向進,行,行,(ForwardPass),之方式檢,視,視網路,: (p. 328),由沒有後,向,向活動之,所,所有活動,開,開始評估,. (,如：,科隆電腦,公,公司中之,活,活動,E,H,J),該活動之,最,最晚完成,時,時間,LF=,最小專案,完,完成時間,(say194),該活動之,最,最晚開始,時,時間,LS =LF -,活動時間,.,計算某活,動,動之,LF,值若該活,動,動之所有,立,立即後置,活,活動之,LS,值已決定,.,LF =,所有立即,後,後置活動,的,的,LS,值之最小,值,值,LS =LF-,活動時間,.,重複此程,序,序直到所,有,有活動皆,被,被評估為,止,止,.,14,B,F,C,A,I,E,D,G,H,H,28,166,194,J,J,45,149,194,E,21,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,D,20,129,149,129,149,129,149,129,149,129,149,129,149,129,149,G,14,115,129,I,30,119,149,29,119,C,5,110,115,B,15,95,110,5,95,F,25,90,115,0,90,A,90,最晚開始,時,時間,/,最晚完成,時,時間,-,反向進行,15,專案完成,過,過程中，,計,計劃中的,或,或不可預,見,見延遲,(Delay),都會影響,活,活動之開,始,始與完成,時,時間。,有些活動,之,之延遲會,影,影響整體,之,之完成時,間,間,為了解此,中,中延遲之,效,效應，我,們,們計算,寬鬆時間,(slack time),並決定要徑,(,criticalpath),.,寬鬆時間,(Slack Times),16,寬鬆時間,昰,昰指某,活,活動之,ES,可以在不,致,致影響整,個,個方案預,期,期完成時,間,間之下可,以,以延遲的,時,時間量,.,寬鬆時間,= LS- ES =LF -EF,寬鬆時間,Slack Times,ES,EF,LS,LF,Slack,Slack,17,重要活動,(Critical Activities),必須嚴格,按,按,計畫執行,科隆電腦,公,公司專案,活,活動的寬,鬆,鬆時間,18,要徑為一,組,組無寬鬆,時,時間,(Slack=0),的活動所,組,組成,此要徑連,結,結,START,活動至,FINISH,活動,.,專案網路,中,中至少存,在,在一條要,徑,徑,要徑昰網,路,路中最長,之,之路徑,要徑上所,有,有活動完,成,成時間之,總,總合為計,劃,劃最小完,成,成時間,要徑,TheCriticalPath,19,B,F,C,A,I,E,D,G,H,H,28,166,194,J,J,45,149,194,E,21,173,194,90,105,90,115,90,120,105,110,115,129,129,149,149,170,149,177,149,194,D,20,0,90,129,149,G,14,115,129,I,30,119,149,A,90,C,5,110,115,B,15,95,110,F,25,90,115,0,90,要徑,TheCriticalPath,20,可能延遲,之,之類型,:,單一延遲,(Singledelays).,多重延遲,(Multiple delays).,可能延遲,分,分析,(p.332),21,單一要徑,活,活動,(,criticalactivity),之延遲，,將,將造成整,個,個專案產,生,生相同之,延,延遲時間,，,，,如活動,D(,要徑活動,),延遲,6,天，整個,專,專案將延,遲,遲,6,天,非要徑活,動,動之延遲,(,non-critical,activity,),只會造成,整,整體專案,落,落後該延,遲,遲超過其,寬,寬鬆時間,之,之量，少,於,於寬鬆時,間,間之延遲,不,不會影響,專,專案完成,之,之時間,如活動,C(,非要徑活,動,動,),有,5,天之寬鬆,時,時間，故,延,延遲,4,天不會影,響,響專案完,成,成之時間,若延遲,7,天，整個,專,專案將延,遲,遲,7-5=2,天,單一延遲,Single delays,22,LS =119,A,90,J,45,H,28,E,21,D,20,I,30,G,14,F,25,C,5,B,15,ES=149,LS=173,DELAYEDSTART=149+15=164,ES=90,DELAYEDSTART=90+15=105,活動,E,與,I,個別延遲,15,天,.,整個專案,不,不受影響,，,，不會延,遲,遲,FINISH,多重延遲,於,於非要徑,活,活動,:,範例,1:,活動於不,同,同路徑上,23,A,90,90,B,15,甘特圖呈,現,現活動,“I”,與,“E”,各,延遲,15,天後 ，,對,對整個專,案,案,並無影響,ActivityI,F,25,I,30,105,C,5,115,G,14,129,D,20,149,E,21,H,28,J,45,194,194,ActivityE,24,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,天,25,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=113;,ES=90,DELAYED START =94,DELAYED FINISH=,94+15=109,LS=110,整個計,劃,劃延遲,3,天,活動,B,延遲,4,天,活動,C,延遲,4,天,整個計,劃,劃延遲,3,天,多重延,遲,遲於非,要,要徑活,動,動,:,範例,3:,活動於,相,相同路,徑,徑上,且未被,要,要徑分,隔,隔,LS=105,26,5.4PERT/CPM,線性規,劃,劃法,變數,X,i,=,活動開,始,始時間,i=A, B, C, ,J,X(FIN)=,計劃完,成,成時間,目標函,數,數,以最少,時,時間完,成,成專案,.,限制式,對於每,個,個弧,為,為,一,一個限,制,制式，,表,表示,M,活動的,開,開始時,間,間不能,比,比前置,活,活動,L,的完成,時,時間來,的,的早,M,L,27,線性規,劃,劃法,定義,X(FIN)=,專案完,成,成時間,，,，,目標函,數,數為,MinimizeX(FIN),28,X(FIN),X,E,+ 21,X(FIN),X,H,+ 28,X(FIN),X,J,+45,X,D,X,G,+14,X,E,X,D,+20X,G,X,C,+ 5,X,H,X,D,+20X,G,X,F,+ 25,X,J,X,D,+20X,I,X,D,+ 90,X,J,X,I,+30X,F,X,A,+ 90,X,C,X,B,+ 15,X,D,X,G,+ 14,X,B,X,A,+ 90,G,C,5,F,25,AllXs arenonnegative,MinimizeX(FIN),ST,線性規,劃,劃法,(see p.330,圖,5.3),29,MinimizeX,A,+X,B,+X,J,此目標,函,函數確,定,定各活,動,動,ES,值之最,佳,佳解,.,Xj= ES,EF= Xj +,活動時,間,間,因此整,個,個專案,之,之活動,時,時間為,最,最小,線性規,劃,劃法,30,5.5,使用,Excel,以獲得,結,結果,31,5.6,甘特圖,GanttCharts (p.337),甘特圖,(Ganttcharts),昰一種,用,用來展,示,示及監,督,督專案,進,進度的,工,工具,甘特圖,為,為圖,形,形表示,法,法,:,橫軸代,表,表時間,，,，縱軸,代,代表各,個,個活動,，,，活動,之,之完成,時,時間以,長,長條表,示,示,.,最早時,間,間之甘,特,特圖，,長,長條開,始,始於某,活,活動之,於,於某活,動,動之最,早,早開始,進,進行之,時,時間,.,32,A,90,90,B,15,F,25,I,30,105,C,5,115,G,14,129,D,20,149,E,21,H,28,J,45,194,194,科隆電,腦,腦公司,之,之最早,時,時間甘,特,特圖,33,甘特圖,可,可以用,來,來監控,各,各個活,動,動之進,度,度,做法昰,在,在以完,成,成之部,份,份就其,所,所佔之,比,比例在,長,長條上,畫,畫上陰,影,影,.,管理者,可,可以檢,視,視此圖,就,就可以,了,了解專,案,案是否,按,按時間,完,完成,甘特圖,-,監控專,案,案進度,34,A,90,B,15,F,25,I,30,C,5,G,14,D,20,E,21,H,28,J,45,194,194,135,監控專案進,度,度,陰影部份長,條,條代表進行,135,天後完成之,工,工作,並不表示某活動延遲,會造成完工時間延遲,因活動,“I”,有寬鬆時間，,因此可以延遲,!,35,優點,容易製作,可決定最早,完,完成時間,.,提供一個能,符,符合專案之,最,最早開始與,完,完成時間之,活,活動排程,缺點,甘特圖只提,供,供一個可能,之,之會早活動,排,排程,無法辨識專,案,案進度是否,落,落後,未顯示活動,之,之先後順序,關,關係，由甘,特,特圖無法明,顯,顯看出某活,動,動之延遲如,何,何影響另一,活,活動之開始,時,時間,.,甘特圖之優,缺,缺點,(p. 339),36,5.7,資源均分法,(,略,),37,5.8,專案排程機,率,率法,(p. 345)The ProbabilityApproachtoProject Scheduling,活動之完成,時,時間很少能,100%,正確估算，,經,經常發生變,動,動，故活動,完,完成時間可,視,視為隨機變,數,數,視活動完成,時,時間為隨機,變,變數之專案,排,排程技術稱,為,為,PERT.,PERT,中用來表示,完,完成時間變,動,動性之方法,稱,稱為三種時間估,計,計法,(,ThreeTimeEstimateapproach),38,三種時間估,計,計法提供每,個,個活動之完,成,成時間估計,.,使用符號,(notation):,a =,執行該活動,之,之樂觀時間,.,m =,執行該活動,之,之最可能時,間,間,.,b =,執行該活動,之,之悲觀時間,.,機率法,三種時間估,計,計法,39,在只有,(a,m,b),存在之情形,下,下很難預測,其,其機率分配,對於活動完,成,成時間平均,數,數與標準差,之,之近似值可,以,以用,Beta,分配估計,(seep. 346,圖,5.13),活動分配，,平,平均數與標,準,準差,40,為了計算專,案,案完成時間,之,之平均數與,標,標準差，我,們,們有以下之,假,假設,.,專案完成時,間,間之機率分,配,配,-,假設,41,假設,2,完成某活動,之,之時間與完,成,成另外一個,活,活動之時間,無,無關,.,假設,3,要徑上有足,夠,夠之活動，,故,故專案之完,成,成時間可以,用,用常態分配,來,來估計,專案完成時,間,間之機率分,配,配,-,假設,(p.347),假設,1,要徑，可用活動之平均,完,完成時間來決定,.,專案平均完,成,成時間為要,徑,徑上各活動,之,之平均完成,時,時間總和來,決,決定,.,42,平均數,(,Mean),=,要徑上平均,完,完成時間之,總,總合,此三個假設,可,可以暗示，,整,整個專案之完成時間近似一個常,態,態分配,N(,2,),。,專案完成時,間,間之機率分,配,配,(p. 349),變異數,(Variance),2,=,要徑上個活,動,動完成,時間變異數,之,之總合,標準差,(Standarddeviation),= Variance,43,機率分配,科隆電腦公,司,司,44,科隆管理階,層,層對下列問,題,題有興趣,.,專案在,194,天內完成之,機,機率,專案在,180,天內完成之,機,機率,.,專案超過,210,天完成之機,率,率,.,機率分配,科隆電腦公,司,司,(p. 349),45,m,A,=(a+4m+b)/6 =76+4(86)+120,/,6 = 90,s,A,= (b-a)/6= (120 -76),/,6 = 7.33,s,A,2,= (7.33),2,= 53.78,s,2,科隆電腦公,司,司,計算活動之,平,平均數與變,異,異數,(P.350),46,所有活動之,平,平均時間與,PERT/CPM,問題相同,因此，要徑,為,為,A - F- G -D J.,平均完成時,間,間,=,m,A,+,m,F,+,m,G,+,m,D,+,m,J,=194.,專案之變異,數,數,=,s,A,2,+,s,F,2,+,s,G,2,+,s,D,2,+,s,J,2,= 85.66,專案之標準,差,差,=9.255,s,2,科隆電腦公,司,司,計算要徑平,均,均數與變異,數,數,s,2,47,令,X=,專案完成時,間,間則,X N(194,9.255 ),機率分配,194,近似,專案於,194,天內完成之,機,機率為,=,48,95%,信賴區間為,m,s,z,0.025,機率分配,.95,m,95%,信賴區間為,= 194,1.96(9.255),175,213,天,.,也就是說，,完,完工時間為,175,213,天之機率為,0.95.,49,X,Z,194,0,180,天內完工之,機,機率,=,P(X,180)= P(Z,-1.51) = 0.5 -0.4345 = 0.0655,180,-1.51,0.0655,機率分配,50,超過,210,以上之完工,機,機率為,X,Z,194,0,.4582,210,1.73,?,0.0418,機率分配,51,X,Z,194,0,專案幾乎,確,確定如期,完,完成,(,假設僅能有,1%,延遲,),，則專案必,須,須於何時完,成,成,?,X,0,2.33,0.01,.49,機率分配,P(X,X,0,)= 0.01,orP(Z, (,X,0,m,)/,s,= P(Z,Z,0,) =.01,P(Z,2.33) =0.01; X,0,=,m,+Z,0,s,=194+ 2.33(9.255) =215.56days.,由分配圖,知,知，有,99%,機率,專案將於,215.56,天內完成,.,52,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),機率分配,使用試算,表,表作機率,分,分析,SeeP.41,說明,53,使用試算,表,表作要徑,分,分析,(PERT Input)(p.349),54,使用試算,表,表作要徑,分,分析,(PERT Output),55,5.9,使用期望,值,值法進行,成,成本分析,(,略,),56,5.10,使用要徑,法,法,(CPM),進行成本,分,分析,(p.356),要徑法,(CPM),為一種專,案,案計畫之,明,明確方法,計畫之完,成,成時間牽,涉,涉到每個,活,活動所分,配,配到的金,錢,錢資源,.,以額外之,金,金錢來降,低,低活動所,需,需時間之,過,過程成為,趕,趕工,“crashing.”,57,每種活動,有,有兩種重,要,要的完成,時,時間,.,正常完成,時,時間,(T,N,).,趕工完成,時,時間,(T,C,),最小可能,完,完成時間,.,趕工時間,Crash time,/,趕工成本,Crash cost,每種活動,有,有兩種重,要,要的成本,正常成本,(C,N,),若活動於,T,N,時間內完,成,成,.,趕工成本,(C,C,),若活動於,T,C,時間內完,成,成,.,T,C,C,N,58,趕工時間,/,趕工成本,CPM,線性假設,R=T,N, T,C,=,某活動最,大,大可能減,少,少時間,E=C,C,C,N,=,達到最大,可,可能減少,時,時間所需,之,之趕工成,本,本,若某個介,於,於,(C,N,C,C,),之間之金,額,額被用於,一,一活動上,，,，則活動,減,減少之時,間,間與成本,之,之增加成,正,正比,59,時間,(,天,),成本,($100),20,18,16,14,12,10,8,6,4,2,51015202530354045,正常,C,N,= $2000,T,N,= 20days,於正常成,本,本外,加入趕工,成,成本,省下之完,工,工時間,於正常成,本,本外,加入更多,趕,趕工成本,趕工,C,C,= $4400,T,C,= 12days,省下更多,之,之完工時,間,間,加入,25%,額外,趕工成本,省下,25%,最大,完工時間,總成本,= $2600,工作時間,= 18 days,CPM,線性假設,60,邊際成本,(M)=,加入趕工,之,之額外成,本,本,( E),趕工所減,少,少之時間,( R),=,(4400 -2000)/(20 -12)= $300 per day,M =,E,R,趕工時間,/,趕工成本,CPM,線性假設,(p.357),總成本,= $2600,工作時間縮短,X days,X =,2600-2000,300,= 2,61,若一專案,無,無法於正,常,常時間之,期,期限,(Dead_Line),完成，則,需,需要使用,額,額外資源,與,與費用於,趕,趕工活動,上,上,其目的為,以,以最小額,外,外成本達,到,到期限要,求,求,趕工活動,以最小成,本,本達到期,限,限要求,62,芭茄餐廳,(BB),為墨西哥,是,是速食餐,廳,廳，該餐,廳,廳希望於,19,週中設立,一,一家新的,餐,餐廳,管理者希,望,望,評估此計,畫,畫之可能,性,性,了解計劃,是,是否可以,在,在,19,週之期限,內,內完成,芭茄餐廳,範,範例,(p.358),63,芭茄餐廳,範,範例,若不花費額外費用，餐廳將於,29,週後以正常成本,$200,000,完工,.,若趕工的話，參廳可於,17,週後以加工成本,$300,000,完工,.,Determined by the PERT.xls template,64,A,D,C,B,E,F,G,I,H,芭茄餐廳,網路圖形,L,O,J,N,M,K,P,65,芭茄餐廳,邊際成本,R = T,N, T,C,= 5 3 = 2,E = C,C, C,N,= 36 25 = 11,M = E/R = 11/2 = 5.5,66,芭茄餐廳,啟發式演,算,算法求解,啟發式演,算,算法需考,慮,慮下列三,種,種結果：,只有在,要徑上,之活動被,縮,縮減時，,專,專案時間,才,才可以被,縮,縮減,.,每個活動,之,之最大縮,減,減時間是,有,有限的,另一非要,徑,徑路線,可能在縮,減,減時間之,過,過程中成,為,為另一條,要,要徑,要徑上某,活,活動可以,被,被縮減之,數,數量是有,限,限的,小型演算,法,法可以用,啟,啟發式演,算,算法求解,67,線性規劃,模,模式,變數,X,j,=,第,i,個活動之,開,開始時間,.,Y,j,=,第,i,個活動之,被,被縮減之,量,量,.,目標函數,極小化趕,工,工需要花,費,費的額外,總,總費用,.,限制式,所有活動,不,不可超過,最,最大允許,的,的縮減量,每個活動,之,之開始時,間,間不可以,早,早於所有,前,前置活動,的,的完成時,間,間,專案完成,時,時間必須,在,在期限,( deadline date)D,完成,.,芭茄餐廳,趕工之線,性,性規劃模,式,式,68,Min5.5Y,A,+10Y,B,+2.67Y,C,+4Y,D,+2.8Y,E,+6Y,F,+6.67Y,G,+10Y,H,+5.33Y,I,+12Y,J,+4Y,K,+5.33Y,L,+1.5Y,N,+4Y,O,+5.33Y,P,Minimize,總趕工成,本,本,芭茄餐廳,趕工之線,性,性規劃模,式,式,69,Min5.5Y,A,+10Y,B,+2.67Y,C,+4Y,D,+2.8Y,E,+6Y,F,+6.67Y,G,+10Y,H,+5.33Y,I,+12Y,J,+4Y,K,+5.33Y,L,+1.5Y,N,+4Y,O,+5.33Y,P,最大時間,縮減限制,式,式,H,F,E,D,C,B,A,0.5,2.0,0.5,0.5,2.5,1.0,1.5,Y,Y,Y,Y,Y,Y,Y,Y,G,1.5,.,19,FIN,X,),(,ST,滿足期限,線性規劃,模,模式,70,X,A,Min5.5Y,A,+10Y,B,+2.67Y,C,+4Y,D,+2.8Y,E,+6Y,F,+6.67Y,G,+10Y,H,+5.33Y,I,+12Y,J,+4Y,K,+5.33Y,L,+1.5Y,N,+4Y,O,+5.33Y,P,X,B,X,A,+(5, Y,A,),B,X,B,A,-Y,A,X,A,+5-Y,A,A,X,A,+5,B,X,B,B,X,B,B,X,B,線性規劃,模,模式,B,X,B,每個活動,之,之開始時,間,間,不可以早,於,於所有,前置活動,的,的完成時,間,間,71,X,B,X,A,+(5, Y,A,),X,C,X,A,+(5, Y,A,),X,D,X,A,+(5, Y,A,),X,e,X,A,+(5, Y,A,),X,F,X,A,+(5,Y,A,),X,B,X,B,+(1,Y,B,),X,F,X,C,+(3,Y,C,),X,G,X,F,+(1,Y,F,),X(FIN),X,N,+(3,Y,N,),X(FIN),X,O,+(4,Y,O,),X(FIN),X,P,+(4,Y,P,),Min5.5Y,A,+10Y,B,+2.67Y,C,+4Y,D,+2.8Y,E,+6Y,F,+6.67Y,G,+10Y,H,+5.33Y,I,+12Y,J,+4Y,K,+5.33Y,L,+1.5Y,N,+4Y,O,+5.33Y,P,每,個,個,活,活,動,動,必,必,須,須,於,所,所,有,有,前,前,置,置,活,活,動,完,完,成,成,完,完,成,成,後,後,才,能,能,開,開,始,始,.,線,性,性,規,規,劃,劃,模,模,式,式,72,芭,茄,茄,餐,餐,廳,廳,Deadline,試,算,算,表,表,73,