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

第十一章制造業(yè)作業(yè)計劃與控制§11.1排序問題的基本概念§11.2流水作業(yè)排序問題§11.3

單件作業(yè)排序問題§11.4生產(chǎn)作業(yè)控制精選課件第十一章制造業(yè)作業(yè)計劃與控制§11.1排序問題的基本概1第一節(jié)排序的基本概念一、相關(guān)名詞術(shù)語排序：確定工件在機(jī)器上的加工順序。編制作業(yè)計劃：不僅包括確定工件的加工順序，還包括確定機(jī)器加工每個工件的開始時間和完成時間。我們習(xí)慣上不加區(qū)別地使用作業(yè)排序與作業(yè)計劃。

派工：按照作業(yè)計劃的要求，將具體的生產(chǎn)任務(wù)安排到具體的機(jī)床上加工。趕工：當(dāng)實際進(jìn)度落后于計劃進(jìn)度時采取的行動。加工線路：工件按照工藝過程進(jìn)行加工的過程，一般用M1,M2,M3,M4來表示。加工順序：表示每臺機(jī)器加工n個工件的先后順序，是排序要解決的問題。精選課件第一節(jié)排序的基本概念一、相關(guān)名詞術(shù)語精選課件2二、排序問題的分類按機(jī)器的種類和數(shù)量不同，可以分為單臺機(jī)器的排序問題和多臺機(jī)器的排序問題;

按加工路線的特征，可分為單件作業(yè)排序問題和流水作業(yè)排序問題;

按工件到達(dá)工作中心（或車間）的情況不同可分為靜態(tài)的排序問題（當(dāng)進(jìn)行排序時，所有工件都已到達(dá)，或準(zhǔn)備就緒）和動態(tài)的排序問題（工件的到達(dá)是陸續(xù)的，要隨時安排它們的加工順序）;第一節(jié)排序的基本概念精選課件二、排序問題的分類按機(jī)器的種類和數(shù)量不同，可以分為單臺機(jī)3二、排序問題的分類按目標(biāo)函數(shù)不同，可分為流程最短問題與誤工最少問題等；按目標(biāo)函數(shù)的性質(zhì)不同分為單目標(biāo)排序問題與多目標(biāo)排序問題;

按參數(shù)的性質(zhì)，可以劃分為確定型排序問題與隨機(jī)型排序問題。第一節(jié)排序的基本概念精選課件二、排序問題的分類按目標(biāo)函數(shù)不同，可分為流程最短問題與誤4第一節(jié)排序的基本概念三、假設(shè)條件與符號說明（一）排序問題的假設(shè)條件一個工件不能同時在幾臺不同的機(jī)器上加工；工件在加工過程中采取平行移動方式；不允許中斷；每道工序只在一臺機(jī)器上完成；工件數(shù)、機(jī)器數(shù)和加工時間已知，加工時間與加工順序無關(guān)；每臺機(jī)器同時只能加工一個工件。精選課件第一節(jié)排序的基本概念三、假設(shè)條件與符號說明精選課件5第一節(jié)排序的基本概念三、假設(shè)條件與符號說明（二）有關(guān)符號說明精選課件第一節(jié)排序的基本概念三、假設(shè)條件與符號說明精選課件6四、排序問題的一般表示方法

4參數(shù)法：n/m/A/B

其中：n——工件數(shù)；

m——機(jī)器數(shù)；

A——工作車間類型；

B——目標(biāo)函數(shù)，通常是使其最小

若A處為F代替，則表示流水作業(yè)排序問題；

若A處為P代替，則表示流水作業(yè)排列排序問題，即每個工件在各臺機(jī)器上的加工順序都相同；若m為1時，A為空白，即單臺機(jī)器的排序，對于單臺機(jī)器排序問題，無所謂加工路線問題。第一節(jié)排序的基本概念精選課件四、排序問題的一般表示方法第一節(jié)排序的基本概念精選課件7第二節(jié)流水作業(yè)排序問題流水作業(yè)排序問題的基本特征是每個工件的加工線路都一致。加工線路一致，是指工件的流向一致，并不是指每個工件必須經(jīng)過加工線路上的每臺機(jī)器加工。本節(jié)要討論的是所有工件在各臺機(jī)器上的加工順序相同的情況，就是排列排序問題n/m/P/B。精選課件第二節(jié)流水作業(yè)排序問題流水作業(yè)排序問題的基本特征是每個工件8第二節(jié)流水作業(yè)排序問題一、最長流程時間Fmax的計算P263[例11.1]有一個6/4/P/Fmax問題，其加工時間如表，當(dāng)按順序S=(6，1，5，2，4，3)加工時，求Fmax。表11-1加工時間矩陣i123456Pi1423142Pi2456745Pi3587555Pi4424331精選課件第二節(jié)流水作業(yè)排序問題一、最長流程時間Fmax的計算P269表11-2順序下的加工時間矩陣P263[例11.1]有一個6/4/P/Fmax問題，其加工時間如表，當(dāng)按順序S=(6，1，5，2，4，3)加工時，求Fmax。表11-1加工時間矩陣i123456Pi1423142Pi2456745Pi3587555Pi4424331i615243Pi12246410212113316Pi257411415520727633Pi3512517522830535742Pi4113421325232338446精選課件表11-2順序下的加工時間矩陣P263[例11.1]有一10對于第1行第1列，只需把加工時間的數(shù)值作為完工時間標(biāo)在加工時間的右上角;對于第1行的其它元素，從左到右依次將前一列右上角的數(shù)字加上計算列的加工時間，將結(jié)果填在計算列加工時間的右上角。對于從第2行到第m行，只要把上一行右上角的數(shù)字和本行的加工時間相加，將結(jié)果填在加工時間的右上角；從第2列到第n列，則要從本行前一列右上角和本列上一行的右上角數(shù)字中取較大者，再和本列加工時間相加，將結(jié)果填在本列加工時間的右上角。這樣計算下去，最后一行的最后一列右上角數(shù)字，即為Fmax。Fmax的標(biāo)注完工時間的規(guī)則精選課件對于第1行第1列，只需把加工時間的數(shù)值作為完工時間標(biāo)在加11第二節(jié)流水作業(yè)排序問題二、n/2/F/Fmax問題的最優(yōu)算法對于n個工件1臺機(jī)器的排序問題，既適用于流程作業(yè),也適用于單件作業(yè)，在第三節(jié)單件作業(yè)排序討論。對于n/2/F/Fmax問題，S.M.Johson于1954年給出了有效的算法，即著名的Johson算法。其目標(biāo)是使從第一個工件開始到最后一個工件結(jié)束的總流程時間最短。精選課件第二節(jié)流水作業(yè)排序問題二、n/2/F/Fmax12

Johnson算法的步驟：列出所有工件在兩臺機(jī)器上的加工時間矩陣；從加工時間矩陣中找出最短的加工時間；若最短的加工時間出現(xiàn)在M1上，則對應(yīng)的工件往前排；如果最短的加工時間出現(xiàn)在M2上，則對應(yīng)的工件往后排；然后，劃去已經(jīng)排序的工件。若最短的加工時間有多個，則任選一個；當(dāng)所有的工件都已排序，停止計算，轉(zhuǎn)步驟①。二、n/2/F/Fmax問題的最優(yōu)算法精選課件Johnson算法的步驟：二、n/2/F/F13

P264[例11.2]按Johnson法求下表所示的6/2/F/Fmax問題的最優(yōu)解。i123456ai518534bi722474表11-3加工時間矩陣最優(yōu)加工順序為S=（2，5，6，1，4，3）最優(yōu)順序下的Fmax=28精選課件P264[例11.2]i123456ai5185314Johnson算法的變形步驟：將所有ai≤bi的工件按照ai值不減（遞升）的順序排列成一個序列A；將所有ai＞bi的工件按bi值不增（遞減）的順序排列成一個序列B；將A放到B之前，就構(gòu)成了最優(yōu)加工順序。精選課件Johnson算法的變形步驟：精選課件15

P264[例11.2]——Johnson算法的變形求下表所示的6/2/F/Fmax問題的最優(yōu)解。i123456ai518534bi722474表11-3加工時間矩陣序列A為（2,5,6,1），序列B為（4,3），則最優(yōu)序列為S=（2,5,6,1,4,3），與Johnson算法的結(jié)果一致。精選課件P264[例11.2]——Johnson算法的變16n/m/P/Fmax問題的啟發(fā)式算法啟發(fā)式算法（試探法）是一種能在可接受的費(fèi)用內(nèi)尋找最好的解的技術(shù)，但不一定能保證所得解的可行性和最優(yōu)性，甚至在多數(shù)情況下，無法闡述所得解同最優(yōu)解的近似程度。啟發(fā)式算法是解決NP問題（不確定性問題）的重要方法，由于其計算量都比較大，所以隨著計算機(jī)技術(shù)的發(fā)展，啟發(fā)式算法取得了巨大的成就。常見的啟發(fā)式算法有貪婪法、局部搜索法、退火算法、蟻群算法等。

精選課件n/m/P/Fmax問題的啟發(fā)式算法啟發(fā)式算法（17經(jīng)典算法與啟發(fā)式算法駕駛汽車到達(dá)某人的家，寫成算法是這樣的：沿長張高速公路北行至太子廟；從西北出口出來后往山上開4.5公里；在一個雜貨店旁邊的紅綠燈路口右轉(zhuǎn)，接著在第一個路口左轉(zhuǎn)；從左邊褐色大房子的車道進(jìn)去，就是桃源路714

號。用啟發(fā)式方法來描述則可能是這樣：找出上一次我們寄給你的信，照著信上面的寄出地址開車到這個鎮(zhèn)；到了之后你問一下我們的房子在哪里。這里每個人都認(rèn)識我們——肯定有人會很愿意幫助你的；如果你找不到人，那就找個公共電話亭給我們打電話，我們會出來接你。精選課件經(jīng)典算法與啟發(fā)式算法駕駛汽車到達(dá)某人的家，寫成算法是這樣的：18

1965年，D·S·Palmer提出按斜度指標(biāo)排列工件的啟發(fā)式算法，這種算法稱之為Palmer算法。其中工件斜度指標(biāo)可按下式計算：算出λi后，按λi不增（遞減）的順序排列工件，可得出較滿意的加工順序。三、一般n/m/P/Fmax問題的啟發(fā)式算法（一）Palmer（帕默）算法精選課件

1965年，D·S·Palmer提出按斜度指標(biāo)19（一）Palmer

算法P266[例11.3]有一個4/3/F/Fmax問題，用Palmer算法求解最優(yōu)加工順序。加工時間矩陣為：三、一般n/m/P/Fmax問題的啟發(fā)式算法i1234Pi11263Pi18429Pi14582精選課件（一）Palmer算法P266[例11.3]有一個4/320i1234Pi11263Pi18429Pi14582解：按照不增的順序，得到最優(yōu)加工順序(1,2,3,4)和(2,1,3,4)精選課件i1234Pi11263Pi18429Pi14582解：按照21（二）關(guān)鍵工件法步驟如下：

1.計算每個工件的總加工時間Pi=∑pij，找出加工時間最長的工件C（j=m），將其作為關(guān)鍵工件。

2.對于余下的工件，若Pi1≤Pim，則按Pi1不減的順序排列一個序列Sa；若Pi1>Pim，則按Pim不增的順序排成一個序列Sb。

3.加工順序（Sa，C，Sb）即為所求近優(yōu)解。例11.3i1234Pi11263Pi18429Pi14582精選課件（二）關(guān)鍵工件法步驟如下：i1234Pi11263Pi18422三、一般n/m/P/Fmax問題的啟發(fā)式算法（三）CDS算法

Campbell，Dudek，Smith三人提出了一個啟發(fā)式算法，簡稱CDS算法。他們把Johnson算法用于一般n/m/P/Fmax問題，得到（m-1）個加工順序，取其中優(yōu)者。對加工時間，按下列公式求和，即：當(dāng)l=1時,有兩種排序方式,用Johnson方法排序得到一個最優(yōu)排序；當(dāng)l=2時，又有兩種排序方法，用Johnson方法排序，得到又一個最優(yōu)排序；當(dāng)l=3,…，(m-1)，又可求出對應(yīng)的每一種排序方法。最后比較取得最優(yōu)解。精選課件三、一般n/m/P/Fmax問題的啟發(fā)式算法（23本次課小結(jié)相關(guān)名次術(shù)語（排序、編制作業(yè)計劃、派工、趕工、加工線路、加工順序）最長流程時間的計算n/2/F/Fmax問題的最優(yōu)算法（Johson算法）精選課件本次課小結(jié)相關(guān)名次術(shù)語（排序、編制作業(yè)計劃、派工、趕工、24§11.3單件作業(yè)排序問題一、問題的描述特點(diǎn)：每個工件都有其獨(dú)特的加工路線，工件沒有固定的流向問題的描述：描述一道工序，要用3個參數(shù)(i,j,k)，表示工件i的第j道工序在機(jī)器k上進(jìn)行?？梢杂眉庸っ枋鼍仃噥砻枋鏊泄ぜ募庸ぞx課件§11.3單件作業(yè)排序問題特點(diǎn)：每個工件都有其獨(dú)特的25§11.3單件作業(yè)排序問題一、問題的描述可以用加工描述矩陣來描述所有工件的加工例如，一個2/3/G/Fmax問題：工序1工序2工序3工件1工件2精選課件§11.3單件作業(yè)排序問題可以用加工描述矩陣來描述所26二、三種作業(yè)計劃半能動作業(yè)計劃（Semi-activeschedule）各工序都按最早可能開（完）工時間安排的作業(yè)計劃能動作業(yè)計劃（Activeschedule）任何一臺機(jī)器的每段空閑時間都不足以加工一道可加工工序的半能動作業(yè)計劃無延遲作業(yè)計劃（Non-delayschedu1e）沒有任何延遲出現(xiàn)的能動作業(yè)計劃“延遲”：有工件等待加工時，機(jī)器出現(xiàn)空閑，即使這段空閑時間不足以完成一道工序精選課件二、三種作業(yè)計劃半能動作業(yè)計劃（Semi-activesc27能動作業(yè)計劃與無延遲作業(yè)計劃的生成符號說明將每安排一道工序稱作一“步”，設(shè)：｛St｝—第t步之前已排序工序構(gòu)成的部分作業(yè)計劃｛Ot｝—第t步可以排序的工序的集合

Tk—｛Ot｝中Ok的最早可能開工時間

T’k—｛Ot｝中Ok的最早可能完工時間精選課件能動作業(yè)計劃與無延遲作業(yè)計劃的生成符號說明精選課件28精選課件精選課件29P269例11.4

有一個2/3/G/Fmax問題，其加工描述矩陣D和加工時間矩陣T已知，求一個能動作業(yè)計劃。精選課件P269例11.4

有一個2/3/G/Fmax問題30精選課件精選課件31精選課件精選課件32精選課件精選課件33精選課件精選課件34精選課件精選課件35三、三類啟發(fā)式算法優(yōu)先調(diào)度法則隨機(jī)抽樣法概率調(diào)度法精選課件三、三類啟發(fā)式算法優(yōu)先調(diào)度法則精選課件361.優(yōu)先調(diào)度法則SPT（Shortestprocessingtime）法則優(yōu)先選擇加工時間最短的工序可使工件的平均流程時間最短，從而減少在制品量FCFS（Firstcomefirstserved）法則優(yōu)先選擇最早進(jìn)入可排工序集合的工件來自排隊論，對工件較公平EDD（Earliestduedate）法則優(yōu)先選擇完工期限緊的工件可使工件最大延誤時間最小MWKR（Mostworkremaining）法則優(yōu)先選擇余下加工時間最長的工件不同工作量的工件的完工時間盡量接近精選課件1.優(yōu)先調(diào)度法則SPT（Shortestprocessin371.優(yōu)先調(diào)度法則（續(xù)）LWKR（Leastworkremaining）法則優(yōu)先選擇余下加工時間最短的工件使工作量小的工件盡快完成MOPNR（Mostoperationsremaining）法則優(yōu)先選擇余下工序數(shù)最多的工件與MWKR法則類似，只不過考慮工件在不同機(jī)器上的轉(zhuǎn)運(yùn)排隊時間是主要的SCR（Smallestcriticalratio）法則優(yōu)先選擇臨界比最小的工件（臨界比：工件允許停留時間與工件余下加工時間之比）保證工件延誤最少RANDOM法則隨機(jī)地挑一個工件精選課件1.優(yōu)先調(diào)度法則（續(xù)）LWKR（Leastworkrem38精選課件精選課件392.隨機(jī)抽樣法隨機(jī)抽樣法?實際上是對同一個問題多次運(yùn)用RANDOM法則來決定要挑選的工序，從而得到多個作業(yè)計劃?這種方法不一定能得到最優(yōu)作業(yè)計劃，但可以得到較滿意的作業(yè)計劃效果與樣本大小有關(guān)。樣本越大，獲取較好解的可能性越大從無延遲作業(yè)計劃母體中抽樣所得到的結(jié)果比從能動作業(yè)計劃母體中抽樣所得到的結(jié)果要好精選課件2.隨機(jī)抽樣法隨機(jī)抽樣法精選課件403.概率調(diào)度法給不同的工序按某一優(yōu)先調(diào)度法則分配不同的挑選概率，可以得到多個作業(yè)計劃供比較。例如，在構(gòu)成無延遲作業(yè)計劃的第（3）步

?有3道工序，A、B和C可挑選

?3道工序所需的時間分別為3，4和7?將這3道工序按加工時間從小到大排列，然后給每道工序從大到小分配一個被挑選的概率比如A、B和C的挑選概率分別為6/14、5/14和3/14既保證了SPT法則起作用，又可產(chǎn)生多個作業(yè)計劃供挑選精選課件3.概率調(diào)度法給不同的工序按某一優(yōu)先調(diào)度法則分配不同的挑選41生產(chǎn)作業(yè)控制是指在生產(chǎn)過程中，按既定的政策、目標(biāo)、計劃和標(biāo)準(zhǔn)，通過監(jiān)督和檢查生產(chǎn)活動的進(jìn)展情況、實際成效，及時發(fā)現(xiàn)偏差，找出原因，采取措施，以保證目標(biāo)、計劃的實現(xiàn)。生產(chǎn)運(yùn)作控制的受控客體是生產(chǎn)運(yùn)作過程，其預(yù)定目標(biāo)是主生產(chǎn)計劃與生產(chǎn)作業(yè)計劃的目標(biāo)值?！?1.4生產(chǎn)作業(yè)控制精選課件生產(chǎn)作業(yè)控制是指在生產(chǎn)過程中，按既定的政策、目標(biāo)、計劃和42一、生產(chǎn)活動與作業(yè)計劃產(chǎn)生偏差的原因（1）加工時間估計不準(zhǔn)確（2）隨機(jī)因素的影響（3）加工路線的多樣性（4）企業(yè)環(huán)境的動態(tài)性§11.4生產(chǎn)作業(yè)控制精選課件一、生產(chǎn)活動與作業(yè)計劃產(chǎn)生偏差的原因§11.4生產(chǎn)作業(yè)控制43二、生產(chǎn)作業(yè)控制的程序制定生產(chǎn)作業(yè)監(jiān)控體系監(jiān)控實際生產(chǎn)過程評估偏差情況采取糾偏措施§11.4生產(chǎn)作業(yè)控制精選課件二、生產(chǎn)作業(yè)控制的程序§11.4生產(chǎn)作業(yè)控制精選課件44三、生產(chǎn)作業(yè)控制的主要工具實際生產(chǎn)中，有不少工具可以用來進(jìn)行生產(chǎn)作業(yè)控制，這些工具容易通過運(yùn)用適當(dāng)?shù)能浖砩?，主要包括：調(diào)度單日報、月報例外報告、異常報告輸入/輸出（I/O）報告精選課件三、生產(chǎn)作業(yè)控制的主要工具實際生產(chǎn)中，有不少工具可以用來進(jìn)45漏斗模型德國漢諾威大學(xué)的Bechte和Wiendall等人于20世紀(jì)80年代初在實施輸入/輸出控制時提出了漏斗模型（FunnelModel）。精選課件漏斗模型德國漢諾威大學(xué)的Bechte和Wiendall等人于46漏斗模型漏斗模型的基本原則：工作中心的輸入永遠(yuǎn)不能超過工作中心的輸出。當(dāng)工作中心的輸入超過輸出，就會拖欠訂單，結(jié)果將會出現(xiàn)作業(yè)推遲、客戶不滿、下游作業(yè)或相關(guān)作業(yè)的延期。

精選課件漏斗模型精選課件47注：曲線圖的垂直段表示到達(dá)或完成的工作量；水平段表示相鄰到達(dá)或完成的任務(wù)之間的時間間隔。精選課件注：曲線圖的垂直段表示到達(dá)或完成的工作量；水平段表示相鄰到達(dá)48控制規(guī)則在一段較長的時間內(nèi)(如數(shù)周)內(nèi)，若工況穩(wěn)定，輸入輸出兩條曲線可以近似地用兩條直線來表示，其斜率(平均生產(chǎn)率)等于平均在制品庫存/平均通過時間。實際實踐中，可以采用四個規(guī)則來調(diào)整輸入、輸出、在制品庫存和通過時間：若希望保持在制品庫存量，可暫時增加或減少輸入。若希望改變在制品庫存量，可暫時增加或減少輸入。若希望平均通過時間在所控制的范圍內(nèi)，則適當(dāng)調(diào)整平均在制品庫存與生產(chǎn)率的比例。要使各個工件的平均通過時間穩(wěn)定，可以采用FIFO規(guī)則來安排各工件的加工順序。精選課件控制規(guī)則在一段較長的時間內(nèi)(如數(shù)周)內(nèi)，若工況穩(wěn)定，輸入輸出49本章小結(jié)§11.1排序問題的基本概念§11.2流水作業(yè)排序問題§11.3

單件作業(yè)排序問題§11.4生產(chǎn)作業(yè)控制精選課件本章小結(jié)§11.1排序問題的基本概念精選課件50第十一章制造業(yè)作業(yè)計劃與控制§11.1排序問題的基本概念§11.2流水作業(yè)排序問題§11.3

單件作業(yè)排序問題§11.4生產(chǎn)作業(yè)控制精選課件第十一章制造業(yè)作業(yè)計劃與控制§11.1排序問題的基本概51第一節(jié)排序的基本概念一、相關(guān)名詞術(shù)語排序：確定工件在機(jī)器上的加工順序。編制作業(yè)計劃：不僅包括確定工件的加工順序，還包括確定機(jī)器加工每個工件的開始時間和完成時間。我們習(xí)慣上不加區(qū)別地使用作業(yè)排序與作業(yè)計劃。

派工：按照作業(yè)計劃的要求，將具體的生產(chǎn)任務(wù)安排到具體的機(jī)床上加工。趕工：當(dāng)實際進(jìn)度落后于計劃進(jìn)度時采取的行動。加工線路：工件按照工藝過程進(jìn)行加工的過程，一般用M1,M2,M3,M4來表示。加工順序：表示每臺機(jī)器加工n個工件的先后順序，是排序要解決的問題。精選課件第一節(jié)排序的基本概念一、相關(guān)名詞術(shù)語精選課件52二、排序問題的分類按機(jī)器的種類和數(shù)量不同，可以分為單臺機(jī)器的排序問題和多臺機(jī)器的排序問題;

按加工路線的特征，可分為單件作業(yè)排序問題和流水作業(yè)排序問題;

按工件到達(dá)工作中心（或車間）的情況不同可分為靜態(tài)的排序問題（當(dāng)進(jìn)行排序時，所有工件都已到達(dá)，或準(zhǔn)備就緒）和動態(tài)的排序問題（工件的到達(dá)是陸續(xù)的，要隨時安排它們的加工順序）;第一節(jié)排序的基本概念精選課件二、排序問題的分類按機(jī)器的種類和數(shù)量不同，可以分為單臺機(jī)53二、排序問題的分類按目標(biāo)函數(shù)不同，可分為流程最短問題與誤工最少問題等；按目標(biāo)函數(shù)的性質(zhì)不同分為單目標(biāo)排序問題與多目標(biāo)排序問題;

按參數(shù)的性質(zhì)，可以劃分為確定型排序問題與隨機(jī)型排序問題。第一節(jié)排序的基本概念精選課件二、排序問題的分類按目標(biāo)函數(shù)不同，可分為流程最短問題與誤54第一節(jié)排序的基本概念三、假設(shè)條件與符號說明（一）排序問題的假設(shè)條件一個工件不能同時在幾臺不同的機(jī)器上加工；工件在加工過程中采取平行移動方式；不允許中斷；每道工序只在一臺機(jī)器上完成；工件數(shù)、機(jī)器數(shù)和加工時間已知，加工時間與加工順序無關(guān)；每臺機(jī)器同時只能加工一個工件。精選課件第一節(jié)排序的基本概念三、假設(shè)條件與符號說明精選課件55第一節(jié)排序的基本概念三、假設(shè)條件與符號說明（二）有關(guān)符號說明精選課件第一節(jié)排序的基本概念三、假設(shè)條件與符號說明精選課件56四、排序問題的一般表示方法

4參數(shù)法：n/m/A/B

其中：n——工件數(shù)；

m——機(jī)器數(shù)；

A——工作車間類型；

B——目標(biāo)函數(shù)，通常是使其最小

若A處為F代替，則表示流水作業(yè)排序問題；

若A處為P代替，則表示流水作業(yè)排列排序問題，即每個工件在各臺機(jī)器上的加工順序都相同；若m為1時，A為空白，即單臺機(jī)器的排序，對于單臺機(jī)器排序問題，無所謂加工路線問題。第一節(jié)排序的基本概念精選課件四、排序問題的一般表示方法第一節(jié)排序的基本概念精選課件57第二節(jié)流水作業(yè)排序問題流水作業(yè)排序問題的基本特征是每個工件的加工線路都一致。加工線路一致，是指工件的流向一致，并不是指每個工件必須經(jīng)過加工線路上的每臺機(jī)器加工。本節(jié)要討論的是所有工件在各臺機(jī)器上的加工順序相同的情況，就是排列排序問題n/m/P/B。精選課件第二節(jié)流水作業(yè)排序問題流水作業(yè)排序問題的基本特征是每個工件58第二節(jié)流水作業(yè)排序問題一、最長流程時間Fmax的計算P263[例11.1]有一個6/4/P/Fmax問題，其加工時間如表，當(dāng)按順序S=(6，1，5，2，4，3)加工時，求Fmax。表11-1加工時間矩陣i123456Pi1423142Pi2456745Pi3587555Pi4424331精選課件第二節(jié)流水作業(yè)排序問題一、最長流程時間Fmax的計算P2659表11-2順序下的加工時間矩陣P263[例11.1]有一個6/4/P/Fmax問題，其加工時間如表，當(dāng)按順序S=(6，1，5，2，4，3)加工時，求Fmax。表11-1加工時間矩陣i123456Pi1423142Pi2456745Pi3587555Pi4424331i615243Pi12246410212113316Pi257411415520727633Pi3512517522830535742Pi4113421325232338446精選課件表11-2順序下的加工時間矩陣P263[例11.1]有一60對于第1行第1列，只需把加工時間的數(shù)值作為完工時間標(biāo)在加工時間的右上角;對于第1行的其它元素，從左到右依次將前一列右上角的數(shù)字加上計算列的加工時間，將結(jié)果填在計算列加工時間的右上角。對于從第2行到第m行，只要把上一行右上角的數(shù)字和本行的加工時間相加，將結(jié)果填在加工時間的右上角；從第2列到第n列，則要從本行前一列右上角和本列上一行的右上角數(shù)字中取較大者，再和本列加工時間相加，將結(jié)果填在本列加工時間的右上角。這樣計算下去，最后一行的最后一列右上角數(shù)字，即為Fmax。Fmax的標(biāo)注完工時間的規(guī)則精選課件對于第1行第1列，只需把加工時間的數(shù)值作為完工時間標(biāo)在加61第二節(jié)流水作業(yè)排序問題二、n/2/F/Fmax問題的最優(yōu)算法對于n個工件1臺機(jī)器的排序問題，既適用于流程作業(yè),也適用于單件作業(yè)，在第三節(jié)單件作業(yè)排序討論。對于n/2/F/Fmax問題，S.M.Johson于1954年給出了有效的算法，即著名的Johson算法。其目標(biāo)是使從第一個工件開始到最后一個工件結(jié)束的總流程時間最短。精選課件第二節(jié)流水作業(yè)排序問題二、n/2/F/Fmax62

Johnson算法的步驟：列出所有工件在兩臺機(jī)器上的加工時間矩陣；從加工時間矩陣中找出最短的加工時間；若最短的加工時間出現(xiàn)在M1上，則對應(yīng)的工件往前排；如果最短的加工時間出現(xiàn)在M2上，則對應(yīng)的工件往后排；然后，劃去已經(jīng)排序的工件。若最短的加工時間有多個，則任選一個；當(dāng)所有的工件都已排序，停止計算，轉(zhuǎn)步驟①。二、n/2/F/Fmax問題的最優(yōu)算法精選課件Johnson算法的步驟：二、n/2/F/F63

P264[例11.2]按Johnson法求下表所示的6/2/F/Fmax問題的最優(yōu)解。i123456ai518534bi722474表11-3加工時間矩陣最優(yōu)加工順序為S=（2，5，6，1，4，3）最優(yōu)順序下的Fmax=28精選課件P264[例11.2]i123456ai5185364Johnson算法的變形步驟：將所有ai≤bi的工件按照ai值不減（遞升）的順序排列成一個序列A；將所有ai＞bi的工件按bi值不增（遞減）的順序排列成一個序列B；將A放到B之前，就構(gòu)成了最優(yōu)加工順序。精選課件Johnson算法的變形步驟：精選課件65

P264[例11.2]——Johnson算法的變形求下表所示的6/2/F/Fmax問題的最優(yōu)解。i123456ai518534bi722474表11-3加工時間矩陣序列A為（2,5,6,1），序列B為（4,3），則最優(yōu)序列為S=（2,5,6,1,4,3），與Johnson算法的結(jié)果一致。精選課件P264[例11.2]——Johnson算法的變66n/m/P/Fmax問題的啟發(fā)式算法啟發(fā)式算法（試探法）是一種能在可接受的費(fèi)用內(nèi)尋找最好的解的技術(shù)，但不一定能保證所得解的可行性和最優(yōu)性，甚至在多數(shù)情況下，無法闡述所得解同最優(yōu)解的近似程度。啟發(fā)式算法是解決NP問題（不確定性問題）的重要方法，由于其計算量都比較大，所以隨著計算機(jī)技術(shù)的發(fā)展，啟發(fā)式算法取得了巨大的成就。常見的啟發(fā)式算法有貪婪法、局部搜索法、退火算法、蟻群算法等。

精選課件n/m/P/Fmax問題的啟發(fā)式算法啟發(fā)式算法（67經(jīng)典算法與啟發(fā)式算法駕駛汽車到達(dá)某人的家，寫成算法是這樣的：沿長張高速公路北行至太子廟；從西北出口出來后往山上開4.5公里；在一個雜貨店旁邊的紅綠燈路口右轉(zhuǎn)，接著在第一個路口左轉(zhuǎn)；從左邊褐色大房子的車道進(jìn)去，就是桃源路714

號。用啟發(fā)式方法來描述則可能是這樣：找出上一次我們寄給你的信，照著信上面的寄出地址開車到這個鎮(zhèn)；到了之后你問一下我們的房子在哪里。這里每個人都認(rèn)識我們——肯定有人會很愿意幫助你的；如果你找不到人，那就找個公共電話亭給我們打電話，我們會出來接你。精選課件經(jīng)典算法與啟發(fā)式算法駕駛汽車到達(dá)某人的家，寫成算法是這樣的：68

1965年，D·S·Palmer提出按斜度指標(biāo)排列工件的啟發(fā)式算法，這種算法稱之為Palmer算法。其中工件斜度指標(biāo)可按下式計算：算出λi后，按λi不增（遞減）的順序排列工件，可得出較滿意的加工順序。三、一般n/m/P/Fmax問題的啟發(fā)式算法（一）Palmer（帕默）算法精選課件

1965年，D·S·Palmer提出按斜度指標(biāo)69（一）Palmer

算法P266[例11.3]有一個4/3/F/Fmax問題，用Palmer算法求解最優(yōu)加工順序。加工時間矩陣為：三、一般n/m/P/Fmax問題的啟發(fā)式算法i1234Pi11263Pi18429Pi14582精選課件（一）Palmer算法P266[例11.3]有一個4/370i1234Pi11263Pi18429Pi14582解：按照不增的順序，得到最優(yōu)加工順序(1,2,3,4)和(2,1,3,4)精選課件i1234Pi11263Pi18429Pi14582解：按照71（二）關(guān)鍵工件法步驟如下：

1.計算每個工件的總加工時間Pi=∑pij，找出加工時間最長的工件C（j=m），將其作為關(guān)鍵工件。

2.對于余下的工件，若Pi1≤Pim，則按Pi1不減的順序排列一個序列Sa；若Pi1>Pim，則按Pim不增的順序排成一個序列Sb。

3.加工順序（Sa，C，Sb）即為所求近優(yōu)解。例11.3i1234Pi11263Pi18429Pi14582精選課件（二）關(guān)鍵工件法步驟如下：i1234Pi11263Pi18472三、一般n/m/P/Fmax問題的啟發(fā)式算法（三）CDS算法

Campbell，Dudek，Smith三人提出了一個啟發(fā)式算法，簡稱CDS算法。他們把Johnson算法用于一般n/m/P/Fmax問題，得到（m-1）個加工順序，取其中優(yōu)者。對加工時間，按下列公式求和，即：當(dāng)l=1時,有兩種排序方式,用Johnson方法排序得到一個最優(yōu)排序；當(dāng)l=2時，又有兩種排序方法，用Johnson方法排序，得到又一個最優(yōu)排序；當(dāng)l=3,…，(m-1)，又可求出對應(yīng)的每一種排序方法。最后比較取得最優(yōu)解。精選課件三、一般n/m/P/Fmax問題的啟發(fā)式算法（73本次課小結(jié)相關(guān)名次術(shù)語（排序、編制作業(yè)計劃、派工、趕工、加工線路、加工順序）最長流程時間的計算n/2/F/Fmax問題的最優(yōu)算法（Johson算法）精選課件本次課小結(jié)相關(guān)名次術(shù)語（排序、編制作業(yè)計劃、派工、趕工、74§11.3單件作業(yè)排序問題一、問題的描述特點(diǎn)：每個工件都有其獨(dú)特的加工路線，工件沒有固定的流向問題的描述：描述一道工序，要用3個參數(shù)(i,j,k)，表示工件i的第j道工序在機(jī)器k上進(jìn)行。可以用加工描述矩陣來描述所有工件的加工精選課件§11.3單件作業(yè)排序問題特點(diǎn)：每個工件都有其獨(dú)特的75§11.3單件作業(yè)排序問題一、問題的描述可以用加工描述矩陣來描述所有工件的加工例如，一個2/3/G/Fmax問題：工序1工序2工序3工件1工件2精選課件§11.3單件作業(yè)排序問題可以用加工描述矩陣來描述所76二、三種作業(yè)計劃半能動作業(yè)計劃（Semi-activeschedule）各工序都按最早可能開（完）工時間安排的作業(yè)計劃能動作業(yè)計劃（Activeschedule）任何一臺機(jī)器的每段空閑時間都不足以加工一道可加工工序的半能動作業(yè)計劃無延遲作業(yè)計劃（Non-delayschedu1e）沒有任何延遲出現(xiàn)的能動作業(yè)計劃“延遲”：有工件等待加工時，機(jī)器出現(xiàn)空閑，即使這段空閑時間不足以完成一道工序精選課件二、三種作業(yè)計劃半能動作業(yè)計劃（Semi-activesc77能動作業(yè)計劃與無延遲作業(yè)計劃的生成符號說明將每安排一道工序稱作一“步”，設(shè)：｛St｝—第t步之前已排序工序構(gòu)成的部分作業(yè)計劃｛Ot｝—第t步可以排序的工序的集合

Tk—｛Ot｝中Ok的最早可能開工時間

T’k—｛Ot｝中Ok的最早可能完工時間精選課件能動作業(yè)計劃與無延遲作業(yè)計劃的生成符號說明精選課件78精選課件精選課件79P269例11.4

有一個2/3/G/Fmax問題，其加工描述矩陣D和加工時間矩陣T已知，求一個能動作業(yè)計劃。精選課件P269例11.4

有一個2/3/G/Fmax問題80精選課件精選課件81精選課件精選課件82精選課件精選課件83精選課件精選課件84精選課件精選課件85三、三類啟發(fā)式算法優(yōu)先調(diào)度法則隨機(jī)抽樣法概率調(diào)度法精選課件三、三類啟發(fā)式算法優(yōu)先調(diào)度法則精選課件861.優(yōu)先調(diào)度法則SPT（Shortestprocessingtime）法則優(yōu)先選擇加工時間最短的工序可使工件的平均流程時間最短，從而減少在制品量FCFS（Firstcomefirstserved）法則優(yōu)先選擇最早進(jìn)入可排工序集合的工件來自排隊論，對工件較公平EDD（Earliestduedate）法則優(yōu)先選擇完工期限緊的工件可使工件最大延誤時間最小MWKR（Mostworkremaining）法則優(yōu)先選擇余下加工時間最長的工件不同工作量的工件的完工時間盡量接近精選課件1.優(yōu)先調(diào)度法則SPT（Shortestprocessin871.優(yōu)先調(diào)度法則（續(xù)）LWKR（Leastworkremaining）法則優(yōu)先選擇余下加工時間最短的工件使工作量小的工件盡快完成MOPNR（Mostoperationsremaining）法則優(yōu)先選擇余下工序數(shù)最多的工件與MWKR法則類似，只不過考慮工件在不同機(jī)器上的轉(zhuǎn)運(yùn)排隊時間是主要的SCR（Smallestcriticalratio）法則優(yōu)先選擇臨界比最小的工件（臨界比：工件允許停留時間與工件余下加工時間之比）保證工件延誤最少RANDOM法則隨機(jī)地挑一個工件精選課件1.優(yōu)先調(diào)度法則（續(xù)）LWKR（Leas