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

2、 1 1、單臺機器的排序問題、單臺機器的排序問題 2 2、多臺機器的排序問題、多臺機器的排序問題 按照工件加工路線的不同，又可以分為：按照工件加工路線的不同，又可以分為： 流水型（流水型（flow shop)flow shop)的排序問題的排序問題 所有工件的工藝路線都相同所有工件的工藝路線都相同 非流水型（非流水型（job shop)job shop)的排序問題的排序問題 每個工件的工藝路線各不相同每個工件的工藝路線各不相同 （二）按照工件的到達情況的不同（二）按照工件的到達情況的不同 1 1、靜態排序、靜態排序當排序時，所有的工件都已到達，并當排序時，所有的工件都已到達，并已準備就緒，可以

3、對全部工件進行一次性排序。已準備就緒，可以對全部工件進行一次性排序。 2 2、動態排序、動態排序若工件陸續到達，要隨時安排它們的若工件陸續到達，要隨時安排它們的加工順序。加工順序。 （三）按照目標函數的不同按照目標函數的不同 1 1、平均流程時間最少、平均流程時間最少 2 2、延期工件最少、延期工件最少 排序規則：（1）最短加工時間優先規則SPT(Shortest processing time)（2）最短交貨期優先規則EDD(Earliest due date)（3）先到先加工規則FCFS(First come first served)（4）最小松動時間優先規則STR(Slack time

4、 remaining)（松動時間=交貨期-加工時間）（5）臨界比率最小優先規則SCR(Smallest critical ratio) 交貨期當前日期 作業時間（6）綜合規則（綜合使用兩種規則，如先按照交貨期優先排序，然后按照最短加工時間優先的原則排序）（7）后到先加工規則（8）隨機規則（9）延遲工件最少的規則（Moore法則） CR= 以上這些規則各有其特點，不同的規則適用于不同的目標。例如，FCFS規則比較公平；SPT規則可使平均流程時間最短，從而減少在制品數量；EDD規則可使工件的最大延遲時間最小、平均延誤時間最小；Moore法則可使延遲的工件數最少等。【例6-1】下表是在某工作中心等待

5、加工的6項作業的加工時間（包含換產時間）與預定日期，假設工作的到達順序與表中順序相符 。根據以下規則來決定其作業順序：FCFSSPTEDD并對它們分別進行評價。 作 業加工時間（天）預定日期（天）ABCDEF284105127164171518 排序的結果是A-B-C-D-E-F。順序加工時間流程時間預定交貨期延期天數(如果為負則賦值0) ABCDEF 28410512210142429417164171518001071423合計4112054平均 120/6=2054/6=9 作業順序是A-C-E-B-D-F順序加工時間流程時間預定交貨期延期天數(如果為負則賦值0) ACEBDF 2458

6、10122611192941741516171802031223合計4110840平均 108/6=1840/6=6.67 作業順序是C-A-E-B-D-F順序加工時間流程時間預定交貨期延期天數(如果為負則賦值0) CAEBDF425810124611192941471516171800031223合計4111038平均 110/6=18.33 38/6=6.33 規則規則流動時間流動時間（天）（天）平均流動平均流動時間時間 （天）（天）總延期時總延期時間（天）間（天）平均延期平均延期時間時間 （天）（天）FCFS12020549SPT10818406.67EDD11018.33386.33不

7、同排序規則的結果分析不同排序規則的結果分析排序規則的比較：1、SPT規則，可以使作業流程時間最短，使滯留在加工過程的平均在制品占用量最少，有利于節約流動資金，節約廠房、倉庫面積和保管費用。但是，由于未考慮交貨期，所以可能發生交貨延期。 2、EDD規則，平均延遲天數最少，減少違約罰款損失，但缺點是平均流程時間增加，不利于節約在制品占用資金。3、FCFS規則，主要問題是加工時間過長。但其使用簡單，且體現公平，常用于服務業的排隊系統。假設：（1）一個工件不能同時在不同機器上加工。（2）工件在加工過程中采用平行移動方式（當上一道工序完成后立即進入下道工序）。（3）不允許中斷，工件一旦進入加工狀態，一直

8、加工完成為止，中途不插入其他工件。（4）每道工序只在一臺設備上加工。（5）工件數、機器數與加工時間已知。（6）每臺設備同時只能加工一個工件。 N N項作業，項作業，2 2臺機器，所有工件的加工路臺機器，所有工件的加工路線都相同線都相同。（S.M.Johnson，1954，）AB目標：目標：使全部完工時間最小。條件：條件：每種工件在每臺機器上的加工時間均為已知。 步驟：步驟：1.1.選擇最短的作業時間；選擇最短的作業時間；2.2.如果最短時間的作業在第如果最短時間的作業在第1 1個加工中心，則個加工中心，則安排在最前面，若在第安排在最前面，若在第2 2個加工中心，則安排個加工中心，則安排在最后；

9、在最后；3.3.在等待的隊列中，取消第在等待的隊列中，取消第2 2步安排了的作業；步安排了的作業；4.4.重復重復1 1，2 2，3 3步。步。某公司在一次火災中損壞了某公司在一次火災中損壞了5 5臺儀器，這些儀器的修復需臺儀器，這些儀器的修復需要經過如下要經過如下2 2道工序：道工序：（1 1）將損壞的儀器運至修理車間，拆卸開；）將損壞的儀器運至修理車間，拆卸開；（2 2）清洗儀器部件，更換報廢部分，裝配，測試，并送）清洗儀器部件，更換報廢部分，裝配，測試，并送回原車間?；卦囬g。每臺儀器在兩個工序的各自所需時間如表所示。兩道工每臺儀器在兩個工序的各自所需時間如表所示。兩道工序分別由不同的人

10、擔當。由于原車間沒有這序分別由不同的人擔當。由于原車間沒有這5 5臺儀器就臺儀器就無法恢復生產，所以希望找到一個較好的排序方案，無法恢復生產，所以希望找到一個較好的排序方案，使全部修理時間盡可能短。使全部修理時間盡可能短。儀器工序1工序2Y1 Y2 Y3 Y4 Y5 12 4 5 15 1022 5 3 16 8 原則：原則：1.1.找找minmin，前道工序，前道工序-最前最前 后道工序后道工序-最后最后2.2.若多個若多個min,min,任選。任選。 Y3Y3Y2-Y3Y2-Y3Y2- Y5-Y3Y2- Y5-Y3Y2-Y1- Y5-Y3 Y2-Y1- Y5-Y3 Y2-Y1-Y4- Y5

11、-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作業排序結果的圖示：Y2Y2Y14Y1438Y41631Y454Y541Y346Y5629Y3651600【例例6-3】某一班組有某一班組有A、B兩臺設備，要完成兩臺設備，要完成5個工件的加工個工件的加工任務。每個工件在設備上的加工時間如下表所示。求總加任務。每個工件在設備上的加工時間如下表所示。求總加工周期最短的作業順序。工周期最短的作業順序。 工

12、件在兩臺設備上的加工時間工件在兩臺設備上的加工時間 工件編號工件編號 J1 J2 J3 J4 J5 設備設備A 3 6 7 1 5 設備設備B 2 8 6 4 3 解：由約翰遜法可知，表解：由約翰遜法可知，表5-8中最小加工時間值是中最小加工時間值是1個時間單個時間單位，它又是出現在設備位，它又是出現在設備1上，根據約翰遜法的規則，應將上，根據約翰遜法的規則，應將對應的工件對應的工件4排在第一位，即得：排在第一位，即得： J4 - * - * - * - * 去掉去掉J4，在剩余的工件中再找最小值，不難看出，最小值，在剩余的工件中再找最小值，不難看出，最小值是是2個時間單位，它是出現在設備個時

13、間單位，它是出現在設備2上的，所以應將對應的上的，所以應將對應的工件工件J1排在最后一位，即：排在最后一位，即： J4 - * - * - * - J1 再去掉再去掉J1，在剩余的，在剩余的J2、J3、J5中重復上述步驟，求解中重復上述步驟，求解過程為：過程為： J4 - * - * - J5 - J1 J4 - J2 - * - J5 - J1 J4 - J2 - J3- J5 - J1 當同時出現多個最小值時，可從中任選一個。最后得當同時出現多個最小值時，可從中任選一個。最后得 J4 - J2 - J3- J5 - J1 (a) J1 - J2 - J3- J4 - J5 26A B(b)

14、 J4 - J2 - J3- J5 - J1 可以看出，初始作業順序的總加工周期是可以看出，初始作業順序的總加工周期是30，用約翰遜法排出的作業，用約翰遜法排出的作業順序總加工周期是順序總加工周期是26，顯然后者的結果優于前者。，顯然后者的結果優于前者。 30A B0 服務作業計劃 將服務員工安排到不同的服務需求時間上的作業計劃是服務員工輪班問題。1、單班次問題：每天只有一個班次，部門每天都、單班次問題：每天只有一個班次，部門每天都要營業要營業 （1）啟發方法: 如循環排序法 （2）最優化方法:如整數線性規劃法 (3）解析法2、多班次問題：每天有多班，一般為兩班或三班、多班次問題：每天有多班，

15、一般為兩班或三班 循環排序法循環排序法是一種是一種既簡單又實用的啟發式方法，其基本步驟既簡單又實用的啟發式方法，其基本步驟如下：如下： 1、從每周的員工需求從每周的員工需求人數人數中找到所需員工數量之和最小的連中找到所需員工數量之和最小的連續兩個工作日續兩個工作日,安排一名員工在這兩天中休息。安排一名員工在這兩天中休息。 若有相同的兩個最小總需求量，則可任選其一；或按照預先若有相同的兩個最小總需求量，則可任選其一；或按照預先約定好的方法選擇其一，如優先選擇周六約定好的方法選擇其一，如優先選擇周六周日。周日。 2、使該兩天的需求人數保持不變、使該兩天的需求人數保持不變, 其他日期的需求人數減其他

16、日期的需求人數減1(如果是如果是0不變不變) 3、在新一行中找出所需員工數量最少的連續兩天，并再次循在新一行中找出所需員工數量最少的連續兩天，并再次循環。將下一名員工分配到剩余的工作日中。環。將下一名員工分配到剩余的工作日中。 4、重復上述過程（步驟重復上述過程（步驟2和和3），直到所有的人員需求得到滿），直到所有的人員需求得到滿足。足?！纠?-4】郵局一周內每天的員工需求如表6-1所示。工會要求每名員工連續工作五天，然后連續休息兩天。試制定排班計劃。日期周一周二周三周四周五周六周日員工需求量3656555表表6-1 一周內每天的員工需求量一周內每天的員工需求量 員工員工周一周一周二周二周三周

17、三周四周四周五周五周六周六周日周日A3(*)656555（*)B3(*)5(*)45445C35343(*)3(*)4D242(*)3(*)333E1(*)323222(*)F12121(*)1(*)2G0(*)1(*)01111H0100(*)0(*)00在崗員在崗員工工4676566需要員需要員工工3656555多余員多余員工工1020011解：解：表表6-2 每周員工安排表（循環排序法）每周員工安排表（循環排序法）且為整數（星期日的約束）（星期六的約束）（星期五的約束）（星期四的約束）（星期三的約束）（星期二的約束）（星期一的約束）0.min77654366543255432147432

18、13763212765211765417654321ixbxxxxxbxxxxxbxxxxxbxxxxxbxxxxxbxxxxxbxxxxxtsxxxxxxxZ（3）單班次問題的解析法）單班次問題的解析法 (Brownell and Lowerre,1976) 求解以下問題的單班次人員安排問題：求解以下問題的單班次人員安排問題：1、保證每人每周休息兩天、保證每人每周休息兩天2、保證每人每周連休兩天、保證每人每周連休兩天 3、保證每人每周休息兩天、保證每人每周休息兩天 ，隔一周在周末休息隔一周在周末休息 4、保證每人每周連休兩天，隔一周在周末休息、保證每人每周連休兩天，隔一周在周末休息 1、保證

19、每人每周休息兩天、保證每人每周休息兩天 設某單位每周工作7天，每天一班，平常日需要N人，周末需要n人。 W表示所需勞動力下限。求解步驟：（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 ，則有多余的休息日供分配，此時可按需要調整班次計劃，只要保證每名工人一周休息兩天，平日有N人當班即可。 工人工人1工人工人9工人工人8工人工人7工人工人6工人工人5工人工人4工人工人3工人工人2

20、日日六六五五四四三三二二一一日日六六五五四四三三二二一一【例1】 設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）利用上式計算W2，給W2名工人編號； （2）取k = max 0 , 2N +n - 2 W2 ； （3）1至k號工人（五，六）休息，（k + 1 ） 2 k號工人（日，一）休息，接下來的 W2

21、n k 名工人周末（六，日）休息； （4）對余下的工人，按（一，二），（二，三），（三，四），（四，五）的順序安排連休，保證有N名工人在平常日當班。 【例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（8-5-1=2）名工人（六、日）休息4、余下的工人按（一、二）,（二、三）, （三、四）, （四、五）工人工人1工人工人8工人工人7工人工人6工人工人5工人工人4工

22、人工人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名工人第一周的班次計劃與A組的第二周安排