車間生產(chǎn)作業(yè)排序知識(shí)講座

生產(chǎn)作業(yè)排序一、基本概念二、最長流程時(shí)間三、n/2/F/Fmax問題的算法四、一般n/m/P/Fmax問題的啟發(fā)式算法五、單件車間排序問題第一頁，共三十九頁。一、基本概念1、排序排序就是要將不同的工作任務(wù)安排一個(gè)執(zhí)行的順序，使預(yù)定的目標(biāo)最優(yōu)化。實(shí)際上就是要解決如何按時(shí)間的先后，將有限的人力、物力資源分配給不同工作任務(wù)，使預(yù)定目標(biāo)最優(yōu)化的問題。第二頁，共三十九頁。一、基本概念排序中常用的幾個(gè)概念工件（Job）：服務(wù)對(duì)象；機(jī)器（Machine、Processor）：服務(wù)者。如：n個(gè)零件在機(jī)器上加工，則零件是工件，設(shè)備是機(jī)器；工人維修設(shè)備，出故障的設(shè)備是工件，工人是機(jī)器。第三頁，共三十九頁。一、基本概念所以，作業(yè)排序也就是要確定工件在機(jī)器上的加工順序，可用一組工件代號(hào)的一種排列來表示。如可用（1，6，5，4，3，2）表示加工順序：J1—J6—J5—J4—J3—J2。第四頁，共三十九頁。一、基本概念2、作業(yè)計(jì)劃（Scheduling）作業(yè)計(jì)劃與排序不是一回事，它不僅要確定工件的加工順序，而且還要確定每臺(tái)機(jī)器加工每個(gè)工件的開工時(shí)間和完工時(shí)間。如果按最早可能開（完）工時(shí)間來編排作業(yè)計(jì)劃，則排序完后，作業(yè)計(jì)劃也就確定了。第五頁，共三十九頁。一、基本概念3、排序問題的分類與表示1）單臺(tái)機(jī)器與多臺(tái)機(jī)器的排序問題。2）流水車間與單件車間排序問題。第六頁，共三十九頁。一、基本概念流水車間排序問題的基本特征：每個(gè)工件的加工路線都一樣。如車—銑—磨。這里指的是工件的加工流向一致，并不要求每個(gè)工件必須在每臺(tái)機(jī)器上加工。如有的工件為車—磨，有的為銑—磨。不僅加工路線一致，而且所有工件在各臺(tái)機(jī)器上的加工順序也一樣，這種排序稱為排列排序（同順序排序）。如工件排序?yàn)椋篔1—J3—J2，則表示所有機(jī)器都是先加工J1，然后加工J3，最后加工J2。第七頁，共三十九頁。一、基本概念單件車間排序問題的基本特征：每個(gè)工件都有其獨(dú)特的加工路線，工件沒有一定的流向。第八頁，共三十九頁。一、基本概念3）表示方法一般正規(guī)的表示方法為：n/m/A/Bn：工件數(shù)；m：機(jī)器數(shù)；A：車間類型（F、P、G）；B：目標(biāo)函數(shù)第九頁，共三十九頁。一、基本概念 4）一般來說，排列排序問題的最優(yōu)解不一定是相應(yīng)流水車間排序問題的最優(yōu)解，但一般是比較好的解。而對(duì)于僅有2臺(tái)或3臺(tái)機(jī)器的情況，則排列排序問題的最優(yōu)解一定是相應(yīng)流水車間排序問題的最優(yōu)解。第十頁，共三十九頁。一、基本概念4、排序問題的假設(shè)條件一個(gè)工件不能同時(shí)在幾臺(tái)不同的機(jī)器上加工。工件在加工過程中采取平行移動(dòng)方式。不允許中斷。每道工序只在一臺(tái)機(jī)器上完成。每臺(tái)機(jī)器同時(shí)只能加工一個(gè)工件。工件數(shù)、機(jī)器數(shù)和加工時(shí)間已知，加工時(shí)間與加工順序無關(guān)。第十一頁，共三十九頁。二、最長流程時(shí)間最長流程時(shí)間（加工周期）：從第一個(gè)工件在第一臺(tái)機(jī)器上加工起到最后一個(gè)工件在最后一臺(tái)機(jī)器上加工完畢為止所經(jīng)過的時(shí)間。假定所有工件的到達(dá)時(shí)間都為0，則Fmax等于排在末位加工的工件在車間的停留時(shí)間。第十二頁，共三十九頁。二、最長流程時(shí)間計(jì)算Fmax的幾個(gè)假定條件：機(jī)器M1不會(huì)發(fā)生空閑；對(duì)其它機(jī)器，能對(duì)某一工件加工必須具備2個(gè)條件：機(jī)器必須完成排前一位的工件的加工；要加工的工件的上道工序已經(jīng)完工。第十三頁，共三十九頁。二、最長流程時(shí)間第十四頁，共三十九頁。二、最長流程時(shí)間ipi1pi2pi3pi4615243255144544453258217533674261012131671115202733121722303542132125323846第十五頁，共三十九頁。三、n/2/F/Fmax問題的算法Johnson算法：假定：ai為工件Ji在機(jī)器M1上的加工時(shí)間，bi為工件Ji在機(jī)器M2上的加工時(shí)間，每個(gè)工件按M1—M2的路線加工。第十六頁，共三十九頁。三、n/2/F/Fmax問題的算法Johnson算法的步驟：從加工時(shí)間矩陣中找出最短的加工時(shí)間。若最短時(shí)間出現(xiàn)在M1上，則對(duì)應(yīng)的工件盡可能往前排。若最短時(shí)間出現(xiàn)在M2上，則對(duì)應(yīng)的工件盡可能往后排。若最短時(shí)間有多個(gè)，則任選一個(gè)。劃去已排序的工件。若所有工件都已排序，則停止，否則重復(fù)上述步驟。第十七頁，共三十九頁。四、一般n/m/P/Fmax問題的啟發(fā)式算法對(duì)于一般的n/m/P/Fmax問題，可以用分支定界法求得最優(yōu)解，但計(jì)算量很大。實(shí)際中，可以用啟發(fā)式算法求近優(yōu)解。第十八頁，共三十九頁。四、一般n/m/P/Fmax問題的啟發(fā)式算法1、Palmer法計(jì)算工件斜度指標(biāo)i：m:機(jī)器數(shù)pik：工件i在機(jī)器k上的加工時(shí)間。i=1,2,,n排序方法:按i從大到小的順序排列。按排序的順序計(jì)算Fmax第十九頁，共三十九頁。四、一般n/m/P/Fmax問題的啟發(fā)式算法2、關(guān)鍵工件法：計(jì)算Pi=Pij，找出Pi最長的工件，將之作為關(guān)鍵工件C。對(duì)其余工件，若Pi1≤Pim，則按Pi1由小到大排成序列SA。若Pi1>Pim，則按Pim由大到小排成序列SB。順序（SA，C，SB）即為近優(yōu)解。第二十頁，共三十九頁。四、一般n/m/P/Fmax問題的啟發(fā)式算法得到的加工順序?yàn)?1，2，3，4)第二十一頁，共三十九頁。四、一般n/m/P/Fmax問題的啟發(fā)式算法3、CDS法：CDS法是Johnson算法的擴(kuò)展方法，從M-1個(gè)排序中找出近優(yōu)解。第二十二頁，共三十九頁。四、一般n/m/P/Fmax問題的啟發(fā)式算法L＝1，按Johnson算法得到加工順序(1，2，3，4)，F(xiàn)max＝28L＝2，按Johnson算法得到加工順序(2，3，1，4)，F(xiàn)max＝29取順序(1，2，3，4）為最優(yōu)順序。第二十三頁，共三十九頁。五、單件車間排序問題（n/m/G/Fmax）1、問題描述(i，j，k)：表示工件i的第j道工序是在機(jī)器k上進(jìn)行。加工描述矩陣D：每一行描述一個(gè)工件的加工，每一列的工序序號(hào)相同。D=1,1,11,2,31,3,22,1,32,2,12,3,2第二十四頁，共三十九頁。五、單件車間排序問題（n/m/G/Fmax）加工時(shí)間矩陣T：與D相對(duì)應(yīng)。D=1,1,11,2,31,3,22,1,32,2,12,3,2T=463574第二十五頁，共三十九頁。五、單件車間排序問題（n/m/G/Fmax）加工順序矩陣S：每一行與機(jī)器相對(duì)應(yīng)，每一列與工件相對(duì)應(yīng)。D=1,1,11,2,31,3,22,1,32,2,12,3,2S=1,1,12,2,11,3,22,3,22,1,31,2,3第二十六頁，共三十九頁。五、單件車間排序問題（n/m/G/Fmax）用方塊圖表示：D=1,1,11,2,31,3,22,1,32,2,12,3,2S=1,1,12,2,11,3,22,3,22,1,31,2,3T=4635741,1,12,1,31,2,32,2,11,3,22,3,2M1M2M3第二十七頁，共三十九頁。五、單件車間排序問題（n/m/G/Fmax）2、能動(dòng)作業(yè)計(jì)劃的構(gòu)成各工序都按最早可能開(完)工時(shí)間安排且任何一臺(tái)機(jī)器的每段空閑時(shí)間都不足以加工一道可加工工序。符號(hào)說明：{Ot}第t步可以排序的工序的集合{St}t步之前已排序的工序構(gòu)成的部分作業(yè)計(jì)劃Tk{Ot}中工序Ok的最早可能開工時(shí)間T’k{Ot}中工序Ok的最早可能完工時(shí)間第二十八頁，共三十九頁。五、單件車間排序問題（n/m/G/Fmax）能動(dòng)作業(yè)計(jì)劃的構(gòu)成步驟：①設(shè)t＝1，{St}為空，{Ot}為各工件第一道工序的集合。②求最小的最早完工時(shí)間T*=min{T’k},并找到出現(xiàn)T*的機(jī)器M*，若有多臺(tái)，任選一臺(tái)。③從{Ot}中跳出滿足以下兩條件的工序Oj需要機(jī)器M*加工；Tj<T*④將確定的Oj放入{St}，從{Ot}中消去Oj并將Oj的緊后工序放入{Ot}中，使t=t+1。⑤若還有未安排的工序，轉(zhuǎn)步驟②；否則，停止。第二十九頁，共三十九頁。一個(gè)實(shí)例：D=1,1,11,2,31,3,22,1,32,2,12,3,2T=241345i1{Ot}TkT’kT*M*Oj1,1,1022M11,1,12,1,30321,2,3263M32,1,32,1,30331,2,3377M31,2,32,2,13741,3,2787M12,2,12,2,13751,3,2788M21,3,22,3,2712613M22,3,22,3,2813第三十頁，共三十九頁。得到加工順序矩陣：S=1,1,12,2,11,3,22,3,22,1,31,2,31,1,12,1,31,2,32,2,11,3,22,3,2M1M2M323773813第三十一頁，共三十九頁。五、單件車間排序問題（n/m/G/Fmax）3、無延遲作業(yè)計(jì)劃的構(gòu)成沒有任何延遲出現(xiàn)的能動(dòng)作業(yè)計(jì)劃。所謂“延遲”，指有工件等待加工時(shí)，機(jī)器出現(xiàn)空閑，即使這段空閑時(shí)間不足以完成一道工序。構(gòu)成步驟：第三十二頁，共三十九頁。五、單件車間排序問題（n/m/G/Fmax）無延遲作業(yè)計(jì)劃的構(gòu)成步驟：①設(shè)t＝1，{St}為空，{Ot}為各工件第一道工序的集合。②求最小的最早完工時(shí)間T*=min{Tk},并找到出現(xiàn)T*的機(jī)器M*，若有多臺(tái)，任選一臺(tái)。③從{Ot}中跳出滿足以下兩條件的工序Oj需要機(jī)器M*加工；Tj=T*④將確定的Oj放入{St}，從{Ot}中消去Oj并將Oj的緊后工序放入{Ot}中，使t=t+1。⑤若還有未安排的工序，轉(zhuǎn)步驟②；否則，停止。第三十三頁，共三十九頁。一個(gè)實(shí)例：D=1,1,11,2,31,3,22,1,32,2,12,3,2T=241345i1{Ot}TkT’kT*M*Oj1,1,1020M11,1,12,1,30321,2,3260M32,1,32,1,30331,2,3373M31,2,32,2,13741,3,2783M12,2,12,2,13751,3,2787M22,3,22,3,2712612M21,3,22,3,212130M33M17M2第三十四頁，共三十九頁。得到加工順序矩陣：S=1,1,12,2,12,3,21,3,22,1,31,2,31,1,12,1,31,2,32,2,11,3,22,3,2M1M2M3237731213第三十五頁，共三十九頁。4、啟發(fā)式算法：

能動(dòng)作業(yè)計(jì)劃和無延遲作業(yè)計(jì)劃盡管不一定是最優(yōu)作業(yè)計(jì)劃，但一般是較好的作業(yè)計(jì)劃，特別是無延遲作業(yè)計(jì)劃能提供令人滿意的解。一般能動(dòng)作業(yè)計(jì)劃和無延遲作業(yè)計(jì)劃都有多個(gè)，可用啟發(fā)式方法從中選擇結(jié)果較好的作業(yè)計(jì)劃。一般來說，以構(gòu)成無延遲作業(yè)計(jì)劃的步驟為基礎(chǔ)的啟發(fā)式算法比以構(gòu)成能動(dòng)作業(yè)計(jì)劃的步驟為基礎(chǔ)的啟發(fā)算法的效果要好。五、單件車間排序問題（n/m/G/Fmax）第三十六頁，共三十九頁。優(yōu)選調(diào)度法則：

SPT(ShortestProcessingTime)法則：優(yōu)先選擇加工時(shí)間最短的工序。FCFS(FirstComeFirstServed)法則：優(yōu)先選擇最早進(jìn)入可排工序集合的工件。EDD(EarliestDueDate)法則：優(yōu)先選擇完工期限緊的工件。MWKR(MostWorkRemaining)法則：優(yōu)先選擇余下加工時(shí)間最長的工件。LWKR(LeastWorkRemaining)法則：優(yōu)先選擇余下加工時(shí)間最短的工件。MOPNR(MostOperation