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

方案2：藍-紅-灰-白T-setup=20

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

作業(yè)排序也就是要確定工件在機器上的加工順序，可用一組工件代號的一種排列來表示。如，用（1，6，5，4，3，2）表示加工順序：J1—J6—J5—J4—J3—J2。一、基本概念2、作業(yè)計劃（Scheduling）作業(yè)計劃與排序不是一回事，它不僅要確定工件的加工順序，而且還要確定每臺機器加工每個工件的開工時間和完工時間。如果按最早可能開（完）工時間來編排作業(yè)計劃，則排序完后，作業(yè)計劃也就確定了。一、基本概念3、排序問題的分類與表示1）單臺機器與多臺機器的排序問題。2）流水車間與單件車間排序問題。排序問題的分類單機排序和多機排序：按設(shè)備的種類和數(shù)量：單目標(biāo)排序和多目標(biāo)排序：按目標(biāo)函數(shù)的性質(zhì)流水型與非流水型排序：按工件加工路線的特征（加工路線是否相同）

同順序排列（P）

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

非流水型(G):單件車間(Job-shop)一、、基基本本概概念念流水水車車間間排排序序問問題題的的基基本本特特征征：：每個個工工件件的的加加工工路路線線都都一一樣樣。。如如車車——銑銑——磨磨。。這這里里指指的的是是工工件件的的加加工工流流向向一一致致，，并并不不要要求求每每個個工工件件必必須須在在每每臺臺機機器器上上加加工工。。如如有有的的工工件件為為車車——磨磨，，有有的的為為銑銑——磨磨。。不僅僅加加工工路路線線一一致致，，而而且且所所有有工工件件在在各各臺臺機機器器上上的的加加工工順順序序也也一一樣樣，，這這種種排排序序稱稱為為排排列列排排序序（（同同順順序序排排序序））。。如如工工件件排排序序為為：：J1——J3——J2，，則則表表示示所所有有機機器器都都是是先先加加工工J1，，然然后后加加工工J3，，最最后后加加工工J2。。一、、基基本本概概念念單件件車車間間排排序序問問題題的的基基本本特特征征：：每個個工工件件都都有有其其獨獨特特的的加加工工路路線線，，工工件件沒沒有有一一定定的的流流向向。。一、、基基本本概概念念3））表表示示方方法法一般般正正規(guī)規(guī)的的表表示示方方法法為為：：n/m/A/Bn：：工工件件數(shù)數(shù)；；m：：機機器器數(shù)數(shù)；；A：：車車間間類類型型（（F、、P、、G））；；同順順序序排排列列（（P））一般般流流水水型型(F):流流水水車車間間(Flow-shop)非流流水水型型(G):單單件件車車間間(Job-shop)B：：目目標(biāo)標(biāo)函函數(shù)數(shù)加工工周周期期交貨貨期期總費費用用一、、基基本本概概念念4））一一般般來來說說，，排排列列排排序序問問題題的的最最優(yōu)優(yōu)解解不不一一定定是是相相應(yīng)應(yīng)流流水水車車間間排排序序問問題題的的最最優(yōu)優(yōu)解解，，但但一一般般是是比比較較好好的的解解。。而而對對于于僅僅有有2臺臺或或3臺臺機機器器的的情情況況，，則則排排列列排排序序問問題題的的最最優(yōu)優(yōu)解解一一定定是是相相應(yīng)應(yīng)流流水水車車間間排排序序問問題題的的最最優(yōu)優(yōu)解解。。符號號說說明明Ji------工工件件iMj------機機器器jpij------工工件件i在在機機器器j上上的的加加工工時時間間,Pi------工工件件i總總的的加加工工時時間間Pi=pijri------工工件件i的的到到達達時時間間di------工工件件i的的完完工工期期限限wij-----工工件件i在在第第j道道工工序序的的等等待待時時間間Wi------工工件件i總總的的等等待待時時間間Wi=wijCi------工工件件i的的完完工工時時間間Ci=ri+Wi+PiFi------工工件件i的的流流程程時時間間Fi=Ci－ri=Wi+PiLi------工件i的延延遲時間Li=Ci－di一、基本概念念4、排序問題題的假設(shè)條件件一個工件不能能同時在幾臺臺不同的機器器上加工。工件在加工過過程中采取平平行移動方式式。不允許中斷。。每道工序只在在一臺機器上上完成。每臺機器同時時只能加工一一個工件。工件數(shù)、機器器數(shù)和加工時時間已知，加加工時間與加加工順序無關(guān)關(guān)。二、最長流程程時間最長流程時間間（加工周期期）：從第一一個工件在第第一臺機器上上加工起到最最后一個工件件在最后一臺臺機器上加工工完畢為止所所經(jīng)過的時間間。假定所有工件件的到達時間間都為0，則則Fmax等等于排在末位位加工的工件件在車間的停停留時間。二、最長流程程時間計算Fmax的幾個假定定條件：機器M1不會會發(fā)生空閑；；對其它機器，，能對某一工工件加工必須須具備2個條條件：機器必必須完成排前前一位的工件件的加工；要要加工的工件件的上道工序序已經(jīng)完工。二、最長流程程時間二、最長流程程時間ipi1pi2pi3pi4615243255144544453258217533674261012131671115202733121722303542132125323846三、n/2/F/Fmax問問題的的算法法Johnson算法法：假定：：ai為工件件Ji在機器器M1上的的加工工時間間，bi為工件件Ji在機器器M2上的的加工工時間間，每每個工工件按按M1—M2的的路線線加工工。三、n/2/F/Fmax問問題的的算法法Johnson算法法的步步驟：：從加工工時間間矩陣陣中找找出最最短的的加工工時間間。若最短短時間間出現(xiàn)現(xiàn)在M1上，則則對應(yīng)應(yīng)的工工件盡盡可能能往前前排。。若最短短時間間出現(xiàn)現(xiàn)在M2上，則則對應(yīng)應(yīng)的工工件盡盡可能能往后后排。。若最短短時間間有多多個，，則任任選一一個。。劃去已已排序序的工工件。。若所有有工件件都已已排序序，則則停止止，否否則重重復(fù)上上述步步驟。。n/2/F/Fmax流水型型排序序（1））按約約翰遜遜-貝貝爾曼曼規(guī)則則排序序，得得到2--6--3--5--4--1（2））列表表計算算流程程時間間四、一一般n/m/P/Fmax問題題的啟啟發(fā)式式算法法對于一一般的的n/m/P/Fmax問題題，可可以用用分支支定界界法求求得最最優(yōu)解解，但但計算算量很很大。。實際際中，，可以以用啟啟發(fā)式式算法法求近近優(yōu)解解。四、一一般n/m/P/Fmax問題題的啟啟發(fā)式式算法法1、Palmer法法計算工工件斜斜度指指標(biāo)i：：m:機機器數(shù)數(shù)pik：工件件i在在機器器k上上的加加工時時間。。M=3i=-pi1+pi3M=4i=-1.5pi1-0.5pi2+0.5pi3+1.5pi4排序方方法:按按i從大到到小的的順序序排列列。按排序序的順順序計計算Fmax四、一一般n/m/P/Fmax問題題的啟啟發(fā)式式算法法2、關(guān)關(guān)鍵工工件法法：計算Pi=Pij，找出出Pi最長的的工件件，將將之作作為關(guān)關(guān)鍵工工件C。對其余余工件件，若若Pi1≤Pim，則按按Pi1由小到到大排排成序序列SA。若Pi1>Pim，則按按Pim由大到到小排排成序序列SB。順序（（SA，C，，SB）即為為近優(yōu)優(yōu)解。。四、一一般n/m/P/Fmax問題題的啟啟發(fā)式式算法法得到的的加工工順序序為(1，2，3，4)四、一一般n/m/P/Fmax問題題的啟啟發(fā)式式算法法3、CDS法：CDS法是是Johnson算算法的的擴展展方法法，從從M-1個個排序序中找找出近近優(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)順序序。問題描述述流水(i,j)(工件件，工序序)單件(i,j,k)(工工件，工工序，機機器)加工描述述矩陣和和加工時時間矩陣陣五、單件件車間排排序問題題（n/m/G/Fmax）五、單件件車間排排序問題題（n/m/G/Fmax）1、問題描述述(i，j，k)：表示示工件i的第j道工序序是在機機器k上上進行。。加工描述述矩陣D：每一一行描述述一個工工件的加加工，每每一列的的工序序序號相同同。D=1,1,11,2,31,3,22,1,32,2,12,3,2五、單件件車間排排序問題題（n/m/G/Fmax）加工時間間矩陣T：與D相對應(yīng)應(yīng)。D=1,1,11,2,31,3,22,1,32,2,12,3,2T=463574五、單件件車間排排序問題題（n/m/G/Fmax）加工順序序矩陣S：每一一行與機機器相對對應(yīng)，每每一列與與工件相相對應(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、能動作業(yè)業(yè)計劃的的構(gòu)成各工序都都按最早早可能開開(完)工時間間安排且且任何一一臺機器器的每段段空閑時時間都不不足以加加工一道道可加工工工序。。符號說明明：{Ot}第t步可以以排序的的工序的的集合{St}t步步之前已已排序的的工序構(gòu)構(gòu)成的部部分作業(yè)業(yè)計劃Tk{Ot}中工序序Ok的最早可可能開工工時間T’k{Ot}中工序序Ok的最早可可能完工工時間五、單件件車間排排序問題題（n/m/G/Fmax）能動作業(yè)業(yè)計劃的的構(gòu)成步步驟：①設(shè)t＝1，{St}為空，，{Ot}為各工工件第一一道工序序的集合合。②求最小的的最早完完工時間間T*=min{T’k},并找到出現(xiàn)現(xiàn)T*的機器M*，若有多多臺，任任選一臺臺。③從{Ot}中跳出出滿足以以下兩條條件的工工序Oj需要機器器M*加工；Tj<T*④將確定定的Oj放入{St}，從{Ot}中消去去Oj并并將Oj的緊后后工序放放入{Ot}中中，使t=t+1。⑤若還有有未安排排的工序序，轉(zhuǎn)步步驟②；；否則，，停止。。一個實例例：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è)計計劃的構(gòu)成沒有任何延遲遲出現(xiàn)的能動動作業(yè)計劃。。所謂“延遲遲”，指有工工件等待加工工時，機器出出現(xiàn)空閑，即即使這段空閑閑時間不足以以完成一道工工序。構(gòu)成步驟：五、單件車間間排序問題（（n/m/G/Fmax）無延遲作業(yè)計計劃的構(gòu)成步步驟：①設(shè)t＝1，{St}為空，{Ot}為各工件第第一道工序的的集合。②求最小的最早早完工時間T*=min{Tk},并找到出現(xiàn)T*的機器M*，若有多臺，，任選一臺。。③從{Ot}中跳出滿足足以下兩條件件的工序Oj需要機器M*加工；Tj=T*④將確定的Oj放入{St}，從{Ot}中消消去Oj并將將Oj的緊后后工序放入{Ot}中，，使t=t+1。⑤若還有未安安排的工序，，轉(zhuǎn)步驟②；；否則，停止止。一個實例：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得到加工順順