第十一章制造業(yè)作業(yè)計劃與控制

1《生產(chǎn)運作管理》第十一章制造業(yè)作業(yè)計劃與控制2引導(dǎo)案例-忙碌，不代表有效率某忙碌的制造企業(yè)的生產(chǎn)準備會議史黛西（生產(chǎn)主管）坐在會議桌旁，前面堆了一大堆文件，她手上拿著一張名單，似乎已經(jīng)準備好應(yīng)付圍攻。她說：“對，已經(jīng)查出來了。事實上，昨天晚上我一直忙著追蹤和查證這些資料。結(jié)果，我發(fā)現(xiàn)出問題的零件有三十種。”鐘納說：“你確定原材料都發(fā)出去了嗎？”“沒錯，”史黛西說，“他們已經(jīng)根據(jù)時間表，把原材料發(fā)出去了，但是在最后裝配部還看不到這些零件，零件卡在新瓶頸那里了?！薄暗纫坏?，你怎么知道那真的是瓶頸呢？”她說：“因為這些零件被耽擱了，我覺得一定是······”思考目前現(xiàn)狀大量（超過30種）零部件延遲，未按期交貨；可能設(shè)備生產(chǎn)能力出現(xiàn)瓶頸，但生產(chǎn)能力事先已知；生產(chǎn)過程存在一定的約束，包括人力、時間、設(shè)備等；基于一定的優(yōu)先策略，零部件的加工存在優(yōu)先順序；假定排除設(shè)備故障等意外情況發(fā)生，問題出在哪里？任務(wù)分配作業(yè)排序生產(chǎn)作業(yè)計劃與控制出了問題！生產(chǎn)作業(yè)計劃生產(chǎn)控制戰(zhàn)略管理文化管理項目及網(wǎng)絡(luò)計劃產(chǎn)品R&D

生產(chǎn)系統(tǒng)選址和布置BPRJIT、LN、OPT等先進生產(chǎn)方式質(zhì)量管理設(shè)備管理庫存管理市場分析需求預(yù)測訂單生產(chǎn)計劃MRP主要內(nèi)容作業(yè)計劃問題基本概念流水車間的作業(yè)計劃問題單件車間的作業(yè)計劃問題生產(chǎn)作業(yè)控制1作業(yè)計劃問題基本概念MRP->零部件投入出產(chǎn)計劃車間生產(chǎn)作業(yè)計劃；落實車間生產(chǎn)任務(wù)到班組、工作地、工人；涉及到任務(wù)分配和作業(yè)排序的問題。作業(yè)計劃問題任務(wù)分配、資源分配和作業(yè)排序約束編制作業(yè)計劃要解決的問題編制作業(yè)計劃要解決的問題任務(wù)分配：每個工人、每個工作地的日生產(chǎn)任務(wù)；生產(chǎn)排序：通過排序方法編制生產(chǎn)計劃，提高生產(chǎn)效率。作業(yè)計劃與作業(yè)排序是一回事么？否作業(yè)計劃與作業(yè)排序二者含義差別作業(yè)計劃是安排零部件的出產(chǎn)數(shù)量、設(shè)備及人工使用、投入時間及出產(chǎn)時間。分配資源給不同的任務(wù)，按照既定的優(yōu)化目標，確定各種資源利用的時間問題。排序，給出零部件在一臺或一組設(shè)備上加工的先后順序的工作。編制作業(yè)計劃與排序的概念和目的都是不同的。但是，編制作業(yè)計劃的主要工作之一就是要確定出最佳的作業(yè)順序。舉例-工藝專業(yè)化9鉆床倉庫車床壓床銑床銑床車床車床銑床銑床鉆床磨床焊接油漆磨床裝配裝配焊接焊接倉庫如何進行任務(wù)分配?很困難!舉例-產(chǎn)品專業(yè)化機器k-1機器k機器k-1機器k第一種情況第二種情況SiSi-1SiSi-1兩種零件不同在流水線上各機器的生產(chǎn)時間也不相同如何進行排序?很困難!根據(jù)排序規(guī)則對每一個到達的工件安排作業(yè)順序工作地工件排隊等待加工來自上游工作地的工件加工完畢的工件流向下一工作地排序的概念排序的概念(續(xù))生產(chǎn)作業(yè)排序就是指對于等候某個設(shè)備或工作中心加工的多個任務(wù)，確定這些任務(wù)加工的先后次序。目的：提高設(shè)備或工作中心的效率減少在制品占用量縮短生產(chǎn)周期保證按期交貨排序問題的分類排序問題分類按機器單臺機器排序問題多臺機器排序問題單件作業(yè)排序問題流水線作業(yè)排序問題按零件到達車間的情況靜態(tài)的排序問題動態(tài)的排序問題按目標函數(shù)的性質(zhì)分類按參數(shù)確定型排序問題隨機型排序問題單臺機器的排序問題n個工件全部經(jīng)由一臺機器處理J1J2J3Jn機器到達系統(tǒng)工件的集合離開系統(tǒng)（機器）

為實現(xiàn)任務(wù)總等待時間最短的目標，保證盡可能多的對象早日加工出來，加速資金周轉(zhuǎn)，只需根據(jù)最短加工時間準則對加工對象排序即可。n項任務(wù)在兩臺機器的排序問題n個工件都必須經(jīng)過機器1和機器2的加工，即工藝路線是一致的。

15機器1到達系統(tǒng)工件的集合離開系統(tǒng)（機器）J1J2J3Jn機器2作業(yè)計劃問題的相關(guān)概念若干名詞和概念排序、調(diào)度、派工、趕工、控制；機器：服務(wù)者；零件：服務(wù)對象；加工路線：由加工工藝過程決定（既定的）；加工順序：每臺機器加工N個零件的先后順序（是待解決的問題）。加工路線示意圖排序問題的參數(shù)表示方法返回目錄2流水車間的作業(yè)計劃問題流水車間的作業(yè)計劃問題問題的描述n個不同零件要按相同的加工路線經(jīng)過m臺機器加工，目標是使這批零件的加工周期最短（加工路線確定，對不同的零件，根據(jù)目標求各個零件的加工次序）問題的表示加工周期加工周期是指第一個零件在第一臺機器上開始加工到最后一個零件在最后一臺機器上完成加工為止，所需要的時間。假設(shè)n個零件的加工順序為S=(S1,S2……,Sn)

Si為排在i位加工的零件代號表示零件Si在機器Mk上的完工時間表示零件Si在Mk上的加工時間k=1,2,3,……,m，i=1,2,3,……,n加工周期的計算【例】有一個6/4/P/Fmax問題，其加工時間如表所示。當按順序S＝(6，1，5，2，4，3)加工時，求Fmax。加工周期的計算結(jié)果加工周期又稱為最長流程時間；若零件的到達時間都為0，加工周期等于排在末尾加工的零件在車間的停留時間，也等于一批零件的最長完工時間。2臺機器的排序問題求解算法描述和表示描述：n個零件經(jīng)過2臺機器加工，使加工周期最短的流水作業(yè)排序問題表示：求解方法Johnson算法Johnson算法Johnson算法的求解步驟：①從加工時間矩陣中找出最短的加工時間；②若最短的加工時間出現(xiàn)在機器M1上，則對應(yīng)的零件盡可能往前排；若最短加工時間出現(xiàn)在機器M2上，則對應(yīng)零件盡可能往后排。然后，從加工時間矩陣中劃去已排序零件的加工時間。若最短加工時間有多個，則任挑一個；③若所有零件都已排序，停止。否則，轉(zhuǎn)步驟①。Johnson算法舉例【例】求如下6/2/P/Fmax問題的最優(yōu)解。求解過程如下：Johnson算法步驟的改進把Johnson算法作些改變，改變后的算法按以下步驟進行：①將所有ai≤bi的零件按ai值不減的順序排成一個序列A；②將所有ai＞bi的零件按bi值不增的順序排成一個序列B；③將A放到B之前，就構(gòu)成了最優(yōu)加工順序。一般n/m/P/Fmax問題的啟發(fā)式算法一般的流水車間排列排序問題如想求得精確解可用分支界定法：但計算量比較大，以至于計算機也無法求解，因此常用一些啟發(fā)式算法求近似解。作為一般生產(chǎn)實際中的排序問題，近優(yōu)解能夠滿足需要。Palmer法關(guān)鍵零件法CDS法Palmer法按零件的斜度指標排列零件的啟發(fā)式算法零件的斜度指標算法規(guī)則：按照各零件λi不增的順序排列零件，可得出令人滿意的順序，如果排列的結(jié)果有多個，可以通過計算Fmax，取其中最優(yōu)Fmax對應(yīng)的排序作為排序結(jié)果。Palmer法舉例【例】有一個4/3/P/Fmax問題，其加工時間如下表所示，試用Palmer法求解。關(guān)鍵零件法1找出關(guān)鍵零件C，序號為m。2對余下的零件，若pi1≤pim，則按照pi1不減的順序排序為Sa，否則按pim不增的順序排序為Sb。3

順序（Sa，C，Sb）即為近優(yōu)解。CDS法Campbell-Dudek-Smith

三人提出了一個啟發(fā)式算法,簡稱CDS法。把Johnson算法用于一般的n/m/P/Fmax問題，得到(m-1)個加工順序，取其中優(yōu)者。具體做法是對加工時間用Johnson算法求m-1次加工順序，取其中最好的結(jié)果。CDS法舉例對l=1,2,…,m-1分別排序，取最優(yōu)者。當l＝1時，按Johnson算法得到加工順序(1，2，3，4)，F(xiàn)max＝28；當l＝2時，得到加工順序(2，3，1，4)。對于順序(2，3，1，4)，相應(yīng)的Fmax＝29；所以，取順序(1，2，3，4)。這就是最優(yōu)順序。返回目錄3單件作業(yè)計劃問題是十分復(fù)雜的一種作業(yè)計劃問題，內(nèi)容和方法。描述n個零件在m臺機器上進行作業(yè)，使加工時間最短的單件作業(yè)排序結(jié)果。表示實質(zhì)是任務(wù)分配問題：匈牙利算法。任務(wù)分配的匈牙利算法從加工時間（費用）矩陣中尋找每一行的最小元素將每一行元素減去該行最小元素從加工時間（費用）矩陣中尋找每一列的最小元素將每一列元素減去該列最小元素劃出能覆蓋盡可能多的零元素的直線線條數(shù)等于矩陣的行數(shù)？從僅有一個零的行或列開始，找出零元素對應(yīng)的分配方案，每行和每列僅能確定一個元素，最后使每行和每列都有一個零元素是零元素對應(yīng)的就是最優(yōu)分配方案矩陣中未被線條穿過的元素中減去這些元素中的最小值，并將這個最小值加到直線交叉的元素上，其余元素不變否任務(wù)分配的匈牙利算法舉例【例】如左上表，請用匈牙利法求出任務(wù)分配。任務(wù)分配的匈牙利算法舉例(續(xù))結(jié)果矩陣表示：零件1由機器3加工(J1—M3)零件2由機器2加工(J2—M2)

零件3由機器4加工(J3—M4)

零件4由機器1加工(J4—M1)單件作業(yè)排序問題描述一般的單件作業(yè)排序問題中單個工件可以描述為：工件i的第j道工序是在機器k上進行【例】下列加工矩陣所代表的含義？

一般n/m/G/Fmax問題的啟發(fā)式算法可以采用分支定界法或整數(shù)規(guī)劃法求得最優(yōu)解。但都是效率較低的算法，不能用于生產(chǎn)實際中；啟發(fā)式方法是求解一般單件車間排序問題使用最多的方法。兩種作業(yè)計劃三種啟發(fā)式算法兩種作業(yè)計劃兩種作業(yè)計劃的構(gòu)成半能動作業(yè)計劃：各工序都按最早可能開工時間安排的作業(yè)計劃；能動作業(yè)計劃：任何一臺機器的每段空閑時間都不足以加工一道可加工工序的半能動計劃；無延遲作業(yè)計劃：沒有任何延遲出現(xiàn)的能動作業(yè)計劃。若干算法符號假設(shè)：{St}——t道工序之前已排序工序構(gòu)成的部分作業(yè)計劃；{Ot}——第t道工序可以安排的工序集合；Tk——{Ot}中工序Ok最早可能開工時間；Tk′——{Ot}中工序Ok最早可能完工時間。能動作業(yè)計劃的構(gòu)成步驟設(shè)t=1，{S1}為空集，{O1}為各工件第一道工序的集合求T*=min{Tk′}和T*出現(xiàn)的機器M*M*是多臺？從{Ot}中挑出滿足條件（需要機器M*加工且Tj′<T*）的工序Oj將確定的工序Oj放入{St}從{Ot}中消去Oj并將Oj的緊后工序放入{Ot}是否還有未安排的工序？結(jié)束否否t=t+1能動作業(yè)計劃的構(gòu)成算例【例】有一個2/3/G/Fmax問題，其加工描述矩陣D和加工時間矩陣T，分別為能動作業(yè)計劃的計算結(jié)果設(shè)t=1，{S1}為空集，{O1}為各工件第一道工序的集合求T*=min{Tk}和T*出現(xiàn)的機器M*M*是多臺？從{Ot}中挑出滿足條件（需要機器M*加工且Tj=T*）的工序Oj將確定的工序Oj放入{St}從{Ot}中消去Oj并將Oj的緊后工序放入{Ot}是否還有未安排的工序？結(jié)束否否t=t+1無延遲作業(yè)計劃的構(gòu)成步驟無延遲作業(yè)計劃的構(gòu)成舉例三類啟發(fā)式算法優(yōu)先調(diào)度法SPT：優(yōu)先選擇加工時間最短的工序；平均流程時間最短FCFS：優(yōu)先選擇最早進入可排工序集合的工件；對工件較為公平EDD：優(yōu)先選擇完工期限緊的工件；使工件的最大延誤時間最小MWKR：優(yōu)先選擇余下加工時間最長的工件；使不同工作量的工件完工時間盡量接近三類啟發(fā)式算法(續(xù))優(yōu)先調(diào)度法(續(xù))LWKR：優(yōu)先選擇余下加工時間最短的工件；使工作量小的工件盡快完成MOPNR：優(yōu)先選擇余下工序數(shù)最多的工件；SCR：優(yōu)先選擇臨界比最小的工件（臨界比為工件允許停留時間與工件余下加工時間之比）；RANDOM：隨機地挑一個工件。有時是多種優(yōu)先調(diào)度法的有序組合。三類啟發(fā)式算法(續(xù))隨機抽樣法從全部能動作業(yè)計劃或無延遲作業(yè)計劃中隨機抽樣，得到多個作業(yè)計劃，從中選優(yōu)；計算量小。概率調(diào)度法結(jié)合隨機抽樣和優(yōu)先調(diào)度法則。返回目錄4生產(chǎn)作業(yè)控制實行生產(chǎn)作業(yè)控制的原因加工時間估計不準確隨機因素的影響加工路線的多樣化企業(yè)環(huán)境動態(tài)性生產(chǎn)作業(yè)控制的條件控制標準：生產(chǎn)計劃和生產(chǎn)作業(yè)計劃控制信息：實際生產(chǎn)進度和計劃的偏離信息控