1、第八章第八章 生產(chǎn)作業(yè)計劃生產(chǎn)作業(yè)計劃 Operations Scheduling and Controlling第一節(jié)第一節(jié) 生產(chǎn)作業(yè)排序生產(chǎn)作業(yè)排序第二節(jié)第二節(jié) 生產(chǎn)作業(yè)控制生產(chǎn)作業(yè)控制 第一節(jié)第一節(jié) 生產(chǎn)作業(yè)排序生產(chǎn)作業(yè)排序一、基本概念一、基本概念1、排序、排序 排序就是要將不同的工作任務(wù)安排一個執(zhí)行的順序，使預(yù)定的目標(biāo)最優(yōu)化。 實際上就是要解決如何按時間的先后，將有限的人力、物力資源分配給不同工作任務(wù)，使預(yù)定目標(biāo)最優(yōu)化的問題。 排序的作用排序的作用 油漆生產(chǎn)順序：油漆生產(chǎn)順序：某企業(yè)生產(chǎn)白、灰、紅、藍四種油漆，每次生產(chǎn)前都有清洗容器的調(diào)整準(zhǔn)備時間。按怎樣的順序，總的調(diào)整準(zhǔn)備時間最少？

2、復(fù)印排序問題：復(fù)印排序問題：有四人同時到達復(fù)印室，每人的復(fù)印量不同，如何安排順序，使得他們的平均等待時間和平均流程時間最?。?方案1：白-灰-紅-藍 T-setup=12方案2：藍-紅-灰-白 T-setup=20白白灰灰紅紅藍藍白白0123灰灰5012紅紅7601藍藍9860排序中常用的幾個概念排序中常用的幾個概念 工件（Job）：服務(wù)對象； 機器（Machine、Processor）：服務(wù)者。如： n個零件在機器上加工，則零件是工件，設(shè)備是機器； 工人維修設(shè)備，出故障的設(shè)備是工件，工人是機器。 所以，作業(yè)排序也就是要確定工件在機器上的加工順序，可用一組工件代號的一種排列來表示。 如可用（1

3、，6，5，4，3，2）表示加工順序：J1J6J5J4J3J2。2、作業(yè)計劃（、作業(yè)計劃（Scheduling） 作業(yè)計劃是安排零部件（作業(yè)、活動）的出產(chǎn)數(shù)量、設(shè)備及人工使用、投入時間及出產(chǎn)時間。 作業(yè)計劃與排序不是一回事，它不僅要確定工件的加工順序，而且還要確定每臺機器加工每個工件的開工時間和完工時間。 如果按最早可能開（完）工時間來編排作業(yè)計劃，則排序完后，作業(yè)計劃也就確定了。3、排序問題的分類與表示、排序問題的分類與表示 根據(jù)機器數(shù)的多少 單臺機器的排序問題 多臺機器的排序問題 根據(jù)加工路線的特征 單件作業(yè)排序(Job Shop) 流水型排序(Flow Shop)流水作業(yè)排序問題的基本特征

4、：流水作業(yè)排序問題的基本特征： 每個工件的加工路線都一樣。如車銑磨。這里指的是工件的加工流向一致，并不要求每個工件必須在每臺機器上加工。如有的工件為車磨，有的為銑磨。 不僅加工路線一致，而且所有工件在各臺機器上的加工順序也一樣，這種排序稱為排列排序（同順序排序）。如工件排序為：J1J3J2，則表示所有機器都是先加工J1，然后加工J3，最后加工J2。單件車間排序問題的基本特征：單件車間排序問題的基本特征： 每個工件都有其獨特的加工路線，工件沒有一定的流向。表示方法表示方法 一般正規(guī)的表示方法為：n/m/A/B n：工件數(shù)；m：機器數(shù)； A：作業(yè)類型（F、P、G）；B：目標(biāo)函數(shù) 4、排序常用的符號

5、、排序常用的符號 Ji-工件i，i=1,2,.n Mj -機器,j=1,2m di-工件i的交貨期 pij-工件i在機器j上的加工時間,j=1,m Pi-工件i的加工時間, mjijipP1mjijiwW1 Wi-工件i在系統(tǒng)內(nèi)的等待時間, wij-工件i在機器j前的等待時間, j=1,m Ci-工件i的完成時間, 在工件都已到達的情況下, Ci= Pi+ Wi Fi-工件i的流程時間，在工件都已到達的情況下, Fi= Pi+ Wi Li-工件i的延誤時間, Li= Ci- di , Li0 延誤 Ti-工件i的延期量, Ti=max0, Li Ei-工件i提前完成的時間5、排序問題的假設(shè)條件

6、、排序問題的假設(shè)條件 工件同時到達。 一個工件不能同時在幾臺不同的機器上加工。 工件在加工過程中采取平行移動方式。 不允許中斷。 每道工序只在一臺機器上完成。 每臺機器同時只能加工一個工件。 工件數(shù)、機器數(shù)和加工時間已知，加工時間與加工順序無關(guān)。二、兩臺機器的排序問題二、兩臺機器的排序問題1、 兩臺機器排序問題的含義兩臺機器排序問題的含義 n個工件都必須經(jīng)過機器1和機器2的加工，即工藝路線是一致的。 機器1到達系統(tǒng)工件的集合離開系統(tǒng)（機器）J1J2J3Jn機器22、最長流程時間、最長流程時間 最長流程時間（加工周期Fmax ）：從第一個工件在第一臺機器上加工起到最后一個工件在最后一臺機器上加工

7、完畢為止所經(jīng)過的時間。Fmax 時間 機器 A B在機器A上的作業(yè)時間總加工周期 假定所有工件的到達時間都為0，則Fmax等于排在末位加工的工件在車間的停留時間。 計算Fmax的幾個假定條件： 機器M1不會發(fā)生空閑； 對其它機器，能對某一工件加工必須具備2個條件：機器必須完成排前一位的工件的加工；要加工的工件的上道工序已經(jīng)完工。3、 Fmax問題的算法問題的算法 兩臺機器排序的目標(biāo)是使Fmax最短。 假定：ai為工件Ji在機器M1上的加工時間，bi為工件Ji在機器M2上的加工時間，每個工件按M1M2的路線加工。 Johnson算法：算法： 從加工時間矩陣中找出最短的加工時間。 若最短時間出現(xiàn)在

8、M1上，則對應(yīng)的工件盡可能往前排。 若最短時間出現(xiàn)在M2上，則對應(yīng)的工件盡可能往后排。 若最短時間有多個，則任選一個。 劃去已排序的工件。 若所有工件都已排序，則停止，否則重復(fù)上述步驟。例：某一班組有A、B兩臺設(shè)備，要完成5個工件的加工任務(wù)。每個工件在設(shè)備上的加工時間如下表所示。求總加工周期最短的作業(yè)順序。 工件在兩臺設(shè)備上的加工時間工件編號 J1 J2 J3 J4 J5設(shè)備A 3 6 7 1 5設(shè)備B 2 8 6 4 3解：由約翰遜法可知，表中最小加工時間值是1個時間單位，它又是出現(xiàn)在設(shè)備1上，根據(jù)約翰遜法的規(guī)則，應(yīng)將對應(yīng)的工件4排在第一位，即得： J4 - * - * - * - * 去掉

9、J4，在剩余的工件中再找最小值，不難看出，最小值是2個時間單位，它是出現(xiàn)在設(shè)備2上的，所以應(yīng)將對應(yīng)的工件J1排在最后一位，即： J4 - * - * - * - J1 再去掉J1，在剩余的J2、J3、J5中重復(fù)上述步驟，求解過程為： J4 - * - * - J5 - J1 J4 - J2 - * - J5 - J1 J4 - J2 - J3- J5 - J1 當(dāng)同時出現(xiàn)多個最小值時，可從中任選一個。最后得J4 - J2 - J3- J5 - J1(a) J1 - J2 - J3- J4 - J5 30AB26AB(b) J4 - J2 - J3- J5 - J1 可以看出，初始作業(yè)順序的總加

10、工周期是30，用約翰遜法排出的作業(yè)順序總加工周期是26，顯然后者的結(jié)果優(yōu)于前者。任務(wù)j1j2j3j4j5j6j7j8 Ma taj23 5867123 Mb tbj1171095432Mc tcj1113121516111214 求最優(yōu)解條件，滿足如下條件之一：jbjcjbjatttt,maxminmaxmin 求解步驟： 1、把三臺設(shè)備轉(zhuǎn)換為兩臺假象設(shè)備，假想設(shè)備加 工時間按如下公式轉(zhuǎn)換：jbjcjhjbjajgtttttt, 任 務(wù)j1j2j3j4j5j6j7j8 Mg tgj131015171111155 Mh thj2220222421151516jbjctt,maxmin三、一般三、

11、一般n/m/P/ Fmax問題的問題的啟發(fā)式算法啟發(fā)式算法 對于一般的n/m/P/Fmax問題，可以用分支定界法求得最優(yōu)解，但計算量很大。實際中，可以用啟發(fā)式算法求近優(yōu)解。1 1、PalmerPalmer法法 計算工件斜度指標(biāo)計算工件斜度指標(biāo) i i ： m : m : 機器數(shù)機器數(shù) p pikik ：工件：工件i i在機器在機器k k上的加工時間。上的加工時間。 i=1,2,i=1,2,n,n 排序方法排序方法: : 按按 i i從大到小的順序排列。從大到小的順序排列。 按排序的順序計算按排序的順序計算FmaxFmaxm1kikip2/ ) 1m(k2 2、關(guān)鍵工件法、關(guān)鍵工件法： 計算Pi

12、= Pij ，找出Pi最長的工件，將之作為關(guān)鍵工件C。 對其余工件，若Pi1Pim ，則按Pi1由小到大排成序列SA。若Pi1 Pim ，則按Pim由大到小排成序列SB。 順序（SA，C，SB）即為近優(yōu)解。用用關(guān)關(guān)鍵鍵工工件件法法求求解解i 1 2 3 4Pi1 1 2 6 3Pi2 8 4 2 9Pi3 4 5 8 2pi 13 11 16 14得到的加工順序為得到的加工順序為 (1，2，3，4)關(guān)鍵工件法舉例J1J2J3J4J5J6機器1pi15541210機器2pi25553610機器3pi3833474機器4pi4282156機器5pi5 5212810總和252315112840找出

13、關(guān)鍵工件：工作負荷最大的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 3、CDS法法： CDS法法是Johnson算法算法的擴展方法，從M-1個排序中找出近優(yōu)解。加工順序 A 加工時間 B 加工時間1t1tm2t1+t2tm-1+tm3t1+t2+t3tm-2+tm-1+tmm-1t1+t2+tm-1t2+tm-1+tm L1，按Johnson算法得到加工順序(1，2，3，

14、4)，F(xiàn)max28 L2，按Johnson算法得到加工順序(2，3，1，4)， Fmax29 取順序(1，2，3，4）為最優(yōu)順序。用用 CDS 法求解法求解i 1 2 3 4Pi1 1 2 6 3L=1Pi3 4 5 8 2Pi1+pi2 9 6 8 12L=2Pi2+pi3 12 9 10 11四、四、N N個零件在某個加工中心的個零件在某個加工中心的排序排序排序的優(yōu)先規(guī)則主要有：先到的先服務(wù)（FCFSFCFS）加工時間短的優(yōu)先加工（SPTSPT）交貨期早的先加工（EDDEDD）最短松弛時間先加工（LSLS）(某項任務(wù)距計劃交貨期的剩余時間與該任務(wù)的作業(yè)時間之差)隨機加工比較研究：例：有5個

15、任務(wù)到達，原始排序是任務(wù)到達順序 加工時間/天 交貨期/天ABCDE34261567921 1、先到的先服務(wù)、先到的先服務(wù)（FCFS）加工順序加工時間交貨日期流程時間延期交貨時間ABCDE34261567920+3=33+4=77+2=99+6=1515+1=1612614總流程時間=3+7+9+15+16=50(天)平均流程時間=50/5=10（天）平均延遲時間=(1+2+6+14)/5=4.6(天) 2 2、加工時間短的優(yōu)先加工、加工時間短的優(yōu)先加工（SPT）加工順序加工時間交貨日期流程時間延期交貨時間ECABD12346275690+1=11+2=33+3=66+4=1010+6=16-

16、147總流程時間=1+3+6+10+16=36(天)平均流程時間=36/5=7.2（天）平均延遲時間=(1+4+7)/5=2.4(天)3 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 4、最短松弛時間先加工、最短松弛時間先加工（LS）加工順序加工時間交貨日期流程時間延期交貨時間EABD1=11+3=

17、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ī)則比較優(yōu)先調(diào)度規(guī)則比較規(guī)則總的完成時間平均完成時間平均延期FCFS50104.6SPT367.22.4EDD397.82.4LS438.63.2零件在加工過程中的移動方式，零件在加工過程中的移動方式，包括： 順序移動方式； 平行移動方式； 平行順序移動方式。五、相同零件、不同移動方式五、相同零件、不同移動方式下加工周期的計算下加工周期的計算1 1、順序移動方式、順序移動方式 一批零件在上道工序全部加工完畢后才整批

18、地轉(zhuǎn)移到下道工序繼續(xù)加工。 優(yōu)點：設(shè)備利用率高；移動次數(shù)少 缺點：加工周期長；管理工作復(fù)雜 常用于單件或成批生產(chǎn)過程工藝原則T順順=n t1+ n t2 + +n tn = n ti時間時間工序工序n=4件， m=4 工序t1=10分鐘/件，t2=5分鐘/件，t3=20分鐘/件，t4=10分鐘/件總加工周期T順2 2、平行移動方式、平行移動方式 每個零件在前道工序加工完畢后立即轉(zhuǎn)移到下道工序繼續(xù)加工，形成前后工序交叉作業(yè)。 優(yōu)點：加工周期短；管理工作簡單 缺點：設(shè)備利用率低；移動次數(shù)多 常用于裝配流水線、大量生產(chǎn)過程對象原則T平平= ti + （n-1）tl時間時間工序工序總加工周期T平平n=4件， m=4 工序t1=10分鐘/件，t2=5分鐘/件，t3=20分鐘/件，t4=10分鐘/件 3 3、平行順序移動方式、平行順序移動方式 要求： 每道工序連續(xù)進行加工； 各道工序盡可能平行地加工；