第4講 制造業(yè)作業(yè)計劃及控制

1、1生產(chǎn)運作管理生產(chǎn)運作管理Production & Operations Management青島理工大學（臨沂）馮海俠2016年5月2第4章 制造業(yè)作業(yè)計劃與控制Scheduling and Controlling for Manufacturing4.1 作業(yè)計劃問題的基本概念4.2 流水車間作業(yè)計劃問題4.3 單件車間作業(yè)計劃問題4.4 生產(chǎn)作業(yè)控制 34.1作業(yè)計劃問題的基本概念4.1.1 生產(chǎn)作業(yè)計劃概述4.1.2 有關的名詞術語4.1.3 假設條件與符號說明4.1.4 排序問題的分類和表示法44.1.1生產(chǎn)作業(yè)計劃概述生產(chǎn)作業(yè)計劃是企業(yè)年度生產(chǎn)計劃和MRP輸出的具體執(zhí)行計劃

2、。它根據(jù)年度生產(chǎn)計劃的要求對每個生產(chǎn)單位（車間、工段、班組），在每個具體的時期（月、旬、周、日、輪班、小時等）內(nèi)的生產(chǎn)任務作出詳細的安排并規(guī)定實現(xiàn)的方法，從而保證企業(yè)按數(shù)量、品種、質量、交貨期的要求全面完成生產(chǎn)計劃。5n 生產(chǎn)作業(yè)計劃的內(nèi)容生產(chǎn)作業(yè)計劃的內(nèi)容 生產(chǎn)作業(yè)計劃的主要任務是將主生產(chǎn)計劃或MRP中零部件的投入出產(chǎn)計劃細化，他是MRP的具體執(zhí)行計劃，具體、詳細地規(guī)定了各車間、工段、班組以至每個工作地在較短的時間內(nèi)（月、旬、周、日、輪班、小時）的生產(chǎn)運作任務。6 生產(chǎn)作業(yè)計劃工作由作業(yè)計劃編制與作業(yè)計劃控制兩部分組成。 作業(yè)計劃編制：包括制定期量標準、開展生產(chǎn)運作能力核算與平衡、編制各種形

3、式的生產(chǎn)作業(yè)計劃等。 作業(yè)計劃控制包括生產(chǎn)運作調度、生產(chǎn)運作作業(yè)統(tǒng)計與分析等內(nèi)容。7生產(chǎn)作業(yè)計劃的作用 保證主生產(chǎn)計劃規(guī)定的生產(chǎn)運作任務的完成。 保證企業(yè)獲取更好的經(jīng)濟效益。8 4.1.2 有關的名詞術語排序：排序：就是要將不同的工作任務安排一個執(zhí)行的順序，使預定的目標最優(yōu)化。實際上就是要解決如何按時間的先后，將有限的人力、物力分配給不同工作任務，使預定目標最優(yōu)化的問題。 派工派工：在作業(yè)計劃制定以后，按照作業(yè)計劃的要求，將具體生產(chǎn)任務通過工票或施工單的形式下達到具體的機床和工人。 趕工趕工：是在實際進度已經(jīng)落后于計劃進度時采取的行動。 調度調度：是作業(yè)計劃編制以后，實行生產(chǎn)控制的一切行動。9

4、4.1.2有關的名詞術語（續(xù)）“機器”，表示“服務者”.可以是工廠里的各種機床，也可以是維修工人；可以是輪船要?？康拇a頭，也可以是電子的計算機中央處理單元、存貯器和輸入、輸出單元?！傲慵贝怼胺諏ο蟆薄Ａ慵梢允菃蝹€零件，也可以是一批相同的零件“加工路線”是零件加工的工藝過程決定的，它是零件加工在技術上的約束 “加工順序”則表示每臺機器加工n個零件的先后順序，是排序和編制作業(yè)計劃要解決的問題104.1.3 假設條件與符號說明假設條件假設條件n一個零件不能同時在幾臺不同的機器上加工。n零件在加工過程中采取平行移動方式，即當上一道工序完工后，立即送下道工序加工。n不允許中斷。當一個零件一旦開始

5、加工，必須一直進行到完工，不得中途停止插入其它零件。n每道工序只在一臺機器上完成。n零件數(shù)、機器數(shù)和加工時間已知。n每臺機器同時只能加工一個零件。 114.1.3 假設條件與符號說明（續(xù)）nJi 零件i，i1,2,n。nMj機器j，j1,2,m。npij一Ji在Mj上的加工時間，Ji的總加工時間為Pipij nri一Ji的到達時間，指Ji從外部進入車間，可以開始加工的最早時間。ndi一Ji的完工期限。nCi一Ji的完工時間, Ciri(wij+ pij) = ri+Wi+Pi.nCmax最長完工時間, Cmaxmax Ci .12nFi一Ji的流程時間，即零件在車間的實際停留時間, FiCi-

6、 riWi+Pi.nFmax最長流程時間，F(xiàn)maxmax Fi .nLi零件的延遲時間Li= Ci- din當Li0 (正延遲)，說明Ji的實際完工時間超過了完工期限；當Li0(負延遲)，說明Ji提前完工；當Li0(零延遲)，Ji按期完工。nLmax最長延遲時間，Lmaxmax Li .4.1.3 假設條件與符號說明（續(xù)）134.1.4 排序問題的分類和表示法按機器單機排序問題和多機排序問題w多機：單件作業(yè)排序與流水作業(yè)排序按工件到達情況n靜態(tài)和動態(tài)按目標函數(shù)n單目標排序問題和多目標排序問題14按參數(shù)的性質按參數(shù)的性質 確定型排序問題確定型排序問題（加工時間和其他有關參數(shù)是已知的確定量） 隨機

7、型排序問題隨機型排序問題（加工時間和有關參數(shù)為隨機變量）四參數(shù)表示法（康韋（四參數(shù)表示法（康韋（Conway）：）： n/m/A/B 其中，其中，n為零件數(shù)，為零件數(shù)，m為機器數(shù)，為機器數(shù)，A為車間類型，若標以為車間類型，若標以F，則代，則代表流水作業(yè)排序問題，若標以表流水作業(yè)排序問題，若標以P，則代表流水作業(yè)排列排序問題，則代表流水作業(yè)排列排序問題，若標以若標以G，則表示一般單件作業(yè)排序問題。，則表示一般單件作業(yè)排序問題。B為目標函數(shù)，通常為目標函數(shù)，通常是使其值最小。是使其值最小。 例如：例如：n/3/P/Cmax表示表示n個零件經(jīng)個零件經(jīng)3臺機器加工的流水作業(yè)排列排臺機器加工的流水作業(yè)排

8、列排序問題，目標函數(shù)是使最長完工時間序問題，目標函數(shù)是使最長完工時間Cmax最短最短。154.2 流水作業(yè)排序問題流水車間(Flow shop):工件的加工路線都一致，典型的如流水線4.2.1 加工周期的計算 4.2.2 兩臺機器排序問題的最優(yōu)算法 4.2.3 一般n/m/p/Fmax排序問題的啟發(fā)式算法4.2.4 相同零件、不同移動方式下加工周期Work Center #1Work Center #2Output16n個不同的零件要按相同的加工路線經(jīng)過m臺機器加工，目標是使這批零件的加工周期最短-n/m/P/Fmax加工周期加工周期又稱為最長流程時間，它是從第一個零件在第一臺機器開始加工時起

9、，到最后一個零件在最后一臺機器上完成加工時為止所經(jīng)過的時間。假設所有零件的到達時間都為零（ri=0,i=1,2,n)，則Fmax等于排在末位加工的零件在車間的停留時間，也等于一批零件的最長完工時間Cmax4.2.1 加工周期的計算17設n個零件的加工順序為S=（S1，S2，,Sn），其中Si為排第i位加工的零件的代號。以CkSi表示零件Si在機器Mk上的完工時間，P Sik表示零件Si在Mk上的加工時間，k=1,2,m; i=1,2,n,則CkSi可按以下公式計算 C1Si= C1Si-1+ P Si1 CkSi=max C(k-1)Si, CkSi-1 + P Sik k=2,3,m;i=1

10、,2,n CmSn,即為最長流程時間Fmax184.2.1 加工周期的計算工件代號i 1 2 3 4 5 6Pi1 4 6 4 5 8 3Pi2 3 5 3 9 7 1Pi3 7 9 2 6 5 8Pi4 5 4 9 6 2 3 有一個6/4/P/Fmax問題，其加工時間如下表所示。當按順序 S=（1,4,6,3,5,2）加工時，求Fmax194.2.1 加工周期的計算工件代號i 1 4 6 3 5 2Pi1 4 5 3 4 8 6Pi2 3 9 1 3 7 5Pi3 7 6 8 2 5 9Pi4 5 6 3 9 2 44 9 12 16 24 307 18 19 22 31 3614 24

11、32 34 39 4819 30 35 44 46 5220對于n個零件經(jīng)過兩臺機器加工，要使加工周期最短的流水作業(yè)排序問題，即n/2/F/Fmax問題，約翰遜于1954年提出了一個最優(yōu)算法，即著名的Johnson算法。為敘述方便，以ai表示零件Ji在機器M1上的加工時間，以bi表示零件Ji在機器M2上的加工時間，每個零件都按M1 M2的路線加工。4.2.2 兩臺機器排序問題的最優(yōu)算法214.2.2 兩臺機器排序問題的最優(yōu)算法約翰遜法則n如果Min(ai, bj) pim 則按pim不增的順序排成一個序列Sb;n3. 順序（Sa,C,Sb）即為所求順序。284.2.3 多臺機器排序問題的 啟發(fā)

12、式算法（續(xù)） 舉例工件i 1 2 3 4Pi1 2 1 6 3Pi2 4 8 2 9Pi3 5 4 8 211 13 16 14CSa (2,1)Sb(4)所求順序：（2,1,3,4）29Palmer（帕爾默）法1965年，帕爾默（D.S. Palmer) 對流水作業(yè)排序問題提出了按斜度指標排列工件的啟發(fā)式算法，該算法先定義工件的斜度指標，然后將各工件按其斜度指標不增進行排序。零件的斜度指標可按下式計算：1(),1,2,. .21ikmmikP knkl+=-=式中，m為機器數(shù)，Pik為零件i在機器Mk上的加工時間。按照各零件 不增的順序排列零件，可得出令人滿意的加工順序。il30例3：有一個

13、4/3/F/Fmax問題，其加工時間如下表所示，試用Palmer法求解。工件i 1 2 3 4Pi1 1 2 6 3Pi2 8 4 2 9Pi3 4 5 8 231CDS法坎貝爾（Campbell）、杜德克（Dudek）、史密斯（Smith）三人提出了一個啟發(fā)式算法，簡稱CDS法。他們把Johnson算法用于一般的n/m/F/Fmax問題，得到（m-1）個加工順序，取其中的優(yōu)者。 具體的做法是：對加工時間,1,2,.,1;11iklmpikp lmkkml根據(jù)Johnson算法可以求得一個排序，共可得到m-1個排序，從中選優(yōu)。=-邋=+ -注：當 取不同值，對每一組值，看成是分別在兩個機器上的

14、加工時間。l324.3 單件車間作業(yè)計劃問題4.3.1 任務分配問題4.3.2 排序問題的描述4.3.3 兩種作業(yè)計劃的構成4.3.4 求解一般n/m/G/Fmax問題的啟發(fā)式方法334.3.1 任務分配問題把n項任務分給n臺機器加工，有n!方案匈牙利算法n(1)從加工時間(費用)矩陣每一行所有元素減去該行最小的元素，使每行至少出現(xiàn)一個零元素。n(2)從實施第(1)步得到的矩陣中的每一列所有元素減去該列最小的元素，使每列至少出現(xiàn)一個零元素。n(3)從實施第(2)步得到的矩陣中，劃出能覆蓋盡可能多的零元素的直線，如果線條數(shù)等于矩陣的行數(shù)，則已找到最優(yōu)矩陣，轉第(6)步；否則，轉第(4)步。n(4

15、)從矩陣中未被線條穿過的元素中減去這些元素中的最小數(shù)，并將這個最小數(shù)加到直線交叉的元素上，其余元素不變。n(5)重復步驟(3)和步驟(4)，直到獲得最優(yōu)矩陣。n（6）從僅有一個零的行或列開始，找出零元素對應的分配方案，每行和每列僅能確定一個元素，最后使每行和每列都有一個零元素。零元素對應的就是最優(yōu)分配方案。例例4-3-1有如下任務分配問題有如下任務分配問題:34求解過程如下表所示：求解過程如下表所示：3536 e零件零件1由機器由機器M3加工，零件加工，零件2由機器由機器M2加工，加工，零件零件3由機器由機器M4加工，零件加工，零件4由機器由機器M1加工，加工，可使總加工時間最少。可使總加工時

16、間最少。3738對于一般單件作業(yè)排序問題，要描述一道工序，要用三個參數(shù)：i,j,和k。i表示工件的代號，j表示工序，k表示完成工件i的第j道工序的機器的代號。用（i,j,k）表示工件i的第j道工序是在機器k上進行加工的。于是可以用加工描述矩陣的形式來描述所有工件的加工。4.3.2 單件作業(yè)排序問題的描述394.3.2 單件作業(yè)排序問題的描述D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2T=2 4 13 4 5加工描述矩陣D和加工時間矩陣T對應40兩種作業(yè)計劃的構成兩種作業(yè)計劃的構成半能動作業(yè)計劃：半能動作業(yè)計劃：各工序都按最早可能開（完）工時間安排的作業(yè)計劃；能動作業(yè)

17、計劃能動作業(yè)計劃：任何一臺機器的每段空閑時間都不足以加工一道可加工工序的半能動作業(yè)計劃；無延遲作業(yè)計劃無延遲作業(yè)計劃：沒有任何延遲出現(xiàn)的能動作業(yè)計劃。延遲：延遲：指有工件等待加工時，機器出現(xiàn)空閑，既使這段空閑時間不足以完成一道工序。4.3.3一般n/m/G/Fmax問題的啟發(fā)式算法414.3.3 兩種作業(yè)計劃的構成（續(xù)）符號說明n每安排一道工序稱為一“步”nSt:t步之前已排序工序構成的部分作業(yè)計劃；nOt:t步可排序工序的集合；nTk為Ot中工序Ok的最早可能開始時間；nTk為Ot中工序Ok的最早可能完成時間。424.3.3 兩種作業(yè)計劃的構成（續(xù)）能動作業(yè)計劃的構成步驟n（1）設t=1,S

18、1為空集，O1為各工件第一道工序的集合。n（2）求T* = minTk,并求出T*所出現(xiàn)的機器M*。如果M*有多臺，則任選一臺。n（3）從Ot中選出滿足以下兩個條件的工序Oj：需要M*加工，且Tj T* 。n（4）將選定的工序Oj放入St,從Ot中消去Oj,并將Oj的緊后工序放入Ot ，使t=t+1.n（5）若還有未安排的工序，轉步驟（2）；否則，停止。43能動作業(yè)計劃的構成tOtTkTkT*M*Oj11,1,12,1,300232M11,1,121,2,32,1,320633M32,1,331,2,32,2,133777M3M11,2,341,3,22,2,173877M12,2,151,3

19、,22,3,2778128M21,3,262,3,281313M22,3,244能動作業(yè)計劃的甘特圖2,3,21,1,1 2,2,11,3,22,1,3 1,2,3 3 7 7 8 13 2 3 70時間時間機器 M1M2M3454.3.3 兩種作業(yè)計劃的構成（續(xù)）無延遲作業(yè)計劃的構成無延遲作業(yè)計劃的構成n（1）設t=1,S1為空集，O1為各工件第一道工序的集合。n（2）求T* = minTk,并求出T*所出現(xiàn)的機器M*。如果M*有多臺，則任選一臺。n（3）從Ot中選出滿足以下兩個條件的工序Oj：需要M*加工，且Tj=T* 。n（4）將選定的工序Oj放入St,從Ot中消去Oj,并將Oj的緊后工

20、序放入Ot ，使t=t+1.n（5）若還有未安排的工序，轉步驟（2）；否則，停止。46無延遲作業(yè)計劃的構成tOtTkTkT*M*Oj11,1,12,1,3002300M1M31,1,121,2,32,1,320630M32,1,331,2,32,2,1337733M3M11,2,341,3,22,2,173873M12,2,151,3,22,3,27781277M2M22,3,261,3,2121312M21,3,247無延遲作業(yè)計劃的甘特圖2,3,21,1,1 2,2,12,1,3 1,2,3 3 7 7 12 2 3 70時間時間機器 M1M2M31,3,2484.3.4 三類啟發(fā)式算法（

21、1）優(yōu)先調度法則n構成兩種作業(yè)計劃的第（3）步一般都有多道工序可以滿足，按不同的優(yōu)先調度法則來選擇工序，可以得出滿足不同目標函數(shù)的作業(yè)計劃n更能符合計劃編制者的要求n計算量小n已經(jīng)提出100多種優(yōu)先調度法則49優(yōu)先調度法則nFCFS（first come, first served）優(yōu)先選擇最早進入可排序集合的工序nSPT( shortest processing time）優(yōu)先選擇加工時間最短的工序nEDD（earliest due date）優(yōu)先選擇完工期限緊的工序nSCR(smallest critical ratio)選擇臨界比最小的工件（臨界比：工件允許停留時間與工件余下加工時間之比

22、）nMWKR(most work remaining)優(yōu)先選擇余下加工時間最長的工件nLWKR(least work remaining)優(yōu)先選擇余下加工時間最短的工件nMOPNR(most operations remaining)優(yōu)先選擇余下工序數(shù)最多的工件50按SPT法則，可使工件的平均流程時間最短，從而減少在制品庫存量；FCFS法則來自排隊論，它對工件較公平；EDD法則可使工件最大延誤時間最??；SCR法則也是保證工件延誤最小的法則；MWKR與MOPNR法則類似使不同工作量的工件的完工時間盡量接近；LWKR法則使工作量小的工件盡快完成；nRANDOM 隨機挑選一個工件51在應用優(yōu)先調度法

23、則時，只要將構成能動作業(yè)計劃的第3步修改為： 對Ot中需要M*加工，且TjT* 的工序，按預定的優(yōu)先調度法則確定一個進入St的工序。對于構成無延遲作業(yè)計劃的第3步修改為：對Ot中需要M*加工，且Tj=T* 的工序，按預定的優(yōu)先調度法則確定一個進入St的工序。一般來說，以構成無延遲作業(yè)計劃的步驟為基礎的啟發(fā)式算法比以構成能動作業(yè)計劃的步驟為基礎的啟發(fā)算法的效果要好。有時應用一個優(yōu)先法則還不能惟一地確定一道應挑選的工序，需要多個優(yōu)先調度法則的有序組合。譬如， SPT+MWKR+RANDOM524.3.3 三類啟發(fā)式算法（續(xù)）（2）隨機抽樣法n從全部能動計劃或無延遲計劃中隨機抽樣，得出多個作業(yè)計劃，

24、從中取優(yōu)。n介于兩個極端之間n效果與樣本大小和母體有關n比用優(yōu)先調度法則得到的結果一般要好一些，但計算量要大一些n從無延遲作業(yè)計劃母體抽樣所得到的結果比從能動作業(yè)計劃母體中抽樣所得到的結果要好（3）概率調度法n將優(yōu)先調度法則與隨機抽樣法結合n對不同工件按優(yōu)先調度法則分配不同的挑選概率，效果較好534.4 生產(chǎn)作業(yè)控制4.4.1 實行生產(chǎn)作業(yè)控制的原因和條件4.4.2 不同生產(chǎn)類型生產(chǎn)控制的特點4.4.3 利用“漏斗模型”進行生產(chǎn)控制544.4.1 實行生產(chǎn)作業(yè)控制的原因和條件原因n加工時間估計不準確n隨機因素的影響n加工路線的多樣性n企業(yè)環(huán)境的動態(tài)性條件n要有控制標準n取得實際進度偏離計劃的信

25、息n能夠采取糾正行動55生產(chǎn)作業(yè)控制的程序 制定生產(chǎn)作業(yè)監(jiān)控體系 監(jiān)控實際生產(chǎn)過程 評估偏差情況 采取糾偏措施56生產(chǎn)作業(yè)控制的功能 為每個車間的工單指派優(yōu)先級 維護車間在制品數(shù)量 將車間工單信息傳送到相應辦公室 提供實際產(chǎn)出數(shù)據(jù)來為能力控制服務 根據(jù)車間工單對機位的要求，為在制品庫存管理提供數(shù)量信息 測量人員和設備的效率、利用率和產(chǎn)量。574.4.2 不同生產(chǎn)類型生產(chǎn)控制的特點特點單件小批生產(chǎn)大量大批生產(chǎn)零件的流動瓶頸設備調整準備費用工人操作工人工作的范圍工作節(jié)奏的控制在制品庫存產(chǎn)品庫存供應商作業(yè)計劃編制沒有主要的流動路線經(jīng)常變動通用設備，有柔性低多寬工人自己和工長高很少經(jīng)常變化不確定性高，

26、變化大單一的流動路線穩(wěn)定高效專用設備高少窄由機器和工藝過程低較高穩(wěn)定不確定性低，變化小不同生產(chǎn)類型的特點不同生產(chǎn)類型的特點584.4.2 不同生產(chǎn)類型生產(chǎn)控制的特點（續(xù)）單件小批生產(chǎn)，排隊時間是主要的，通過輸入/輸出控制排隊隊長大量大批生產(chǎn)，控制問題較簡單，主要是調整工作班次、工作時間和工人數(shù)量移動 時間排隊 時間調整準備時間加工 時間待運 時間零件加工提前期的構成59生產(chǎn)作業(yè)控制的主要工具n 實際生產(chǎn)中，有不少工具可以用來進行生產(chǎn)作業(yè)控制，這些工具容易通過運用適當?shù)能浖砩?，主要包括?調度單 日報、月報 例外報告、異常報告 輸入/輸出（Input/output control，I/O）報

27、告604.4.3 利用“漏斗模型”進行生產(chǎn)控制德國漢諾威大學的貝克特（Bechte）和溫道爾（Wiendall）等人于20世紀80年代初在實施輸入/輸出控制時提出了漏斗模型（Funnel Model）。漏斗模型的基本原則：工作中心的輸入永遠不能超過工作中心的輸出。當工作中心的輸入超過輸出，就會拖欠訂單，結果將會出現(xiàn)作業(yè)推遲、客戶不滿、下游作業(yè)或相關作業(yè)的延期。61在制品在制品到達的任務到達的任務計劃能力計劃能力實際能力實際能力完成的任務完成的任務62注：曲線圖的垂直段表示某天到達或完成的一個或多個工件之間所包含的工作量；水平段表示相鄰兩個到達或完成的任務之間的時間間隔。如果運輸時間不變，輸入曲

28、線與上道工序的輸出曲線相對應。634.4.3 利用“漏斗模型”進行生產(chǎn)控制(續(xù))在一段較長的時間內(nèi)（如數(shù)周）內(nèi)，若工況穩(wěn)定，輸入輸出兩條曲線可以近似地用兩條直線來表示，其斜率（平均生產(chǎn)率）等于平均在制品庫存/平均通過時間實際實踐中，可以采用四個規(guī)則來調整輸入、輸出、在制品庫存和通過時間：n若希望保持在制品庫存穩(wěn)定，就要使單位時間內(nèi)的平均輸入等于平均輸出。n若希望改變在制品庫存量，可暫時增加或減少輸入。n若希望平均通過時間在所控制的范圍內(nèi)，則適當調整平均在制品庫存與生產(chǎn)率的比例。n要使各個工件的平均通過時間穩(wěn)定，可以采用FIFO規(guī)則來安排各工件的加工順序。漏斗模型適合于多品種中小批量生產(chǎn)系統(tǒng)的控制。64本章習題：思考題： 1、作業(yè)計劃解決什么問題？請舉例說明。 2、排序、編制作業(yè)計劃、派工、趕工、調度、控制等術語的含義及其相互關系。 3、解釋加工路線和加工順序。 4、說明能動作業(yè)計劃和無延遲作業(yè)計劃的關系。 5、漏斗模型的基本原理是什么？它在生產(chǎn)控制中的用途如何？65判斷題：1.排序是指安排工件在機器上的加工順序。排序是指安排工件在機器上的加工順序。2.按照按照JohnsonJohnson法則可得到多個加工順序，則應從中取最法則可得到多個加工順序，則應從中取最優(yōu)者。優(yōu)者。3.3.派工屬于通常所說的調度范圍。派工屬于通常所說的調度范圍。4 4