第十四章作業(yè)排序

1、 第十四章第十四章 作業(yè)排序作業(yè)排序 當(dāng)多項任務(wù)（零件）排隊等候某個工作中心加工時，哪項任務(wù)應(yīng)當(dāng)優(yōu)先安排？這就是作業(yè)優(yōu)先次序安排（簡稱為作業(yè)排序）要解決的問題。 1、排序規(guī)則 常用的排序規(guī)則有； 先到先服務(wù)規(guī)則(FCFS 排序排序)：即任務(wù)的處理順序是按照其到達(dá)工作中心的先后次序依次進(jìn)行。 最短作業(yè)時間規(guī)則(SPT 排序排序)：即在所有排隊等候某個工作中心加工的任務(wù)中，選擇作業(yè)時間（準(zhǔn)備時間十加工時間）最短的那一件最先加工。 第十五章第十五章 作業(yè)排序作業(yè)排序 超限最短加工時間規(guī)則：即事先設(shè)定一個排隊等候時間限度對于等候時間超過此時間限度的任務(wù)，優(yōu)先安排其中作業(yè)時間最短的任務(wù)。如果沒有哪項任務(wù)

2、的排隊等候時間超限，則按最短作業(yè)時間規(guī)則排序。 最早到期規(guī)則：即在所有排隊等候某個工作中心加工的任務(wù)中，按照計劃交貨期從早到晚的順序，最先安排計劃交貨期最早的任務(wù)，而不管該項任務(wù)何時到達(dá)該工作中心。最短松弛時間規(guī)則：所謂松弛時間，等于某項任務(wù)距離計劃交貨期的剩余時間與該項任務(wù)的作業(yè)時間之差。而最短松弛時間規(guī)則，是將最高優(yōu)先級分派給具有最短松弛時間的任務(wù)，而不管其計劃交貨期的早晚。 第十五章第十五章 作業(yè)排序作業(yè)排序例： 假設(shè)任務(wù)是按字母順序依次同時到達(dá)某個工作中心的即A任務(wù)第1個到達(dá)；其次是B任務(wù)；等等。顧客要求的交貨日期（或計劃交貨日期）和各項任務(wù)的作業(yè)時間均列示于表中。表還列出了每項任務(wù)的

3、通過時間，所謂通過時間是任務(wù)在系統(tǒng)中的排隊等候時間與作業(yè)時間之和。 下面我們以平均通過時間、系統(tǒng)中每天的平均任務(wù)數(shù)（包括等候的任務(wù)和正處于加工中的任務(wù)）和任務(wù)的平均延遲時間三項指標(biāo)，分別對先到先服務(wù)、按最短作業(yè)時間規(guī)則和按最短松弛時間規(guī)則的排序結(jié)果進(jìn)行評價。 按先到先服務(wù)規(guī)則排序按先到先服務(wù)規(guī)則排序 a.全部完成時間為55天。b.平均通過時間為318天。其計算過程如下： （421354455）5= 318（天） c.系統(tǒng)中每天的平均任務(wù)數(shù)為289。 54+417+314+29+111 55 = 289（件天） d.任務(wù)的平均延遲時間為18.6天。 （0十117十32十43）5186（天） 任務(wù)

4、的優(yōu)先次序作業(yè)時間通過時間交貨期從現(xiàn)在算起ABCDE41714911421354455620181212 全部完成55 按最短作業(yè)時間規(guī)則對其排序結(jié)果如表所示按最短作業(yè)時間規(guī)則對其排序結(jié)果如表所示a.全部完成時間為55天。b.平均通過時間計算過程如下： （413243855）5= 26.8（天）c.系統(tǒng)中每天的平均任務(wù)數(shù)計算方法如下： 54+49+311+214+11755=2.44（件天） d. 任務(wù)的平均延遲時間計算如下：0+1+12+20+355=13.6天 任務(wù)的優(yōu)先次序作業(yè)時間通過時間交貨期從現(xiàn)在算起ADECB49111417413243855612121820 全部完成55按最短松

5、弛時間規(guī)則排序其結(jié)果如表所示按最短松弛時間規(guī)則排序其結(jié)果如表所示a.全部完成時間為55天。 b.平均通過時間計算過程如下： （1115324155）5= 30.8（天）c.系統(tǒng)中每天的平均任務(wù)數(shù)計算方法如下：511+44+317+29+11455=2.8（件天）d. 任務(wù)的平均延遲時間計算如下：0+9+12+29+375=17.4天 任務(wù)的優(yōu)先次序作業(yè)時間松馳時間通過時間交貨期從現(xiàn)在算起EABDC11417914123341115324155126201218 全部完成55B和D調(diào)換順序后的結(jié)果：a.全部完成時間為55天。b.平均通過時間計算過程如下： 29.2（天）c.系統(tǒng)中每天的平均任務(wù)數(shù)

6、計算方法如下： 2.65（件天）d. 任務(wù)的平均延遲時間計算如下：15.8天 平均通平均通過時間過時間（天）（天）系統(tǒng)中每系統(tǒng)中每天的平均天的平均任務(wù)數(shù)任務(wù)數(shù)（件（件/天）天）任務(wù)的平任務(wù)的平均延遲時均延遲時間（天）間（天）先到先服務(wù)規(guī)則先到先服務(wù)規(guī)則31.82.8918.6最短作業(yè)時間規(guī)則最短作業(yè)時間規(guī)則26.82.4413.6最短松弛時間規(guī)則最短松弛時間規(guī)則30.82.817.4三種規(guī)則的排序結(jié)果三種規(guī)則的排序結(jié)果 第十五章第十五章 作業(yè)排序作業(yè)排序 通過比較三種規(guī)則的排序結(jié)果，我們發(fā)現(xiàn)最短作業(yè)時間規(guī)則的效果最好。雖然每種規(guī)則的全部作業(yè)時間都是55天，但最短作業(yè)時間規(guī)則具有較低平均通過時間

7、，由于任務(wù)在系統(tǒng)中平均逗留的時間較短。故系統(tǒng)的在制品庫存較低，以及顧客（零件）服務(wù)質(zhì)量較高；又由于系統(tǒng)中平均任務(wù)數(shù)較少，使得系統(tǒng)較少出現(xiàn)堵塞現(xiàn)象；此外，平均延遲時間較短說明交貨比較及時。最短作業(yè)時間規(guī)則具有較優(yōu)越的排序效果，這不是本例中的一種偶然現(xiàn)象而是一種一般的特征。 第十五章第十五章 作業(yè)排序作業(yè)排序 2、作業(yè)排序1 n個工件在一臺設(shè)備上加工 這是一種最簡單的排序問題，排序規(guī)律是加工工時短的工件先加工。2n個工件需經(jīng)過二臺設(shè)備加工 比較簡單的一種情況是所有工件在二臺設(shè)備上加工的次序相同，此時用約翰遜法可以求解。排序規(guī)則：第一步，取出最小工時tmin，若該工時為第一工序的，則最先加工；反之，則放在最后加工。第二步，將該已排序工件劃去。第三步，對余下的工件重復(fù)上述排序步驟，直至完畢。 例：有五個工件在二臺設(shè)備上加工，加工順序相同，先在設(shè)備1上加工，再在設(shè)備2加工，工時列于表，用約翰遜法排序。 工件作業(yè)工時tij設(shè)備1設(shè)備2ABCDE5374626534B C E D A B C E D A 2 4 6 8 10 11 12 14 16 18 20 22 24 26 28 加工周期為：27 第十五章第十五章 作業(yè)排序