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

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