第六章生產(chǎn)與運(yùn)作管理(生產(chǎn)作業(yè)排序)

1、一、作業(yè)排序的概念一、作業(yè)排序的概念 作業(yè)排序就是確定工件在設(shè)備上的加工順序，作業(yè)排序就是確定工件在設(shè)備上的加工順序，使預(yù)定的目標(biāo)得以實(shí)現(xiàn)的過程。使預(yù)定的目標(biāo)得以實(shí)現(xiàn)的過程。二、作業(yè)排序的目標(biāo)二、作業(yè)排序的目標(biāo) 1、總流程時(shí)間最短、總流程時(shí)間最短 流程時(shí)間流程時(shí)間=加工時(shí)間加工時(shí)間+等待時(shí)間等待時(shí)間+運(yùn)輸時(shí)間運(yùn)輸時(shí)間 2、平均流程時(shí)間最短、平均流程時(shí)間最短 3、平均在制品占用量最小、平均在制品占用量最小 4、最大延遲時(shí)間最短、最大延遲時(shí)間最短 5、平均延遲時(shí)間最短、平均延遲時(shí)間最短 6、延遲工件最少、延遲工件最少三、排序問題的分類排序問題的分類 （一）（一）按照機(jī)器數(shù)目的不同按照機(jī)器數(shù)目的不同

2、 1 1、單臺機(jī)器的排序問題、單臺機(jī)器的排序問題 2 2、多臺機(jī)器的排序問題、多臺機(jī)器的排序問題 按照工件加工路線的不同，又可以分為：按照工件加工路線的不同，又可以分為： 流水型（流水型（flow shop)flow shop)的排序問題的排序問題 所有工件的工藝路線都相同所有工件的工藝路線都相同 非流水型（非流水型（job shop)job shop)的排序問題的排序問題 每個(gè)工件的工藝路線各不相同每個(gè)工件的工藝路線各不相同 （二）按照工件的到達(dá)情況的不同（二）按照工件的到達(dá)情況的不同 1 1、靜態(tài)排序、靜態(tài)排序當(dāng)排序時(shí)，所有的工件都已到達(dá)，并當(dāng)排序時(shí)，所有的工件都已到達(dá)，并已準(zhǔn)備就緒，可以

3、對全部工件進(jìn)行一次性排序。已準(zhǔn)備就緒，可以對全部工件進(jìn)行一次性排序。 2 2、動(dòng)態(tài)排序、動(dòng)態(tài)排序若工件陸續(xù)到達(dá)，要隨時(shí)安排它們的若工件陸續(xù)到達(dá)，要隨時(shí)安排它們的加工順序。加工順序。 （三）按照目標(biāo)函數(shù)的不同按照目標(biāo)函數(shù)的不同 1 1、平均流程時(shí)間最少、平均流程時(shí)間最少 2 2、延期工件最少、延期工件最少 排序規(guī)則：（1）最短加工時(shí)間優(yōu)先規(guī)則SPT(Shortest processing time)（2）最短交貨期優(yōu)先規(guī)則EDD(Earliest due date)（3）先到先加工規(guī)則FCFS(First come first served)（4）最小松動(dòng)時(shí)間優(yōu)先規(guī)則STR(Slack time

4、 remaining)（松動(dòng)時(shí)間=交貨期-加工時(shí)間）（5）臨界比率最小優(yōu)先規(guī)則SCR(Smallest critical ratio) 交貨期當(dāng)前日期 作業(yè)時(shí)間（6）綜合規(guī)則（綜合使用兩種規(guī)則，如先按照交貨期優(yōu)先排序，然后按照最短加工時(shí)間優(yōu)先的原則排序）（7）后到先加工規(guī)則（8）隨機(jī)規(guī)則（9）延遲工件最少的規(guī)則（Moore法則） CR= 以上這些規(guī)則各有其特點(diǎn)，不同的規(guī)則適用于不同的目標(biāo)。例如，F(xiàn)CFS規(guī)則比較公平；SPT規(guī)則可使平均流程時(shí)間最短，從而減少在制品數(shù)量；EDD規(guī)則可使工件的最大延遲時(shí)間最小、平均延誤時(shí)間最??；Moore法則可使延遲的工件數(shù)最少等。FCFS、SPT、EDD優(yōu)先規(guī)則的

5、應(yīng)用【例6-1】下表是在某工作中心等待加工的6項(xiàng)作業(yè)的加工時(shí)間（包含換產(chǎn)時(shí)間）與預(yù)定日期，假設(shè)工作的到達(dá)順序與表中順序相符 。根據(jù)以下規(guī)則來決定其作業(yè)順序：FCFSSPTEDD并對它們分別進(jìn)行評價(jià)。 作 業(yè)加工時(shí)間（天）預(yù)定日期（天）ABCDEF284105127164171518按FCFS規(guī)則排序 排序的結(jié)果是A-B-C-D-E-F。順序加工時(shí)間流程時(shí)間預(yù)定交貨期延期天數(shù)(如果為負(fù)則賦值0) ABCDEF 28410512210142429417164171518001071423合計(jì)4112054平均 120/6=2054/6=9按SPT規(guī)則 作業(yè)順序是A-C-E-B-D-F順序加工時(shí)間流

6、程時(shí)間預(yù)定交貨期延期天數(shù)(如果為負(fù)則賦值0) ACEBDF 245810122611192941741516171802031223合計(jì)4110840平均 108/6=1840/6=6.67按EDD規(guī)則 作業(yè)順序是C-A-E-B-D-F順序加工時(shí)間流程時(shí)間預(yù)定交貨期延期天數(shù)(如果為負(fù)則賦值0) CAEBDF425810124611192941471516171800031223合計(jì)4111038平均 110/6=18.33 38/6=6.33 規(guī)則規(guī)則流動(dòng)時(shí)間流動(dòng)時(shí)間（天）（天）平均流動(dòng)平均流動(dòng)時(shí)間時(shí)間 （天）（天）總延期時(shí)總延期時(shí)間（天）間（天）平均延期平均延期時(shí)間時(shí)間 （天）（天）FCFS

7、12020549SPT10818406.67EDD11018.33386.33不同排序規(guī)則的結(jié)果分析不同排序規(guī)則的結(jié)果分析排序規(guī)則的比較：1、SPT規(guī)則，可以使作業(yè)流程時(shí)間最短，使滯留在加工過程的平均在制品占用量最少，有利于節(jié)約流動(dòng)資金，節(jié)約廠房、倉庫面積和保管費(fèi)用。但是，由于未考慮交貨期，所以可能發(fā)生交貨延期。 2、EDD規(guī)則，平均延遲天數(shù)最少，減少違約罰款損失，但缺點(diǎn)是平均流程時(shí)間增加，不利于節(jié)約在制品占用資金。3、FCFS規(guī)則，主要問題是加工時(shí)間過長。但其使用簡單，且體現(xiàn)公平，常用于服務(wù)業(yè)的排隊(duì)系統(tǒng)。假設(shè)：（1）一個(gè)工件不能同時(shí)在不同機(jī)器上加工。（2）工件在加工過程中采用平行移動(dòng)方式（當(dāng)

8、上一道工序完成后立即進(jìn)入下道工序）。（3）不允許中斷，工件一旦進(jìn)入加工狀態(tài)，一直加工完成為止，中途不插入其他工件。（4）每道工序只在一臺設(shè)備上加工。（5）工件數(shù)、機(jī)器數(shù)與加工時(shí)間已知。（6）每臺設(shè)備同時(shí)只能加工一個(gè)工件。 N N項(xiàng)作業(yè)，項(xiàng)作業(yè)，2 2臺機(jī)器，所有工件的加工路臺機(jī)器，所有工件的加工路線都相同線都相同。（S.M.Johnson，1954，）AB目標(biāo)：目標(biāo)：使全部完工時(shí)間最小。條件：條件：每種工件在每臺機(jī)器上的加工時(shí)間均為已知。 步驟：步驟：1.1.選擇最短的作業(yè)時(shí)間；選擇最短的作業(yè)時(shí)間；2.2.如果最短時(shí)間的作業(yè)在第如果最短時(shí)間的作業(yè)在第1 1個(gè)加工中心，則個(gè)加工中心，則安排在最前

9、面，若在第安排在最前面，若在第2 2個(gè)加工中心，則安排個(gè)加工中心，則安排在最后；在最后；3.3.在等待的隊(duì)列中，取消第在等待的隊(duì)列中，取消第2 2步安排了的作業(yè)；步安排了的作業(yè)；4.4.重復(fù)重復(fù)1 1，2 2，3 3步。步。某公司在一次火災(zāi)中損壞了某公司在一次火災(zāi)中損壞了5 5臺儀器，這些儀器的修復(fù)需臺儀器，這些儀器的修復(fù)需要經(jīng)過如下要經(jīng)過如下2 2道工序：道工序：（1 1）將損壞的儀器運(yùn)至修理車間，拆卸開；）將損壞的儀器運(yùn)至修理車間，拆卸開；（2 2）清洗儀器部件，更換報(bào)廢部分，裝配，測試，并送）清洗儀器部件，更換報(bào)廢部分，裝配，測試，并送回原車間。回原車間。每臺儀器在兩個(gè)工序的各自所需時(shí)間

10、如表所示。兩道工每臺儀器在兩個(gè)工序的各自所需時(shí)間如表所示。兩道工序分別由不同的人擔(dān)當(dāng)。由于原車間沒有這序分別由不同的人擔(dān)當(dāng)。由于原車間沒有這5 5臺儀器就臺儀器就無法恢復(fù)生產(chǎn)，所以希望找到一個(gè)較好的排序方案，無法恢復(fù)生產(chǎn)，所以希望找到一個(gè)較好的排序方案，使全部修理時(shí)間盡可能短。使全部修理時(shí)間盡可能短。儀器工序1工序2Y1 Y2 Y3 Y4 Y5 12 4 5 15 1022 5 3 16 8 原則：原則：1.1.找找minmin，前道工序，前道工序-最前最前 后道工序后道工序-最后最后2.2.若多個(gè)若多個(gè)min,min,任選。任選。 Y3Y3Y2-Y3Y2-Y3Y2- Y5-Y3Y2- Y5-

11、Y3Y2-Y1- Y5-Y3 Y2-Y1- Y5-Y3 Y2-Y1-Y4- Y5-Y3Y2-Y1-Y4- Y5-Y3儀器工序1工序2Y1 Y2 Y3 Y4 Y5 12 4 5 15 1022 5 3 16 8儀器工序1工序2Y1 Y2 Y3 Y4 Y5 12 4 5 15 1022 5 3 16 8Y2-Y1-Y4-Y5-Y3作業(yè)排序結(jié)果的圖示：Y2Y2Y14Y1438Y41631Y454Y541Y346Y5629Y3651600【例例6-3】某一班組有某一班組有A、B兩臺設(shè)備，要完成兩臺設(shè)備，要完成5個(gè)工件的加工個(gè)工件的加工任務(wù)。每個(gè)工件在設(shè)備上的加工時(shí)間如下表所示。求總加任務(wù)。每個(gè)工件在設(shè)

12、備上的加工時(shí)間如下表所示。求總加工周期最短的作業(yè)順序。工周期最短的作業(yè)順序。 工件在兩臺設(shè)備上的加工時(shí)間工件在兩臺設(shè)備上的加工時(shí)間 工件編號工件編號 J1 J2 J3 J4 J5 設(shè)備設(shè)備A 3 6 7 1 5 設(shè)備設(shè)備B 2 8 6 4 3 解：由約翰遜法可知，表解：由約翰遜法可知，表5-8中最小加工時(shí)間值是中最小加工時(shí)間值是1個(gè)時(shí)間單個(gè)時(shí)間單位，它又是出現(xiàn)在設(shè)備位，它又是出現(xiàn)在設(shè)備1上，根據(jù)約翰遜法的規(guī)則，應(yīng)將上，根據(jù)約翰遜法的規(guī)則，應(yīng)將對應(yīng)的工件對應(yīng)的工件4排在第一位，即得：排在第一位，即得： J4 - * - * - * - * 去掉去掉J4，在剩余的工件中再找最小值，不難看出，最小值

13、，在剩余的工件中再找最小值，不難看出，最小值是是2個(gè)時(shí)間單位，它是出現(xiàn)在設(shè)備個(gè)時(shí)間單位，它是出現(xiàn)在設(shè)備2上的，所以應(yīng)將對應(yīng)的上的，所以應(yīng)將對應(yīng)的工件工件J1排在最后一位，即：排在最后一位，即： J4 - * - * - * - J1 再去掉再去掉J1，在剩余的，在剩余的J2、J3、J5中重復(fù)上述步驟，求解中重復(fù)上述步驟，求解過程為：過程為： J4 - * - * - J5 - J1 J4 - J2 - * - J5 - J1 J4 - J2 - J3- J5 - J1 當(dāng)同時(shí)出現(xiàn)多個(gè)最小值時(shí)，可從中任選一個(gè)。最后得當(dāng)同時(shí)出現(xiàn)多個(gè)最小值時(shí)，可從中任選一個(gè)。最后得 J4 - J2 - J3- J5

14、 - J1 (a) J1 - J2 - J3- J4 - J5 26A B(b) J4 - J2 - J3- J5 - J1 可以看出，初始作業(yè)順序的總加工周期是可以看出，初始作業(yè)順序的總加工周期是30，用約翰遜法排出的作業(yè)，用約翰遜法排出的作業(yè)順序總加工周期是順序總加工周期是26，顯然后者的結(jié)果優(yōu)于前者。，顯然后者的結(jié)果優(yōu)于前者。 30A B0 服務(wù)作業(yè)計(jì)劃 人員班次人員班次計(jì)劃計(jì)劃 將服務(wù)員工安排到不同的服務(wù)需求時(shí)間上的作業(yè)計(jì)劃是服務(wù)員工輪班問題。1、單班次問題：每天只有一個(gè)班次，部門每天都、單班次問題：每天只有一個(gè)班次，部門每天都要營業(yè)要營業(yè) （1）啟發(fā)方法: 如循環(huán)排序法 （2）最優(yōu)化

15、方法:如整數(shù)線性規(guī)劃法 (3）解析法2、多班次問題：每天有多班，一般為兩班或三班、多班次問題：每天有多班，一般為兩班或三班 （1）循環(huán)排序法循環(huán)排序法 循環(huán)排序法循環(huán)排序法是一種是一種既簡單又實(shí)用的啟發(fā)式方法，其基本步驟既簡單又實(shí)用的啟發(fā)式方法，其基本步驟如下：如下： 1、從每周的員工需求從每周的員工需求人數(shù)人數(shù)中找到所需員工數(shù)量之和最小的連中找到所需員工數(shù)量之和最小的連續(xù)兩個(gè)工作日續(xù)兩個(gè)工作日,安排一名員工在這兩天中休息。安排一名員工在這兩天中休息。 若有相同的兩個(gè)最小總需求量，則可任選其一；或按照預(yù)先若有相同的兩個(gè)最小總需求量，則可任選其一；或按照預(yù)先約定好的方法選擇其一，如優(yōu)先選擇周六約

16、定好的方法選擇其一，如優(yōu)先選擇周六周日。周日。 2、使該兩天的需求人數(shù)保持不變、使該兩天的需求人數(shù)保持不變, 其他日期的需求人數(shù)減其他日期的需求人數(shù)減1(如果是如果是0不變不變) 3、在新一行中找出所需員工數(shù)量最少的連續(xù)兩天，并再次循在新一行中找出所需員工數(shù)量最少的連續(xù)兩天，并再次循環(huán)。將下一名員工分配到剩余的工作日中。環(huán)。將下一名員工分配到剩余的工作日中。 4、重復(fù)上述過程（步驟重復(fù)上述過程（步驟2和和3），直到所有的人員需求得到滿），直到所有的人員需求得到滿足。足。 【例6-4】郵局一周內(nèi)每天的員工需求如表6-1所示。工會要求每名員工連續(xù)工作五天，然后連續(xù)休息兩天。試制定排班計(jì)劃。日期周一

17、周二周三周四周五周六周日員工需求量3656555表表6-1 一周內(nèi)每天的員工需求量一周內(nèi)每天的員工需求量 員工員工周一周一周二周二周三周三周四周四周五周五周六周六周日周日A3(*)656555（*)B3(*)5(*)45445C35343(*)3(*)4D242(*)3(*)333E1(*)323222(*)F12121(*)1(*)2G0(*)1(*)01111H0100(*)0(*)00在崗員在崗員工工4676566需要員需要員工工3656555多余員多余員工工1020011解：解：表表6-2 每周員工安排表（循環(huán)排序法）每周員工安排表（循環(huán)排序法）（2）線性規(guī)劃法線性規(guī)劃法且為整數(shù)（星期

18、日的約束）（星期六的約束）（星期五的約束）（星期四的約束）（星期三的約束）（星期二的約束）（星期一的約束）0.min7765436654325543214743213763212765211765417654321ixbxxxxxbxxxxxbxxxxxbxxxxxbxxxxxbxxxxxbxxxxxtsxxxxxxxZ （3）單班次問題的解析法）單班次問題的解析法 (Brownell and Lowerre,1976) 求解以下問題的單班次人員安排問題：求解以下問題的單班次人員安排問題：1、保證每人每周休息兩天、保證每人每周休息兩天2、保證每人每周連休兩天、保證每人每周連休兩天 3、保證每人

19、每周休息兩天、保證每人每周休息兩天 ，隔一周在周末休息隔一周在周末休息 4、保證每人每周連休兩天，隔一周在周末休息、保證每人每周連休兩天，隔一周在周末休息 1、保證每人每周休息兩天、保證每人每周休息兩天 設(shè)某單位每周工作7天，每天一班，平常日需要N人，周末需要n人。 W表示所需勞動(dòng)力下限。求解步驟：（1）Wi = max n , N+ 2n / 5 （2）安排Wi n 名工人在周末休息； （3）對余下的n名工人從1到n編號，1號至Wi N號工人周一休息； （4）安排緊接著的Wi N名工人第二天休息，這里，工人1緊接著工人n ； （5）如果5 Wi 5N + 2n ，則有多余的休息日供分配，此時(shí)

20、可按需要調(diào)整班次計(jì)劃，只要保證每名工人一周休息兩天，平日有N人當(dāng)班即可。 工人工人1工人工人9工人工人8工人工人7工人工人6工人工人5工人工人4工人工人3工人工人2日日六六五五四四三三二二一一日日六六五五四四三三二二一一【例1】 設(shè)N=5，n = 8，求班次安排。 （1）W1= max 8 , 5+ 28 / 5 = 9，（2）W1-n=9-8=1名工人在周末休息 ；（3）W1-N=9-5=4名工人在周一休息 解解2、保證每人每周連休兩天、保證每人每周連休兩天 求解步驟：W2 = max n , N + 2n / 5 , ( 2N + 2 n ) / 3 （1）利用上式計(jì)算W2，給W2名工人編

21、號； （2）取k = max 0 , 2N +n - 2 W2 ； （3）1至k號工人（五，六）休息，（k + 1 ） 2 k號工人（日，一）休息，接下來的 W2 n k 名工人周末（六，日）休息； （4）對余下的工人，按（一，二），（二，三），（三，四），（四，五）的順序安排連休，保證有N名工人在平常日當(dāng)班。 【例2】 對于N=6，n=5，求班次安排。 1、W2 =max 5 , 6 + 25 / 5 , ( 26 + 2 5 ) / 3 =8 2、k = max 0 , 26 +5 - 2 8 =1。3、1k（1）號工人（五、六）休息；k+12k（2）號（日、一）休息；接下來W2-n-k（

22、8-5-1=2）名工人（六、日）休息4、余下的工人按（一、二）,（二、三）, （三、四）, （四、五）工人工人1工人工人8工人工人7工人工人6工人工人5工人工人4工人工人3工人工人2日日六六五五四四三三二二一一日日六六五五四四三三二二一一解解3、保證每人每周休息兩天、保證每人每周休息兩天 ，隔一周在周末休息隔一周在周末休息 求解步驟：求解步驟：W3 = max 2n , N + 2n / 5 ： 1、將W3 - 2 n 名工人安排周末休息； 2、將余下的2 n名工人A、B兩組，每組 n名工人，A組的工人第一周周末休息，B組的工人第二周周末休息； 3、按照條件一 每周休息兩天的步驟（3）和（4），給A組工人分配第二周的休息日。如果5 W35N + 2n ，可以先安排1至W3 N 號工人周五休息，按周五、周四、周一的順序安排休息日； 4、B組的n名工人第一周的班次計(jì)劃