流水作業(yè)的排序問題.ppt

第九章 流水作業(yè)的排序問題,9.1 排序問題概述 9.2 流水作業(yè)排序問題,9.1 排序問題概述 一、排序問題的基本概念 排序是確定工件（零部件）在一臺或一組設備 上加工的先后順序。 在一定約束條件下，尋找總加工時間最短的安 排產(chǎn)品加工順序的方法，就是生產(chǎn)作業(yè)排序。,例如，考慮32項任務（工件），有32！2.61035種方案,假定計算機每秒鐘可以檢查1 billion個順序, 全部檢驗完畢需要8.41015個世紀. 如果只有16個工件, 同樣按每秒鐘可以檢查1 billion個順序計算, 也需要2/3年. 以上問題還沒有考慮其他的約束條件, 如機器、人力資源、廠房場地等，如果加上這些約束條件，所需要的時間就無法想象了。 所以，很有必要去尋找一些有效算法，解決管理中的實際問題。,假設條件,1.一個工件不能同時在幾臺不同的機器上加工。 2.工件在加工過程中采取平行移動方式，即當上一道工序完工后，立即送下道工序加工。 3.不允許中斷。當一個工件一旦開始加工，必須一直進行到完工，不得中途停止插入其它工件。 4.每道工序只在一臺機器上完成。 5.工件數(shù)、機器數(shù)和加工時間已知，加工時間與加工順序無關。 6.每臺機器同時只能加工一個工件。,排序常用的符號,Ji-工件i，i=1,2,n。 Mj - 機器j，j1，2，m. pij-工件Ji在機器Mj上的加工時間,j=1,m Pi-工件Ji的加工時間； di-工件Ji 的完工期限； Ci-工件Ji 的完成時間； Fi-工件Ji 的流程時間，即工件在車間的實際停留時間，在工件都已到達的情況下, Fi= Pi+ Wi Wi-工件Ji在加工過程中總的等待時間 Li-工件Ji 的延誤時間, Li= Ci- di , Li0 延誤 Fmax-最長流程時間， FmaxmaxFi,二、排序問題的分類和表示法,1、排序問題的分類： (1)根據(jù)機器數(shù)的多少 單臺機器的排序問題 多臺機器的排序問題 (2)根據(jù)加工路線的特征 單件作業(yè)排序(Job Shop)：工件加工路線不同 流水作業(yè)排序(Flow Shop)：所有工件加工路線完全相同 (3) 根據(jù)工件到達系統(tǒng)的情況 靜態(tài)排序：進行排序時，所有工件都已到達，可以一次對他們排序 動態(tài)排序：工件陸續(xù)到達，要隨時安排他們的加工順序,（4）根據(jù)參數(shù)的性質(zhì) 確定型排序：指加工時間和其他參數(shù)是已知確定的量 隨機型排序：指加工時間和有關參數(shù)為隨機變量 （5）根據(jù)要實現(xiàn)的目標 單目標排序 多目標排序,2、排序問題的表示法,排序問題常用四個符號來描述: n/m/A/B 其中, n-工件數(shù)； m-機器數(shù)； A-車間類型； F流水作業(yè)排序， P流水作業(yè)排列排序 G一般類型,即單件型排序 B-目標函數(shù),9.2 流水作業(yè)排序問題,一、最長流程時間Fmax的計算 工件 Si在機器MK 上的完工時間為CKSi 工件 Si在機器MK 上的加工時間為PSiK C1Si= C1Si-1+PSi1 CKSi=max C(k-1)Si, CkSi-1 +PSik,舉例：有一個6/4/p/ Fmax問題，其加工時間如下表所示。當按順序S（6，1，5，2，4，3）加工時，求Fmax。,二、兩臺機器排序問題,兩臺機器排序的目標是使最大完成時間（總加工周期）Fmax最短 。 實現(xiàn)兩臺機器排序的最大完成時間Fmax最短的目標，一優(yōu)化算法就是著名的約翰遜法(Johnsons Law)。其具體求解過程如下例所示。,約翰遜貝爾曼法則,約翰遜法解決這種問題分為4個步驟： (1)列出所有工件在兩臺設備上的作業(yè)時間。 (2)找出作業(yè)時間最小者。 (3)如果該最小值是在設備1上，將對應的工件排在前面，如果該最小值是在設備2上，則將對應的工件排在后面。 (4)排除已安排好的工件，在剩余的工件中重復步驟(2)和(3)，直到所有工件都安排完畢。,舉例 AB兩臺設備完成6個零件的加工任務，每個工件在設備上的加工時間如下表所示。求總加工周期最短的作業(yè)順序。,機器,工件編 號,求解過程,由約翰遜法可知，表中最小加工時間值是1個時間單位,出現(xiàn)在設備1上，根據(jù)約翰遜法的規(guī)則，應將對應的工件2排在第一位，即得： J2- * - * - * - * -* 去掉J2，在剩余的工件中再找最小值，最小值是2個時間單位，它是出現(xiàn)在設備2上，所以應將對應的工件J3排在最后一位，即： J2 - * - * - * -* J3 再去掉J3，在剩余的J1、J4、J5、J6中重復上述步驟，求解過程為： J2 J5 - * - * - * - J3 J2 J5 J6 - * - * J3 J2 J5 J6 - * -J4 J3 J2 J5 J6 J1 - -J4 J3 當同時出現(xiàn)多個最小值時，可從中任選一個。,J2 J5 J6- J1- J4J3 或 J2 J5 J1-J6 - J4J3,求得最優(yōu)順序下的Fmax28,Johnson算法的改進,1. 將所有ai bi的工件按ai值不減的順序排成一個序列A； 2. 將aibi的工件按bi值不增的順序排成一個序列B； 3. 將A放到B之前，就構(gòu)成了一個最優(yōu)加工順序。,ai bi工件按ai值不減的順序（由小到大）排列 ： J2 J5 J6- J1 ； aibi的工件按bi值不增的順序（由大到小）排列： J4J3 最后排序 J2 J5 J6- J1- J4J3,三、m(m 3)臺機器排序問題的算法,一般采用啟發(fā)式算法解決這類問題。 斜度指標法 關鍵工件法 CDS法,（一）Palmer（斜度指標法）,工件的斜度指標計算公式,k1，2，m 式中，m機器數(shù)；Pik為工件i在Mk上的加工時間。 按照各工件i不增的順序排列工件，可得出令人滿意 的順序。,i=,舉例,有一個4/3/F/Fmax問題，其加工時間如下表所示，用Palmer法求解。,i -Pi1+Pi3 1-P11+P13= -143 2-P21+P23= -2+5=3 3-P31+P33= -6+8=2 4-P41+P43= -3+2=-1 按i不增的順序排列工件，得到加工順序 （1，2，3，4）或（2，1，3，4）,k=1，2，3,Fmax=28,Fmax=28 加工順序（1，2，3，4）或（2，1，3，4）,（二）關鍵工件法,1、 計算 Pi= , 找出其中最大者，定義為關鍵工件 Jc。 2、除Jc外，將滿足Pi1Pim的工件，按Pi1值的 大小，從小到大排在Jc的前面。 3 、除Jc外，將滿足pi1pim的工件，按Pim值的大小，從大到小排在Jc的后面。,（1）工件3加工時間最長，作為關鍵工件。 （2）滿足Pi1pi3的工件是4，將4排在3的后面。 所以加工順序為（1，2，3，4）。,舉例,具體過程,（1）找出關鍵工件：工作負荷最大的40，對應的是工 件 6， Jc=J6 （2）滿足Pi1Pi5的工件有J1 、J4、J5, 按Pi1值由小到大排在關鍵工件前面，所以有 J4 J5 J1 -J6 （3）滿足pi1pi5的工件有J2、J3，按Pi5值由大到小排在關鍵工件的后面, 所以有 J6 J2 J3 J4 J5 J1 J6 J2 J3 Fmax=51,（三）CDS法,Campbell, Dudek, Smith三人于1970年共同提出了一個啟發(fā)式算法，簡稱CDS法。他們把Johnson算法用于一般的n /m /P/Fmax問題，得到（m一1)個加工順序，取其中優(yōu)者。 具體做法是，對加工時間 和 （l=1，2，m-1），用Johnson算法求（m-1)次加工順序，取其中最好的結(jié)果。,舉例,當l1時，按Johnson算法得到加工順序 （1，2，3，4）,Fmax=28,當l=2時，得到加工順序(2，3，1，4) 對于順序（2，3，1，4）,Fmax=29 所以，取順序（1，2，3，4）,四、相同零件、不同移動方式下加工周期的計算 1、順序移動 一批零件在上道工序全部加工完畢后才整批轉(zhuǎn)移到下道工序繼續(xù)加工。一批零件的加工周期為：,例：已知n=4,t1=10分，t25分鐘，t315分鐘， t410分鐘，求T順,T順4(10+5+15+10)=160（分鐘）,2、平行移動方式 每個零件在前道工序加工完畢后，立即轉(zhuǎn)移到下道工 序繼續(xù)加工，形成前后交叉作業(yè)。一批零件的加工周期為：,T平（1051510）（4-1) 15 = 85 (分鐘）,3、平順移動方式 當t1ti+1時，零件按平行移動方式轉(zhuǎn)移； 當t1ti+1時，以I工序最后一個零件的完工時間為準，往前推移（n-1) ti+1,作為零件在（i+1)工序的開工時間。一批零件的加工周期為：,T平順4 （1051510）（41）（5510） 100（分鐘）,三種移動方式的比較,練習題： 設某種零件批量為5件，加工工序數(shù)為4，每道工序單件加工時間為t1=6小時，t2=10小時，t3=8小時t4=16小時，試求三種移動方式下該批零件的加工周期？ T順=5*(6+10+