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

1、2022/7/25第六章 生產(chǎn)作業(yè)排序 2022/7/25 一、作業(yè)排序的概念 作業(yè)排序就是確定工件在設(shè)備上的加工順序，使預(yù)定的目標(biāo)得以實(shí)現(xiàn)的過(guò)程。二、作業(yè)排序的目標(biāo) 1、總流程時(shí)間最短 流程時(shí)間=加工時(shí)間+等待時(shí)間+運(yùn)輸時(shí)間 2、平均流程時(shí)間最短 3、平均在制品占用量最小 4、最大延遲時(shí)間最短 5、平均延遲時(shí)間最短 6、延遲工件最少2022/7/25 三、排序問(wèn)題的分類(lèi) （一）按照機(jī)器數(shù)目的不同 1、單臺(tái)機(jī)器的排序問(wèn)題 2、多臺(tái)機(jī)器的排序問(wèn)題 按照工件加工路線的不同，又可以分為： 流水型（flow shop)的排序問(wèn)題 所有工件的工藝路線都相同 非流水型（job shop)的排序問(wèn)題 每個(gè)工

2、件的工藝路線各不相同 （二）按照工件的到達(dá)情況的不同 1、靜態(tài)排序當(dāng)排序時(shí)，所有的工件都已到達(dá)，并已準(zhǔn)備就緒，可以對(duì)全部工件進(jìn)行一次性排序。 2、動(dòng)態(tài)排序若工件陸續(xù)到達(dá)，要隨時(shí)安排它們的加工順序。 2022/7/25 （三）按照目標(biāo)函數(shù)的不同 1、平均流程時(shí)間最少 2、延期工件最少 2022/7/25四、單臺(tái)設(shè)備上的作業(yè)排序方法排序規(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ī)則ST

3、R(Slack time 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=2022/7/25 以上這些規(guī)則各有其特點(diǎn)，不同的規(guī)則適用于不同的目標(biāo)。例如，F(xiàn)CFS規(guī)則比較公平；SPT規(guī)則可使平均流程時(shí)間最短，從而減少在制品數(shù)量；EDD規(guī)則可使工件的最大延遲時(shí)間最小、平均延誤時(shí)間最小；Moore法則可使延遲的工件數(shù)

4、最少等。FCFS、SPT、EDD優(yōu)先規(guī)則的應(yīng)用【例6-1】下表是在某工作中心等待加工的6項(xiàng)作業(yè)的加工時(shí)間（包含換產(chǎn)時(shí)間）與預(yù)定日期，假設(shè)工作的到達(dá)順序與表中順序相符 。根據(jù)以下規(guī)則來(lái)決定其作業(yè)順序：FCFSSPTEDD并對(duì)它們分別進(jìn)行評(píng)價(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è)順序

5、是A-C-E-B-D-F順序加工時(shí)間流程時(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ī)則流動(dòng)時(shí)間（天）平均流動(dòng)時(shí)間 （天）總延期時(shí)間（天）平均延期時(shí)間 （天）FCFS12020549SPT108184

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

7、加工。（2）工件在加工過(guò)程中采用平行移動(dòng)方式（當(dāng)上一道工序完成后立即進(jìn)入下道工序）。（3）不允許中斷，工件一旦進(jìn)入加工狀態(tài)，一直加工完成為止，中途不插入其他工件。（4）每道工序只在一臺(tái)設(shè)備上加工。（5）工件數(shù)、機(jī)器數(shù)與加工時(shí)間已知。（6）每臺(tái)設(shè)備同時(shí)只能加工一個(gè)工件。2022/7/252、多項(xiàng)作業(yè)、兩臺(tái)機(jī)器的排序- Johnson方法N項(xiàng)作業(yè)，2臺(tái)機(jī)器，所有工件的加工路線都相同。（S.M.Johnson，1954，）AB目標(biāo)：使全部完工時(shí)間最小。條件：每種工件在每臺(tái)機(jī)器上的加工時(shí)間均為已知。2022/7/25Johnson方法步驟：1.選擇最短的作業(yè)時(shí)間；2.如果最短時(shí)間的作業(yè)在第1個(gè)加工中心

8、，則安排在最前面，若在第2個(gè)加工中心，則安排在最后；3.在等待的隊(duì)列中，取消第2步安排了的作業(yè)；4.重復(fù)1，2，3步。2022/7/25【例6-2】五臺(tái)儀器修復(fù)作業(yè)排序某公司在一次火災(zāi)中損壞了5臺(tái)儀器，這些儀器的修復(fù)需要經(jīng)過(guò)如下2道工序：（1）將損壞的儀器運(yùn)至修理車(chē)間，拆卸開(kāi)；（2）清洗儀器部件，更換報(bào)廢部分，裝配，測(cè)試，并送回原車(chē)間。每臺(tái)儀器在兩個(gè)工序的各自所需時(shí)間如表所示。兩道工序分別由不同的人擔(dān)當(dāng)。由于原車(chē)間沒(méi)有這5臺(tái)儀器就無(wú)法恢復(fù)生產(chǎn)，所以希望找到一個(gè)較好的排序方案，使全部修理時(shí)間盡可能短。儀器工序1工序2Y1 Y2 Y3 Y4 Y5 12 4 5 15 1022 5 3 16 820

9、22/7/25解： 原則：1.找min，前道工序-最前 后道工序-最后2.若多個(gè)min,任選。 Y3Y2-Y3Y2- Y5-Y3Y2-Y1- Y5-Y3 Y2-Y1-Y4- Y5-Y3儀器工序1工序2Y1 Y2 Y3 Y4 Y5 12 4 5 15 1022 5 3 16 82022/7/25儀器工序1工序2Y1 Y2 Y3 Y4 Y5 12 4 5 15 1022 5 3 16 8Y2-Y1-Y4-Y5-Y3作業(yè)排序結(jié)果的圖示：機(jī)器空閑Y2Y2Y14Y1438Y41631Y454Y541Y346Y5629Y3651600工序1工序2機(jī)器空閑2022/7/25【例6-3】某一班組有A、B兩臺(tái)設(shè)

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

11、在剩余的J2、J3、J5中重復(fù)上述步驟，求解過(guò)程為： J4 - * - * - J5 - J1 J4 - J2 - * - J5 - J1 J4 - J2 - J3- J5 - J1 當(dāng)同時(shí)出現(xiàn)多個(gè)最小值時(shí)，可從中任選一個(gè)。最后得 J4 - J2 - J3- J5 - J1 2022/7/25(a) J1 - J2 - J3- J4 - J5 26A B(b) J4 - J2 - J3- J5 - J1 可以看出，初始作業(yè)順序的總加工周期是30，用約翰遜法排出的作業(yè)順序總加工周期是26，顯然后者的結(jié)果優(yōu)于前者。 30A B0 服務(wù)作業(yè)計(jì)劃 人員班次計(jì)劃 將服務(wù)員工安排到不同的服務(wù)需求時(shí)間上的作

12、業(yè)計(jì)劃是服務(wù)員工輪班問(wèn)題。1、單班次問(wèn)題：每天只有一個(gè)班次，部門(mén)每天都要營(yíng)業(yè) （1）啟發(fā)方法: 如循環(huán)排序法 （2）最優(yōu)化方法:如整數(shù)線性規(guī)劃法 (3）解析法2、多班次問(wèn)題：每天有多班，一般為兩班或三班 （1）循環(huán)排序法 循環(huán)排序法是一種既簡(jiǎn)單又實(shí)用的啟發(fā)式方法，其基本步驟如下： 1、從每周的員工需求人數(shù)中找到所需員工數(shù)量之和最小的連續(xù)兩個(gè)工作日,安排一名員工在這兩天中休息。 若有相同的兩個(gè)最小總需求量，則可任選其一；或按照預(yù)先約定好的方法選擇其一，如優(yōu)先選擇周六周日。 2、使該兩天的需求人數(shù)保持不變, 其他日期的需求人數(shù)減1(如果是0不變) 3、在新一行中找出所需員工數(shù)量最少的連續(xù)兩天，并再

13、次循環(huán)。將下一名員工分配到剩余的工作日中。 4、重復(fù)上述過(guò)程（步驟2和3），直到所有的人員需求得到滿足。 【例6-4】郵局一周內(nèi)每天的員工需求如表6-1所示。工會(huì)要求每名員工連續(xù)工作五天，然后連續(xù)休息兩天。試制定排班計(jì)劃。日期周一周二周三周四周五周六周日員工需求量3656555表6-1 一周內(nèi)每天的員工需求量 員工周一周二周三周四周五周六周日A3(*)656555（*)B3(*)5(*)45445C35343(*)3(*)4D242(*)3(*)333E1(*)323222(*)F12121(*)1(*)2G0(*)1(*)01111H0100(*)0(*)00在崗員工4676566需要員工3

14、656555多余員工1020011解：表6-2 每周員工安排表（循環(huán)排序法）（2）線性規(guī)劃法 （3）單班次問(wèn)題的解析法 (Brownell and Lowerre,1976) 求解以下問(wèn)題的單班次人員安排問(wèn)題：1、保證每人每周休息兩天2、保證每人每周連休兩天 3、保證每人每周休息兩天 ，隔一周在周末休息 4、保證每人每周連休兩天，隔一周在周末休息 1、保證每人每周休息兩天 設(shè)某單位每周工作7天，每天一班，平常日需要N人，周末需要n人。 W表示所需勞動(dòng)力下限。求解步驟：（1）Wi = max n , N+ 2n / 5 （2）安排Wi n 名工人在周末休息； （3）對(duì)余下的n名工人從1到n編號(hào)，

15、1號(hào)至Wi N號(hào)工人周一休息； （4）安排緊接著的Wi N名工人第二天休息，這里，工人1緊接著工人n ； （5）如果5 Wi 5N + 2n ，則有多余的休息日供分配，此時(shí)可按需要調(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

16、/ 5 , ( 2N + 2 n ) / 3 （1）利用上式計(jì)算W2，給W2名工人編號(hào)； （2）取k = max 0 , 2N +n - 2 W2 ； （3）1至k號(hào)工人（五，六）休息，（k + 1 ） 2 k號(hào)工人（日，一）休息，接下來(lái)的 W2 n k 名工人周末（六，日）休息； （4）對(duì)余下的工人，按（一，二），（二，三），（三，四），（四，五）的順序安排連休，保證有N名工人在平常日當(dāng)班。 【例2】 對(duì)于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、1

17、k（1）號(hào)工人（五、六）休息；k+12k（2）號(hào)（日、一）休息；接下來(lái)W2-n-k（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組工人分配第二周的休

18、息日。如果5 W35N + 2n ，可以先安排1至W3 N 號(hào)工人周五休息，按周五、周四、周一的順序安排休息日； 4、B組的n名工人第一周的班次計(jì)劃與A組的第二周安排計(jì)劃相同?！纠?】 N=7，n = 4，求班次安排。 解：W3 = 9，W3 - 2n = 1名工人周末休息，剩下 2n（8）名分成A、B兩組，A組第1個(gè)周末休息，B組第2個(gè)周末休息。工人1工人9工人8工人7工人6工人5工人4工人3工人2日六五四三二一日六五四三二一4、保證每人每周連休兩天，隔一周在周末休息 求解步驟： W4 = max 2n , N + 2n / 5 ，（4N + 4 n）/ 5 （1）將W4名工人分成A、B兩組：A組W4 / 2名工人，第一周周末休息；B組（W4 W4 / 2 ）名工人，第二周周末休息。 （2）k = max 0 , 4N + 2n 4 W4 ，A組中k/2名工人（五2，六2）休息，k/2名工人（日2，一3）k/2名工人；B組中k/2名工人（五1，六