生產(chǎn)作業(yè)計劃教材

第八章生產(chǎn)作業(yè)計劃

OperationsSchedulingandControlling第一節(jié)生產(chǎn)作業(yè)排序第二節(jié)生產(chǎn)作業(yè)控制第一節(jié)生產(chǎn)作業(yè)排序

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

方案2：藍(lán)-紅-灰-白T-setup=20排序中常用的幾個概念工件（Job）：服務(wù)對象；機(jī)器（Machine、Processor）：服務(wù)者。如：n個零件在機(jī)器上加工，則零件是工件，設(shè)備是機(jī)器；工人維修設(shè)備，出故障的設(shè)備是工件，工人是機(jī)器。所以，作業(yè)排序也就是要確定工件在機(jī)器上的加工順序，可用一組工件代號的一種排列來表示。如可用（1，6，5，4，3，2）表示加工順序：J1—J6—J5—J4—J3—J2。2、作業(yè)計劃（Scheduling）作業(yè)計劃是安排零部件（作業(yè)、活動）的出產(chǎn)數(shù)量、設(shè)備及人工使用、投入時間及出產(chǎn)時間。作業(yè)計劃與排序不是一回事，它不僅要確定工件的加工順序，而且還要確定每臺機(jī)器加工每個工件的開工時間和完工時間。如果按最早可能開（完）工時間來編排作業(yè)計劃，則排序完后，作業(yè)計劃也就確定了。3、排序問題的分類與表示根據(jù)機(jī)器數(shù)的多少單臺機(jī)器的排序問題多臺機(jī)器的排序問題根據(jù)加工路線的特征單件作業(yè)排序(JobShop)流水型排序(FlowShop)流水作業(yè)排序問題的基本特征：每個工件的加工路線都一樣。如車—銑—磨。這里指的是工件的加工流向一致，并不要求每個工件必須在每臺機(jī)器上加工。如有的工件為車—磨，有的為銑—磨。不僅加工路線一致，而且所有工件在各臺機(jī)器上的加工順序也一樣，這種排序稱為排列排序（同順序排序）。如工件排序為：J1—J3—J2，則表示所有機(jī)器都是先加工J1，然后加工J3，最后加工J2。單件車間排序問題的基本特征：每個工件都有其獨(dú)特的加工路線，工件沒有一定的流向。表示方法一般正規(guī)的表示方法為：n/m/A/Bn：工件數(shù)；m：機(jī)器數(shù)；A：作業(yè)類型（F、P、G）；B：目標(biāo)函數(shù)4、排序常常用的符號號Ji----工件i，i=1,2,....nMj----機(jī)機(jī)器,j=1,2…mdi----工件i的交貨期pij----工工件i在機(jī)機(jī)器j上的的加工時間間,j=1,……,mPi----工件件i的加加工工時時間間,Wi----工件件i在系系統(tǒng)統(tǒng)內(nèi)內(nèi)的的等等待待時時間間,wij----工工件件i在在機(jī)機(jī)器器j前前的的等等待待時時間間,j=1,……,mCi----工件件i的完完成成時時間間,在在工工件件都都已已到到達(dá)達(dá)的的情情況況下下,Ci=Pi+WiFi----工件件i的流流程程時時間間，在工工件件都都已已到到達(dá)達(dá)的的情情況況下下,Fi=Pi+WiLi----工件件i的延延誤誤時時間間,Li=Ci-di,Li<=0按期期或或完完成成提提前前；Li>0延誤誤Ti----工件件i的延延期期量量,Ti=max{0,Li}Ei----工件件i提前前完完成成的的時時間間5、、排排序序問問題題的的假假設(shè)設(shè)條條件件工件件同同時時到到達(dá)達(dá)。。一個個工工件件不不能能同同時時在在幾幾臺臺不不同同的的機(jī)機(jī)器器上上加加工工。。工件件在在加加工工過過程程中中采采取取平平行行移移動動方方式式。。不允允許許中中斷斷。。每道道工工序序只只在在一一臺臺機(jī)機(jī)器器上上完完成成。。每臺臺機(jī)機(jī)器器同同時時只只能能加加工工一一個個工工件件。。工件件數(shù)數(shù)、、機(jī)機(jī)器器數(shù)數(shù)和和加加工工時時間間已已知知，，加加工工時時間間與與加加工工順順序序無無關(guān)關(guān)。。二、、兩兩臺臺機(jī)機(jī)器器的的排排序序問問題題1、、兩兩臺臺機(jī)機(jī)器器排排序序問問題題的的含含義義n個工工件件都都必必須須經(jīng)經(jīng)過過機(jī)機(jī)器器1和和機(jī)機(jī)器器2的的加加工工，，即即工工藝藝路路線線是是一一致致的的。。機(jī)器1到達(dá)系統(tǒng)工件的集合離開系統(tǒng)（機(jī)器）J1J2J3Jn機(jī)器22、、最最長長流流程程時時間間最長長流流程程時時間間（（加加工工周周期期Fmax））：：從從第第一一個個工工件件在在第第一一臺臺機(jī)機(jī)器器上上加加工工起起到到最最后后一一個個工工件件在在最最后后一一臺臺機(jī)機(jī)器器上上加加工工完完畢畢為為止止所所經(jīng)經(jīng)過過的的時時間間。。Fmax時間

機(jī)器A

B在機(jī)器A上的作業(yè)時間總加工周期假定定所所有有工工件件的的到到達(dá)達(dá)時時間間都都為為0，，則則Fmax等等于于排排在在末末位位加加工工的的工工件件在在車車間間的的停停留留時時間間。。計算算Fmax的的幾幾個個假假定定條條件件：：機(jī)器器M1不不會會發(fā)發(fā)生生空空閑閑；；對其其它它機(jī)機(jī)器器，，能能對對某某一一工工件件加加工工必必須須具具備備2個個條條件件：：機(jī)機(jī)器器必必須須完完成成排排前前一一位位的的工工件件的的加加工工；；要要加加工工的的工工件件的的上上道道工工序序已已經(jīng)經(jīng)完完工工。。3、Fmax問題的算算法兩臺機(jī)器排序序的目標(biāo)是使使Fmax最短。假定：ai為工件Ji在機(jī)器M1上上的加工時間間，bi為工件Ji在機(jī)器M2上上的加工時間間，每個工件件按M1—M2的路線加加工。Johnson算法：從加工時間矩矩陣中找出最最短的加工時時間。若最短時間出出現(xiàn)在M1上，則對應(yīng)的的工件盡可能能往前排。若最短時間出出現(xiàn)在M2上，則對應(yīng)的的工件盡可能能往后排。若最短時間有有多個，則任任選一個。劃去已排序的的工件。若所有工件都都已排序，則則停止，否則則重復(fù)上述步步驟。例：某一班組組有A、B兩兩臺設(shè)備，要要完成5個工工件的加工任任務(wù)。每個工工件在設(shè)備上上的加工時間間如下表所示示。求總加工工周期最短的的作業(yè)順序。。工件在兩臺設(shè)備上的加工時間工件編號J1J2J3J4J5設(shè)備A36715設(shè)備B28643解：由約翰遜法可可知，表中最最小加工時間間值是1個時時間單位，它它又是出現(xiàn)在在設(shè)備1上，，根據(jù)約翰遜遜法的規(guī)則，，應(yīng)將對應(yīng)的的工件4排在在第一位，即即得：J4-*-*-*-*去掉J4，在剩余的工件件中再找最小小值，不難看看出，最小值值是2個時間間單位，它是是出現(xiàn)在設(shè)備備2上的，所所以應(yīng)將對應(yīng)應(yīng)的工件J1排在最后一位位，即：J4-*-*-*-J1再去掉J1，，在剩余的J2、J3、、J5中重復(fù)復(fù)上述步驟，，求解過程為為：J4-*-*-J5-J1J4-J2-*-J5-J1J4-J2-J3-J5-J1當(dāng)同時出現(xiàn)多多個最小值時時，可從中任任選一個。最最后得J4-J2-J3-J5-J1(a)J1-J2-J3-J4-J530AB26AB(b)J4-J2-J3-J5-J1可以看出，初初始作業(yè)順序序的總加工周周期是30，，用約翰遜法法排出的作業(yè)業(yè)順序總加工工周期是26，顯然后者者的結(jié)果優(yōu)于于前者。任務(wù)j1j2j3j4j5j6j7j8Mataj235867123Mbtbj1171095432Mctcj1113121516111214N項任務(wù)、三三臺設(shè)備的排排序例：三臺設(shè)備備、8項任務(wù)務(wù)，各任務(wù)的的工藝順序相相同，資料如如下：求最優(yōu)解條件件，滿足如下下條件之一：：求解步驟：1、把三臺設(shè)設(shè)備轉(zhuǎn)換為兩兩臺假象設(shè)備備，假想設(shè)備備加工時間按如下下公式轉(zhuǎn)換：：任務(wù)j1j2j3j4j5j6j7j8Mgtgj131015171111155Mhthj2220222421151516用約-貝規(guī)則則求得排序結(jié)結(jié)果如下：J8-J2-J5-J6-J1-J3-J7-J4；(或：-J4-J7）上例中，滿足足條件轉(zhuǎn)換兩臺假想想設(shè)備，結(jié)果果如下表：三、一般n/m/P/Fmax問問題的啟發(fā)式式算法對于一般的n/m/P/Fmax問問題，可以用用分支定界法法求得最優(yōu)解解，但計算量量很大。實際際中，可以用用啟發(fā)式算法法求近優(yōu)解。。1、Palmer法計算工件斜度度指標(biāo)i：m:機(jī)器器數(shù)pik：工件i在機(jī)機(jī)器k上的加加工時間。i=1,2,,n排序方法:按按i從大到小的順順序排列。按排序的順序序計算Fmax2、關(guān)鍵工件件法：計算Pi=Pij，找出Pi最長的工件，，將之作為關(guān)關(guān)鍵工件C。。對其余工件，，若Pi1≤Pim，則按Pi1由小到大排成成序列SA。若Pi1>Pim，則按Pim由大到小排成成序列SB。順序（SA，C，SB）即為近優(yōu)解解。得到的加工順順序為(1，2，3，，4)關(guān)鍵工件法舉舉例J1J2J3J4J5J6機(jī)器1pi15541210機(jī)器2pi25553610機(jī)器3pi3833474機(jī)器4pi4282156機(jī)器5pi55212810總和252315112840找出關(guān)鍵工件件：工作負(fù)荷荷最大的40，對應(yīng)的是是工件6，所所以JC=J6確定排在關(guān)鍵鍵工件前面的的工件：滿足足步驟2條件件的有J1,J4,J5,所以有SA=J4–J5–J1確定排在關(guān)鍵鍵工件后面的的工件：滿足足步驟3條件件的有J2,J3,所以有SB=J2–J3最后有：J4–J5–J1–J6–J2–J33、CDS法：CDS法是Johnson算法的擴(kuò)展方法，，從M-1個個排序中找出出近優(yōu)解。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個零件件在某個加工工中心的排序序排序的優(yōu)先規(guī)規(guī)則主要有：：先到的先服務(wù)務(wù)（FCFS）加工時間短的的優(yōu)先加工（（SPT）交貨期早的先先加工（EDD）最短松弛時間間先加工（LS）(某項任務(wù)距距計劃交貨期期的剩余時間間與該任務(wù)的的作業(yè)時間之之差)隨機(jī)加工比較研究：例：有5個任任務(wù)到達(dá)，原原始排序是任務(wù)到達(dá)順序加工時間/天交貨期/天ABCDE34261567921、先到的先先服務(wù)（FCFS））加工順序加工時間交貨日期流程時間延期交貨時間ABCDE34261567920+3=33+4=77+2=99+6=1515+1=16——12614總流程時間=3+7+9+15+16=50(天)平均流程時間=50/5=10（天）平均延遲時間=(1+2+6+14)/5=4.6(天)2、加工時間間短的優(yōu)先加加工（SPT）加工順序加工時間交貨日期流程時間延期交貨時間ECABD12346275690+1=11+2=33+3=66+4=1010+6=16——-----147總流程時間=1+3+6+10+16=36(天)平均流程時間=36/5=7.2（天）平均延遲時間=(1+4+7)/5=2.4(天)3、交貨期早早的先加工（EDD）加工順序a加工時間交貨日期流程時間延期交貨時間EABC1=11+3=44+4=88+2=1010+6=16——-----237總流程時間=1+4+8+10+16=39(天)平均流程時間=39/5=7.8（天）平均延遲時間=(2+3+7)/5=2.4(天)4、最短松弛弛時間先加工工（LS）加工順序加工時間交貨日期流程時間延期交貨時間EABD1=11+3=44+4=88+6=1414+2=16——-----259總流程時間=1+4+8+14+16=43(天)平均流程時間=43/5=8.6（天）平均延遲時間=(2+5+9)/5=3.2(天)優(yōu)先調(diào)度規(guī)則則比較規(guī)則總的完成時間平均完成時間平均延期FCFS50104.6SPT367.22.4EDD397.82.4LS438.63.2零件在加工過過程中的移動動方式，包括：順序移動方式式；平行移動方式式；平行順序移動動方式。五、相同零件件、不同移動動方式下加工工周期的計算算1、順序移動動方式一批零件在上上道工序全部部加工完畢后后才整批地轉(zhuǎn)轉(zhuǎn)移到下道工工序繼續(xù)加工工。優(yōu)點(diǎn)：設(shè)備利利用率高；移移動次數(shù)少缺點(diǎn)：加工周周期長；管理理工作復(fù)雜常用于單件或或成批生產(chǎn)過過程——工藝藝原