制造業(yè)作業(yè)生產(chǎn)計(jì)劃課件

1、第十一章 制造業(yè)作業(yè)計(jì)劃與控制11.1 排序問(wèn)題的基本概念 11.2 流水作業(yè)排序問(wèn)題11.3 單件作業(yè)排序問(wèn)題11.4 生產(chǎn)作業(yè)控制第一節(jié) 排序的基本概念一、相關(guān)名詞術(shù)語(yǔ)排序：確定工件在機(jī)器上的加工順序。編制作業(yè)計(jì)劃：不僅包括確定工件的加工順序，還包括確定機(jī)器加工每個(gè)工件的開(kāi)始時(shí)間和完成時(shí)間。我們習(xí)慣上不加區(qū)別地使用作業(yè)排序與作業(yè)計(jì)劃。 派工：按照作業(yè)計(jì)劃的要求，將具體的生產(chǎn)任務(wù)安排到具體的機(jī)床上加工。趕工：當(dāng)實(shí)際進(jìn)度落后于計(jì)劃進(jìn)度時(shí)采取的行動(dòng)。加工線路：工件按照工藝過(guò)程進(jìn)行加工的過(guò)程，一般用M1,M2,M3,M4來(lái)表示。加工順序：表示每臺(tái)機(jī)器加工n個(gè)工件的先后順序，是排序要解決的問(wèn)題。二、

2、排序問(wèn)題的分類 按機(jī)器的種類和數(shù)量不同，可以分為單臺(tái)機(jī)器的排序問(wèn)題和多臺(tái)機(jī)器的排序問(wèn)題; 按加工路線的特征，可分為單件作業(yè)排序問(wèn)題和流水作業(yè)排序問(wèn)題; 按工件到達(dá)工作中心（或車間）的情況不同可分為靜態(tài)的排序問(wèn)題（當(dāng)進(jìn)行排序時(shí)，所有工件都已到達(dá)，或準(zhǔn)備就緒）和動(dòng)態(tài)的排序問(wèn)題（工件的到達(dá)是陸續(xù)的，要隨時(shí)安排它們的加工順序）; 第一節(jié) 排序的基本概念二、排序問(wèn)題的分類 按目標(biāo)函數(shù)不同，可分為流程最短問(wèn)題與誤工最少問(wèn)題等； 按目標(biāo)函數(shù)的性質(zhì)不同分為單目標(biāo)排序問(wèn)題與多目標(biāo)排序問(wèn)題; 按參數(shù)的性質(zhì)，可以劃分為確定型排序問(wèn)題與隨機(jī)型排序問(wèn)題。 第一節(jié) 排序的基本概念第一節(jié) 排序的基本概念三、假設(shè)條件與符號(hào)說(shuō)

3、明（一）排序問(wèn)題的假設(shè)條件一個(gè)工件不能同時(shí)在幾臺(tái)不同的機(jī)器上加工；工件在加工過(guò)程中采取平行移動(dòng)方式；不允許中斷；每道工序只在一臺(tái)機(jī)器上完成；工件數(shù)、機(jī)器數(shù)和加工時(shí)間已知，加工時(shí)間與加工順序無(wú)關(guān)；每臺(tái)機(jī)器同時(shí)只能加工一個(gè)工件。第一節(jié) 排序的基本概念三、假設(shè)條件與符號(hào)說(shuō)明（二）有關(guān)符號(hào)說(shuō)明四、排序問(wèn)題的一般表示方法 4參數(shù)法：n/m/A/B 其中：n 工件數(shù)； m機(jī)器數(shù)； A工作車間類型； B目標(biāo)函數(shù)，通常是使其最小 若A處為F代替，則表示流水作業(yè)排序問(wèn)題； 若A處為P代替，則表示流水作業(yè)排列排序問(wèn)題，即每個(gè)工件在各臺(tái)機(jī)器上的加工順序都相同； 若m為1時(shí)，A為空白，即單臺(tái)機(jī)器的排序，對(duì)于單臺(tái)機(jī)器排

4、序問(wèn)題，無(wú)所謂加工路線問(wèn)題。第一節(jié) 排序的基本概念第二節(jié) 流水作業(yè)排序問(wèn)題流水作業(yè)排序問(wèn)題的基本特征是每個(gè)工件的加工線路都一致。加工線路一致，是指工件的流向一致，并不是指每個(gè)工件必須經(jīng)過(guò)加工線路上的每臺(tái)機(jī)器加工。本節(jié)要討論的是所有工件在各臺(tái)機(jī)器上的加工順序相同的情況，就是排列排序問(wèn)題n/m/P/B。第二節(jié) 流水作業(yè)排序問(wèn)題一、最長(zhǎng)流程時(shí)間Fmax的計(jì)算P263例11.1 有一個(gè)6/4/P/Fmax問(wèn)題，其加工時(shí)間如表，當(dāng)按順序 S=(6，1，5，2，4，3)加工時(shí)，求 Fmax。表11-1 加工時(shí)間矩陣i123456Pi1423142Pi2456745Pi3587555Pi4424331表11

5、-2 順序下的加工時(shí)間矩陣P263例11.1 有一個(gè)6/4/P/Fmax問(wèn)題，其加工時(shí)間如表，當(dāng)按順序 S=(6，1，5，2，4，3)加工時(shí)，求 Fmax。表11-1 加工時(shí)間矩陣i123456Pi1423142Pi2456745Pi3587555Pi4424331i615243Pi12246410212113316Pi257411415520727633Pi3512517522830535742Pi4113421325232338446 對(duì)于第1行第1列，只需把加工時(shí)間的數(shù)值作為完工時(shí)間標(biāo)在加工時(shí)間的右上角;對(duì)于第1行的其它元素，從左到右依次將前一列右上角的數(shù)字加上計(jì)算列的加工時(shí)間，將結(jié)果填

6、在計(jì)算列加工時(shí)間的右上角。 對(duì)于從第2行到第m行，只要把上一行右上角的數(shù)字和本行的加工時(shí)間相加，將結(jié)果填在加工時(shí)間的右上角； 從第2列到第n列，則要從本行前一列右上角和本列上一行的右上角數(shù)字中取較大者，再和本列加工時(shí)間相加，將結(jié)果填在本列加工時(shí)間的右上角。這樣計(jì)算下去，最后一行的最后一列右上角數(shù)字，即為Fmax。 Fmax的標(biāo)注完工時(shí)間的規(guī)則 第二節(jié) 流水作業(yè)排序問(wèn)題二、n / 2 / F / Fmax 問(wèn)題的最優(yōu)算法 對(duì)于n個(gè)工件1臺(tái)機(jī)器的排序問(wèn)題，既適用于流程作業(yè),也適用于單件作業(yè)，在第三節(jié)單件作業(yè)排序討論。 對(duì)于n / 2 / F / Fmax 問(wèn)題，S.M.Johson于1954年給出

7、了有效的算法，即著名的Johson算法。其目標(biāo)是使從第一個(gè)工件開(kāi)始到最后一個(gè)工件結(jié)束的總流程時(shí)間最短。 Johnson算法的步驟： 列出所有工件在兩臺(tái)機(jī)器上的加工時(shí)間矩陣； 從加工時(shí)間矩陣中找出最短的加工時(shí)間； 若最短的加工時(shí)間出現(xiàn)在M1上，則對(duì)應(yīng)的工件往前排；如果最短的加工時(shí)間出現(xiàn)在M2上，則對(duì)應(yīng)的工件往后排；然后，劃去已經(jīng)排序的工件。若最短的加工時(shí)間有多個(gè)，則任選一個(gè)； 當(dāng)所有的工件都已排序，停止計(jì)算，轉(zhuǎn)步驟。二、n / 2 / F / Fmax 問(wèn)題的最優(yōu)算法 P264例11.2 按Johnson法求下表所示的6/2/F/Fmax問(wèn)題的最優(yōu)解。i123456ai518534bi72247

8、4表11-3 加工時(shí)間矩陣最優(yōu)加工順序?yàn)镾=（2，5，6，1，4，3）最優(yōu)順序下的Fmax=28Johnson算法的變形步驟：將所有aibi的工件按照ai值不減（遞升）的順序排列成一個(gè)序列A；將所有aibi的工件按bi值不增（遞減）的順序排列成一個(gè)序列B；將A放到B之前，就構(gòu)成了最優(yōu)加工順序。 P264例11.2 Johnson算法的變形求下表所示的6/2/F/Fmax問(wèn)題的最優(yōu)解。i123456ai518534bi722474表11-3 加工時(shí)間矩陣序列A為（2,5,6,1），序列B為（4,3），則最優(yōu)序列為S=（2,5,6,1,4,3），與Johnson算法的結(jié)果一致。n / m / P

9、/ Fmax問(wèn)題的啟發(fā)式算法啟發(fā)式算法（試探法）是一種能在可接受的費(fèi)用內(nèi)尋找最好的解的技術(shù)，但不一定能保證所得解的可行性和最優(yōu)性，甚至在多數(shù)情況下，無(wú)法闡述所得解同最優(yōu)解的近似程度 。啟發(fā)式算法是解決NP問(wèn)題（不確定性問(wèn)題）的重要方法，由于其計(jì)算量都比較大，所以隨著計(jì)算機(jī)技術(shù)的發(fā)展，啟發(fā)式算法取得了巨大的成就。常見(jiàn)的啟發(fā)式算法有貪婪法、局部搜索法、退火算法、蟻群算法等。 經(jīng)典算法與啟發(fā)式算法駕駛汽車到達(dá)某人的家，寫成算法是這樣的：沿長(zhǎng)張高速公路北行至太子廟；從西北出口出來(lái)后往山上開(kāi)4.5公里；在一個(gè)雜貨店旁邊的紅綠燈路口右轉(zhuǎn)，接著在第一個(gè)路口左轉(zhuǎn)；從左邊褐色大房子的車道進(jìn)去，就是桃源路714號(hào)

10、。用啟發(fā)式方法來(lái)描述則可能是這樣：找出上一次我們寄給你的信，照著信上面的寄出地址開(kāi)車到這個(gè)鎮(zhèn)；到了之后你問(wèn)一下我們的房子在哪里。這里每個(gè)人都認(rèn)識(shí)我們肯定有人會(huì)很愿意幫助你的；如果你找不到人，那就找個(gè)公共電話亭給我們打電話，我們會(huì)出來(lái)接你。 1965年，DSPalmer提出按斜度指標(biāo)排列工件的啟發(fā)式算法，這種算法稱之為Palmer算法。其中工件斜度指標(biāo)可按下式計(jì)算： 算出i后，按i不增（遞減）的順序排列工件，可得出較滿意的加工順序。三、一般n / m / P / Fmax問(wèn)題的啟發(fā)式算法（一）Palmer（帕默） 算法（一）Palmer 算法P266例11.3 有一個(gè)4/3/F/Fmax問(wèn)題，用

11、Palmer算法求解最優(yōu)加工順序。加工時(shí)間矩陣為：三、一般n / m / P / Fmax問(wèn)題的啟發(fā)式算法i1234Pi11263Pi18429Pi14582i1234Pi11263Pi18429Pi14582解：按照 不增的順序，得到最優(yōu)加工順序(1,2,3,4)和(2,1,3,4)（二）關(guān)鍵工件法步驟如下： 1. 計(jì)算每個(gè)工件的總加工時(shí)間Pi=pij，找出加工時(shí)間最長(zhǎng)的工件C（j=m），將其作為關(guān)鍵工件。 2. 對(duì)于余下的工件，若Pi1Pim，則按Pi1不減的順序排列一個(gè)序列Sa；若Pi1Pim，則按Pim不增的順序排成一個(gè)序列Sb。 3. 加工順序（Sa，C，Sb）即為所求近優(yōu)解。例11

12、.3i1234Pi11263Pi18429Pi14582三、一般n / m / P / Fmax問(wèn)題的啟發(fā)式算法 （三）CDS算法 Campbell，Dudek，Smith三人提出了一個(gè)啟發(fā)式算法，簡(jiǎn)稱CDS算法。他們把Johnson 算法用于一般 n / m / P /Fmax問(wèn)題，得到（m-1）個(gè)加工順序，取其中優(yōu)者。對(duì)加工時(shí)間，按下列公式求和，即： 當(dāng)l=1時(shí),有兩種排序方式,用Johnson 方法排序得到一個(gè)最優(yōu)排序；當(dāng)l=2時(shí)，又有兩種排序方法，用Johnson方法排序，得到又一個(gè)最優(yōu)排序；當(dāng)l=3,，(m-1)，又可求出對(duì)應(yīng)的每一種排序方法。最后比較取得最優(yōu)解。本次課小結(jié) 相關(guān)名次

13、術(shù)語(yǔ)（排序、編制作業(yè)計(jì)劃、 派工、趕工、加工線路、加工順序）最長(zhǎng)流程時(shí)間的計(jì)算n/2/F/Fmax問(wèn)題的最優(yōu)算法（ Johson算法）11.3 單件作業(yè)排序問(wèn)題一、問(wèn)題的描述 特點(diǎn)：每個(gè)工件都有其獨(dú)特的加工路線，工件沒(méi)有固定的流向 問(wèn)題的描述：描述一道工序，要用3個(gè)參數(shù)(i,j,k)，表示工件 i 的第 j 道工序在機(jī)器 k 上進(jìn)行。 可以用加工描述矩陣來(lái)描述所有工件的加工11.3 單件作業(yè)排序問(wèn)題一、問(wèn)題的描述 可以用加工描述矩陣來(lái)描述所有工件的加工 例如，一個(gè)2/3/G/Fmax問(wèn)題：工序1工序2工序3工件1工件2二、三種作業(yè)計(jì)劃半能動(dòng)作業(yè)計(jì)劃（Semi-active schedule）各

14、工序都按最早可能開(kāi)（完）工時(shí)間安排的作業(yè)計(jì)劃能動(dòng)作業(yè)計(jì)劃（Active schedule）任何一臺(tái)機(jī)器的每段空閑時(shí)間都不足以加工一道可加工工序的半能動(dòng)作業(yè)計(jì)劃無(wú)延遲作業(yè)計(jì)劃（Non-delay schedu1e）沒(méi)有任何延遲出現(xiàn)的能動(dòng)作業(yè)計(jì)劃“延遲”：有工件等待加工時(shí)，機(jī)器出現(xiàn)空閑，即使這段空閑時(shí)間不足以完成一道工序能動(dòng)作業(yè)計(jì)劃與無(wú)延遲作業(yè)計(jì)劃的生成符號(hào)說(shuō)明將每安排一道工序稱作一“步”，設(shè)：St第t 步之前已排序工序構(gòu)成的部分作業(yè)計(jì)劃Ot第t 步可以排序的工序的集合 TkOt中Ok的最早可能開(kāi)工時(shí)間 TkOt中Ok的最早可能完工時(shí)間P269 例11.4 有一個(gè)2/3/G/Fmax問(wèn)題，其加工描

15、述矩陣D和加工時(shí)間矩陣T已知，求一個(gè)能動(dòng)作業(yè)計(jì)劃。三、三類啟發(fā)式算法優(yōu)先調(diào)度法則隨機(jī)抽樣法概率調(diào)度法1.優(yōu)先調(diào)度法則SPT（Shortest processing time）法則優(yōu)先選擇加工時(shí)間最短的工序可使工件的平均流程時(shí)間最短，從而減少在制品量FCFS（First come first served）法則優(yōu)先選擇最早進(jìn)入可排工序集合的工件來(lái)自排隊(duì)論，對(duì)工件較公平EDD（Earliest due date）法則優(yōu)先選擇完工期限緊的工件可使工件最大延誤時(shí)間最小MWKR（Most work remaining）法則優(yōu)先選擇余下加工時(shí)間最長(zhǎng)的工件不同工作量的工件的完工時(shí)間盡量接近1.優(yōu)先調(diào)度法則（

16、續(xù)）LWKR（Least work remaining）法則優(yōu)先選擇余下加工時(shí)間最短的工件使工作量小的工件盡快完成MOPNR（Most operations remaining）法則優(yōu)先選擇余下工序數(shù)最多的工件與MWKR法則類似，只不過(guò)考慮工件在不同機(jī)器上的轉(zhuǎn)運(yùn)排隊(duì)時(shí)間是主要的SCR（Smallest critical ratio）法則優(yōu)先選擇臨界比最小的工件（臨界比：工件允許停留時(shí)間與工件余下加工時(shí)間之比）保證工件延誤最少RANDOM法則隨機(jī)地挑一個(gè)工件2.隨機(jī)抽樣法隨機(jī)抽樣法實(shí)際上是對(duì)同一個(gè)問(wèn)題多次運(yùn)用RANDOM法則來(lái)決定要挑選的工序，從而得到多個(gè)作業(yè)計(jì)劃這種方法不一定能得到最優(yōu)作業(yè)計(jì)劃

17、，但可以得到較滿意的作業(yè)計(jì)劃效果與樣本大小有關(guān)。樣本越大，獲取較好解的可能性越大從無(wú)延遲作業(yè)計(jì)劃母體中抽樣所得到的結(jié)果比從能動(dòng)作業(yè)計(jì)劃母體中抽樣所得到的結(jié)果要好3. 概率調(diào)度法給不同的工序按某一優(yōu)先調(diào)度法則分配不同的挑選概率，可以得到多個(gè)作業(yè)計(jì)劃供比較。例如，在構(gòu)成無(wú)延遲作業(yè)計(jì)劃的第（3）步 有3道工序，A、B和C可挑選 3道工序所需的時(shí)間分別為3，4和7 將這3道工序按加工時(shí)間從小到大排列，然后給每道工序從大到小分配一個(gè)被挑選的概率比如A、B和C的挑選概率分別為6/14、5/14和3/14既保證了SPT法則起作用，又可產(chǎn)生多個(gè)作業(yè)計(jì)劃供挑選 生產(chǎn)作業(yè)控制是指在生產(chǎn)過(guò)程中，按既定的政策、目標(biāo)、

18、計(jì)劃和標(biāo)準(zhǔn)，通過(guò)監(jiān)督和檢查生產(chǎn)活動(dòng)的進(jìn)展情況、實(shí)際成效，及時(shí)發(fā)現(xiàn)偏差，找出原因，采取措施，以保證目標(biāo)、計(jì)劃的實(shí)現(xiàn)。 生產(chǎn)運(yùn)作控制的受控客體是生產(chǎn)運(yùn)作過(guò)程，其預(yù)定目標(biāo)是主生產(chǎn)計(jì)劃與生產(chǎn)作業(yè)計(jì)劃的目標(biāo)值。11.4 生產(chǎn)作業(yè)控制一、生產(chǎn)活動(dòng)與作業(yè)計(jì)劃產(chǎn)生偏差的原因（1）加工時(shí)間估計(jì)不準(zhǔn)確（2）隨機(jī)因素的影響（3）加工路線的多樣性（4）企業(yè)環(huán)境的動(dòng)態(tài)性11.4 生產(chǎn)作業(yè)控制二、生產(chǎn)作業(yè)控制的程序 制定生產(chǎn)作業(yè)監(jiān)控體系 監(jiān)控實(shí)際生產(chǎn)過(guò)程 評(píng)估偏差情況 采取糾偏措施11.4 生產(chǎn)作業(yè)控制三、生產(chǎn)作業(yè)控制的主要工具 實(shí)際生產(chǎn)中，有不少工具可以用來(lái)進(jìn)行生產(chǎn)作業(yè)控制，這些工具容易通過(guò)運(yùn)用適當(dāng)?shù)能浖?lái)生成，主要包括： 調(diào)度單 日?qǐng)?bào)、月報(bào) 例外報(bào)告、異常報(bào)告 輸入/輸出（I/O）報(bào)告漏斗模型德國(guó)漢諾威大學(xué)的Bechte和Wiendall等人于20世紀(jì)80年代初在實(shí)施輸入/輸出控制時(shí)提出了漏斗模型（Funnel Model）。漏斗模型 漏斗模型的基本原則：工作中心的輸入永遠(yuǎn)不能超過(guò)工作中心的輸出。當(dāng)工作中心的輸入超過(guò)輸出，就會(huì)拖欠訂單，結(jié)果將會(huì)出現(xiàn)作業(yè)推遲、客戶不滿、下游作業(yè)或相關(guān)作業(yè)的延期。 注：曲線圖的垂直段表示到達(dá)或完成的工作量；水平段表示相鄰到達(dá)或完成的任務(wù)之間的時(shí)