如何進(jìn)展生產(chǎn)作業(yè)排序

1、如何進(jìn)展生產(chǎn)作業(yè)排序一、根本概念1、排序排序就是要將不同的工作任務(wù)安排一個(gè)執(zhí)行的順序，使預(yù)定的目標(biāo)最優(yōu)化。實(shí)際上就是要解決如何按時(shí)間的先后，將有限的人力、物力資源分配給不同工作任務(wù)，使預(yù)定目標(biāo)最優(yōu)化的問題。一、根本概念排序中常用的幾個(gè)概念工件Job：效勞對(duì)象；機(jī)器Machine、Processor：效勞者。如：n個(gè)零件在機(jī)器上加工，那么零件是工件，設(shè)備是機(jī)器；工人維修設(shè)備，出故障的設(shè)備是工件，工人是機(jī)器。一、根本概念 所以，作業(yè)排序也就是要確定工件在機(jī)器上的加工順序，可用一組工件代號(hào)的一種排列來表示。 如可用1，6，5，4，3，2表示加工順序：J1J6J5J4J3J2。一、根本概念2、作業(yè)方案

2、Scheduling作業(yè)方案與排序不是一回事，它不僅要確定工件的加工順序，而且還要確定每臺(tái)機(jī)器加工每個(gè)工件的開工時(shí)間和完工時(shí)間。如果按最早可能開完工時(shí)間來編排作業(yè)方案，那么排序完后，作業(yè)方案也就確定了。一、根本概念3、排序問題的分類與表示1單臺(tái)機(jī)器與多臺(tái)機(jī)器的排序問題。2流水車間與單件車間排序問題。一、根本概念流水車間排序問題的根本特征：每個(gè)工件的加工路線都一樣。如車銑磨。這里指的是工件的加工流向一致，并不要求每個(gè)工件必須在每臺(tái)機(jī)器上加工。如有的工件為車磨，有的為銑磨。不僅加工路線一致，而且所有工件在各臺(tái)機(jī)器上的加工順序也一樣，這種排序稱為排列排序同順序排序。如工件排序?yàn)椋篔1J3J2，那么表

3、示所有機(jī)器都是先加工J1，然后加工J3，最后加工J2。一、根本概念單件車間排序問題的根本特征：每個(gè)工件都有其獨(dú)特的加工路線，工件沒有一定的流向。一、根本概念3表示方法 一般正規(guī)的表示方法為：n/m/A/B n：工件數(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ī)

4、器上完成。每臺(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í)間ipi1pi2pi3pi4615243255144544453258217533674261

5、012131671115202733121722303542132125323846三、n/2/F/Fmax問題的算法Johnson算法：假定：ai為工件Ji在機(jī)器M1上的加工時(shí)間，bi為工件Ji在機(jī)器M2上的加工時(shí)間，每個(gè)工件按M1M2的路線加工。三、n/2/F/Fmax問題的算法Johnson算法的步驟：從加工時(shí)間矩陣中找出最短的加工時(shí)間。假設(shè)最短時(shí)間出現(xiàn)在M1上，那么對(duì)應(yīng)的工件盡可能往前排。假設(shè)最短時(shí)間出現(xiàn)在M2上，那么對(duì)應(yīng)的工件盡可能往后排。假設(shè)最短時(shí)間有多個(gè)，那么任選一個(gè)。劃去已排序的工件。假設(shè)所有工件都已排序，那么停止，否那么重復(fù)上述步驟。四、一般n/m/P/ Fmax問題的啟發(fā)式

6、算法 對(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ì)其余工件，假設(shè)Pi1Pim ，那么按Pi1由小到大排成序列SA。假設(shè)Pi1 Pim ，那么按Pim由大到小排成序列SB。順序SA，C，SB

7、即為近優(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ā)式算法L1，按Johnson算法得到加工順序(1，2，3，4)，F(xiàn)max28L2，按Johnson算法得到加工順序(2，3，1，4)， Fmax29取順序(1，2，3，4為最優(yōu)順序。五、單件車間排序問題n/m/G/Fmax1、問題描述(i，j，k)：表示工件i的第j道工序是在機(jī)器k上進(jìn)行。加工描述矩陣D：每一行描述一個(gè)工件的加工，每一

8、列的工序序號(hào)相同。D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2五、單件車間排序問題n/m/G/Fmax加工時(shí)間矩陣T：與D相對(duì)應(yīng)。D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2T=4 6 35 7 4五、單件車間排序問題n/m/G/Fmax加工順序矩陣S：每一行與機(jī)器相對(duì)應(yīng)，每一列與工件相對(duì)應(yīng)。D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2S=1,1,1 2,2,11,3,2 2,3,22,1,3 1,2,3五、單件車間排序問題n/m/G/Fmax用方塊圖表示：D=1,1,1 1,2,3 1,3,22,1,3 2,

9、2,1 2,3,2S=1,1,1 2,2,11,3,2 2,3,22,1,3 1,2,3T=4 6 35 7 41,1,12,1,31,2,32,2,11,3,22,3,2M1M2M3五、單件車間排序問題n/m/G/Fmax2、能動(dòng)作業(yè)方案的構(gòu)成各工序都按最早可能開(完)工時(shí)間安排且任何一臺(tái)機(jī)器的每段空閑時(shí)間都缺乏以加工一道可加工工序。符號(hào)說明：Ot 第t步可以排序的工序的集合St t步之前已排序的工序構(gòu)成的局部作業(yè)方案Tk Ot中工序Ok的最早可能開工時(shí)間Tk Ot中工序Ok的最早可能完工時(shí)間五、單件車間排序問題n/m/G/Fmax能動(dòng)作業(yè)方案的構(gòu)成步驟：設(shè)t1，St為空，Ot為各工件第一道

10、工序的集合。求最小的最早完工時(shí)間 T*= minTk ,并找到出現(xiàn)T*的機(jī)器M*，假設(shè)有多臺(tái)，任選一臺(tái)。從Ot中跳出滿足以下兩條件的工序Oj 需要機(jī)器M*加工；Tj T*將確定的Oj放入St，從Ot中消去Oj并將Oj的緊后工序放入Ot中，使t=t+1。假設(shè)還有未安排的工序，轉(zhuǎn)步驟；否那么，停止。一個(gè)實(shí)例：D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2T=2 4 13 4 5i1OtTkTkT*M*Oj1,1,1022M11,1,12,1,30321,2,3263M32,1,32,1,30331,2,3377M31,2,32,2,13741,3,2787M12,2,12

11、,2,13751,3,2788M21,3,22,3,2712613M22,3,22,3,2813得到加工順序矩陣：S=1,1,1 2,2,11,3,2 2,3,22,1,3 1,2,31,1,12,1,31,2,32,2,11,3,22,3,2M1M2M323773813五、單件車間排序問題n/m/G/Fmax3、無延遲作業(yè)方案的構(gòu)成沒有任何延遲出現(xiàn)的能動(dòng)作業(yè)方案。所謂“延遲，指有工件等待加工時(shí)，機(jī)器出現(xiàn)空閑，即使這段空閑時(shí)間缺乏以完成一道工序。構(gòu)成步驟：五、單件車間排序問題n/m/G/Fmax無延遲作業(yè)方案的構(gòu)成步驟：設(shè)t1，St為空，Ot為各工件第一道工序的集合。求最小的最早完工時(shí)間 T*

12、= minTk ,并找到出現(xiàn)T*的機(jī)器M*，假設(shè)有多臺(tái)，任選一臺(tái)。從Ot中跳出滿足以下兩條件的工序Oj 需要機(jī)器M*加工；Tj = T*將確定的Oj放入St，從Ot中消去Oj并將Oj的緊后工序放入Ot中，使t=t+1。假設(shè)還有未安排的工序，轉(zhuǎn)步驟；否那么，停止。一個(gè)實(shí)例：D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2T=2 4 13 4 5i1OtTkTkT*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,2787M2

13、2,3,22,3,2712612M21,3,22,3,212130M33M17M2得到加工順序矩陣：S=1,1,1 2,2,12,3,2 1,3,22,1,3 1,2,31,1,12,1,31,2,32,2,11,3,22,3,2M1M2M32377312134、啟發(fā)式算法： 能動(dòng)作業(yè)方案和無延遲作業(yè)方案盡管不一定是最優(yōu)作業(yè)方案，但一般是較好的作業(yè)方案，特別是無延遲作業(yè)方案能提供令人滿意的解。一般能動(dòng)作業(yè)方案和無延遲作業(yè)方案都有多個(gè)，可用啟發(fā)式方法從中選擇結(jié)果較好的作業(yè)方案。一般來說，以構(gòu)成無延遲作業(yè)方案的步驟為根底的啟發(fā)式算法比以構(gòu)成能動(dòng)作業(yè)方案的步驟為根底的啟發(fā)算法的效果要好。五、單件車間排序問題n/m/G/Fmax優(yōu)選調(diào)度法那么： SPT(Shortest Processing Time)法那么：優(yōu)先選擇加工時(shí)間最短的工序。FCFS(First Come First Served)法那么：優(yōu)先選擇最早進(jìn)入