作業(yè)排序講解課件

1、第十一章 作業(yè)排序本章主要介紹制造業(yè)的作業(yè)排序問題。2022/8/91武漢理工大學(xué)管理學(xué)院 袁付禮一、作業(yè)排序的概念和類型1、概念對一定期間內(nèi)分配給生產(chǎn)單位的作業(yè)任務(wù)，根據(jù)產(chǎn)品(零件)的工藝路線和設(shè)備負(fù)荷可能性，確定各個生產(chǎn)單位作業(yè)任務(wù)的先后順序。作業(yè)排序問題通常表述為“n項(xiàng)作業(yè)任務(wù)在m個生產(chǎn)單位的排序的問題”。2022/8/92武漢理工大學(xué)管理學(xué)院 袁付禮一、作業(yè)排序的概念和類型2、作業(yè)排序的類型：流水型mn排序問題 指n項(xiàng)任務(wù)在m臺設(shè)備上加工，所有任務(wù)的工藝順序相同，有n!個排序方案。非流水型mn排序問題 指n項(xiàng)任務(wù)在m臺設(shè)備上加工，所有任務(wù)的工藝順序不同，有(n!)m個排序方案。 202

2、2/8/93武漢理工大學(xué)管理學(xué)院 袁付禮一、作業(yè)排序的概念和類型作業(yè)排序的表示方法為 生產(chǎn)單位數(shù)作業(yè)任務(wù)數(shù)/排序問題類型/評價尺度(優(yōu)化目標(biāo))如m n/FLW/Fmax表示m個生產(chǎn)單位完成n項(xiàng)作業(yè)任務(wù)、流水型排序問題和以最大流程時間作為評價尺度。2022/8/94武漢理工大學(xué)管理學(xué)院 袁付禮二、作業(yè)排序的評價尺度最大流程時間平均流程時間最大延期量平均延期量在制品占用量總調(diào)整時間2022/8/95武漢理工大學(xué)管理學(xué)院 袁付禮計(jì)算公式設(shè)n為作業(yè)任務(wù)數(shù)，m為機(jī)床數(shù)，Ji為第i項(xiàng)作業(yè)任務(wù)，Oij為第i項(xiàng)作業(yè)任務(wù)的和j工序，tij為第i項(xiàng)作業(yè)任務(wù)在第j臺機(jī)床上的作業(yè)時間，ri為任務(wù)Ji可以開始加工的時刻

3、，di為Ji的要求完成時刻，wij為Oij在進(jìn)行加工前的等候時間。如果沒有等候，wij=0。第i項(xiàng)任務(wù)的完成時刻(ci)為 ci = ri+ti1 +wi1+ti2+wi2+tim + wim2022/8/96武漢理工大學(xué)管理學(xué)院 袁付禮計(jì)算公式(續(xù))令ti為作業(yè)任務(wù)i的總作業(yè)時間，則：令wi為作業(yè)任務(wù)i的總等候時間，則：則 ci=ri+ti+wi2022/8/97武漢理工大學(xué)管理學(xué)院 袁付禮計(jì)算公式(續(xù))第i項(xiàng)作業(yè)任務(wù)在機(jī)床組的流程時間為： Fi=ci-ri=ti+wi如果作業(yè)任務(wù)i的完成時刻ci已超過要求完成時刻di，則形成交貨延期，延期量Di為： Di= ci-di=Fi+ri-di如果

4、ci未超過di ，則延期量Di為0。2022/8/98武漢理工大學(xué)管理學(xué)院 袁付禮排序問題解法的約定一個工件不能同時在不同的設(shè)備上加工；每道工序只在一臺設(shè)備上完成，每臺設(shè)備只完成一道工序；每臺設(shè)備同時只能加工一個工件；工件在加工過程中采取平行移動方式；工件數(shù)(n)、設(shè)備數(shù)(m)與加工時間均已知，允許工件在工序之間等待，允許設(shè)備在工件未到達(dá)時閑置。 2022/8/99武漢理工大學(xué)管理學(xué)院 袁付禮三、單臺機(jī)床作業(yè)排序方法1n流水排序型問題的優(yōu)先規(guī)則：先到先服務(wù)(FCFS)最短作業(yè)時間(SPT)最短交貨延期量(EDD)SPT與EDD結(jié)合原則最小松弛時間(SST) 后到先服務(wù)(LCFS)按期完成作業(yè)項(xiàng)

5、目最多的原則按期完成作業(yè)項(xiàng)目最多的原則：即先按交貨期優(yōu)先原則逐項(xiàng)安排作業(yè)順序，并依次計(jì)算每項(xiàng)任務(wù)是否拖期，如果遇到某項(xiàng)任務(wù)拖期，則將其移至最后加工；之后，若又有任務(wù)拖期，則又將其移至最后加工。 2022/8/910武漢理工大學(xué)管理學(xué)院 袁付禮三、單臺機(jī)床作業(yè)排序方法例：下表是在某工作中心等待加工的6項(xiàng)作業(yè)的加工時間（包含換產(chǎn)時間）與預(yù)定日期，假設(shè)工作的到達(dá)順序與表中順序相符 。根據(jù)以下規(guī)則來決定其作業(yè)順序：FCFSSPTEDDSST并對它們分別進(jìn)行評價。 作 業(yè)加工時間（天）預(yù)定日期（天）ABCDEF2841051271641715182022/8/911武漢理工大學(xué)管理學(xué)院 袁付禮按FCFS

6、規(guī)則排序排序的結(jié)果是A-B-C-D-E-F。順序加工時間流程時間預(yù)定交貨期延期天數(shù)(如果為負(fù)則賦值0) ABCDEF 28410512210142429417164171518001071423合計(jì)4112054平均120/41=2.93120/6=2054/6=92022/8/912武漢理工大學(xué)管理學(xué)院 袁付禮按SPT規(guī)則作業(yè)順序是A-C-E-B-D-F順序加工時間流程時間預(yù)定交貨期延期天數(shù)(如果為負(fù)則賦值0) ACEBDF 245810122611192941741516171802031223合計(jì)4110840平均108/41=2.63108/6=1840/6=6.672022/8/91

7、3武漢理工大學(xué)管理學(xué)院 袁付禮按EDD規(guī)則作業(yè)順序是C-A-E-B-D-F順序加工時間流程時間預(yù)定交貨期延期天數(shù)(如果為負(fù)則賦值0) CAEBDF425810124611192941471516171800031223合計(jì)4111038平均110/41=2.68110/6=18.33 38/6=6.332022/8/914武漢理工大學(xué)管理學(xué)院 袁付禮按SST規(guī)則松弛時間=預(yù)定日期-加工時間，按松弛時間從小到大排列，可得順序：C-A-F-D-B-E順序松弛時間加工時間流程時間預(yù)定交貨期延期天數(shù)(如果為負(fù)則賦值0) CAEBDF05678104212108546182836414718171615

8、000112026合計(jì)4113357平均133/41=3.24133/6=22.1757/6=9.52022/8/915武漢理工大學(xué)管理學(xué)院 袁付禮四、兩臺機(jī)床作業(yè)排序方法加工順序相同的若干個作業(yè)在兩臺機(jī)床上的加工排序，我們運(yùn)用約翰遜（Johnson）規(guī)則解決。其步驟如下：(1)列出每個作業(yè)在兩臺機(jī)床上的作業(yè)時間；(2)選擇最短的作業(yè)時間；(3)如果最短的作業(yè)時間來自第一臺機(jī)床，則首先進(jìn)行這個作業(yè)；如果最短的作業(yè)時間來自第二臺機(jī)床，則最后進(jìn)行這個作業(yè)；(4)重復(fù)上述步驟，直到排序完成。2022/8/916武漢理工大學(xué)管理學(xué)院 袁付禮約翰遜-貝爾曼規(guī)則例：4項(xiàng)作業(yè)在兩臺設(shè)備上進(jìn)行加工，其加工順序

9、相同，作業(yè)時間如下表所示:625374268TT = 2+4+8+6+5 = 2553A786t1t26機(jī)床作業(yè)BDC24ADC12022/8/917武漢理工大學(xué)管理學(xué)院 袁付禮五、3臺機(jī)器上N項(xiàng)作業(yè)的排序(簡稱為N/3排序)此方法是約翰遜（Johnson）規(guī)則的擴(kuò)展方法，它是將三臺設(shè)備合并為兩臺假想的設(shè)備，然后按約翰遜(Johnson)規(guī)則進(jìn)行排序。此方法可得到最優(yōu)解；否則，只能得到近似最優(yōu)解。當(dāng)滿足或時注意：2022/8/918武漢理工大學(xué)管理學(xué)院 袁付禮約翰遜(Johnson)規(guī)則的擴(kuò)展方法例：4項(xiàng)作業(yè)在三臺設(shè)備上進(jìn)行加工，其加工順序相同，作業(yè)時間如下表所示:9A1046t1t26機(jī)床作

10、業(yè)BDC t3 7 8 12 65391ADCB作業(yè)12A15tG10機(jī)床BDC tH1012181115解：2022/8/919武漢理工大學(xué)管理學(xué)院 袁付禮續(xù)2T = 7+6+12+6+9+6 = 46 T7 81266549106933A786t1t26機(jī)床作業(yè)BDCEF2679457作業(yè)題： 排序并計(jì)算加工周期。2022/8/920武漢理工大學(xué)管理學(xué)院 袁付禮六、M臺機(jī)器上N項(xiàng)作業(yè)的排序(簡稱為N/M排序) 一般解法：分枝定界法啟發(fā)式算法稱為CDS算法，該算法是將N/3的約貝擴(kuò)展方法進(jìn)一步擴(kuò)展到一般的N/M問題，以求得一個近似的最優(yōu)解。也叫坎貝爾-杜達(dá)克-史密斯法。關(guān)鍵零件法最小排序系數(shù)

11、 2022/8/921武漢理工大學(xué)管理學(xué)院 袁付禮CDS算法的步驟 第一步，根據(jù)第1臺與第M臺（即最后一臺）機(jī)器的兩組操作時間，應(yīng)用約貝規(guī)則排出第1個作業(yè)順序方案；第二步，根據(jù)第1臺與第2臺機(jī)器的操作時間合并，以及第（M-1）與第M臺機(jī)器的操作時間合并，得到兩組操作時間，應(yīng)用約貝規(guī)則排出第2個作業(yè)順序方案；第三步，根據(jù)第1、第2、第3臺，三臺機(jī)器的操作時間合并，以及第（M-2）、第（M-1）、第M臺三臺機(jī)器的操作時間合并，又得到兩組操作時間，應(yīng)用約貝規(guī)則，排出第3個作業(yè)順序方案；2022/8/922武漢理工大學(xué)管理學(xué)院 袁付禮CDS算法的步驟(續(xù))第四步，重復(fù)以上運(yùn)算，最后將第1、第2、，第（M-1）共（M-1）臺機(jī)器和操作時間合并，以及將