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

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

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

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

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

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

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

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