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

1、第八章第八章 生產(chǎn)作業(yè)計(jì)劃生產(chǎn)作業(yè)計(jì)劃 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ù)安排一個(gè)執(zhí)行的順序，使預(yù)定的目標(biāo)最優(yōu)化。 實(shí)際上就是要解決如何按時(shí)間的先后，將有限的人力、物力資源分配給不同工作任務(wù)，使預(yù)定目標(biāo)最優(yōu)化的問題。 排序的作用排序的作用 油漆生產(chǎn)順序：油漆生產(chǎn)順序：某企業(yè)生產(chǎn)白、灰、紅、藍(lán)四種油漆，每次生產(chǎn)前都有清洗容器的調(diào)整準(zhǔn)備時(shí)間。按怎樣的順序，總的調(diào)整準(zhǔn)備時(shí)間最少？

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

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

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

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

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

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

8、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) J1 J2 J3 J4 J5設(shè)備A 3 6 7 1 5設(shè)備B 2 8 6 4 3解：由約翰遜法可知，表中最小加工時(shí)間值是1個(gè)時(shí)間單位，它又是出現(xiàn)在設(shè)備1上，根據(jù)約翰遜法的規(guī)則，應(yīng)將對(duì)應(yīng)的工件4排在第一位，即得： J4 - * - * - * - * 去掉

9、J4，在剩余的工件中再找最小值，不難看出，最小值是2個(gè)時(shí)間單位，它是出現(xiàn)在設(shè)備2上的，所以應(yīng)將對(duì)應(yīng)的工件J1排在最后一位，即： J4 - * - * - * - J1 再去掉J1，在剩余的J2、J3、J5中重復(fù)上述步驟，求解過程為： J4 - * - * - J5 - J1 J4 - J2 - * - J5 - J1 J4 - J2 - J3- J5 - J1 當(dāng)同時(shí)出現(xiàn)多個(gè)最小值時(shí)，可從中任選一個(gè)。最后得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、把三臺(tái)設(shè)備轉(zhuǎn)換為兩臺(tái)假象設(shè)備，假想設(shè)備加 工時(shí)間按如下公式轉(zhuǎn)換：jbjcjhjbjajgtttttt, 任 務(wù)j1j2j3j4j5j6j7j8 Mg tgj131015171111155 Mh thj2220222421151516jbjctt,maxmin三、一般三、

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

12、 Pij ，找出Pi最長的工件，將之作為關(guān)鍵工件C。 對(duì)其余工件，若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得到的加工順序?yàn)榈玫降募庸ろ樞驗(yàn)?(1，2，3，4)關(guān)鍵工件法舉例J1J2J3J4J5J6機(jī)器1pi15541210機(jī)器2pi25553610機(jī)器3pi3833474機(jī)器4pi4282156機(jī)器5pi5 5212810總和252315112840找出關(guān)

13、鍵工件：工作負(fù)荷最大的40，對(duì)應(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算法算法的擴(kuò)展方法，從M-1個(gè)排序中找出近優(yōu)解。加工順序 A 加工時(shí)間 B 加工時(shí)間1t1tm2t1+t2tm-1+tm3t1+t2+t3tm-2+tm-1+tmm-1t1+t2+tm-1t2+tm-1+tm L1，按Johnson算法得到加工順序(1，2，3，4

14、)，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個(gè)零件在某個(gè)加工中心的個(gè)零件在某個(gè)加工中心的排序排序排序的優(yōu)先規(guī)則主要有：先到的先服務(wù)（FCFSFCFS）加工時(shí)間短的優(yōu)先加工（SPTSPT）交貨期早的先加工（EDDEDD）最短松弛時(shí)間先加工（LSLS）(某項(xiàng)任務(wù)距計(jì)劃交貨期的剩余時(shí)間與該任務(wù)的作業(yè)時(shí)間之差)隨機(jī)加工比較研究：例：有5個(gè)任

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

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

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

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