生產(chǎn)運作管理作業(yè)計劃與控制課件

1、1 制造業(yè)作業(yè)計劃與控制Scheduling and Controlling for Manufacturing211.1 作業(yè)計劃問題的基本概念11.2 流水車間作業(yè)計劃問題11.3 單件車間作業(yè)計劃問題11.4 生產(chǎn)作業(yè)控制 311.1作業(yè)計劃問題的基本概念11.1.1 編制作業(yè)計劃要解決的問題11.1.2 有關的名詞術語11.1.3 假設條件與符號說明11.1.4 排序問題的分類和表示法4 物料需求計劃（物料需求計劃（MRP）與與 能力需求計劃（能力需求計劃（CRP）的關系的關系物料需求計劃：物料需求計劃： 對象：物料物料物料1物料2物料3 能力需求計劃能力需求計劃：對象：工作中心工作中

2、心工藝路線1工作中心1工序10工作中心2工序20工作中心4工序30工藝路線2工序10工序20工藝路線3工序10工序40工作中心3工序30工序20 054511.1.1編制作業(yè)計劃要解決的問題 Scheduling-編制作業(yè)計劃，排程，安排日程計劃 編制作業(yè)計劃實質(zhì)上是要將資源分配給不同的任務，按照既定的優(yōu)化目標，確定各種資源利用的時間問題。 由于每臺機器都可能被分配了多項任務，而這些任務受到加工路線的約束，就帶來了零件在機器上加工的順序問題。6能力需求計劃能力需求計劃 邏輯流程圖邏輯流程圖加工任務加工任務計劃/確認/下達定單工藝路線工藝路線能力需求計劃能力需求計劃工作中心工作中心 能力能力需用

3、需用能力能力可用可用能力能力需用需用負荷負荷工作中心平均能力小時時段(日期）1. 多少負荷？2. 需用能力？3. 可用能力？4. 平衡負荷/能力。平衡負荷未結(jié)定單計劃定單 0557 11.1.2 有關的名詞術語 編制作業(yè)計劃或日程安排(Scheduling) 排序(Sequencing) 派工(Dispatching) 控制(Controlling) 趕工(Expediting) “調(diào)度”是作業(yè)計劃編制后實施生產(chǎn)控制所采取的一切行動，“編制作業(yè)計劃”是加工制造發(fā)生之前的活動811.1.2有關的名詞術語（續(xù)） “機器”，表示“服務者”.可以是工廠里的各種機床，也可以是維修工人；可以是輪船要停靠的

4、碼頭，也可以是電子的計算機中央處理單元、存貯器和輸入、輸出單元。 “零件”代表“服務對象”。零件可以是單個零件，也可以是一批相同的零件 “加工路線”是零件加工的工藝過程決定的，它是零件加工在技術上的約束 “加工順序”則表示每臺機器加工n個零件的先后順序，是排序和編制作業(yè)計劃要解決的問題911.1.3 假設條件與符號說明v假設條件一個零件不能同時在幾臺不同的機器上加工。零件在加工過程中采取平行移動方式，即當上一道工序完工 后，立即送下道工序加工。不允許中斷。當一個零件一旦開始加工，必須一直進行到完 工，不得中途停止插入其它零件。每道工序只在一臺機器上完成。零件數(shù)、機器數(shù)和加工時間已知。每臺機器同

5、時只能加工一個零件。 1011.1.4 排序問題的分類和表示法v 按機器 單機和多機 多機：單件作業(yè)車間與流水作業(yè)車間排序 專用機與平行機v 按工件到達情況 靜態(tài)和動態(tài)v 按目標函數(shù) n/m/A/B,n為工件數(shù)，m機器數(shù)，A作業(yè)車間類型，B為目標函數(shù)112基于性能指標 Make-span最少，生產(chǎn)成本低，脫期小，等 3調(diào)度環(huán)境 靜態(tài)調(diào)度和動態(tài)調(diào)度 4考慮不確定性因素 自適應確定性調(diào)度和不確定性的調(diào)度生產(chǎn)調(diào)度問題的分類生產(chǎn)調(diào)度問題的分類1離散型制造調(diào)度單機、多機并行、Flow-shop、Job-shop和Open-shop121基于經(jīng)濟的調(diào)度目標主要：產(chǎn)費用最小 ，利潤最大，庫存費用最少 等2最

6、大能力指標：包括最大生產(chǎn)率、最短的生產(chǎn)周期等 3客戶滿意度指標：包括最短的延遲，最小提前或者拖后懲罰，平均延遲時間小等 1311.2 流水作業(yè)排序問題v 流水車間(Flow shop):工件的加工路線都一致，典型的如流水線11.2.1 加工周期的計算 11.2.2 兩臺機器排序問題的最優(yōu)算法 11.2.3 一般n/m/p/Fmax排序問題的啟發(fā)式算法11.2.4 相同零件、不同移動方式下加工周期AABB14 FSSPFSSP一般可以描述為:v n個工件在m臺機器上加工，v 每個工件需要經(jīng)過m道工序, v 每道工序要求不同的機器, v n個工件在m臺機器上的加工順序相同加工順序相同，v 不妨設所

7、有產(chǎn)品依次通過 臺設備才能完成加工任務，工件沒有先后次序的限制。為了簡化問題，該類調(diào)度的理論研究中通常使用一下假設:Flowshop調(diào)度調(diào)度m,2,12.每個機器在同一時刻只能加工一個工件 3.3.工件的各個工序工件的各個工序加工時間始終為非加工時間始終為非零定值，不因操作零定值，不因操作人員的不同而不同人員的不同而不同 4.每個工件在每臺機器上只能加工一次 6.各種導致生產(chǎn)的意外不作考慮，并且不考慮機器的準備時間 153個工件在三臺機器上加工時間如下矩陣所示：（三個人在三個窗口上接受服務） 矩陣的列表示工件，行表示機器 調(diào)度順序有：3 1 2，3 2 1，1 3 2，1 2 3，2 1 3，

8、2 3 1 6種， 調(diào)度的GATT圖如下：6826119815T16301813214381412323431420123 25234423 1 2調(diào)度的GATT 圖123PMPT05101520253035406826119815T17201114211231812732693123PMPT05101520253020212129272 3 1調(diào)度的GATT 圖6826119815T18單件車間 排序問題v 單件車間(Job shop):工件的加工路線不一致BBAA19 JSSP JSSP一般可描述為： vn個工件需要在m臺機器上加工，v 每個工件有其特定的加工工序，v 每道工序要求不同的機

9、器，每道工序加工時間己知，v 工件沒有先后次序的限制。Jobshop調(diào)度調(diào)度2.每個機器在同一時刻只能加工一個工件 3.3.工件的各個工序工件的各個工序加工時間始終為非加工時間始終為非零定值，不因操作零定值，不因操作人員的不同而不同人員的不同而不同 4.每個工件在每臺機器上只能加工一次 6.各種導致生產(chǎn)的意外不作考慮，并且不考慮機器的準備時間 203個工件在三臺機器上加工（三個人在三個窗口上接受服務） 調(diào)度順序有：3 1 3 2 1 2 3 2 1 等362880種方案,當工件為5，機器為5時，存在的調(diào)度方案是3300， 調(diào)度的GATT圖如下：6688111295T322213131GX213

10、 03 16 01 2 72 20 9 3411 9 101PM12305101520253035PT322213131GX223 2 1032 20 2623 1 3 2 1 2 3 2 1調(diào)度的GATT 圖6688111295T22 03210510152025PMPT132 2 7 9 20321 10 20 26 18213 0 9 10 16 23,2,1,1,3,1,3,2,2 的GATT 圖23Flowshop模型： 故makespan為 ， 上式中 是工件 j在機器 i上的加工時間。) 1 , 1 () 1 , 1 (pC), 1 () 1, 1 (), 1 (jpjCjC)

11、1 ,() 1 , 1() 1 ,(tpiCiC),(), 1(),1,(max),(jipjiCjiCjiC),(maxnmCC),(jip24Jobshop模型： 故makespan為 ，上式中 是工件 j在機器 i上的加工時間。),(jip) 1 ,() 1 ,() 1 , 1 (111)1(11pTOCCp),(),(),1, 1 (max), 1 (1)1(1jpTjOCjCjCjjpj)1 ,()1 ,()1 ,(11)1(1ippTOCiCi),(),(),1,(max), () 1(jpTjOCjOCjiCijjpjptjtj),(maxmax11maxniCCnjmi25調(diào)度

12、系統(tǒng)的研究調(diào)度系統(tǒng)的研究 并行機調(diào)度的研究并行機調(diào)度的研究 大規(guī)模復雜調(diào)度問題的研究大規(guī)模復雜調(diào)度問題的研究 動態(tài)適時調(diào)度的研究動態(tài)適時調(diào)度的研究 其它更加復雜的調(diào)度研制開發(fā)應用于實際的調(diào)度軟件研制開發(fā)應用于實際的調(diào)度軟件 算法性能的提高及理論的研究算法性能的提高及理論的研究 2611.1.3 假設條件與符號說明（續(xù)）v 用康韋（Conway）提出的方法來表示。v 表示大多數(shù)不同的排序問題 n n/m/A/B/m/A/B n n為為零件數(shù)零件數(shù)， m m為為機器數(shù)機器數(shù)。 A A為為車間類型車間類型(F(F表示表示flow shop flow shop 流水作業(yè)排序問題。流水作業(yè)排序問題。P

13、P表示表示job job shopshop流水作業(yè)排列排序問題流水作業(yè)排列排序問題) ) B B為為目標函數(shù)目標函數(shù)27 Fi一Ji的流程時間，即零件在車間的實際停留時間, FiCi- riWi+Pi. Fmax最長流程時間，F(xiàn)maxmax Fi . Li零件的延遲時間 當Li0 (正延遲)，說明Ji的實際完工時間超過了完工期限；當Li0(負延遲)，說明Ji提前完工；當Li0(零延遲)，Ji按期完工。 Lmax最長延遲時間，Lmaxmax Li . Ji一零件i，i1,2,n。 Mj機器j，j1,2,m。 pij一Ji在Mj上的加工時間，Ji的總加工時間為Pipij ri一Ji的到達時間，指J

14、i從外部進入車間，可以開始加工的最早時間。 di一Ji的完工期限。 Ci一Ji的完工時間, Ciri(wij+ pij) = ri+Wi+Pi. Cmax最長完工時間, Cmaxmax Ci .2811.2 流水作業(yè)排序問題v 流水車間(Flow shop):工件的加工路線都一致，典型的如流水線11.2.1 加工周期的計算 11.2.2 兩臺機器排序問題的最優(yōu)算法 11.2.3 一般n/m/p/Fmax排序問題的啟發(fā)式算法11.2.4 相同零件、不同移動方式下加工周期Work Center #1Work Center #2Output2911.2.1 加工周期的計算工件代號i 1 4 6 3

15、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 32 34 39 4819 30 35 44 46 52P291 例11-1I 1 2 3 4 5 6Pi1 4 6 4 5 8 3Pi2 3 5 3 9 7 13011.2.2 兩臺機器排序問題的 最優(yōu)算法v 約翰森法則 如果Min(ai, bj) pim 則按pim不增的順序排成一個序列Sb; 3. 順序（Sa,C,Sb）即為所求順序。3511.2.3 多臺機器排序問題的 啟發(fā)式算法（續(xù)） 舉

16、例工件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）3611.2.4 相同零件不同移動方式下 加工周期的計算v當n個零件相同， 則無排序問題。但不同移動方式下的加工周期不同v三種典型的移動方式 順序移動方式：一批零件全部加工完成后，整批移動到下道工序加工 平行移動方式：單個零件加工完成后，立即移動到下道工序加工 平行順序移動方式：兩者混合37順序移動方式 加工周期時間工序 1 2 3 4順序移動方式順序移動方式itititit38 設零件批量為n（件），工序數(shù)目為m，一批零件不計

17、算工序間運輸時間，只考慮加工時間，設其加工的周期為T（分鐘），零件在i道工序的單件工時為（分鐘/件），i=1.2n. 則該批零件的加工周期為： it121.mimiTntntntnt順序移動方式（續(xù)）39平行移動方式工序 1 2 34時間 加工周期itititititititit40平行移動方式（續(xù)）零件平行移動的加工周期 為： T平12111.(1)mmiiTttntnttnt平41平行順序移動方式 特點：既保持一批零件順序加工，有盡可能使相鄰工序加工時間平行進行。如圖所示： 時間工序1234 加工 周期42平行順序移動方式（續(xù)）平行順序移動加工周期計算 111(1)mmiiiiTtnt平

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

19、線條穿過的元素中減去這些元素中的最小數(shù)，并將這個最小數(shù)加到直線交叉的元素上，其余元素不變。(5)重復步驟(3)和步驟(4)，直到獲得最優(yōu)矩陣。(6)從僅有一個零的行或列開始，找出零元素對應的分配方案，每行和每列僅能確定一個元素，最后使每行和每列都有一個零元素。零元素對應的就是最優(yōu)分配方案。4511.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對應4611.3.3 兩種作業(yè)計劃的構成v符號說明 每安排一道工序稱為一“步” St:t步之前已排序工序構成的部分作業(yè)計劃； Ot:t步可排序工

20、序的集合； Tk為Ot中工序Ok的最早可能開始時間； Tk為Ot中工序Ok的最早可能完成時間。4711.3.3 兩種作業(yè)計劃的構成（續(xù)）v 能動作業(yè)計劃的構成（1）設t=1,S1為空集，O1為各工件第一道工序的集合。（2）求T* = minTk,并求出T*所出現(xiàn)的機器M*。如果M*有多臺 則任選一臺。（3）從Ot中選出滿足以下兩個條件的工序Oj：需要M*加工， 且Tj T* 。（4）將選定的工序Oj放入St,從Ot中消去Oj,并將Oj的緊后工 序放入Ot ，使t=t+1.（5）若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止。48能動作業(yè)計劃的構成tOtTkTkT*M*Oj11,1,12,1,30

21、0232M11,1,121,2,32,1,320633M32,1,331,2,32,2,133777M3M11,2,341,3,22,2,173877M12,2,151,3,22,3,2778128M21,3,262,3,281313M22,3,249能動作業(yè)計劃的甘特圖2,3,21,1,1 2,2,11,3,22,1,3 1,2,3 3 7 7 8 13 2 3 70時間時間機器 M1M2M35011.3.3 兩種作業(yè)計劃的構成（續(xù)）v 無延遲作業(yè)計劃的構成（1）設t=1,S1為空集，O1為各工件第一道工序的集合。（2）求T* = minTk,并求出T*所出現(xiàn)的機器M*。如果M*有多臺， 則

22、任選一臺。（3）從Ot中選出滿足以下兩個條件的工序Oj：需要M*加工， 且Tj=T* 。（4）將選定的工序Oj放入St,從Ot中消去Oj,并將Oj的緊后工 序放入Ot ，使t=t+1.（5）若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止。51無延遲作業(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,252無延遲作業(yè)計劃的甘特圖

23、2,3,21,1,1 2,2,12,1,3 1,2,3 3 7 7 12 13 2 3 70時間時間機器 M1M2M31,3,25311.3.4 三類啟發(fā)式算法v（1）優(yōu)先調(diào)度法則 構成兩種作業(yè)計劃的第（3）步一般都有多道工序可以滿足，按不同的優(yōu)先調(diào)度法則來選擇工序，可以得出滿足不同目標函數(shù)的作業(yè)計劃 計算量小 已經(jīng)提出100多種優(yōu)先調(diào)度法則54v 優(yōu)先調(diào)度法則 FCFS（first come, first served）選擇最早進入可排序集合的工序 SPT( shortest processing time）選擇加工時間最短的工序 EDD（earliest due date）選擇完工期限最緊

24、的工序 SCR(smallest critical ratio)選擇臨界比最小的工件 MWKR(most work remaining)選擇余下加工時間最長的工件 LWKR(least work remaining)選擇余下加工時間最短的工件 MOPNR(most operations remaining)選擇余下工序數(shù)最多的工件 RANDOM 隨機挑選一個工件 RushTop Priority5511.3.3 三類啟發(fā)式算法（續(xù)）v（2）隨機抽樣法 從全部能動計劃或無延遲計劃中隨機抽樣，得出多個作業(yè)計劃，從中取優(yōu)。v（3）概率調(diào)度法 將優(yōu)先調(diào)度法則與隨機抽樣法結(jié)合 對不同工件將優(yōu)先調(diào)度法則分配不同的挑選概率，效果較好5611.4 生產(chǎn)作業(yè)控制11.4.1 實行生產(chǎn)作業(yè)控制的原因和條件11.4.2 不同生產(chǎn)類型生產(chǎn)控制的特點11.4.3 利用“漏斗模型”進行生產(chǎn)控制5711.4.1 實行生產(chǎn)作業(yè)控制的原因和條件v 原因 加工時間估計不準確 隨機因素的影響 加工路線的多樣性 企業(yè)環(huán)境的動態(tài)性v 條件 要有控制標準 取得實際進度偏離計劃的信息 能