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

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

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

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

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

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

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

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

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

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

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