工程網(wǎng)絡(luò)圖及有關(guān)排序問題(講稿).ppt

1、第二章 工程網(wǎng)絡(luò)圖及有關(guān)排序問題,2.1工程網(wǎng)絡(luò) 2.2工程網(wǎng)絡(luò)圖的要求及其檢驗(yàn)方法 2.3工程網(wǎng)絡(luò)圖的分析方法,2.1工程網(wǎng)絡(luò),在實(shí)踐中經(jīng)常會(huì)遇到合理地安排工作次序、統(tǒng)籌使用各種資源，以便在最短時(shí)間內(nèi)完成預(yù)定的任務(wù)的一類問題，統(tǒng)籌方法就是解決這類問題行之有效的一種數(shù)學(xué)方法。統(tǒng)籌方法利用工程網(wǎng)絡(luò)圖（也稱統(tǒng)籌圖）來表示組成任務(wù)的各個(gè)環(huán)節(jié)及其先后次序，并據(jù)此對(duì)工程網(wǎng)絡(luò)作進(jìn)一步的分析和計(jì)算，以幫助人們進(jìn)行合理地安排任務(wù)的各個(gè)環(huán)節(jié)，科學(xué)地進(jìn)行決策和管理，達(dá)到優(yōu)化完成任務(wù)的目的。,在國內(nèi)外許多科學(xué)技術(shù)和管理科學(xué)的文獻(xiàn)中，統(tǒng)籌方法經(jīng)常被稱作CPM方法或PERT技術(shù)，這是因?yàn)樵诮y(tǒng)籌方法形成的歷史過程中有兩件

2、事起了很大的作用。這兩件事都發(fā)生在20世紀(jì)50年代；美國的蘭德公司為杜邦公司改善內(nèi)部管理而提出的關(guān)鍵路線法（Critical Path Method，簡(jiǎn)稱CPM方法），使后者大大提高了效益；美國的特種技術(shù)規(guī)劃局采用計(jì)劃評(píng)估技術(shù)（Program Evaluation and Reciew Techniques，簡(jiǎn)稱PERT技術(shù)），使美國提前兩年完成了戰(zhàn)略核武器北極星核潛艇的建造。這兩件成功應(yīng)用統(tǒng)籌方法的案例刺激了各種行業(yè)競(jìng)相采用PERT/CPM技術(shù)編制項(xiàng)目的計(jì)劃，加快了統(tǒng)籌方法的普及過程，以致后來在有些國家，把是否使用CPM方法或PERT技術(shù)核驗(yàn)投標(biāo)計(jì)劃書法定為政府部門接受公司投標(biāo)國家項(xiàng)目的先決

3、條件。與此幾乎同時(shí)，在20世紀(jì)5060年代，在華羅庚先生的倡導(dǎo)和推動(dòng)起來，總結(jié)為統(tǒng)籌方法。他的統(tǒng)籌方法評(píng)估及補(bǔ)充一書為在我國普及統(tǒng)籌方法起了很大的作用。,我們從一個(gè)最簡(jiǎn)單的例子來了解這種方法的思想，設(shè)想我們要以茶待客，為此要完成下面各項(xiàng)事情，并把各件事情所需時(shí)間列于其后（為簡(jiǎn)單計(jì)，時(shí)間取為整數(shù)）： 洗茶杯，1分鐘； 找茶葉并放入茶杯，1分鐘； 燒開水，5分鐘； 沖茶，1分鐘。 我們?nèi)绾伟淹瓿伞耙圆璐汀边@件任務(wù)用圖表示？,從圖中分析可以得到：我們可以先燒水，再去洗茶杯、放茶葉，等水開了后再為客人沖茶。這樣的安排可以用最短的時(shí)間完成所有的事情。由此可知，客人最少要6分鐘以后才能喝到茶，也就是完成

4、所有事情的最短“工期”是6分鐘。 工程網(wǎng)絡(luò)圖還說明，為縮短客人的等待時(shí)間，可以考慮的辦法是用更短的時(shí)間把水燒開，或者縮短沖茶的時(shí)間，而不是在縮短洗茶杯、放茶葉的時(shí)間上動(dòng)腦筋。,例1表2-1所示是某個(gè)機(jī)床要加工的5種零件的先后次序關(guān)系，試根據(jù)表格畫出相應(yīng)的工程網(wǎng)絡(luò)圖來。,例2圖2-3標(biāo)出了自行車有關(guān)零件的名稱。把自行車零件組裝成一輛自行車，主要有以下幾個(gè)工序： A組裝車架，包括裝前叉，車把和前后擋泥板； B安裝并校正前輪； C安裝并校正后輪（含飛輪）； D安裝中軸，包括裝輪盤和腳蹬； E在輪盤和飛輪間連接鏈條； F安裝左、右腳蹬； G安裝前后車間和車座。,對(duì)于熟練的裝配工，各工序所需要的時(shí)間如表

5、2-2所示。,如果由一個(gè)人完成全部組裝工作至少需要45分鐘。自行車組裝過程中的有些工序的前后次序是確定的。例如，在后輪與中軸輪盤裝好之前無法連接后輪上的飛輪與輪盤之間的鏈條等等。根據(jù)經(jīng)驗(yàn)，如下的裝配順序是必須遵循的： (1)在安裝并校正前后輪之前組裝車架； (2)車閘的安裝要在前后輪轉(zhuǎn)好之后再進(jìn)行； (3)連接飛輪和輪盤間的鏈條要在后輪和中軸裝好之后再進(jìn)行； (4)先裝中軸，再裝腳蹬。 現(xiàn)安排兩個(gè)工人合作組裝一輛自行車，每道工序只能由一個(gè)完成。請(qǐng)你為這兩位工人安排一個(gè)組裝的工序流程，使他們?cè)谧疃痰臅r(shí)間內(nèi)裝配好這輛自行車，并請(qǐng)算出最短時(shí)間。（北京市1999年決賽）,例2圖2-3標(biāo)出了自行車有關(guān)零

6、件的名稱。把自行車零件組裝成一輛自行車，主要有以下幾個(gè)工序： A組裝車架，包括裝前叉，車把和前后擋泥板；B安裝并校正前輪； C安裝并校正后輪（含飛輪）； D安裝中軸，包括裝輪盤和腳蹬； E在輪盤和飛輪間連接鏈條；F安裝左、右腳蹬； G安裝前后車間和車座。,(1)在安裝并校正前后輪之前組裝車架； (2)車閘的安裝要在前后輪轉(zhuǎn)好之后再進(jìn)行； (3)連接飛輪和輪盤間的鏈條要在后輪和中軸裝好之后再進(jìn)行； (4)先裝中軸，再裝腳蹬。,2.2工程網(wǎng)絡(luò)圖的要求及其檢驗(yàn)方法,工程網(wǎng)絡(luò)圖的工作要正確地反映各工序之間的關(guān)系，但是作為整體來說，工程網(wǎng)絡(luò)圖還有其自身的要求。,首先，適應(yīng)每件事情總有“一個(gè)”開始和“一個(gè)

7、”結(jié)束的思維習(xí)慣，我們要求整個(gè)工程網(wǎng)絡(luò)圖只有一個(gè)初始事項(xiàng)和一個(gè)最終事項(xiàng)。這個(gè)要求可以用適當(dāng)添加虛工序和事項(xiàng)來達(dá)到。例如圖2-5(a)中原有兩個(gè)初始事項(xiàng)和，3個(gè)最終事項(xiàng)，可以添加一些虛工序，如圖2-5(b)所示，使新的工程網(wǎng)絡(luò)圖上只有一個(gè)初始事項(xiàng)和一個(gè)最終事項(xiàng)。,其次，正確的工程網(wǎng)絡(luò)圖要求整個(gè)圖內(nèi)不含有“圈”。所謂“圈”是圖中從某個(gè)事項(xiàng)出發(fā)經(jīng)過若干個(gè)首尾相連的工序又回到起點(diǎn)的一個(gè)工序序列。如圖2-6(a)中的B-C-D和圖2-6(b)中的B-C-D與A-B-C-E都是圈的例子。,如何來檢查一張工程網(wǎng)絡(luò)圖有沒有圈呢？ 方法1：“窮竭法”，即“跟蹤”每一個(gè)首尾相連的工序序列，看它是否回到起點(diǎn)。 方法

8、2：“工序刪去法”。,首先，從工程網(wǎng)絡(luò)圖中找尋初始事項(xiàng)，然后刪去該事項(xiàng)和從該事項(xiàng)出發(fā)的所有工序。再在新的工程網(wǎng)絡(luò)圖中找尋初始事項(xiàng)，重復(fù)上述過程。如果圖中沒有圈的話，則在這個(gè)過程中可以把圖中的所有工序全部刪去。圖2-7(a)圖2-7(c)給出了按工序刪去法檢驗(yàn)圖圖2-7(a)的過程。從圖2-7(c)再刪一次，就可以把圖中的所有工序全部刪去。,如果遇到如圖2-6(a)這樣的含有圈的圖，照上述步驟將刪成如圖2-8所示，此后就不可能再刪去任何一道工序了。,請(qǐng)你按照制作工程網(wǎng)絡(luò)圖的要求及其檢驗(yàn)方法，檢查你自己繪制的工程網(wǎng)絡(luò)圖是否合理？,2.3工程網(wǎng)絡(luò)圖的分析方法,2.3.1最短工期 2.3.2縮短工期

9、2.3.3等待時(shí)間,2.3.1最短工期,工程網(wǎng)絡(luò)圖可以幫助我們分析整個(gè)工程的最短工期。 以圖2-9為例，我們把初始事項(xiàng)到最終事項(xiàng)的一個(gè)首尾相連的工序序列稱為路線，例如1-2-3-4是一條路線，1-3-4也是一條路線。一條路線中所有工序時(shí)間的總和稱為該路線的長(zhǎng)，例如，路線1-2-3-4的長(zhǎng)為3，路線1-3-4的長(zhǎng)為6。一張工程網(wǎng)絡(luò)圖中最長(zhǎng)的路線稱為關(guān)鍵路線。圖2-9的關(guān)鍵路線是1-3-4，關(guān)鍵路線的長(zhǎng)為6。從圖2-9分析可知，完成所有事情的最短時(shí)間為6，也就是關(guān)鍵路線的長(zhǎng)。這是一個(gè)普遍成立的規(guī)律：工程的最短工期等于工程網(wǎng)絡(luò)圖中關(guān)鍵路線的長(zhǎng)。,關(guān)鍵路線如此重要，如何從工程網(wǎng)絡(luò)圖中找出關(guān)鍵路線呢？

10、1、可以根據(jù)關(guān)鍵路線的定義，找出圖中所有路線，計(jì)算各路線的長(zhǎng)，通過比較后得到的最長(zhǎng)的路線就是關(guān)鍵路線。 2、計(jì)算每個(gè)事項(xiàng)的“最早出發(fā)時(shí)間”和“最遲到達(dá)時(shí)間”的方法。這種算法也適合于計(jì)算機(jī)編程以處理復(fù)雜的情況。,最早出發(fā)時(shí)間，是指該事項(xiàng)后面的工序最早什么時(shí)間可以開工，規(guī)定初始事項(xiàng)的最早時(shí)間為0。,在一般情況下，設(shè)指向某事項(xiàng)i的工序有n個(gè)（見圖2-12）：A1，A2，An，完成這些工序分別需要時(shí)間t1，t2，tn，且這些工序的起點(diǎn)事項(xiàng)最早時(shí)間都已經(jīng)計(jì)算得到，分別記為E1，E2，En，則事項(xiàng)i的最早時(shí)間Ei由下式計(jì)算：,最遲到達(dá)時(shí)間，是在規(guī)定事項(xiàng)后面各工序最遲完工時(shí)間的條件下，該事項(xiàng)后面的工序最遲什

11、么時(shí)候必須開工，能保證后面的所有工序能在規(guī)定的時(shí)間前完工。,一般地，若從某事項(xiàng)i出發(fā)的工序有n個(gè)： A1，A2，An（見圖2-14），完成這些工序分別需要時(shí)間t1，t2，tn，且這些工序的終點(diǎn)事項(xiàng)的最遲時(shí)間都已經(jīng)計(jì)算得到，分別記為L(zhǎng)1，L2，Ln，則事項(xiàng)i的最遲時(shí)間Li由下式計(jì)算：,現(xiàn)在用這種方法對(duì)如下較復(fù)雜的工程網(wǎng)絡(luò)圖（圖2-15）進(jìn)行計(jì)算。,現(xiàn)在用這種方法對(duì)如下較復(fù)雜的工程網(wǎng)絡(luò)圖（圖2-15）進(jìn)行計(jì)算。,請(qǐng)你計(jì)算例2的最短工期？,我們現(xiàn)在來完成例2的解答。,例3有一批產(chǎn)品的加工要經(jīng)過10道工序，分別記為A,B,C,D,E,F,G,H,I,J。若加工工序X必須要在完成工序Y后才能開工，我們就

12、稱Y是X的緊前工序，現(xiàn)將各工序的加工次序及所需時(shí)間（單位：小時(shí)）列表2-5。,(1)現(xiàn)有兩臺(tái)性能相同的機(jī)器可同時(shí)加工該批產(chǎn)品，問完成這批產(chǎn)品的最短加工時(shí)間是多少（假定每道工序只能安排在一臺(tái)機(jī)器上，并且必須在整批產(chǎn)品完成前一道工序后才開始下道工序的加工）？ (2)經(jīng)過技術(shù)改造，其中一臺(tái)機(jī)器已將其效率提高為原先的兩倍（即加工時(shí)間縮短一半）。問：此時(shí)應(yīng)如何安排兩臺(tái)機(jī)器的加工任務(wù)，才能使完工時(shí)間最短？（上海市2000年決賽）,解(1)首先按工序關(guān)系，畫出工程網(wǎng)絡(luò)圖（如圖2-18所示）。并且求出關(guān)鍵路線B-C-E-I，最短工期為15小時(shí)。 然后，根據(jù)加工順序要求安排加工任務(wù)，工期為15小時(shí)，可以用圖2-

13、19表示兩人的分工情況：圖2-19下方的軸標(biāo)出了時(shí)間尺度，兩人的分工用依次相連的線段表示，線段的長(zhǎng)等于工序的時(shí)間。從圖中可以檢驗(yàn)，兩人的分工滿足了各個(gè)工序的先后次序關(guān)系。例如，動(dòng)手完成工序I時(shí)，其緊前工序E，F(xiàn)，G都已經(jīng)完工。,(2)由全部工序完工總時(shí)間為27小時(shí)，如果第一臺(tái)機(jī)器效率提高一倍，則至少需要9小時(shí)完工。分工時(shí)，應(yīng)優(yōu)先將關(guān)鍵路線上的工序分配給第一臺(tái)機(jī)器，當(dāng)出現(xiàn)第一臺(tái)機(jī)器完成關(guān)鍵路線上的工序需要等待第二臺(tái)機(jī)器完成某個(gè)相應(yīng)的緊前工序時(shí)，適當(dāng)安排第一臺(tái)機(jī)器去完成原本安排第二臺(tái)機(jī)器的任務(wù)。調(diào)整后的分工可以用圖2-20表示，工期為9小時(shí)。,2.3.2縮短工期,工程的最短工期是由關(guān)鍵路線長(zhǎng)決定的

14、，由此可以推出：要縮短工期必須想法縮短關(guān)鍵路線上工序的時(shí)間。,這里應(yīng)該注意兩個(gè)問題： (1)能否縮短某個(gè)工序的時(shí)間要從實(shí)際出發(fā)。例如圖2-21(a)中的工程似乎縮短工序1-3的時(shí)間為好。但是如果這個(gè)工序表示的是澆注水泥，工程師要求有一定的時(shí)間讓水泥固化，因而不能縮短這個(gè)工序的時(shí)間。 (2)縮短了關(guān)鍵路線上的工序后，新的工程網(wǎng)絡(luò)圖的關(guān)鍵路線可能會(huì)改變。例如圖2-21(a)中的關(guān)鍵路線是1-3-4，最短工期是15。設(shè)想我們要把總工期縮短為12。將關(guān)鍵路線上的工序等比例縮短后變成圖2-21(b)的情況。雖然原先的關(guān)鍵路線縮短成了12，但是新的圖上關(guān)鍵路線變成了1-2-3-4，關(guān)鍵路線的長(zhǎng)為13，并沒

15、有達(dá)到縮短工期為12的目標(biāo)，此時(shí)應(yīng)對(duì)新的工程網(wǎng)絡(luò)圖重新計(jì)算關(guān)鍵路線和討論縮短有關(guān)工序的問題。,2.3.3等待時(shí)間,我們用例子說明與等待時(shí)間有關(guān)的加工次序問題。 例4現(xiàn)有9個(gè)工件（編號(hào)A-I）所需加工時(shí)間（小時(shí)）及前期要求完成的工件號(hào)如表2-6所示。,所有工件在一臺(tái)機(jī)床上加工。由于機(jī)床故障，開始加工時(shí)離協(xié)議完成所有工件加工的時(shí)間只有40小時(shí)。按協(xié)議，每個(gè)工件比計(jì)劃每拖延1小時(shí)完成，要付違約金10元。請(qǐng)安排一個(gè)合理地加工次序，可使所附違約金最少。請(qǐng)列出你安排的加工次序，并計(jì)算出違約金總數(shù)（上海市2006年決賽）。,解:根據(jù)加工次序畫出下面的工程網(wǎng)絡(luò)圖（見圖2-22）。取含工件最多（不一定是關(guān)鍵路線

16、）的工件次序：H-D-C-I-G-A- E，連同工件所需時(shí)間畫出示意圖，見圖2-23?，F(xiàn)在考慮在上述序列適當(dāng)?shù)奈恢貌迦牍ぜ﨎和F。,例5某化學(xué)公司在定期檢測(cè)時(shí)發(fā)現(xiàn)生產(chǎn)管道中共有9處閥門（A-I）發(fā)生有害氣體泄漏。每處閥門在每小時(shí)內(nèi)有害氣體的泄漏量大體相等，約為0.01立方米。閥門的堵漏工作可在不停產(chǎn)的情況下實(shí)施。由于各閥門所處位置不同，因此堵漏所需時(shí)間不同，且堵漏時(shí)必須遵從一定的順序關(guān)系，情況見表2-7（時(shí)間以小時(shí)表示）。,(1)現(xiàn)公司只有一臺(tái)閥門堵漏設(shè)備。問：如何安排，可使有害氣體的泄漏總量最少？要求計(jì)算出堵漏開始到結(jié)束期間有害氣體的泄漏總量。 (2)如公司再增添一臺(tái)性能相同的閥門堵漏設(shè)備，

17、問：此時(shí)應(yīng)如何安排，可使有害氣體的泄漏總量最少？同時(shí)要求計(jì)算出堵漏期間有害氣體的泄漏總量（上海市2007年決賽）,解:這是一個(gè)安排有序工作的問題。將檢修一個(gè)閥門看作一道工序，可根據(jù)堵漏先后次序要求畫出統(tǒng)籌圖如圖2-27所示。,(1)根據(jù)題意可知，用一臺(tái)設(shè)備堵漏，用于堵漏的總時(shí)間與安排堵漏次序無關(guān)，但泄漏量依賴于等待時(shí)間，與堵漏次序有關(guān)。因此，要求泄漏量最少，就是要求安排適當(dāng)?shù)囟侣┐涡?，使所有閥門等待的總時(shí)間最短。在圖2-27中選擇含工序最多（不一定是關(guān)鍵路線）的工序序列C-H-D-G-F，再將其他需檢修的閥門按某種次序逐個(gè)插入到該工序序列中。,(2)對(duì)于有兩臺(tái)設(shè)備的情況，為在最短時(shí)間內(nèi)堵漏，第一臺(tái)設(shè)備應(yīng)依次堵漏關(guān)鍵路線上的各閥門C-H-D-G-F，第二臺(tái)設(shè)備配合按一下順序堵漏：I-B-A-E。堵漏工作時(shí)間為93小時(shí)，等待時(shí)間為169小時(shí)，期間共泄漏有害氣體約2.62立方米。,作業(yè)： （上海市2005年決賽）周一甲公司委托乙工廠加工8個(gè)工件，每個(gè)工件加工費(fèi)為1000元，雙方約定于周五中午12:00前在乙工廠