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

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

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

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

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

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

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

7、有產(chǎn)品依次通過 臺(tái)設(shè)備才能完成加工任務(wù)，工件沒有先后次序的限制。為了簡(jiǎn)化問題，該類調(diào)度的理論研究中通常使用一下假設(shè):Flowshop調(diào)度調(diào)度m,2,12.每個(gè)機(jī)器在同一時(shí)刻只能加工一個(gè)工件 3.3.工件的各個(gè)工序工件的各個(gè)工序加工時(shí)間始終為非加工時(shí)間始終為非零定值，不因操作零定值，不因操作人員的不同而不同人員的不同而不同 4.每個(gè)工件在每臺(tái)機(jī)器上只能加工一次 6.各種導(dǎo)致生產(chǎn)的意外不作考慮，并且不考慮機(jī)器的準(zhǔn)備時(shí)間 153個(gè)工件在三臺(tái)機(jī)器上加工時(shí)間如下矩陣所示：（三個(gè)人在三個(gè)窗口上接受服務(wù)） 矩陣的列表示工件，行表示機(jī)器 調(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個(gè)工件需要在m臺(tái)機(jī)器上加工，v 每個(gè)工件有其特定的加工工序，v 每道工序要求不同的機(jī)

9、器，每道工序加工時(shí)間己知，v 工件沒有先后次序的限制。Jobshop調(diào)度調(diào)度2.每個(gè)機(jī)器在同一時(shí)刻只能加工一個(gè)工件 3.3.工件的各個(gè)工序工件的各個(gè)工序加工時(shí)間始終為非加工時(shí)間始終為非零定值，不因操作零定值，不因操作人員的不同而不同人員的不同而不同 4.每個(gè)工件在每臺(tái)機(jī)器上只能加工一次 6.各種導(dǎo)致生產(chǎn)的意外不作考慮，并且不考慮機(jī)器的準(zhǔn)備時(shí)間 203個(gè)工件在三臺(tái)機(jī)器上加工（三個(gè)人在三個(gè)窗口上接受服務(wù)） 調(diào)度順序有：3 1 3 2 1 2 3 2 1 等362880種方案,當(dāng)工件為5，機(jī)器為5時(shí)，存在的調(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在機(jī)器 i上的加工時(shí)間。) 1 , 1 () 1 , 1 (pC), 1 () 1, 1 (), 1 (jpjCjC)

11、1 ,() 1 , 1() 1 ,(tpiCiC),(), 1(),1,(max),(jipjiCjiCjiC),(maxnmCC),(jip24Jobshop模型： 故makespan為 ，上式中 是工件 j在機(jī)器 i上的加工時(shí)間。),(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)的研究 并行機(jī)調(diào)度的研究并行機(jī)調(diào)度的研究 大規(guī)模復(fù)雜調(diào)度問題的研究大規(guī)模復(fù)雜調(diào)度問題的研究 動(dòng)態(tài)適時(shí)調(diào)度的研究動(dòng)態(tài)適時(shí)調(diào)度的研究 其它更加復(fù)雜的調(diào)度研制開發(fā)應(yīng)用于實(shí)際的調(diào)度軟件研制開發(fā)應(yīng)用于實(shí)際的調(diào)度軟件 算法性能的提高及理論的研究算法性能的提高及理論的研究 2611.1.3 假設(shè)條件與符號(hào)說明（續(xù)）v 用康韋（Conway）提出的方法來表示。v 表示大多數(shù)不同的排序問題 n n/m/A/B/m/A/B n n為為零件數(shù)零件數(shù)， m m為為機(jī)器數(shù)機(jī)器數(shù)。 A A為為車間類型車間類型(F(F表示表示flow shop flow shop 流水作業(yè)排序問題。流水作業(yè)排序問題。P

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

14、i從外部進(jìn)入車間，可以開始加工的最早時(shí)間。 di一Ji的完工期限。 Ci一Ji的完工時(shí)間, Ciri(wij+ pij) = ri+Wi+Pi. Cmax最長(zhǎng)完工時(shí)間, Cmaxmax Ci .2811.2 流水作業(yè)排序問題v 流水車間(Flow shop):工件的加工路線都一致，典型的如流水線11.2.1 加工周期的計(jì)算 11.2.2 兩臺(tái)機(jī)器排序問題的最優(yōu)算法 11.2.3 一般n/m/p/Fmax排序問題的啟發(fā)式算法11.2.4 相同零件、不同移動(dòng)方式下加工周期Work Center #1Work Center #2Output2911.2.1 加工周期的計(jì)算工件代號(hào)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 兩臺(tái)機(jī)器排序問題的 最優(yōu)算法v 約翰森法則 如果Min(ai, bj) pim 則按pim不增的順序排成一個(gè)序列Sb; 3. 順序（Sa,C,Sb）即為所求順序。3511.2.3 多臺(tái)機(jī)器排序問題的 啟發(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 相同零件不同移動(dòng)方式下 加工周期的計(jì)算v當(dāng)n個(gè)零件相同， 則無排序問題。但不同移動(dòng)方式下的加工周期不同v三種典型的移動(dòng)方式 順序移動(dòng)方式：一批零件全部加工完成后，整批移動(dòng)到下道工序加工 平行移動(dòng)方式：?jiǎn)蝹€(gè)零件加工完成后，立即移動(dòng)到下道工序加工 平行順序移動(dòng)方式：兩者混合37順序移動(dòng)方式 加工周期時(shí)間工序 1 2 3 4順序移動(dòng)方式順序移動(dòng)方式itititit38 設(shè)零件批量為n（件），工序數(shù)目為m，一批零件不計(jì)

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

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

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

20、序的集合； Tk為Ot中工序Ok的最早可能開始時(shí)間； Tk為Ot中工序Ok的最早可能完成時(shí)間。4711.3.3 兩種作業(yè)計(jì)劃的構(gòu)成（續(xù)）v 能動(dòng)作業(yè)計(jì)劃的構(gòu)成（1）設(shè)t=1,S1為空集，O1為各工件第一道工序的集合。（2）求T* = minTk,并求出T*所出現(xiàn)的機(jī)器M*。如果M*有多臺(tái) 則任選一臺(tái)。（3）從Ot中選出滿足以下兩個(gè)條件的工序Oj：需要M*加工， 且Tj T* 。（4）將選定的工序Oj放入St,從Ot中消去Oj,并將Oj的緊后工 序放入Ot ，使t=t+1.（5）若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止。48能動(dòng)作業(yè)計(jì)劃的構(gòu)成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能動(dòng)作業(yè)計(jì)劃的甘特圖2,3,21,1,1 2,2,11,3,22,1,3 1,2,3 3 7 7 8 13 2 3 70時(shí)間時(shí)間機(jī)器 M1M2M35011.3.3 兩種作業(yè)計(jì)劃的構(gòu)成（續(xù)）v 無延遲作業(yè)計(jì)劃的構(gòu)成（1）設(shè)t=1,S1為空集，O1為各工件第一道工序的集合。（2）求T* = minTk,并求出T*所出現(xiàn)的機(jī)器M*。如果M*有多臺(tái)， 則

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

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

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