《管理運(yùn)籌學(xué)》第12章排序與統(tǒng)籌方法課件

第十二章排序與統(tǒng)籌方法§1車間作業(yè)計(jì)劃模型§2統(tǒng)籌方法在本章中，我們將介紹車間作業(yè)計(jì)劃模型和統(tǒng)籌方法。這兩個(gè)問(wèn)題盡管處理的方法有所不同，但當(dāng)我們面臨必須完成若干項(xiàng)不能同時(shí)進(jìn)行的工作時(shí)，它們都將幫助我們應(yīng)該按照怎樣的次序、怎樣的時(shí)間表來(lái)做這些工作，使得效果最佳（例如完成全部工作所用時(shí)間最短或費(fèi)用最少等等）。1第十二章排序與統(tǒng)籌方法§1車間作業(yè)計(jì)劃模型§1車間作業(yè)計(jì)劃模型車間作業(yè)計(jì)劃是指一個(gè)工廠生產(chǎn)工序的計(jì)劃和安排。一、一臺(tái)機(jī)器、n個(gè)零件的排序問(wèn)題二、兩臺(tái)機(jī)器、n個(gè)零件的排序問(wèn)題2§1車間作業(yè)計(jì)劃模型2§1車間作業(yè)計(jì)劃模型一、一臺(tái)機(jī)器、n個(gè)零件的排序問(wèn)題例1.某車間只有一臺(tái)高精度的磨床，常常出現(xiàn)很多零件同時(shí)要求這臺(tái)磨床加工的情況，現(xiàn)有六個(gè)零件同時(shí)要求加工，這六個(gè)零件加工所需時(shí)間如下表所示。

應(yīng)該按照什么樣的加工順序來(lái)加工這六個(gè)零件，才能使得這六個(gè)零件在車間里停留的平均時(shí)間為最少？零件加工時(shí)間（小時(shí)）零件加工時(shí)間（小時(shí)）1231.82.00.54560.91.31.53§1車間作業(yè)計(jì)劃模型一、一臺(tái)機(jī)器、n個(gè)零件的排序問(wèn)題零件§1車間作業(yè)計(jì)劃模型

例1解：如果我們用Pi表示安排在第i位加工的零件所需的時(shí)間，用Tj表示安排在第j位加工的零件在車間里總的停留時(shí)間，則有

Tj=P1+P2+…+Pj-1+Pj=不同的加工順序得到不同的各零件的平均停留時(shí)間，如何得到一個(gè)使得各零件的平均停留時(shí)間最少的排序呢？這就是我們最后要解決的優(yōu)化問(wèn)題，而且我們要設(shè)法找到一種簡(jiǎn)便的算法。對(duì)于某種加工順序，我們知道安排在第j位加工的零件在車間里總的停留時(shí)間為T(mén)j，Tj=可知這六個(gè)零件的停留時(shí)間為：

T1+T2+T3+T4+T5+T6＝P1+(P1+P2)+(P1+P2+P3)+(P1+P2+P3+P4)+(P1+P2+P3+P4+P5)+(P1+P2+P3+P4+P5+P6)＝6P1+5P2+4P3+3P4+2P5+P6.那么各個(gè)零件平均停留時(shí)間為

從上式可知，對(duì)于一臺(tái)機(jī)器n個(gè)零件的排序問(wèn)題，只要系數(shù)越大，配上加工時(shí)間越少的，即按照加工時(shí)間排出加工順序，加工時(shí)間越少的零件排在越前面，加工時(shí)間越多的零件排在越后面，可使各個(gè)零件的平均停留時(shí)間為最少。4§1車間作業(yè)計(jì)劃模型例1解：如果我們用§1車間作業(yè)計(jì)劃模型二、兩臺(tái)機(jī)器、n個(gè)零件

例2.某工廠根據(jù)合同定做一些零件，這些零件要求先在車床上車削，然后再在磨床上加工，每臺(tái)機(jī)器上各零件加工時(shí)間如表12-5所示。表12-5

應(yīng)該如何安排這五個(gè)零件的先后順序才能使完成這五個(gè)零件的總的加工時(shí)間為最少？解：由于每個(gè)零件必須先進(jìn)行車床加工，再進(jìn)行磨床加工，所以在車床上加工零件的順序與在磨床上加工零件的順序是一樣的。如果這些零件在車床上和磨床上加工順序都為1，2，3，4，5。我們用圖12-1中的線條圖來(lái)表示各零件加工的開(kāi)始時(shí)間與完成時(shí)間，這種圖是由一根時(shí)間軸和車床、磨床在每個(gè)時(shí)間段的狀況的圖形所構(gòu)成。零件車床磨床零件車床磨床1231.52.01.00.50.251.75451.250.752.51.255§1車間作業(yè)計(jì)劃模型二、兩臺(tái)機(jī)器、n個(gè)零件零件車床磨床零§1車間作業(yè)計(jì)劃模型圖12-1從上圖中我們可以看出，加工時(shí)間的延長(zhǎng)主要是由于磨床的停工待料造成的，只要減少磨床的停工待料的時(shí)間就能減少整個(gè)加工任務(wù)的總時(shí)間。為了減少磨床的停工待料，我們應(yīng)該一方面把在車床上加工時(shí)間越短的零件越早加工，減少磨床等待的時(shí)間；另一方面把在磨床上加工時(shí)間越長(zhǎng)的零件越晚加工，以便充分利用前面的時(shí)間，這樣我們就得到了使完成全部零件加工任務(wù)所需總時(shí)間最少的零件排序方法。123451車床磨床23450106§1車間作業(yè)計(jì)劃模型123451車床磨床23450106§1車間作業(yè)計(jì)劃模型尋找例2的最優(yōu)解：我們?cè)诒?2-5中找到所列出的最短加工時(shí)間是0.25,它是第二道工序磨床加工零件2的所需時(shí)間，由于這個(gè)時(shí)間與磨床有關(guān)，故我們把零件2放在加工順序的末尾，即第五位，并在表中劃去零件2所在行。如表12-6中紅色線條所示。

接著，我們又找到最短加工時(shí)間為0.5，這一時(shí)間與磨床（第二工序）有關(guān)，我們把磨床加工時(shí)間為0.5的零件1放到除第五外的加工順序的末尾，即第四位加工，同時(shí)把表中的零件1所在的行劃去。如表12-6中黃色線條所示。下一個(gè)最短加工時(shí)間為0.75，這個(gè)加工時(shí)間是車床（第一工序）加工零件5的所需時(shí)間，故把零件5排在加工順序的第一位上，同時(shí)把表中的零件5所在的行劃去。如表12-6中藍(lán)色線條所示。零件車床（第一工序）磨床（第二工序）零件車床（第一工序）磨床（第二工序）1231.52.01.00.50.251.75451.250.752.51.25表12-67§1車間作業(yè)計(jì)劃模型尋找例2的最優(yōu)解：我

同樣，下一個(gè)最短加工時(shí)間為1，這是車床加工零件3的所需時(shí)間，故把零件3排在第二位上，同時(shí)把零件3所在的行劃去。如表12-6中黑色線條所示。這樣就得到了最優(yōu)加工順序：5，3，4，1，2。一共只需7個(gè)小時(shí)就能完成全部加工。從例2中我們可以歸納出關(guān)于兩臺(tái)機(jī)器n個(gè)零件的排序問(wèn)題，使得全部任務(wù)總的時(shí)間最短的排序算法。在加工所需時(shí)間表上選出最短加工時(shí)間tij，這是第i工序加工j零件所需時(shí)間，當(dāng)i=1時(shí)，將零件j的順序盡量靠前，若i=2時(shí)，將零件j的順序盡量靠后。在表上劃去零件j的所在行，回到步驟1?！?車間作業(yè)計(jì)劃模型8同樣，下一個(gè)最短加工時(shí)間為1，這是車床加工§2統(tǒng)籌方法統(tǒng)籌方法包括繪制計(jì)劃網(wǎng)絡(luò)圖、進(jìn)度安排、網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)，下面進(jìn)行分別討論：一、計(jì)劃網(wǎng)絡(luò)圖統(tǒng)籌方法的第一步工作就是繪制計(jì)劃網(wǎng)絡(luò)圖，也就是將工序（或稱為活動(dòng)）進(jìn)度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡(luò)圖。例3、某公司研制新產(chǎn)品的部分工序與所需時(shí)間以及它們之間的相互關(guān)系都顯示在其工序進(jìn)度表如表12-8所示，請(qǐng)畫(huà)出其統(tǒng)籌方法網(wǎng)絡(luò)圖。表12-8工序代號(hào)工序內(nèi)容所需時(shí)間（天)緊前工序abcde產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì)外購(gòu)配套零件外購(gòu)生產(chǎn)原料自制主件主配可靠性試驗(yàn)601513388-aacb,d9§2統(tǒng)籌方法統(tǒng)籌方法包括繪制計(jì)劃網(wǎng)絡(luò)圖、進(jìn)§2統(tǒng)籌方法解:用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表網(wǎng)絡(luò)圖中的點(diǎn)表示一個(gè)事件,是一個(gè)或若干個(gè)工序的開(kāi)始或結(jié)束,是相鄰工序在時(shí)間上的分界點(diǎn),點(diǎn)用圓圈表示,圓圈里的數(shù)字表示點(diǎn)的編號(hào)?；”硎疽粋€(gè)工序（或活動(dòng)），弧的方向是從工序開(kāi)始指向工序的結(jié)束，弧上是各工序的代號(hào)，下面標(biāo)以完成此工序所需的時(shí)間（或資源）等數(shù)據(jù)，即為對(duì)此弧所賦的權(quán)數(shù)．

１２４５３abcde601383815圖12-410§2統(tǒng)籌方法解:用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表１２４５３ab§2統(tǒng)籌方法

例４、把例３的工序進(jìn)度表做一些擴(kuò)充，如表12-9，請(qǐng)畫(huà)出其統(tǒng)籌方法的網(wǎng)絡(luò)圖。

表12-9工序代號(hào)所需時(shí)間（天）緊前工序工序代號(hào)所需時(shí)間（天）緊前工序abcd60151338－aacefgh810165b，ｄdde，ｆ，ｇ11§2統(tǒng)籌方法例４、把例３的工序進(jìn)度表做一些擴(kuò)充，如表§2統(tǒng)籌方法

解：我們把工序ｆ擴(kuò)充到圖12-4發(fā)生了問(wèn)題，由于ｄ是ｆ的緊前工序，故ｄ的結(jié)束應(yīng)該是ｆ的開(kāi)始，所以代表ｆ的弧的起點(diǎn)應(yīng)該是④，由于工序ｂ的結(jié)束也是④，所以工序ｂ也成了工序ｆ的緊前工序，與題意不符。為此我們?cè)O(shè)立虛工序。虛工序是實(shí)際上并不存在而虛設(shè)的工序，用來(lái)表示相鄰工序的銜接關(guān)系，不需要人力、物力等資源與時(shí)間。

152643a60b158e1013dc38f圖12-512§2統(tǒng)籌方法解：我們把工序ｆ擴(kuò)充到圖12-§2統(tǒng)籌方法在網(wǎng)絡(luò)圖上添加ｇ、ｈ工序得網(wǎng)絡(luò)圖12-6。

在統(tǒng)籌方法的網(wǎng)絡(luò)圖中不允許兩個(gè)點(diǎn)之間多于一條弧，因此增加了一個(gè)點(diǎn)和虛工序如圖12-7。1256734a6015bec13d388h510fg16圖12-613§2統(tǒng)籌方法在網(wǎng)絡(luò)圖上添加ｇ、ｈ§2統(tǒng)籌方法在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時(shí)，要注意圖中不能有缺口和回路。1257834a6015bec13d388h510f616g圖12-714§2統(tǒng)籌方法1257834a6015bec13d388h5§2統(tǒng)籌方法二、網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線在繪制出網(wǎng)絡(luò)圖之后，我們可以由網(wǎng)絡(luò)圖求出：1、完成此工程項(xiàng)目所需的最少時(shí)間。2、每個(gè)工序的開(kāi)始時(shí)間與結(jié)束時(shí)間。3、關(guān)鍵路線及其應(yīng)用的關(guān)鍵工序。4、非關(guān)鍵工序在不影響工程的完成時(shí)間的前提下，其開(kāi)始時(shí)間與結(jié)束時(shí)間可以推遲多久。例5、某公司裝配一條新的生產(chǎn)線，具體過(guò)程如表12-10,求：完成此工程的最少時(shí)間，關(guān)鍵路線及相應(yīng)的關(guān)鍵工序，各工序的最早開(kāi)始時(shí)間和非關(guān)鍵工序在不影響工程完成時(shí)間的前提下，其開(kāi)始時(shí)間與結(jié)束時(shí)間可以推遲多久。15§2統(tǒng)籌方法二、網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線15§2統(tǒng)籌方法表12-10工序代號(hào)工序內(nèi)容所需時(shí)間（天）緊前工序abcdefghij生產(chǎn)線設(shè)計(jì)外購(gòu)零配件下料、鍛件工裝制造1木模、鑄件機(jī)械加工1工裝制造2機(jī)械加工2機(jī)械加工3裝配調(diào)試60451020401830152535/aaaacdd,egb,i,f,h16§2統(tǒng)籌方法表12-10工序代號(hào)工序內(nèi)容所需時(shí)間（天）緊前§2統(tǒng)籌方法解：據(jù)表12-10,繪制網(wǎng)絡(luò)圖如圖12-8。圖12-8如圖12-8,①-②-③-⑦-⑧就是一條關(guān)鍵路線，我們要干完所有的工序就必須走完所有這樣的路線，由于很多工序可以同時(shí)進(jìn)行，所以網(wǎng)絡(luò)中最長(zhǎng)的路線就決定了完成整個(gè)工程所需的最少時(shí)間，這條路線稱為關(guān)鍵路線。12346785a60b45echj35ig1030d204025f181517§2統(tǒng)籌方法解：據(jù)表12-10,繪制網(wǎng)絡(luò)圖如圖12-8。1§2統(tǒng)籌方法下面我們給出找關(guān)鍵路線的辦法首先，從網(wǎng)絡(luò)的發(fā)點(diǎn)開(kāi)始，按順序計(jì)算出每個(gè)工序的最早開(kāi)始時(shí)間（ES)和最早結(jié)束時(shí)間（EF)，設(shè)一個(gè)工序所需的時(shí)間為t，這對(duì)于同一個(gè)工序來(lái)說(shuō)，有EF=ES+t。

工序a的最早開(kāi)始時(shí)間工序a的最早完成時(shí)間11a[0，60]60圖12-918§2統(tǒng)籌方法下面我們給出找關(guān)鍵路線的辦法工序a的最早工序a§2統(tǒng)籌方法

圖12-10其次,從網(wǎng)絡(luò)的收點(diǎn)開(kāi)始計(jì)算出在不影響整個(gè)工程最早結(jié)束時(shí)間的情況下各個(gè)工序的最晚開(kāi)始時(shí)間(縮寫(xiě)為L(zhǎng)S)和最晚結(jié)束時(shí)間（縮寫(xiě)為L(zhǎng)F),顯然對(duì)同一工序有LS=LF-t1236785a[0,60]60b[60,105]45e[60.100]c[60,70]h[100,115]j[135,170]35i[110.135]g[80,110]30d[60.80]204025f[70,88]184101519§2統(tǒng)籌方法1236785a[0,60]60b[60,1§2統(tǒng)籌方法

運(yùn)用此法則，可以從首點(diǎn)開(kāi)始計(jì)算出每個(gè)工序的LF與LS，如圖12-11所示。

接著，可以計(jì)算出每一個(gè)工序的時(shí)差，把在不影響工程最早結(jié)束時(shí)間的條件下，工序最早開(kāi)始（或結(jié)束）的時(shí)間可以推遲的時(shí)間，成為該工序的時(shí)差，對(duì)每個(gè)工序來(lái)說(shuō)其時(shí)差記為T(mén)s有Ts=LS-ES=LF-EF1236785a[0,60]60[0,60]b[60,105]45[90,135]e[60.100]c[60,70]h[100,115]j[135,170]35[135,170]i[110.135]g[80,110]30[80,110]d[60.80]20[60,80]40[80,120]25[110,135]f[70,88]18[117,135]410[107,117]15[120,13520§2統(tǒng)籌方法運(yùn)用此法則，可以從首點(diǎn)開(kāi)始計(jì)算§2統(tǒng)籌方法

最后將各工序的時(shí)差，以及其他信息構(gòu)成工序時(shí)間表如表12-11所示。這樣就找到了一條由關(guān)鍵工序a,d,g,i和j依次連接成的從發(fā)點(diǎn)到收點(diǎn)的關(guān)鍵路線。21§2統(tǒng)籌方法最后將各工序的時(shí)差，以及其他信息構(gòu)第十二章排序與統(tǒng)籌方法§1車間作業(yè)計(jì)劃模型§2統(tǒng)籌方法在本章中，我們將介紹車間作業(yè)計(jì)劃模型和統(tǒng)籌方法。這兩個(gè)問(wèn)題盡管處理的方法有所不同，但當(dāng)我們面臨必須完成若干項(xiàng)不能同時(shí)進(jìn)行的工作時(shí)，它們都將幫助我們應(yīng)該按照怎樣的次序、怎樣的時(shí)間表來(lái)做這些工作，使得效果最佳（例如完成全部工作所用時(shí)間最短或費(fèi)用最少等等）。22第十二章排序與統(tǒng)籌方法§1車間作業(yè)計(jì)劃模型§1車間作業(yè)計(jì)劃模型車間作業(yè)計(jì)劃是指一個(gè)工廠生產(chǎn)工序的計(jì)劃和安排。一、一臺(tái)機(jī)器、n個(gè)零件的排序問(wèn)題二、兩臺(tái)機(jī)器、n個(gè)零件的排序問(wèn)題23§1車間作業(yè)計(jì)劃模型2§1車間作業(yè)計(jì)劃模型一、一臺(tái)機(jī)器、n個(gè)零件的排序問(wèn)題例1.某車間只有一臺(tái)高精度的磨床，常常出現(xiàn)很多零件同時(shí)要求這臺(tái)磨床加工的情況，現(xiàn)有六個(gè)零件同時(shí)要求加工，這六個(gè)零件加工所需時(shí)間如下表所示。

應(yīng)該按照什么樣的加工順序來(lái)加工這六個(gè)零件，才能使得這六個(gè)零件在車間里停留的平均時(shí)間為最少？零件加工時(shí)間（小時(shí)）零件加工時(shí)間（小時(shí)）1231.82.00.54560.91.31.524§1車間作業(yè)計(jì)劃模型一、一臺(tái)機(jī)器、n個(gè)零件的排序問(wèn)題零件§1車間作業(yè)計(jì)劃模型

例1解：如果我們用Pi表示安排在第i位加工的零件所需的時(shí)間，用Tj表示安排在第j位加工的零件在車間里總的停留時(shí)間，則有

Tj=P1+P2+…+Pj-1+Pj=不同的加工順序得到不同的各零件的平均停留時(shí)間，如何得到一個(gè)使得各零件的平均停留時(shí)間最少的排序呢？這就是我們最后要解決的優(yōu)化問(wèn)題，而且我們要設(shè)法找到一種簡(jiǎn)便的算法。對(duì)于某種加工順序，我們知道安排在第j位加工的零件在車間里總的停留時(shí)間為T(mén)j，Tj=可知這六個(gè)零件的停留時(shí)間為：

T1+T2+T3+T4+T5+T6＝P1+(P1+P2)+(P1+P2+P3)+(P1+P2+P3+P4)+(P1+P2+P3+P4+P5)+(P1+P2+P3+P4+P5+P6)＝6P1+5P2+4P3+3P4+2P5+P6.那么各個(gè)零件平均停留時(shí)間為

從上式可知，對(duì)于一臺(tái)機(jī)器n個(gè)零件的排序問(wèn)題，只要系數(shù)越大，配上加工時(shí)間越少的，即按照加工時(shí)間排出加工順序，加工時(shí)間越少的零件排在越前面，加工時(shí)間越多的零件排在越后面，可使各個(gè)零件的平均停留時(shí)間為最少。25§1車間作業(yè)計(jì)劃模型例1解：如果我們用§1車間作業(yè)計(jì)劃模型二、兩臺(tái)機(jī)器、n個(gè)零件

例2.某工廠根據(jù)合同定做一些零件，這些零件要求先在車床上車削，然后再在磨床上加工，每臺(tái)機(jī)器上各零件加工時(shí)間如表12-5所示。表12-5

應(yīng)該如何安排這五個(gè)零件的先后順序才能使完成這五個(gè)零件的總的加工時(shí)間為最少？解：由于每個(gè)零件必須先進(jìn)行車床加工，再進(jìn)行磨床加工，所以在車床上加工零件的順序與在磨床上加工零件的順序是一樣的。如果這些零件在車床上和磨床上加工順序都為1，2，3，4，5。我們用圖12-1中的線條圖來(lái)表示各零件加工的開(kāi)始時(shí)間與完成時(shí)間，這種圖是由一根時(shí)間軸和車床、磨床在每個(gè)時(shí)間段的狀況的圖形所構(gòu)成。零件車床磨床零件車床磨床1231.52.01.00.50.251.75451.250.752.51.2526§1車間作業(yè)計(jì)劃模型二、兩臺(tái)機(jī)器、n個(gè)零件零件車床磨床零§1車間作業(yè)計(jì)劃模型圖12-1從上圖中我們可以看出，加工時(shí)間的延長(zhǎng)主要是由于磨床的停工待料造成的，只要減少磨床的停工待料的時(shí)間就能減少整個(gè)加工任務(wù)的總時(shí)間。為了減少磨床的停工待料，我們應(yīng)該一方面把在車床上加工時(shí)間越短的零件越早加工，減少磨床等待的時(shí)間；另一方面把在磨床上加工時(shí)間越長(zhǎng)的零件越晚加工，以便充分利用前面的時(shí)間，這樣我們就得到了使完成全部零件加工任務(wù)所需總時(shí)間最少的零件排序方法。123451車床磨床234501027§1車間作業(yè)計(jì)劃模型123451車床磨床23450106§1車間作業(yè)計(jì)劃模型尋找例2的最優(yōu)解：我們?cè)诒?2-5中找到所列出的最短加工時(shí)間是0.25,它是第二道工序磨床加工零件2的所需時(shí)間，由于這個(gè)時(shí)間與磨床有關(guān)，故我們把零件2放在加工順序的末尾，即第五位，并在表中劃去零件2所在行。如表12-6中紅色線條所示。

接著，我們又找到最短加工時(shí)間為0.5，這一時(shí)間與磨床（第二工序）有關(guān)，我們把磨床加工時(shí)間為0.5的零件1放到除第五外的加工順序的末尾，即第四位加工，同時(shí)把表中的零件1所在的行劃去。如表12-6中黃色線條所示。下一個(gè)最短加工時(shí)間為0.75，這個(gè)加工時(shí)間是車床（第一工序）加工零件5的所需時(shí)間，故把零件5排在加工順序的第一位上，同時(shí)把表中的零件5所在的行劃去。如表12-6中藍(lán)色線條所示。零件車床（第一工序）磨床（第二工序）零件車床（第一工序）磨床（第二工序）1231.52.01.00.50.251.75451.250.752.51.25表12-628§1車間作業(yè)計(jì)劃模型尋找例2的最優(yōu)解：我

同樣，下一個(gè)最短加工時(shí)間為1，這是車床加工零件3的所需時(shí)間，故把零件3排在第二位上，同時(shí)把零件3所在的行劃去。如表12-6中黑色線條所示。這樣就得到了最優(yōu)加工順序：5，3，4，1，2。一共只需7個(gè)小時(shí)就能完成全部加工。從例2中我們可以歸納出關(guān)于兩臺(tái)機(jī)器n個(gè)零件的排序問(wèn)題，使得全部任務(wù)總的時(shí)間最短的排序算法。在加工所需時(shí)間表上選出最短加工時(shí)間tij，這是第i工序加工j零件所需時(shí)間，當(dāng)i=1時(shí)，將零件j的順序盡量靠前，若i=2時(shí)，將零件j的順序盡量靠后。在表上劃去零件j的所在行，回到步驟1。§1車間作業(yè)計(jì)劃模型29同樣，下一個(gè)最短加工時(shí)間為1，這是車床加工§2統(tǒng)籌方法統(tǒng)籌方法包括繪制計(jì)劃網(wǎng)絡(luò)圖、進(jìn)度安排、網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)，下面進(jìn)行分別討論：一、計(jì)劃網(wǎng)絡(luò)圖統(tǒng)籌方法的第一步工作就是繪制計(jì)劃網(wǎng)絡(luò)圖，也就是將工序（或稱為活動(dòng)）進(jìn)度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡(luò)圖。例3、某公司研制新產(chǎn)品的部分工序與所需時(shí)間以及它們之間的相互關(guān)系都顯示在其工序進(jìn)度表如表12-8所示，請(qǐng)畫(huà)出其統(tǒng)籌方法網(wǎng)絡(luò)圖。表12-8工序代號(hào)工序內(nèi)容所需時(shí)間（天)緊前工序abcde產(chǎn)品設(shè)計(jì)與工藝設(shè)計(jì)外購(gòu)配套零件外購(gòu)生產(chǎn)原料自制主件主配可靠性試驗(yàn)601513388-aacb,d30§2統(tǒng)籌方法統(tǒng)籌方法包括繪制計(jì)劃網(wǎng)絡(luò)圖、進(jìn)§2統(tǒng)籌方法解:用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表網(wǎng)絡(luò)圖中的點(diǎn)表示一個(gè)事件,是一個(gè)或若干個(gè)工序的開(kāi)始或結(jié)束,是相鄰工序在時(shí)間上的分界點(diǎn),點(diǎn)用圓圈表示,圓圈里的數(shù)字表示點(diǎn)的編號(hào)?；”硎疽粋€(gè)工序（或活動(dòng)），弧的方向是從工序開(kāi)始指向工序的結(jié)束，弧上是各工序的代號(hào)，下面標(biāo)以完成此工序所需的時(shí)間（或資源）等數(shù)據(jù)，即為對(duì)此弧所賦的權(quán)數(shù)．

１２４５３abcde601383815圖12-431§2統(tǒng)籌方法解:用網(wǎng)絡(luò)圖表示上述的工序進(jìn)度表１２４５３ab§2統(tǒng)籌方法

例４、把例３的工序進(jìn)度表做一些擴(kuò)充，如表12-9，請(qǐng)畫(huà)出其統(tǒng)籌方法的網(wǎng)絡(luò)圖。

表12-9工序代號(hào)所需時(shí)間（天）緊前工序工序代號(hào)所需時(shí)間（天）緊前工序abcd60151338－aacefgh810165b，ｄdde，ｆ，ｇ32§2統(tǒng)籌方法例４、把例３的工序進(jìn)度表做一些擴(kuò)充，如表§2統(tǒng)籌方法

解：我們把工序ｆ擴(kuò)充到圖12-4發(fā)生了問(wèn)題，由于ｄ是ｆ的緊前工序，故ｄ的結(jié)束應(yīng)該是ｆ的開(kāi)始，所以代表ｆ的弧的起點(diǎn)應(yīng)該是④，由于工序ｂ的結(jié)束也是④，所以工序ｂ也成了工序ｆ的緊前工序，與題意不符。為此我們?cè)O(shè)立虛工序。虛工序是實(shí)際上并不存在而虛設(shè)的工序，用來(lái)表示相鄰工序的銜接關(guān)系，不需要人力、物力等資源與時(shí)間。

152643a60b158e1013dc38f圖12-533§2統(tǒng)籌方法解：我們把工序ｆ擴(kuò)充到圖12-§2統(tǒng)籌方法在網(wǎng)絡(luò)圖上添加ｇ、ｈ工序得網(wǎng)絡(luò)圖12-6。

在統(tǒng)籌方法的網(wǎng)絡(luò)圖中不允許兩個(gè)點(diǎn)之間多于一條弧，因此增加了一個(gè)點(diǎn)和虛工序如圖12-7。1256734a6015bec13d388h510fg16圖12-634§2統(tǒng)籌方法在網(wǎng)絡(luò)圖上添加ｇ、ｈ§2統(tǒng)籌方法在繪制統(tǒng)籌方法的網(wǎng)絡(luò)圖時(shí)，要注意圖中不能有缺口和回路。1257834a6015bec13d388h510f616g圖12-735§2統(tǒng)籌方法1257834a6015bec13d388h5§2統(tǒng)籌方法二、網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線在繪制出網(wǎng)絡(luò)圖之后，我們可以由網(wǎng)絡(luò)圖求出：1、完成此工程項(xiàng)目所需的最少時(shí)間。2、每個(gè)工序的開(kāi)始時(shí)間與結(jié)束時(shí)間。3、關(guān)鍵路線及其應(yīng)用的關(guān)鍵工序。4、非關(guān)鍵工序在不影響工程的完成時(shí)間的前提下，其開(kāi)始時(shí)間與結(jié)束時(shí)間可以推遲多久。例5、某公司裝配一條新的生產(chǎn)線，具體過(guò)程如表12-10,求：完成此工程的最少時(shí)間，關(guān)鍵路線及相應(yīng)的關(guān)鍵工序，各工序的最早開(kāi)始時(shí)間和非關(guān)鍵工序在不影響工程完成時(shí)間的前提下，其開(kāi)始時(shí)間與結(jié)束時(shí)間可以推遲多久。36§2統(tǒng)籌方法二、網(wǎng)絡(luò)時(shí)間與關(guān)鍵路線15§2統(tǒng)籌方法表12-10工序代號(hào)工序內(nèi)容所需時(shí)間（天）緊前工序abcdefghij生產(chǎn)線設(shè)計(jì)外購(gòu)零配件下料、鍛件工裝制造1木模、鑄件機(jī)械加工1工裝制造2機(jī)械加工2機(jī)械加工3裝配調(diào)試60451020401830152535/aaaacdd,egb,i,f,h37§2統(tǒng)籌方法表12-10工序代號(hào)工序內(nèi)容所需時(shí)間（天）緊前§2統(tǒng)籌方法解：據(jù)表12-10,繪制網(wǎng)絡(luò)圖如圖12-8。圖12-8如圖12-8,①-②-③-⑦-⑧就是一條關(guān)鍵路線，我們要干完所有的工序就必須走完所有這樣的路線，由于很多工序可以同時(shí)進(jìn)行，所以網(wǎng)絡(luò)中最長(zhǎng)的路線就決定了完成整個(gè)工程所需的最少時(shí)間，這條路線稱為關(guān)鍵路線。12346785a60b45echj35ig