生產(chǎn)作業(yè)計(jì)劃與排序課件

19七月2023生產(chǎn)作業(yè)計(jì)劃與排序一、基本概念1、排序排序就是要將不同的工作任務(wù)安排一個(gè)執(zhí)行的順序，使預(yù)定的目標(biāo)最優(yōu)化。實(shí)際上就是要解決如何按時(shí)間的先后，將有限的人力、物力資源分配給不同工作任務(wù)，使預(yù)定目標(biāo)最優(yōu)化的問(wèn)題。排序的作用實(shí)例1：油漆生產(chǎn)順序某企業(yè)生產(chǎn)白、灰、紅、藍(lán)四種油漆，每次生產(chǎn)前都有清洗容器的調(diào)整準(zhǔn)備時(shí)間。按怎樣的順序，總的調(diào)整準(zhǔn)備時(shí)間最少？實(shí)例2：復(fù)印排序問(wèn)題有四人同時(shí)到達(dá)復(fù)印室，每人的復(fù)印量不同，如何安排順序，使得他們的平均等待時(shí)間和平均流程時(shí)間最??？方案1：白-灰-紅-藍(lán)T-setup=12

方案2：藍(lán)-紅-灰-白T-setup=20

按最短工時(shí)優(yōu)先原則（SPT）,結(jié)果最優(yōu)。一、基本概念排序中常用的幾個(gè)概念工件（Job）：服務(wù)對(duì)象；機(jī)器（Machine、Processor）：服務(wù)者。如：n個(gè)零件在機(jī)器上加工，則零件是工件，設(shè)備是機(jī)器；工人維修設(shè)備，出故障的設(shè)備是工件，工人是機(jī)器。一、基本概念

作業(yè)排序也就是要確定工件在機(jī)器上的加工順序，可用一組工件代號(hào)的一種排列來(lái)表示。如，用（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í)間來(lái)編排作業(yè)計(jì)劃，則排序完后，作業(yè)計(jì)劃也就確定了。一、基本概念3、排序問(wèn)題的分類與表示1）單臺(tái)機(jī)器與多臺(tái)機(jī)器的排序問(wèn)題。2）流水車間與單件車間排序問(wèn)題。排序問(wèn)題的分類單機(jī)排序和多機(jī)排序：按設(shè)備的種類和數(shù)量：?jiǎn)文繕?biāo)排序和多目標(biāo)排序：按目標(biāo)函數(shù)的性質(zhì)流水型與非流水型排序：按工件加工路線的特征（加工路線是否相同）

同順序排列（P）

一般流水型(F):流水車間(Flow-shop)

非流水型(G):單件車間(Job-shop)一、基本概念流水車間排序問(wèn)題的基本特征：每個(gè)工件的加工路線都一樣。如車—銑—磨。這里指的是工件的加工流向一致，并不要求每個(gè)工件必須在每臺(tái)機(jī)器上加工。如有的工件為車—磨，有的為銑—磨。不僅加工路線一致，而且所有工件在各臺(tái)機(jī)器上的加工順序也一樣，這種排序稱為排列排序（同順序排序）。如工件排序?yàn)椋篔1—J3—J2，則表示所有機(jī)器都是先加工J1，然后加工J3，最后加工J2。一、基本概念單件車間排序問(wèn)題的基本特征：每個(gè)工件都有其獨(dú)特的加工路線，工件沒(méi)有一定的流向。一、基本概念3）表示方法一般正規(guī)的表示方法為：n/m/A/Bn：工件數(shù)；m：機(jī)器數(shù)；A：車間類型（F、P、G）；

同順序排列（P）一般流水型(F):流水車間(Flow-shop)非流水型(G):單件車間(Job-shop)B：目標(biāo)函數(shù)加工周期交貨期總費(fèi)用一、基本概念

4）一般來(lái)說(shuō)，排列排序問(wèn)題的最優(yōu)解不一定是相應(yīng)流水車間排序問(wèn)題的最優(yōu)解，但一般是比較好的解。而對(duì)于僅有2臺(tái)或3臺(tái)機(jī)器的情況，則排列排序問(wèn)題的最優(yōu)解一定是相應(yīng)流水車間排序問(wèn)題的最優(yōu)解。符號(hào)說(shuō)明Ji------工件iMj------機(jī)器jpij------工件i在機(jī)器j上的加工時(shí)間,Pi------工件i總的加工時(shí)間Pi=pijri------工件i的到達(dá)時(shí)間di------工件i的完工期限

wij-----工件i在第j道工序的等待時(shí)間Wi------工件i總的等待時(shí)間Wi=wijCi------工件i的完工時(shí)間Ci=ri+Wi+PiFi------工件i的流程時(shí)間Fi=Ci－ri=Wi+PiLi------工件i的延遲時(shí)間Li=Ci－di

一、基本概念4、排序問(wèn)題的假設(shè)條件一個(gè)工件不能同時(shí)在幾臺(tái)不同的機(jī)器上加工。工件在加工過(guò)程中采取平行移動(dòng)方式。不允許中斷。每道工序只在一臺(tái)機(jī)器上完成。每臺(tái)機(jī)器同時(shí)只能加工一個(gè)工件。工件數(shù)、機(jī)器數(shù)和加工時(shí)間已知，加工時(shí)間與加工順序無(wú)關(guān)。二、最長(zhǎng)流程時(shí)間最長(zhǎng)流程時(shí)間（加工周期）：從第一個(gè)工件在第一臺(tái)機(jī)器上加工起到最后一個(gè)工件在最后一臺(tái)機(jī)器上加工完畢為止所經(jīng)過(guò)的時(shí)間。假定所有工件的到達(dá)時(shí)間都為0，則Fmax等于排在末位加工的工件在車間的停留時(shí)間。二、最長(zhǎng)流程時(shí)間計(jì)算Fmax的幾個(gè)假定條件：機(jī)器M1不會(huì)發(fā)生空閑；對(duì)其它機(jī)器，能對(duì)某一工件加工必須具備2個(gè)條件：機(jī)器必須完成排前一位的工件的加工；要加工的工件的上道工序已經(jīng)完工。二、最長(zhǎng)流程時(shí)間二、最長(zhǎng)流程時(shí)間ipi1pi2pi3pi4615243255144544453258217533674261012131671115202733121722303542132125323846三、n/2/F/Fmax問(wèn)題的算法Johnson算法：假定：ai為工件Ji在機(jī)器M1上的加工時(shí)間，bi為工件Ji在機(jī)器M2上的加工時(shí)間，每個(gè)工件按M1—M2的路線加工。三、n/2/F/Fmax問(wèn)題的算法Johnson算法的步驟：從加工時(shí)間矩陣中找出最短的加工時(shí)間。若最短時(shí)間出現(xiàn)在M1上，則對(duì)應(yīng)的工件盡可能往前排。若最短時(shí)間出現(xiàn)在M2上，則對(duì)應(yīng)的工件盡可能往后排。若最短時(shí)間有多個(gè)，則任選一個(gè)。劃去已排序的工件。若所有工件都已排序，則停止，否則重復(fù)上述步驟。n/2/F/Fmax流水型排序

（1）按約翰遜-貝爾曼規(guī)則排序，得到2--6--3--5--4--1（2）列表計(jì)算流程時(shí)間四、一般n/m/P/Fmax問(wèn)題的啟發(fā)式算法

對(duì)于一般的n/m/P/Fmax問(wèn)題，可以用分支定界法求得最優(yōu)解，但計(jì)算量很大。實(shí)際中，可以用啟發(fā)式算法求近優(yōu)解。四、一般n/m/P/Fmax問(wèn)題的啟發(fā)式算法1、Palmer法計(jì)算工件斜度指標(biāo)i：m:機(jī)器數(shù)pik：工件i在機(jī)器k上的加工時(shí)間。M=3i=-pi1+pi3

M=4i=-1.5pi1-0.5pi2+0.5pi3+1.5pi4排序方法:按i從大到小的順序排列。按排序的順序計(jì)算Fmax四、一般n/m/P/Fmax問(wèn)題的啟發(fā)式算法2、關(guān)鍵工件法：計(jì)算Pi=Pij，找出Pi最長(zhǎng)的工件，將之作為關(guān)鍵工件C。對(duì)其余工件，若Pi1≤Pim，則按Pi1由小到大排成序列SA。若Pi1>Pim，則按Pim由大到小排成序列SB。順序（SA，C，SB）即為近優(yōu)解。四、一般n/m/P/Fmax問(wèn)題的啟發(fā)式算法得到的加工順序?yàn)?1，2，3，4)四、一般n/m/P/Fmax問(wèn)題的啟發(fā)式算法3、CDS法：CDS法是Johnson算法的擴(kuò)展方法，從M-1個(gè)排序中找出近優(yōu)解。四、一般n/m/P/Fmax問(wèn)題的啟發(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)順序。問(wèn)題描述流水(i,j)(工件，工序)單件(i,j,k)(工件，工序，機(jī)器)加工描述矩陣和加工時(shí)間矩陣

五、單件車間排序問(wèn)題（n/m/G/Fmax）五、單件車間排序問(wèn)題（n/m/G/Fmax）1、問(wèn)題描述(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五、單件車間排序問(wèn)題（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五、單件車間排序問(wèn)題（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五、單件車間排序問(wèn)題（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五、單件車間排序問(wèn)題（n/m/G/Fmax）2、能動(dòng)作業(yè)計(jì)劃的構(gòu)成各工序都按最早可能開(完)工時(shí)間安排且任何一臺(tái)機(jī)器的每段空閑時(shí)間都不足以加工一道可加工工序。符號(hào)說(shuō)明：{Ot}第t步可以排序的工序的集合{St}t步之前已排序的工序構(gòu)成的部分作業(yè)計(jì)劃Tk{Ot}中工序Ok的最早可能開工時(shí)間T’k{Ot}中工序Ok的最早可能完工時(shí)間五、單件車間排序問(wèn)題（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五、單件車間排序問(wèn)題（n/m/G/Fmax）3、無(wú)延遲作業(yè)計(jì)劃的構(gòu)成沒(méi)有任何延遲出現(xiàn)的能動(dòng)作業(yè)計(jì)劃。所謂“延遲”，指有工件等待加工時(shí)，機(jī)器出現(xiàn)空閑，即使這段空閑時(shí)間不足以完成一道工序。構(gòu)成步驟：五、單件車間排序問(wèn)題（n/m/G/Fmax）無(wú)延遲作業(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