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

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

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

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

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

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

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

ri——Ji的到達(dá)時(shí)間，指Ji從外部進(jìn)入車(chē)間，可以開(kāi)始加工的最早時(shí)間。di——Ji的完工期限（即計(jì)劃完工期限）。Ci——Ji的完工時(shí)間，Ci＝ri＋∑（wij＋pij）＝ri＋Wi＋Pi

Cmax——最長(zhǎng)完工時(shí)間，Cmax＝max{Ci}

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

第一節(jié)排序問(wèn)題的基本概念（二）符號(hào)說(shuō)明Ji——工件i5第一節(jié)排序問(wèn)題的基本概念（二）符號(hào)說(shuō)明

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

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

ai——Ji的允許停留時(shí)間，ai＝di－ri

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

當(dāng)Li>0（正延遲），說(shuō)明Ji的實(shí)際完工時(shí)間超過(guò)了完工期限；當(dāng)Li<0（負(fù)延遲），說(shuō)明Ji提前完工；當(dāng)Li＝0（零延遲），Ji按期完工。Lmax——最長(zhǎng)延遲時(shí)間，Lmax＝max{Li}

第一節(jié)排序問(wèn)題的基本概念（二）符號(hào)說(shuō)明Fmax——最6第一節(jié)排序問(wèn)題的基本概念三、排序問(wèn)題的分類(lèi)和表示法

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

按工件加工路線的特征，可以將多臺(tái)機(jī)器的排序問(wèn)題分為：

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

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

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

※

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

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

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

（二）排序問(wèn)題的表示法

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

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

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

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

則Fmax=Cma

第二節(jié)流水作業(yè)排序問(wèn)題一、最長(zhǎng)流程時(shí)間Fmax的計(jì)算11第二節(jié)流水作業(yè)排序問(wèn)題一、最長(zhǎng)流程時(shí)間Fmax的計(jì)算

3、計(jì)算公式（1）C1si=C1Si－1+Psi1

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

｝+pksi

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

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

Cksi－1———前一工件，同一機(jī)器的完工時(shí)間;

pksi—工件Si在機(jī)器Mk上的加工時(shí)間

第二節(jié)流水作業(yè)排序問(wèn)題一、最長(zhǎng)流程時(shí)間Fmax的計(jì)算S12第二節(jié)流水作業(yè)排序問(wèn)題

i123456pi1

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

i615243

pi1

pi2pi3pi4224641021211331657411415520727633512517522830535742

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

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

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

i

123456

ai

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

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

i

1234

pi1

Pi2

pi3

1263

8429

45821、Palmer法：

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

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

i

1234

pi1

Pi2

pi3

pi

1263

8429

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

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

對(duì)加工時(shí)間和

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

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

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

★半能動(dòng)作業(yè)計(jì)劃：在可行的加工順序下，可以作出無(wú)數(shù)種作業(yè)計(jì)劃。其中，各工序都按最早可能開(kāi)（完）工時(shí)間安排的作業(yè)計(jì)劃稱(chēng)半能動(dòng)作業(yè)計(jì)劃?！锬軇?dòng)作業(yè)計(jì)劃：任何一臺(tái)機(jī)器的每段空閑時(shí)間都不足以加工一道可加工工序的半能動(dòng)作業(yè)計(jì)劃。

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

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

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

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

通過(guò)例題講授

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能動(dòng)作業(yè)計(jì)劃的構(gòu)成（p270）第三節(jié)單件作業(yè)排序問(wèn)題1．能動(dòng)作業(yè)計(jì)劃的構(gòu)成步驟D＝126第三節(jié)單件作業(yè)排序問(wèn)題

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

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

通過(guò)例題講授

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能動(dòng)作業(yè)計(jì)劃的構(gòu)成（p271）第三節(jié)單件作業(yè)排序問(wèn)題2．無(wú)延遲作業(yè)計(jì)劃的構(gòu)成步驟D＝28第三節(jié)單件作業(yè)排序問(wèn)題（二）三類(lèi)啟發(fā)式算法

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

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

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

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

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

2．實(shí)施生產(chǎn)控制的條件（1）要有一個(gè)標(biāo)準(zhǔn)，標(biāo)準(zhǔn)即生產(chǎn)計(jì)劃和生產(chǎn)作業(yè)計(jì)劃；（2）要取得實(shí)際生產(chǎn)進(jìn)度與計(jì)劃偏離的信息（控制離不開(kāi)信息）；（3）要采取糾正偏差的行動(dòng)（通過(guò)調(diào)度來(lái)實(shí)現(xiàn)）。

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

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

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

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

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

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

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

ri——Ji的到達(dá)時(shí)間，指Ji從外部進(jìn)入車(chē)間，可以開(kāi)始加工的最早時(shí)間。di——Ji的完工期限（即計(jì)劃完工期限）。Ci——Ji的完工時(shí)間，Ci＝ri＋∑（wij＋pij）＝ri＋Wi＋Pi

Cmax——最長(zhǎng)完工時(shí)間，Cmax＝max{Ci}

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

第一節(jié)排序問(wèn)題的基本概念（二）符號(hào)說(shuō)明Ji——工件i50第一節(jié)排序問(wèn)題的基本概念（二）符號(hào)說(shuō)明

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

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

ai——Ji的允許停留時(shí)間，ai＝di－ri

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

當(dāng)Li>0（正延遲），說(shuō)明Ji的實(shí)際完工時(shí)間超過(guò)了完工期限；當(dāng)Li<0（負(fù)延遲），說(shuō)明Ji提前完工；當(dāng)Li＝0（零延遲），Ji按期完工。Lmax——最長(zhǎng)延遲時(shí)間，Lmax＝max{Li}

第一節(jié)排序問(wèn)題的基本概念（二）符號(hào)說(shuō)明Fmax——最51第一節(jié)排序問(wèn)題的基本概念三、排序問(wèn)題的分類(lèi)和表示法

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

按工件加工路線的特征，可以將多臺(tái)機(jī)器的排序問(wèn)題分為：

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

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

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

※

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

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

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

（二）排序問(wèn)題的表示法

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

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

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

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

則Fmax=Cma

第二節(jié)流水作業(yè)排序問(wèn)題一、最長(zhǎng)流程時(shí)間Fmax的計(jì)算56第二節(jié)流水作業(yè)排序問(wèn)題一、最長(zhǎng)流程時(shí)間Fmax的計(jì)算

3、計(jì)算公式（1）C1si=C1Si－1+Psi1

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

｝+pksi

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

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

Cksi－1———前一工件，同一機(jī)器的完工時(shí)間;

pksi—工件Si在機(jī)器Mk上的加工時(shí)間

第二節(jié)流水作業(yè)排序問(wèn)題一、最長(zhǎng)流程時(shí)間Fmax的計(jì)算S57第二節(jié)流水作業(yè)排序問(wèn)題

i123456pi1

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

i615243

pi1

pi2pi3pi4224641021211331657411415520727633512517522830535742

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

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

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

i

123456

ai

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

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

i

1234

pi1

Pi2

pi3

1263

8429

45821、Palmer法：

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

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

i

1234

pi1

Pi2

pi3

pi

1263

8429

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

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

對(duì)加工時(shí)間和

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

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

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

★半能動(dòng)作業(yè)計(jì)劃：在可行的加工順序下，可以作出無(wú)數(shù)種作業(yè)計(jì)劃。其中，各工序都按最早可能開(kāi)（完）工時(shí)間安排的作業(yè)計(jì)劃稱(chēng)半能動(dòng)作業(yè)計(jì)劃?！锬軇?dòng)作業(yè)計(jì)劃：任何一臺(tái)機(jī)器的每段空閑時(shí)間都不足以加工一道可加工工序的半能動(dòng)作業(yè)計(jì)劃。

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

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

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

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

通過(guò)例題講授

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能動(dòng)作業(yè)計(jì)劃的構(gòu)成（p270）第三節(jié)單件作業(yè)排序問(wèn)題1．能動(dòng)作業(yè)計(jì)劃的構(gòu)成步驟D＝171第三節(jié)單件作業(yè)排序問(wèn)題

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

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

通過(guò)例題講授

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