第11章-制造業(yè)作業(yè)計劃與控制-《生產(chǎn)與運作管理》課件

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

第一節(jié)排序問題的基本概念第二節(jié)流水作業(yè)排序問題第三節(jié)單件作業(yè)排序問題第四節(jié)生產(chǎn)作業(yè)控制第十一章制造業(yè)作業(yè)計劃與控制第一節(jié)1第一節(jié)排序問題的基本概念一、名詞術(shù)語1．編制作業(yè)計劃（scheduling）：不僅包括確定工件的加工順序，而且還包括確定機器加工每個工件的開始時間和完成時間。2．排序（Sequencing）：只是確定工件在機器上的加工順序。

由于編制作業(yè)計劃的主要問題是確定各臺機器上工件的加工順序，而且，在通常情況下都是按最早可能開（完）工時間來編排作業(yè)計劃的，因此，當工件的加工順序確定之后，作業(yè)計劃也就確定了。正因為如此，人們常常不加區(qū)別地使用“排序”與“編制作業(yè)計劃”兩個術(shù)語。3．派工（Dispatching）:是按作業(yè)計劃的要求，將具體生產(chǎn)任務(wù)安排到具體的機床上加工，屬于我們經(jīng)常說的“調(diào)度”范圍。第一節(jié)排序問題的基本概念一、名詞術(shù)語2第一節(jié)排序問題的基本概念一、名詞術(shù)語4．趕工（Expediting）：是實際進度已落后于計劃進度時采取的行動，也屬于“調(diào)度”范圍。5．調(diào)度：是實行控制所采取的行動，是在加工制造發(fā)生之后的活動，是發(fā)現(xiàn)實際生產(chǎn)進度已經(jīng)偏離預(yù)定計劃而采取的調(diào)配資源的行動。調(diào)度的依據(jù)是作業(yè)計劃。

第一節(jié)排序問題的基本概念一、名詞術(shù)語3第一節(jié)排序問題的基本概念二、假設(shè)條件與符號說明（一）假設(shè)條件1.一個機器不能同時在幾臺不同的機器上加工。2.工件在加工過程中采取平行移動方式，即當上一道工序完工后，立即送下道工序加工。3.不允許中斷。當一個工件一旦開始加工，必須一直進行到完工，不得中途停止插入其它工作。4.每道只在一臺機器上完成。5.工件數(shù)、機器數(shù)和加工時間已知，加工時間與加工順序無關(guān)。6.每臺機器同時只能加工一個工件。第一節(jié)排序問題的基本概念二、假設(shè)條件與符號說明（一）假4第一節(jié)排序問題的基本概念（二）符號說明

Ji——工件i,i=1，2，……，n

Mj——機器j,j=1，2，……，mpij——Ji在Mj上的加工時間，Ji的總加工時間Pi＝∑pij

ri——Ji的到達時間，指Ji從外部進入車間，可以開始加工的最早時間。di——Ji的完工期限（即計劃完工期限）。Ci——Ji的完工時間，Ci＝ri＋∑（wij＋pij）＝ri＋Wi＋Pi

Cmax——最長完工時間，Cmax＝max{Ci}

Fi——Ji的流程時間，即工件在車間的實際停留時間，F(xiàn)i＝Ci－ri＝Wi＋Pi

第一節(jié)排序問題的基本概念（二）符號說明Ji——工件i5第一節(jié)排序問題的基本概念（二）符號說明

Fmax——最長流程時間，F(xiàn)max＝max{Fi}Li——工件的延長時間。Li＝Ci－di

wij——Ji在Mj上加工之前的等待時間。Wi——Ji在加工過程中總的等待時間，Wi＝∑wij

ai——Ji的允許停留時間，ai＝di－ri

Li＝Ci－di＝ri＋Wi＋Pi－di＝（Wi＋Pi）－（di－ri）＝Fi－ai

當Li>0（正延遲），說明Ji的實際完工時間超過了完工期限；當Li<0（負延遲），說明Ji提前完工；當Li＝0（零延遲），Ji按期完工。Lmax——最長延遲時間，Lmax＝max{Li}

第一節(jié)排序問題的基本概念（二）符號說明Fmax——最6第一節(jié)排序問題的基本概念三、排序問題的分類和表示法

（一）排序問題的表示法1．按機器的種類和數(shù)量不同（1）單臺機器的排序問題（不存在加工路線問題）（2）多臺機器的排序問題

按工件加工路線的特征，可以將多臺機器的排序問題分為：

★單件作業(yè)排序問題（工件的加工路線不同）

★流水作業(yè)排序問題（所有工件的加工路線完全相同）2．按工件到達車間的情況不同（1）靜態(tài)的排序問題（進行排序時，所有工件都已到達，可以一次對它們進行排序）

（2）動態(tài)的排序問題（若工件是陸續(xù)到達，要隨時安排它們的加工順序）第一節(jié)排序問題的基本概念三、排序問題的分類和表示法1．7第一節(jié)排序問題的基本概念三、排序問題的分類和表示法（一）排序問題的表示法3．按目標函數(shù)的性質(zhì)不同

※

如單臺機器的排序，按其目標：（1）平均流程時間最短（2）誤期完工工件數(shù)最少

※按目標函數(shù)的情況（1）單目標排序問題（2）多目標排序問題4．按參數(shù)的性質(zhì)可分為（1）確定型排序問題：指加工時間和其它有關(guān)參數(shù)是已知確定的量。（2）隨機型排序問題：指加工時間和有關(guān)參數(shù)為隨機變量。

第一節(jié)排序問題的基本概念三、排序問題的分類和表示法3．8第一節(jié)排序問題的基本概念

（二）排序問題的表示法

n/m/A/B其中，n為工件數(shù)；m為機器數(shù)。A為車間類型，在A的位置以“F”表示，則代表流水作業(yè)排序問題；若標以“P”，則表示流水作業(yè)排列排序問題；若標以“G”，則表示一般作業(yè)排序問題。當m＝1時，則A處為空白（單臺機器的排序，無所謂加工路線）。B為目標函數(shù)，通常是其值最小。

★流水作業(yè)排列排序問題（P）是流水作業(yè)排序問題（F）的特殊情況。

第一節(jié)排序問題的基本概念（二）排序問題的表示法9第二節(jié)流水作業(yè)排序問題

本節(jié)所討論的是一種特殊情況，即所有工件在各臺機器上加工順序都相同的情況。這就是排列排序問題。流水作業(yè)排列排序問題常被稱作“同順序”排序問題。第二節(jié)流水作業(yè)排序問題10第二節(jié)流水作業(yè)排序問題一、最長流程時間Fmax的計算1．討論的類型屬于n/m/P/Fmax2．目標函數(shù)：最長流程時間最短,Fmax最小。最長流程時間又稱作加工周期，它是從第一個工件在第一臺機器開始加工時算起，到最后一個工件在最后一臺機器上完成加工時為止所經(jīng)過的時間。由于假設(shè)所有工件的到達時間都為零（ri=0,i=1,2，…，n）所以，F(xiàn)max等于排在末位加工的工件在車間的停留時間，也等于一批工件的最長完工時間Cmax，即Fmax=Cmax。推導(dǎo)：∵Fi=Ci-ri又∵ri=o∴Fi=Ci

則Fmax=Cma

第二節(jié)流水作業(yè)排序問題一、最長流程時間Fmax的計算11第二節(jié)流水作業(yè)排序問題一、最長流程時間Fmax的計算

3、計算公式（1）C1si=C1Si－1+Psi1

Si在機器M1上的完工時間工件Si-1在機器M1上的完工時間工件Si在M1上的加工時間＝－（3）Fmax=CmSn（工件Sn在機器Mm上的完工時間，即最后個工件在最后一臺機器上的完工時間）（2）Cksi=max｛C(k－1)si,Cksi－1

｝+pksi

(k=2.3.…m,i=1,2，…n)

C(k－1)si———同一工件，前一機器的完工時間;

Cksi－1———前一工件，同一機器的完工時間;

pksi—工件Si在機器Mk上的加工時間

第二節(jié)流水作業(yè)排序問題一、最長流程時間Fmax的計算S12第二節(jié)流水作業(yè)排序問題

i123456pi1

pi2pi3pi4423142456745587555424331例11.1有一個6/4/P/Fmax問題，其加工時間如表11－1所示。如按順序S＝（6，1，5，2，4，3）加工，求Fmax。表11－1加工時間矩陣(p263)第二節(jié)流水作業(yè)排序問題i113第二節(jié)流水作業(yè)排序問題

i615243

pi1

pi2pi3pi4224641021211331657411415520727633512517522830535742

113421325232338446表11－2順序S下的加工時間矩陣(p263)第二節(jié)流水作業(yè)排序問題i614第二節(jié)流水作業(yè)排序問題二、n/2/F/Fmax問題的最優(yōu)算法

S．M．Johnson于1954年提出的算法。Johnson算法是建立在Johnson法則的基礎(chǔ)上。Johnson法則為：如果min(aibj)<min(aj,bi)則Ji應(yīng)該排在Jj之前。如果中間是等號，則工件i既可以排在工件j之前，也可以排在它之后。改進后的Johnson算法，其步驟：①將所有ai≤bi的工件按ai值不減的順序排成一個序列A（由小到大）；②將所有ai>bi的工件按bi值不增的順序排成一個序列B（由大到?。?；③將A放在B之前就構(gòu)成一個最有加工順序。

第二節(jié)流水作業(yè)排序問題二、n/2/F/Fmax問題的最15第二節(jié)流水作業(yè)排序問題

i

123456

ai

bi518534722474例11.2求表11－3所示的6/2/F/Fmax問題的最優(yōu)解表11－3加工時間矩陣最優(yōu)順序（2，5，6，1，4，3）第二節(jié)流水作業(yè)排序問題i116第二節(jié)流水作業(yè)排序問題三、一般n/m/p/Fmax問題的啟發(fā)式算法1、Palmer法：

λi=[k－(m+1)/2]pikk=1,2,…,mm為機器數(shù)，pik為工件i在Mk上的加工時間。按照各工件λi不增的順序排列工件，可以得出令人滿意的順序。第二節(jié)流水作業(yè)排序問題三、一般n/m/p/Fmax問題17第二節(jié)流水作業(yè)排序問題

i

1234

pi1

Pi2

pi3

1263

8429

45821、Palmer法：

例11.3有一個4/3/P/Fmax問題，其加工時間如表11－5所示，用Palmer法求解表11－5加工時間矩陣（p266)由λi不增可得（1，2，3，4）和（2，1，3，4）第二節(jié)流水作業(yè)排序問題i118第二節(jié)流水作業(yè)排序問題2、關(guān)鍵工件法：關(guān)鍵工件法是陳榮秋1983年提出的一種啟發(fā)式算法。步驟：（1）計算每個工件的總加工時間Pi＝∑pij，找出加工時間最長的工件C（j＝m），將其作為關(guān)鍵工件。（2）對余下的工件，若pi1≤pim，則按pi1不減（由小到大）的順序排成一個序列Sa；若pi1>pim，則按pim不增（由大到?。┑捻樞蚺懦梢粋€序列Sb。（3）順序（Sa，C，Sb）即為所求順序。

第二節(jié)流水作業(yè)排序問題2、關(guān)鍵工件法：19第二節(jié)流水作業(yè)排序問題

i

1234

pi1

Pi2

pi3

pi

1263

8429

458213111614表11－6用關(guān)鍵工件法求解（p267)加工順序為（1，2，3，4）2、關(guān)鍵工件法：第二節(jié)流水作業(yè)排序問題i120第二節(jié)流水作業(yè)排序問題

3、CDS法：Campbell,Dudek,Smith三人提出的一種啟發(fā)式算法，簡稱CDS法。具體做法：

對加工時間和

用Johnson算法求（m-1）次加工順序，取其中最好的結(jié)果。（l=1,2,…,m-1），第二節(jié)流水作業(yè)排序問題3、CDS法：21第二節(jié)流水作業(yè)排序問題

i1234l＝1pi11263pi34582l＝2Pi1＋Pi296812Pi2＋pi312910113、CDS法：表11－7用CDS法求解（p267)當l＝1時，（1，2，3，4）；當l=2時，（2，3，1，4）第二節(jié)流水作業(yè)排序問題i22

第三節(jié)單件作業(yè)排序問題一、問題的描述1．對于一般單件作業(yè)的排序問題，每個工件都有其獨特的加工路線，工件沒有一定的流向。2．每一道工序要用3個參數(shù)來描述：i表示工件代號j表示工序號k表示完成工件的第j道工序的機器代號。3．可以用加工描述矩陣的形式來描述所有工件的加工。（D＝1,1,11,2,31,3,22,1,32,2,12,3,2)M1—M3—M2M3—M1—M2第三節(jié)單件作業(yè)排序問題一、問題的描23第三節(jié)單件作業(yè)排序問題二、一般n/m/G/Fmax問題的啟發(fā)式算法（一）兩種作業(yè)計劃的構(gòu)成

★半能動作業(yè)計劃：在可行的加工順序下，可以作出無數(shù)種作業(yè)計劃。其中，各工序都按最早可能開（完）工時間安排的作業(yè)計劃稱半能動作業(yè)計劃?！锬軇幼鳂I(yè)計劃：任何一臺機器的每段空閑時間都不足以加工一道可加工工序的半能動作業(yè)計劃。

★無延遲作業(yè)計劃：沒有任何延遲出現(xiàn)的能動作業(yè)計劃。所謂“延遲”指有工件等待加工時，機器出現(xiàn)空閑，即使這段空閑時間不足以完成一道工序。

第三節(jié)單件作業(yè)排序問題二、一般n/m/G/Fmax問題24第三節(jié)單件作業(yè)排序問題1．能動作業(yè)計劃的構(gòu)成步驟

（1）設(shè)t=1，{S1}為空集，{O1}為個工件第一道工序的集合。（2）求T*=min{T′k}，并求出T*出現(xiàn)的機器M*。如果M*有多臺，則任選一臺。（3）從{Ot}中挑出滿足以下兩個條件的工序Oj：需要機器M*加工，且Tj<T*。（4）將確定的工序Oj放入{St}，從{Ot}中消去Oj，并將Oj的緊后工序放入{Ot}，使t=t+1。（5）若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止。

二、一般n/m/G/Fmax問題的啟發(fā)式算法（一）兩種作業(yè)計劃的構(gòu)成第三節(jié)單件作業(yè)排序問題1．能動作業(yè)計劃的構(gòu)成步驟（125第三節(jié)單件作業(yè)排序問題1．能動作業(yè)計劃的構(gòu)成步驟

通過例題講授

D＝1,1,11,2,31,3,22,1,32,2,12,3,2)(T＝（2,4,13,4,5)t{Ot}TkTk'T*M*Oj11,1,12,1,30023

2M11,1,121,2,32,1,3

20633M32,1,331,2,32,2,133777

M3M11,2,341,3,22,2,173877M12,2,151,3,22,3,2778128M21,3,262,3,281313M2

2,3,2表11－8能動作業(yè)計劃的構(gòu)成（p270）第三節(jié)單件作業(yè)排序問題1．能動作業(yè)計劃的構(gòu)成步驟D＝126第三節(jié)單件作業(yè)排序問題

（1）t=1，{S1}為空集，{O1}為各工件第一道工序的集合。（2）求T*=min{Tk}，并求出T*出現(xiàn)的機器M*。如果M*有多臺，則任選一臺。（3）{Ot}中挑出滿足以下兩個條件的工序Oj：需要機器M*加工，且Tj＝T*。（4）將確定的工序Oj放入{St}，從{Ot}中消去Oj，并將Oj的緊后工序放入{Ot}，使t=t+1。（5）若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止。

2．無延遲作業(yè)計劃的構(gòu)成步驟（一）兩種作業(yè)計劃的構(gòu)成二、一般n/m/G/Fmax問題的啟發(fā)式算法第三節(jié)單件作業(yè)排序問題（1）t=1，{S1}為空集27第三節(jié)單件作業(yè)排序問題2．無延遲作業(yè)計劃的構(gòu)成步驟

通過例題講授

D＝1,1,11,2,31,3,22,1,32,2,12,3,2)(T＝（2,4,13,4,5)t{Ot}TkTk'T*M*Oj11,1,12,1,30023

00

M1

M31,1,121,2,32,1,3

2063

0

M32,1,331,2,32,2,13377

33

M3M11,2,341,3,22,2,17387

3

M12,2,151,3,22,3,277812

77

M2M22,3,261,3,21213

12

M2

1,3,2表11－9能動作業(yè)計劃的構(gòu)成（p271）第三節(jié)單件作業(yè)排序問題2．無延遲作業(yè)計劃的構(gòu)成步驟D＝28第三節(jié)單件作業(yè)排序問題（二）三類啟發(fā)式算法

二、一般n/m/G/Fmax問題的啟發(fā)式算法1．優(yōu)先調(diào)度法則按優(yōu)先調(diào)度法則挑選工序比隨意挑選一道工序的方法更能符合計劃編制者的要求，同時，又不必列出所有可能的作業(yè)計劃，從而計算量比較小。

第三節(jié)單件作業(yè)排序問題（二）三類啟發(fā)式算法二、一般n29優(yōu)先調(diào)度法則內(nèi)容特點（1）SPT法則：優(yōu)先選擇加工時間最短的工序；可使工件的平均流程時間最短，減少在制品量（2）FCFS法則：優(yōu)先選擇最早進入可排工序集合的工件；來自排隊論，它對工件較公平（3）EDD法則：優(yōu)先選擇完工期限緊的工件（di）可使工件最大延誤時間最小。（4）MWKR法則：優(yōu)先選擇余下加工時間最長的工件；使不同工作量的工件的完工時間盡量接近（5）LWKR法則：優(yōu)先選擇余下加工時間最短的工件；使工作量小的工件盡快完成（6）MOPNR法則：優(yōu)先選擇余下工序數(shù)最多的工件；與MWKR法則類似，只不過考慮工件在不同機器上的轉(zhuǎn)運排隊時間是主要的。（7）SCR法則：優(yōu)先選擇臨界比最小的工件（臨界比為工序允許停留的時間（ai）與工件余下加工時間之比）保證工件延誤最少（8）RANDOM法則：隨機地挑選一個工件

優(yōu)先調(diào)度法則內(nèi)容特點（1）SPT法則：優(yōu)先30第三節(jié)單件作業(yè)排序問題2．隨機抽樣法（1）隨機抽樣法介于窮舉法或分支定界法與優(yōu)先調(diào)度法則之間；（2）應(yīng)用隨機抽樣法時，實際上是對同一個問題多次運用RANDOM法則來決定要挑選的工序。（3）隨機抽樣法的效果與樣本大小有關(guān)。（4）隨即抽樣法比優(yōu)先調(diào)度法則得到的結(jié)果要好一些。

二、一般n/m/G/Fmax問題的啟發(fā)式算法（二）三類啟發(fā)式算法3．概率調(diào)度法（1）給不同的工序按某一優(yōu)先調(diào)度法則分配不同的挑選概率，這樣就可以得到多個作業(yè)計劃供比較。（2）試驗表明，概率調(diào)度法比隨機抽樣法更為有效。第三節(jié)單件作業(yè)排序問題2．隨機抽樣法二、一般n/m/G31第四節(jié)生產(chǎn)作業(yè)控制一、實行生產(chǎn)作業(yè)控制的原因和條件

1．實行生產(chǎn)作業(yè)控制的原因（1）加工時間估計不準確：加工時間是編制作業(yè)計劃的依據(jù)；單件小批生產(chǎn)的任務(wù)往往是一次性的（或是第一次）。（2）隨機因素的影響：如工人的態(tài)度、技能、缺勤、設(shè)備故障、原材料差異或缺陷。（3）加工路線的多樣性：不同的加工路線會造成完成時間的偏離。（4）企業(yè)環(huán)境的動態(tài)性。

2．實施生產(chǎn)控制的條件（1）要有一個標準，標準即生產(chǎn)計劃和生產(chǎn)作業(yè)計劃；（2）要取得實際生產(chǎn)進度與計劃偏離的信息（控制離不開信息）；（3）要采取糾正偏差的行動（通過調(diào)度來實現(xiàn)）。

第四節(jié)生產(chǎn)作業(yè)控制一、實行生產(chǎn)作業(yè)控制的原因和條件32第四節(jié)生產(chǎn)作業(yè)控制二、不同生產(chǎn)類型生產(chǎn)控制的特點（一）單件小批生產(chǎn)1．單件小批生產(chǎn)主要特點（1）產(chǎn)品品種千差萬別，零件種類繁多；（2）每個零件都有其特定的加工路線，整個物流沒有什么主流；（3）各種零件都在不同的機器前面排隊等待加工；（4）各個工作地之間的聯(lián)系不是固定的。2．工件的生產(chǎn)提前期（1）移動時間：取決于運輸工具和運輸距離，相對穩(wěn)定；（2）排隊時間：單個工件的排隊時間是優(yōu)先權(quán)的函數(shù)，所有工件的平均排隊時間與計劃調(diào)度的水平有關(guān)；（3）調(diào)整準備時間：與技術(shù)和現(xiàn)場組織管理水平有關(guān)；（4）加工時間：取決于采用的加工技術(shù)和工人的熟練程度，它與計劃調(diào)度方法無關(guān)；（5）等待運輸時間：與計劃調(diào)度工作有關(guān)。第四節(jié)生產(chǎn)作業(yè)控制二、不同生產(chǎn)類型生產(chǎn)控制的特點33第四節(jié)生產(chǎn)作業(yè)控制（二）大量大批生產(chǎn)1．每個工件的加工順序都是確定的，沒有排隊現(xiàn)象，沒有派工問題，也無優(yōu)先權(quán)問題。2．通過改變工作班次，調(diào)整工作時間和工人數(shù)來控制生產(chǎn)。三、利用“漏斗模型”進行生產(chǎn)控制（一）輸入輸出圖（二）基本公式（三）控制規(guī)則

3．生產(chǎn)控制的重點（解決的主要問題）控制排隊的隊長——控制排隊時間（排隊時間越長，在制品庫存就越高）；控制方法：輸入/輸出控制；二、不同生產(chǎn)類型生產(chǎn)控制的特點（一）單件小批生產(chǎn)第四節(jié)生產(chǎn)作業(yè)控制（二）大量大批生產(chǎn)3．生產(chǎn)控制的34第11章-制造業(yè)作業(yè)計劃與控制-《生產(chǎn)與運作管理》課件35第11章-制造業(yè)作業(yè)計劃與控制-《生產(chǎn)與運作管理》課件36第11章-制造業(yè)作業(yè)計劃與控制-《生產(chǎn)與運作管理》課件37第11章-制造業(yè)作業(yè)計劃與控制-《生產(chǎn)與運作管理》課件38第11章-制造業(yè)作業(yè)計劃與控制-《生產(chǎn)與運作管理》課件39第11章-制造業(yè)作業(yè)計劃與控制-《生產(chǎn)與運作管理》課件40第11章-制造業(yè)作業(yè)計劃與控制-《生產(chǎn)與運作管理》課件41第11章-制造業(yè)作業(yè)計劃與控制-《生產(chǎn)與運作管理》課件42第11章-制造業(yè)作業(yè)計劃與控制-《生產(chǎn)與運作管理》課件43第11章-制造業(yè)作業(yè)計劃與控制-《生產(chǎn)與運作管理》課件44第11章-制造業(yè)作業(yè)計劃與控制-《生產(chǎn)與運作管理》課件45第十一章制造業(yè)作業(yè)計劃與控制

第一節(jié)排序問題的基本概念第二節(jié)流水作業(yè)排序問題第三節(jié)單件作業(yè)排序問題第四節(jié)生產(chǎn)作業(yè)控制第十一章制造業(yè)作業(yè)計劃與控制第一節(jié)46第一節(jié)排序問題的基本概念一、名詞術(shù)語1．編制作業(yè)計劃（scheduling）：不僅包括確定工件的加工順序，而且還包括確定機器加工每個工件的開始時間和完成時間。2．排序（Sequencing）：只是確定工件在機器上的加工順序。

由于編制作業(yè)計劃的主要問題是確定各臺機器上工件的加工順序，而且，在通常情況下都是按最早可能開（完）工時間來編排作業(yè)計劃的，因此，當工件的加工順序確定之后，作業(yè)計劃也就確定了。正因為如此，人們常常不加區(qū)別地使用“排序”與“編制作業(yè)計劃”兩個術(shù)語。3．派工（Dispatching）:是按作業(yè)計劃的要求，將具體生產(chǎn)任務(wù)安排到具體的機床上加工，屬于我們經(jīng)常說的“調(diào)度”范圍。第一節(jié)排序問題的基本概念一、名詞術(shù)語47第一節(jié)排序問題的基本概念一、名詞術(shù)語4．趕工（Expediting）：是實際進度已落后于計劃進度時采取的行動，也屬于“調(diào)度”范圍。5．調(diào)度：是實行控制所采取的行動，是在加工制造發(fā)生之后的活動，是發(fā)現(xiàn)實際生產(chǎn)進度已經(jīng)偏離預(yù)定計劃而采取的調(diào)配資源的行動。調(diào)度的依據(jù)是作業(yè)計劃。

第一節(jié)排序問題的基本概念一、名詞術(shù)語48第一節(jié)排序問題的基本概念二、假設(shè)條件與符號說明（一）假設(shè)條件1.一個機器不能同時在幾臺不同的機器上加工。2.工件在加工過程中采取平行移動方式，即當上一道工序完工后，立即送下道工序加工。3.不允許中斷。當一個工件一旦開始加工，必須一直進行到完工，不得中途停止插入其它工作。4.每道只在一臺機器上完成。5.工件數(shù)、機器數(shù)和加工時間已知，加工時間與加工順序無關(guān)。6.每臺機器同時只能加工一個工件。第一節(jié)排序問題的基本概念二、假設(shè)條件與符號說明（一）假49第一節(jié)排序問題的基本概念（二）符號說明

Ji——工件i,i=1，2，……，n

Mj——機器j,j=1，2，……，mpij——Ji在Mj上的加工時間，Ji的總加工時間Pi＝∑pij

ri——Ji的到達時間，指Ji從外部進入車間，可以開始加工的最早時間。di——Ji的完工期限（即計劃完工期限）。Ci——Ji的完工時間，Ci＝ri＋∑（wij＋pij）＝ri＋Wi＋Pi

Cmax——最長完工時間，Cmax＝max{Ci}

Fi——Ji的流程時間，即工件在車間的實際停留時間，F(xiàn)i＝Ci－ri＝Wi＋Pi

第一節(jié)排序問題的基本概念（二）符號說明Ji——工件i50第一節(jié)排序問題的基本概念（二）符號說明

Fmax——最長流程時間，F(xiàn)max＝max{Fi}Li——工件的延長時間。Li＝Ci－di

wij——Ji在Mj上加工之前的等待時間。Wi——Ji在加工過程中總的等待時間，Wi＝∑wij

ai——Ji的允許停留時間，ai＝di－ri

Li＝Ci－di＝ri＋Wi＋Pi－di＝（Wi＋Pi）－（di－ri）＝Fi－ai

當Li>0（正延遲），說明Ji的實際完工時間超過了完工期限；當Li<0（負延遲），說明Ji提前完工；當Li＝0（零延遲），Ji按期完工。Lmax——最長延遲時間，Lmax＝max{Li}

第一節(jié)排序問題的基本概念（二）符號說明Fmax——最51第一節(jié)排序問題的基本概念三、排序問題的分類和表示法

（一）排序問題的表示法1．按機器的種類和數(shù)量不同（1）單臺機器的排序問題（不存在加工路線問題）（2）多臺機器的排序問題

按工件加工路線的特征，可以將多臺機器的排序問題分為：

★單件作業(yè)排序問題（工件的加工路線不同）

★流水作業(yè)排序問題（所有工件的加工路線完全相同）2．按工件到達車間的情況不同（1）靜態(tài)的排序問題（進行排序時，所有工件都已到達，可以一次對它們進行排序）

（2）動態(tài)的排序問題（若工件是陸續(xù)到達，要隨時安排它們的加工順序）第一節(jié)排序問題的基本概念三、排序問題的分類和表示法1．52第一節(jié)排序問題的基本概念三、排序問題的分類和表示法（一）排序問題的表示法3．按目標函數(shù)的性質(zhì)不同

※

如單臺機器的排序，按其目標：（1）平均流程時間最短（2）誤期完工工件數(shù)最少

※按目標函數(shù)的情況（1）單目標排序問題（2）多目標排序問題4．按參數(shù)的性質(zhì)可分為（1）確定型排序問題：指加工時間和其它有關(guān)參數(shù)是已知確定的量。（2）隨機型排序問題：指加工時間和有關(guān)參數(shù)為隨機變量。

第一節(jié)排序問題的基本概念三、排序問題的分類和表示法3．53第一節(jié)排序問題的基本概念

（二）排序問題的表示法

n/m/A/B其中，n為工件數(shù)；m為機器數(shù)。A為車間類型，在A的位置以“F”表示，則代表流水作業(yè)排序問題；若標以“P”，則表示流水作業(yè)排列排序問題；若標以“G”，則表示一般作業(yè)排序問題。當m＝1時，則A處為空白（單臺機器的排序，無所謂加工路線）。B為目標函數(shù)，通常是其值最小。

★流水作業(yè)排列排序問題（P）是流水作業(yè)排序問題（F）的特殊情況。

第一節(jié)排序問題的基本概念（二）排序問題的表示法54第二節(jié)流水作業(yè)排序問題

本節(jié)所討論的是一種特殊情況，即所有工件在各臺機器上加工順序都相同的情況。這就是排列排序問題。流水作業(yè)排列排序問題常被稱作“同順序”排序問題。第二節(jié)流水作業(yè)排序問題55第二節(jié)流水作業(yè)排序問題一、最長流程時間Fmax的計算1．討論的類型屬于n/m/P/Fmax2．目標函數(shù)：最長流程時間最短,Fmax最小。最長流程時間又稱作加工周期，它是從第一個工件在第一臺機器開始加工時算起，到最后一個工件在最后一臺機器上完成加工時為止所經(jīng)過的時間。由于假設(shè)所有工件的到達時間都為零（ri=0,i=1,2，…，n）所以，F(xiàn)max等于排在末位加工的工件在車間的停留時間，也等于一批工件的最長完工時間Cmax，即Fmax=Cmax。推導(dǎo)：∵Fi=Ci-ri又∵ri=o∴Fi=Ci

則Fmax=Cma

第二節(jié)流水作業(yè)排序問題一、最長流程時間Fmax的計算56第二節(jié)流水作業(yè)排序問題一、最長流程時間Fmax的計算

3、計算公式（1）C1si=C1Si－1+Psi1

Si在機器M1上的完工時間工件Si-1在機器M1上的完工時間工件Si在M1上的加工時間＝－（3）Fmax=CmSn（工件Sn在機器Mm上的完工時間，即最后個工件在最后一臺機器上的完工時間）（2）Cksi=max｛C(k－1)si,Cksi－1

｝+pksi

(k=2.3.…m,i=1,2，…n)

C(k－1)si———同一工件，前一機器的完工時間;

Cksi－1———前一工件，同一機器的完工時間;

pksi—工件Si在機器Mk上的加工時間

第二節(jié)流水作業(yè)排序問題一、最長流程時間Fmax的計算S57第二節(jié)流水作業(yè)排序問題

i123456pi1

pi2pi3pi4423142456745587555424331例11.1有一個6/4/P/Fmax問題，其加工時間如表11－1所示。如按順序S＝（6，1，5，2，4，3）加工，求Fmax。表11－1加工時間矩陣(p263)第二節(jié)流水作業(yè)排序問題i158第二節(jié)流水作業(yè)排序問題

i615243

pi1

pi2pi3pi4224641021211331657411415520727633512517522830535742

113421325232338446表11－2順序S下的加工時間矩陣(p263)第二節(jié)流水作業(yè)排序問題i659第二節(jié)流水作業(yè)排序問題二、n/2/F/Fmax問題的最優(yōu)算法

S．M．Johnson于1954年提出的算法。Johnson算法是建立在Johnson法則的基礎(chǔ)上。Johnson法則為：如果min(aibj)<min(aj,bi)則Ji應(yīng)該排在Jj之前。如果中間是等號，則工件i既可以排在工件j之前，也可以排在它之后。改進后的Johnson算法，其步驟：①將所有ai≤bi的工件按ai值不減的順序排成一個序列A（由小到大）；②將所有ai>bi的工件按bi值不增的順序排成一個序列B（由大到小）；③將A放在B之前就構(gòu)成一個最有加工順序。

第二節(jié)流水作業(yè)排序問題二、n/2/F/Fmax問題的最60第二節(jié)流水作業(yè)排序問題

i

123456

ai

bi518534722474例11.2求表11－3所示的6/2/F/Fmax問題的最優(yōu)解表11－3加工時間矩陣最優(yōu)順序（2，5，6，1，4，3）第二節(jié)流水作業(yè)排序問題i161第二節(jié)流水作業(yè)排序問題三、一般n/m/p/Fmax問題的啟發(fā)式算法1、Palmer法：

λi=[k－(m+1)/2]pikk=1,2,…,mm為機器數(shù)，pik為工件i在Mk上的加工時間。按照各工件λi不增的順序排列工件，可以得出令人滿意的順序。第二節(jié)流水作業(yè)排序問題三、一般n/m/p/Fmax問題62第二節(jié)流水作業(yè)排序問題

i

1234

pi1

Pi2

pi3

1263

8429

45821、Palmer法：

例11.3有一個4/3/P/Fmax問題，其加工時間如表11－5所示，用Palmer法求解表11－5加工時間矩陣（p266)由λi不增可得（1，2，3，4）和（2，1，3，4）第二節(jié)流水作業(yè)排序問題i163第二節(jié)流水作業(yè)排序問題2、關(guān)鍵工件法：關(guān)鍵工件法是陳榮秋1983年提出的一種啟發(fā)式算法。步驟：（1）計算每個工件的總加工時間Pi＝∑pij，找出加工時間最長的工件C（j＝m），將其作為關(guān)鍵工件。（2）對余下的工件，若pi1≤pim，則按pi1不減（由小到大）的順序排成一個序列Sa；若pi1>pim，則按pim不增（由大到?。┑捻樞蚺懦梢粋€序列Sb。（3）順序（Sa，C，Sb）即為所求順序。

第二節(jié)流水作業(yè)排序問題2、關(guān)鍵工件法：64第二節(jié)流水作業(yè)排序問題

i

1234

pi1

Pi2

pi3

pi

1263

8429

458213111614表11－6用關(guān)鍵工件法求解（p267)加工順序為（1，2，3，4）2、關(guān)鍵工件法：第二節(jié)流水作業(yè)排序問題i165第二節(jié)流水作業(yè)排序問題

3、CDS法：Campbell,Dudek,Smith三人提出的一種啟發(fā)式算法，簡稱CDS法。具體做法：

對加工時間和

用Johnson算法求（m-1）次加工順序，取其中最好的結(jié)果。（l=1,2,…,m-1），第二節(jié)流水作業(yè)排序問題3、CDS法：66第二節(jié)流水作業(yè)排序問題

i1234l＝1pi11263pi34582l＝2Pi1＋Pi296812Pi2＋pi312910113、CDS法：表11－7用CDS法求解（p267)當l＝1時，（1，2，3，4）；當l=2時，（2，3，1，4）第二節(jié)流水作業(yè)排序問題i67

第三節(jié)單件作業(yè)排序問題一、問題的描述1．對于一般單件作業(yè)的排序問題，每個工件都有其獨特的加工路線，工件沒有一定的流向。2．每一道工序要用3個參數(shù)來描述：i表示工件代號j表示工序號k表示完成工件的第j道工序的機器代號。3．可以用加工描述矩陣的形式來描述所有工件的加工。（D＝1,1,11,2,31,3,22,1,32,2,12,3,2)M1—M3—M2M3—M1—M2第三節(jié)單件作業(yè)排序問題一、問題的描68第三節(jié)單件作業(yè)排序問題二、一般n/m/G/Fmax問題的啟發(fā)式算法（一）兩種作業(yè)計劃的構(gòu)成

★半能動作業(yè)計劃：在可行的加工順序下，可以作出無數(shù)種作業(yè)計劃。其中，各工序都按最早可能開（完）工時間安排的作業(yè)計劃稱半能動作業(yè)計劃?！锬軇幼鳂I(yè)計劃：任何一臺機器的每段空閑時間都不足以加工一道可加工工序的半能動作業(yè)計劃。

★無延遲作業(yè)計劃：沒有任何延遲出現(xiàn)的能動作業(yè)計劃。所謂“延遲”指有工件等待加工時，機器出現(xiàn)空閑，即使這段空閑時間不足以完成一道工序。

第三節(jié)單件作業(yè)排序問題二、一般n/m/G/Fmax問題69第三節(jié)單件作業(yè)排序問題1．能動作業(yè)計劃的構(gòu)成步驟

（1）設(shè)t=1，{S1}為空集，{O1}為個工件第一道工序的集合。（2）求T*=min{T′k}，并求出T*出現(xiàn)的機器M*。如果M*有多臺，則任選一臺。（3）從{Ot}中挑出滿足以下兩個條件的工序Oj：需要機器M*加工，且Tj<T*。（4）將確定的工序Oj放入{St}，從{Ot}中消去Oj，并將Oj的緊后工序放入{Ot}，使t=t+1。（5）若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止。

二、一般n/m/G/Fmax問題的啟發(fā)式算法（一）兩種作業(yè)計劃的構(gòu)成第三節(jié)單件作業(yè)排序問題1．能動作業(yè)計劃的構(gòu)成步驟（170第三節(jié)單件作業(yè)排序問題1．能動作業(yè)計劃的構(gòu)成步驟

通過例題講授

D＝1,1,11,2,31,3,22,1,32,2,12,3,2)(T＝（2,4,13,4,5)t{Ot}TkTk'T*M*Oj11,1,12,1,30023

2M11,1,121,2,32,1,3

20633M32,1,331,2,32,2,133777

M3M11,2,341,3,22,2,173877M12,2,151,3,22,3,2778128M21,3,262,3,281313M2

2,3,2表11－8能動作業(yè)計劃的構(gòu)成（p270）第三節(jié)單件作業(yè)排序問題1．能動作業(yè)計劃的構(gòu)成步驟D＝171第三節(jié)單件作業(yè)排序問題

（1）t=1，{S1}為空集，{O1}為各工件第一道工序的集合。（2）求T*=min{Tk}，并求出T*出現(xiàn)的機器M*。如果M*有多臺，則任選一臺。（3）{Ot}中挑出滿足以下兩個條件的工序Oj：需要機器M*加工，且Tj＝T*。（4）將確定的工序Oj放入{St}，從{Ot}中消去Oj，并將Oj的緊后工序放入{Ot}，使t=t+1。（5）若還有未安排的工序，轉(zhuǎn)步驟（2）；否則，停止。

2．無延遲作業(yè)計劃的構(gòu)成步驟（一）兩種作業(yè)計劃的構(gòu)成二、一般n/m/G/Fmax問題的啟發(fā)式算法第三節(jié)單件作業(yè)排序問題（1）t=1，{S1}為空集72第三節(jié)單件作業(yè)排序問題2．無延遲作業(yè)計劃的構(gòu)成步驟

通過例題講授

D＝1,1,11,2,31,3,22,1,32,2,12,3,2)(T＝（2,4,13,4,5)t{Ot}TkTk'T*M*Oj11,1,12,1,30023

00

M1

M31,1,121,2,32,1,3

2063

0

M32,1,331,2,32,2,13377

33

M3M11,2,341,3,22,2,173