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

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

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

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

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

機(jī)器A

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