【文章內(nèi)容簡介】 + P5 + P6 ) ＝ 6 P1 + 5 P2 + 4P3 + 3P4 + 2P5 + P6. 那么各個零件平均停留時間為 從上式可知，對于一臺機器 n個零件的排序問題，只要系數(shù)越大，配上加工時間越少的，即按照加工時間排出加工順序，加工時間越少的零件排在越前面，加工時間越多的零件排在越后面，可使各個零件的平均停留時間為最少。 管 理 運 籌 學 49 167。 5 車間作業(yè)計劃模型 二、兩臺機器、 n個零件 例 ，這些零件要求先在車床上車削，然后再在 磨床上加工，每臺機器上各零件加工時間如表 125所示。 表 1 應該如何安排這五個零件的先后順序才能使完成這五個零件的總的加工時間為最少？ 解：由于每個零件必須先進行車床加工，再進行磨床加工，所以在車床上加 工零件的順序與在磨床上加工零件的順序是一樣的。 如果這些零件在車床上和磨床上加工順序都為 1， 2， 3， 4， 5。我們用圖 121 中的線條圖來表示各零件加工的開始時間與完成時間，這種圖是由一根時間軸和 車床、磨床在每個時間段的狀況的圖形所構(gòu)成。 零件 車床 磨床 零件 車床 磨床 1 2 3 4 5 管 理 運 籌 學 50 167。 5 車間作業(yè)計劃模型 圖 1 從上圖中我們可以看出，加工時間的延長主要是由于磨床的停工待料 造成的，只要減少磨床的停工待料的時間就能減少整個加工任務的總時間。 為了減少磨床的停工待料，我們應該一方面把在車床上加工時間越短的零 件越早加工，減少磨床等待的時間；另一方面把在磨床上加工時間越長的 零件越晚加工，以便充分利用前面的時間，這樣我們就得到了使完成全部 零件加工任務所需總時間最少的零件排序方法。 1 2 3 4 5 1 車床 磨床 2 3 4 5 0 10 管 理 運 籌 學 51 167。 5 車間作業(yè)計劃模型 尋找例 2的最優(yōu)解：我們在表 125中找到所列出的最短加工時間是 ,它是第二道工序磨床 加工零件 2的所需時間，由于這個時間與磨床有關(guān)，故我們把零件 2放在加工順序的末尾，即第五位，并在表中劃去零件 2 所在行。如表 126中紅色線條所示。 接著，我們又找到最短加工時間為 ，這一時間與磨床（第二工序）有關(guān)，我們把 磨床加 工時間為 1放到除第五外的加工順序的末尾，即第四位加工，同時把 表中的零件 1所在 的行劃去。如表 126中黃色線條所示。 下一個最短加工時間為 ，這個加工時間是車床（第一工序）加工零件 5的所需時間，故 把零件 5排在加工順序的第一位上，同時把表中的零件 5所在的行劃去。如表 126中藍色線條所 示。 零件 車床 （第一工序） 磨床 （第二工序） 零件 車床 （第一工序） 磨床 （第二工序） 1 2 3 4 5 表 2 管 理 運 籌 學 52 同樣，下一個最短加工時間為 1，這是車床加工零件 3的所需時間，故 把零件 3排在第二位上，同時把零件 3所在的行劃去。如表 126中黑色線條 所示。 這樣就得到了最優(yōu)加工順序： 5， 3， 4， 1， 2。一共只需 7個小時就能 完成全部加工。 從例 2中我們可以歸納出關(guān)于兩臺機器 n個零件的排序問題，使得全部 任務總的時間 最短的排序算法。 在加工所需時間表上選出最短加工時間 tij，這是第 i工序加工 j零件所需時間，當 i=1時，將零件 j的順序盡量靠前，若 i=2時，將零件 j的順序盡量 靠后。在表上劃去零件 j的所在行，回到步驟 1。 167。 5 車間作業(yè)計劃模型 管 理 運 籌 學 基本概念 ? 杜邦公司 — 關(guān)鍵路線法 CPM 確定型 ? 美國海軍武器局 — 計劃評審技術(shù) PERT ? 網(wǎng)絡圖（有向賦權(quán)圖）的構(gòu)成 ? 結(jié)點，也稱事項，一道工序的開始或結(jié)束 ? 工序（?。鄬Κ毩⒌幕顒?，消耗資源 ? 虛工序，只表示銜接關(guān)系，不消耗資源 ? 工序時間（權(quán)），完成工序的時間消耗 167。 6 統(tǒng)籌方法 管 理 運 籌 學 網(wǎng)絡規(guī)則 ? 避免循環(huán)、不留缺口 ? 一一對應：一道工序用兩個事項表示 ? 3 、從左向右依次展開 例： 工 序 A B C D E F G H I 緊前工序 A B B C、 D C、 D E、 F G 工序時間 4 6 6 7 5 9 7 4 8 ? ? ? ? ? ? A,4 B,6 D,7 E,5 F,9 H,4 I,8 C,6 G,7 管 理 運 籌 學 關(guān)鍵路線法－－ CPM 時間參數(shù)運算 什么是關(guān)鍵路線？ 作業(yè)時間 t（ i， j），經(jīng)驗數(shù)據(jù)、統(tǒng)計數(shù)據(jù) 事項最早時間 TE(j)＝ max{TE(i)+ t（ i， j） } 到齊上課，最后到者決定最早開課時間 事項最遲時間 TL(i)＝ min{TL(j) t（ i， j） } 保證 12點吃飯，路最遠者決定最遲下課時間 工序最早可能開工時間 TES(i,j)＝ TE(i) = max{TES(h,i)+ t（ h,i ） } 工序最早可能完工時間 TEF(i,j)＝ TES(i,j)+ t（ i， j） 管 理 運 籌 學 工序最遲必須開工時間 TLS（ i,j)＝ TL(j)－ t（ i,j)＝ min{TLs(j,k) t（ i， j） } 工序最遲必須完工時間 TLF（ i,j)＝ TL(j)＝ TLS（ i,j)+ t（ i,j) 工序總時差：在不影響其緊后工序 最遲必須 開工時間的前提下，本工序可以推遲的時間 R（ i,j）＝ TLS(i,j)－ TES(i,j) ＝ TLF(i,j)－ TEF(i,j) ＝ min{TLS(j,k) } – TEF（ i,j） 工序單時差：在不影響其緊后工序 最早可能 開工時間的前提下，本工序可以推遲的時間 r （ i,j）＝ min{TES(j,k) } – TEF（ i,j） 管 理 運 籌 學 計算關(guān)系式 ? 這些時間參數(shù)的關(guān)系可以用下圖表示工作的關(guān)系狀態(tài)。 工作 A工作 A工作 A 的緊后工作 BES i jLS i jEF i jLF i jES j kEF j kLS i kLF j k工作a的 總時差工作 a 的自由時差工作A的 總時差最早開始最遲開始TF i j = L S i j E S i jTF i j = L F i j E F i jFF i j = E S j k E F i j工作持續(xù)時間 Di i j管 理 運 籌 學 時間參數(shù)圖解 . 解上例： 計算事項 ? ? ? 時間參數(shù) ? ? ? ? 解上例：計算事項時間參數(shù)TES TLS TEF TLF TES TLS TEF TLS r(i,j) R（ i,j） A4 B6 C6 G7 D7 E5 F9 H4 I 8 0 0 4 7 6 13 22 20 28 28 20 24 13 6 關(guān)鍵路線：由總時差為零的工序構(gòu)成 B D G I t（ i,j) t（ j,k) 管 理 運 籌 學 ? 解上例 計算工序時間參數(shù) 工序 i j t(i,j) ES EF LS LF R r A ? ? 4 0 4 3 7 3 0 B ? ? 6 0 6 0 6 0 0 C ? ? 6 4 10 7 13 3 3 D ? ? 7 6 13 6 13 0 0 E ? ? 5 6 11 19 24 13 11 F ? ? 9 13 22 15 24 2 0 G ? ? 7 13 20 13 20 0 0 H ? ? 4 22 26 24 28 2 2 I ? ? 8 20 28 20 28 0 0 管 理 運 籌 學 60 167。 6 統(tǒng)籌方法 統(tǒng)籌方法包括繪制計劃網(wǎng)絡圖、進度安排、網(wǎng)絡優(yōu)化等環(huán)節(jié)，下面進 行分別討論： 一、計劃網(wǎng)絡圖 統(tǒng)籌方法的第一步工作就是繪制計劃網(wǎng)絡圖，也就是將工序（或稱為 活動）進度表轉(zhuǎn)換為統(tǒng)籌方法的網(wǎng)絡圖。 例 某公司研制新產(chǎn)品的部分工序與所需時間以及它們之間的相互 關(guān)系都顯示在其工序進度表如表 3所示，請畫出其統(tǒng)籌方法網(wǎng)絡圖。 表 3 工序代號 工序內(nèi)容 所需時間（天 ) 緊前工序 a b c d e 產(chǎn)品設計與工藝設計 外購配套零件 外購生產(chǎn)原料 自制主件 主配可靠性試驗 60 15 13 38 8 a a c b,d 管 理 運 籌 學 61 167。 6 統(tǒng)籌方法 解 :用網(wǎng)絡圖表示上述的工序進度表 網(wǎng)絡圖中的點表示一個事件 ,是一個或若干個工序的開始或結(jié)束 ,是相 鄰工序在時間上的分界點 ,點用圓圈表示 ,圓圈里的數(shù)字表示點的編號。弧 表示一個工序（或活動），弧的方向是從工序開始指向工序的結(jié)束，弧上 是各工序的代號，下面標以完成此工序所需的時間（或資源）等數(shù)據(jù)，即 為對此弧所賦的權(quán)數(shù)． １ ２ ４ ５ ３ a b c d e 60 13 8 38 15 圖 4 管 理 運 籌 學 62 167。 6 統(tǒng)籌方法 例４、把例３的工序進度表做一些擴充，如表 15，請畫出其統(tǒng)籌方法的網(wǎng)絡圖。 表 5 工序代號 所需時間（天） 緊前工序 工序代號 所需時間（天） 緊前工序 a b c d 60 15 13 38 － a a c e f g h 8 10 16 5 b，ｄ d d e，ｆ，ｇ 管 理 運 籌 學 63 167。 6 統(tǒng)籌方法 解：我們把工序 e 擴充到圖 5發(fā)生了問題，由于ｄ是 e 的緊前工序，故ｄ的結(jié)束應該是 e 的開始，所以代表 e 的弧的起點應該是④，由于工序ｂ的結(jié)束也是④，所以工序ｂ也成了工序 e 的緊前工序，與題意不符。 為此我們設立虛工序。虛工序是實際上并不存在而虛設的工序，用來表示相鄰工序的銜接關(guān)系，不需要人力、物力等資源與時間。 1 5 2 6 4 3 a 60 b 15 8 e 10 13 d c 38 f 圖 5 管 理 運 籌 學 64 167。 6 統(tǒng)籌方法