【正文】 訂單（以到達(dá)的順序） 加工時(shí)間（天） 交貨期（天） A B C D E 3 4 2 6 1 5 6 7 9 2 方案一： FCFS規(guī)則 方案一 利用 FCFS規(guī)則，其流程時(shí)間的結(jié)果如下： 加工順序 加工時(shí)間 交貨日期 流程時(shí)間 A B C D E 3 4 2 6 1 5 6 7 9 2 0+3=3 3+4=7 7+2=9 9+6=15 15+1=16 總流程時(shí)間 =3+7+9+15+16=50（天） 平均流程時(shí)間 =50/5=10天 將每個(gè)訂單的交貨日期與其流程時(shí)間相比較，發(fā)現(xiàn)只有 A訂單能按時(shí)交貨。訂單 B， C， D和 E將會(huì)延期交貨，延期時(shí)間分別為 1,2,6,14天。每個(gè)訂單平均延期 （ 0+1+1+2+6+14） /5= 。 方案二： SPT規(guī)則 方案二 利用 SPT（最短作業(yè)時(shí)間）規(guī)則，流程時(shí)間為： 加工順序 加工時(shí)間 交貨日期 流程時(shí)間 E C A B D 1 2 3 4 6 2 7 5 6 9 0+1=1 1+2=3 3+3=6 6+4=10 10+6=16 總流程時(shí)間 =1+3+6+10+16=36（天） 平均流程時(shí)間 =36/5= SPT規(guī)則的平均流程時(shí)間比 FCFS規(guī)則的平均流程時(shí)間小。另外，訂單 E和 C將在交貨日期前完成，訂單 A僅延期 1天。每個(gè)訂單的平均延期時(shí)間為 （ 0+0+1+4+7） /5=。 方案三： EDD規(guī)則 加工順序 加工時(shí)間 交貨日期 流程時(shí)間 E A B C D 1 3 4 2 6 2 5 6 7 9 0+1=1 1+3=4 4+4=8 8+2=10 10+6=16 總流程時(shí)間 =1+4+8+10+16=39（天） 平均流程時(shí)間 =39/5= 在這種情況下，訂單 B， C和 D將會(huì)延期，平均延期時(shí)間為 （ 0+0+2+3+7） /5=。 方案三 利用 EDD(最早交貨期最先加工 )規(guī)則，排序結(jié)果為 方案四： LCFS規(guī)則 加工順序 加工時(shí)間 交貨日期 流程時(shí)間 E D C B A 1 6 2 4 3 2 9 7 6 5 0+1=1 1+6=7 7+2=9 9+4=13 13+3=16 總流程時(shí)間 =1+7+9+13+16=46（天） 平均流程時(shí)間 =46/5= 平均延期 = 方案四 利用 LCFS（后到先服務(wù)）規(guī)則，預(yù)計(jì)流程時(shí)間為： 方案六： SST規(guī)則 加工順序 加工時(shí)間 交貨日期 流程時(shí)間 E A B D C 1 3 4 6 2 2 5 6 9 7 0+1=1 1+3=4 4+4=8 8+6=14 14+2=16 總流程時(shí)間 =6+4+8+14+16=43（天） 平均流程時(shí)間 =43/5= 平均延期 = 方案六利用 SST剩余松弛時(shí)間最短）規(guī)則，排序結(jié)果為： 優(yōu)先調(diào)度規(guī)則比較 規(guī)則 總的完成時(shí)間 平均完成時(shí)間 平均延期 FCFS SPT EDD LCFS 隨機(jī) SST 50 36 39 46 53 43 10 單臺(tái)設(shè)備排序問題 例：同類型 5個(gè)工件 A、 B、 C、 D、 E，要在一臺(tái)設(shè)備上加工， 用 STP、 EDD規(guī)則及二者混合規(guī)則排序。已知單件加工時(shí)間 和交貨期要求見下表： 零件 A B C D E 加工時(shí)間 3 7 1 5 4 交貨時(shí)間 23 20 8 6 14 “ n個(gè)作業(yè) —— 單臺(tái)工作中心的問題 ” 或 “ n/1” ， 理論上 ， 排序問題的難度隨著工作中心數(shù)量的增加而增大 ， 而不是隨著作業(yè) 數(shù) 量 的 增 加 而 增 大 ， 對 n 的 約 束 是 其 必 須 是 確 定 的有限的數(shù) N個(gè)作業(yè)單臺(tái)工作中心的排序 按照 SPT規(guī)則： 零件加工順序 工序時(shí)間 實(shí)際通過時(shí)間 Fi 要求交貨日期 di 1 3 4 5 7 1 4 8 13 20 C A E D B 8 23 14 6 20 平均流程時(shí)間： 111 ( 1 4 8 13 20) 5niiFF n?? ? ? ? ? ? ? ??交貨最大延誤時(shí)間： Tm a x = m a x( 0 , L 4 ) = F 4 d 4 = 7N個(gè)作業(yè)單臺(tái)工作中心的排序 按照 EDD規(guī)則： 零件加工順序 工序時(shí)間 實(shí)際通過時(shí)間 Fi 要求交貨日期 di 5 1 4 7 3 5 6 10 17 20 D C E B A 6 8 14 20 23 平均流程時(shí)間： 111 ( 5 6 10 17 20) 5niiFF n?? ? ? ? ? ? ? ??交貨最大延誤時(shí)間： Tm ax = 0N個(gè)作業(yè)單臺(tái)工作中心的排序 混合規(guī)則： 如果存在在延誤期為 0的情況下，通過排序使平均通過時(shí)間最小 零件加工順序 工序時(shí)間 實(shí)際通過時(shí)間 Fi 要求交貨日期 di 5 1 3 7 4 1 6 9 13 20 D C A B E 8 6 23 14 20 平均通過設(shè)備時(shí)間： 111 ( 1 6 9 13 20) 5niiFF n?? ? ? ? ? ? ? ??交貨最大延誤時(shí)間： m ax 0D ?n個(gè)作業(yè)兩臺(tái)工作中心排序 1954年提出了一個(gè)排序方法，其目的是極小化從第一個(gè)作業(yè)開始到最后一個(gè)作業(yè)為止的全部流程時(shí)間。約翰遜規(guī)則包含下列幾個(gè)步驟（ n/2)： ； ； ，則將它排到前面；如果最短的作業(yè)時(shí)間來自第二個(gè)工作中心，則將該作業(yè)排到最后； A和 B，直到排序完成 。 n個(gè)作業(yè)兩臺(tái)工作中心排序 i ai bi 1 5 7 2 1 2 3 8 2 4 5 4 5 3 7 6 4 4 1. 從矩陣中找出最短加工時(shí)間，它出現(xiàn)在 M1上，所以，相應(yīng)的工件（工件 2），將工件 2排在第 1位。劃去工件 2的加工時(shí)間。 2. 余下加工時(shí)間中最小者為 2，它出現(xiàn)在 M2上，相應(yīng)的工件（工件 3）應(yīng)將它排到最后一位。劃去工件 3的加工時(shí)間。 3. 繼續(xù)按 Johnson算法安排余下工件的加工順序。 將工件 2排第 1位 2 _ _ _ _ _ 將工件 3排第 6位 2 _ _ _ _ 3 將工件 5排第 2位 2 5 _ _ _ 3 將工件 4排第 5位 2 5 _ _ 4 3 將工件 6排第 3位 2 5 6 _ 4 3 將工件 1排第 4位 2 5 6 1 4 3 答案：最優(yōu)加工順序?yàn)镾=(2,5,6,1,4,3) 例 求表所示， 6/2問題的最優(yōu)解 計(jì)算總流程時(shí)間是多少？ ? 三臺(tái)設(shè)備的流水型排序問題 (n/3/F) ? JohnsonBellman擴(kuò)展算法： ? 當(dāng)滿足下列條件之一時(shí)： ? Min ≥max 或 Min ≥max ? 將 3臺(tái)設(shè)備 A,B,C變換為 2臺(tái)設(shè)備 G， H： ? tiG = tiA+ tiB tiH= tiC+ tiB ? 再按 JohnsonBellman規(guī)則進(jìn)行排序。 ｛ tiA｝ ｛ tiB｝ ｛ tiB｝ ｛ tiC｝ 習(xí)題： ? 例：設(shè)有 J1,J2,J3,J4和 J5等五種零件在三臺(tái)設(shè)備上加工，其工藝順序均相同，加工時(shí)間如下表所示，試求作業(yè)排序問題，并用甘特圖表示，求出總加工時(shí)間。各種零件再機(jī)床上加工所需時(shí)間如下表所示： J1 J2 J3 J4 J5 設(shè)備 A 7 9 10 7 9 設(shè)備 B 6 5 7 4 7 設(shè)備 C 10 6 7 4 12 Min ≥max 或 Min ≥max ｛ tiA｝ ｛ tiB｝ ｛ tiC｝ ｛ tiB｝ 工件 J1 J2 J3 J4 J5 設(shè)備 G 13 14 17 11 16 設(shè)備 H 16 11 14 8 19 排序結(jié)果： J1 J5 J3 J2 J4 甘特圖： 7 9 10 7 9 42 6 10 7 5 4 46 10 12 7 5 4 54 時(shí)間 0 42 46 54 作業(yè) A已辭去了其在政府的工作，以他出色的工作業(yè)績，他能夠在一個(gè)汽車服務(wù)站中找到一個(gè)生產(chǎn)計(jì)劃員的工作。該服務(wù)站的工作主要是按新品牌改制、整修汽車。這個(gè)系統(tǒng)每天能夠處理 10輛汽車。現(xiàn)在的順序是先改制，后噴漆。 問題： A應(yīng)該按什么順序安排汽車修理？ 汽車 1 2 3 4 5 改制時(shí)間 噴漆時(shí)間 汽車 6 7 8 9 10 改制時(shí)間 噴漆時(shí)間 作業(yè) 下表為要排序工件的有關(guān)情況，這些工件需要在一臺(tái)機(jī)床上加工 （ 1）先到先服務(wù)排序結(jié)果是什么？ （ 2）最短作業(yè)時(shí)間排序結(jié)果是什么？ （ 3）剩余松弛時(shí)間排序結(jié)果是什么？ （ 4）最早交貨日期排序結(jié)果是什么？ （ 5）以上排序的流程時(shí)間均值各是多少？ 工件 A B C D E F G 加工時(shí)間 /天 4 12 2 11 10 3 6 交貨日期 20 30 15 16 18 5 9 演講完畢，謝謝觀看！