生產(chǎn)運作及管理 第十一章 制造業(yè)作業(yè)計劃及控制

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

主要內(nèi)容：

排序問題的基本概念流水作業(yè)排序問題單件作業(yè)的排序問題生產(chǎn)作業(yè)控制生產(chǎn)與運作計劃課件§11.1排序問題的基本概念一、名詞術(shù)語

1、編制作業(yè)計劃（scheduling）

確定工件的加工順序，并確定機器加工每個工件的開始時間和完成時間。（是在加工制造發(fā)生之前的活動）2、排序(sequencing)

確定工件在機器上的的加工順序。上述兩個概念一般不加以區(qū)分。描述排序問題的術(shù)語來自加工制造行業(yè)。現(xiàn)范圍已擴展：機器（服務(wù)者）、工件（服務(wù)對象）。作業(yè)排序：是指合理安排生產(chǎn)運作的各項活動、資源使用、設(shè)施配置的時間表。生產(chǎn)與運作計劃課件“派工”是按作業(yè)計劃的要求，將具體生產(chǎn)任務(wù)安排到具體的機床上加工，屬于“調(diào)度”范圍?！摆s工”是實際進度已落后于計劃進度時采取的行動，也屬于“調(diào)度”范圍。“調(diào)度”是實行控制所采取的行動。（是在加工制造發(fā)生之后的活動）假定有n個工件要經(jīng)過m臺機器加工。一般可用M1，M2，……，Mm來表示加工路線。

生產(chǎn)運作周期：由作業(yè)時間、作業(yè)等待時間、設(shè)備調(diào)整時間、運輸時間、檢測時間、庫存時間等構(gòu)成。生產(chǎn)與運作計劃課件

二、假設(shè)條件與符號說明

1、一個工件不能同時在幾臺不同的機器上加工。2、工件在加工過程中采取平行移動方式3、不允許中斷。4、每道工序只在一臺機器上完成。5、工件數(shù)、機器數(shù)和加工時間已知，加工時間與加工順序無關(guān)。6、每臺機器同時只能加工一個工件。生產(chǎn)與運作計劃課件符號說明：i=1,2,3….,n.j=1,2,3….,m.生產(chǎn)與運作計劃課件

三、排序問題的分類和表示法1、按機器的種類和數(shù)量分類可分為：單臺機器的排序問題和多臺機器排序問題。多臺機器的排序問題還可分為：單件作業(yè)排序問題（加工路線不同），流水作業(yè)排序問題（所有的工件加工路線完全相同）。生產(chǎn)與運作計劃課件

2、按工件到達車間的情況不同，可以分為靜態(tài)的排序問題和動態(tài)的排序問題。3、按目標函數(shù)的性質(zhì)不同，也可以劃分不同的排序問題。4、按參數(shù)的性質(zhì)，可以劃分為確定型排序問題和隨機型排序問題。對于本章討論的排序問題，用4參數(shù)表示法。即：n/m/A/B/n為工件數(shù)；m為機器數(shù)；A為車間類型。（F為流水作業(yè)排序問題；P為流水作業(yè)排列排序；G為一般單件作業(yè)排序問題）。B為目標函數(shù)，通常使其最小。生產(chǎn)與運作計劃課件§11.2流水作業(yè)排序問題

流水作業(yè)排序問題的基本特征是每個工件的加工路線都一致。一般說來，工件在不同機器上的加工順序不盡一致，但本節(jié)研究的是工件在不同機器上的加工順序相同的問題。這就是排列排序問題。

一、最長流程時間Fmax的計算

本節(jié)討論n/m/p/Fmax問題，目標函數(shù)是使最長流程時間最短。最長流程時間是從第一個工件在第一臺機器開始加工時間算起，到最后一個工件在最后一臺機器完成加工為止所經(jīng)過的時間。生產(chǎn)與運作計劃課件Fmax等于排在末尾加工的工件在車間的停留時間，也等于一批工件的最長完工時間Cmax（假設(shè)所有的工件到達時間都為零）其計算公式為：表示工件在機器上的完工時間表示工件在上的加工時間生產(chǎn)與運作計劃課件經(jīng)常用表上作業(yè)法例11.1

有一個6/4/p/Fmax問題,其加工時間如表所示，當按順序S=(6，1，5，2，4，3)加工時，求Fmaxi123456pi1423142pi2456745pi3587555pi4424331生產(chǎn)與運作計劃課件計算結(jié)果如下表所示i615243Pi12246410212113316Pi257411415520727633Pi3512517522830535742Pi4113421325232338446生產(chǎn)與運作計劃課件

二、n/2/F/Fmax問題的最優(yōu)算法

Johnson算法1、從加工時間矩陣中找到最短的加工時間。2、若最短的時間出現(xiàn)在M1上，則對應(yīng)的工件盡可能往前排；若最短的加工時間出現(xiàn)在M2上，則對應(yīng)工件盡可能往后排。然后從加工時間矩陣中劃去已排序工件的加工時間，若最短的加工時間有多個，則任挑一個。3、若所有的工件都已排序，停止。否則轉(zhuǎn)步驟1。工件的加工路線：M1到M2

生產(chǎn)與運作計劃課件例11.2求下表所示的6/2/F/Fmax問題的最優(yōu)解.i123456（M1）ai518534（M2）bi722474加工時間矩陣將工件2排在第一位2將工件3排在第六位23將工件5排在第二位253將工件6排在第三位2563將工件4排在第五位25643

將工件1排在第四位

256143生產(chǎn)與運作計劃課件i123456ai518534bi722474i256143ai134558bi274742生產(chǎn)與運作計劃課件三、一般n/m/p/Fmax問題的啟發(fā)式算法

用分支定界法可得到該問題的最優(yōu)解，但計算量較大。下面介紹一般n/m/p/Fmax問題近優(yōu)解的啟發(fā)式算法。

（一）Palmer法

按上述工件計算結(jié)果的不增順序排列工件。例11.3

有一個4/3/F/Fmax問題,其加工時間如下表所示,用Palmer法求解生產(chǎn)與運作計劃課件加工時間矩陣i1234pi11263pi28429pi34582解:按公式計算

按其不增的的順序排列工件，得到加工順序（1，2，3，4）和（2，1，3，4）生產(chǎn)與運作計劃課件（二）關(guān)鍵工件法

1、計算每個工件的總加工時間,找出加工時間最長的工件，將其作為關(guān)鍵工件。2、對于余下的工件，若,則按不減的順序排成一個序列；若則按不增的順序排成一個序列3、順序即為所求順序。用該法求例11.3的近優(yōu)解。生產(chǎn)與運作計劃課件i1234pi11263pi28429pi34582pi13111614

（三）CDS法

把Johnson算法用于n/m/P/Fmax問題，得到（m-1）個加工順序，取其中較優(yōu)者。對加工時間和，用Johnson算法求（m-1）次加工順序，取其中最好的結(jié)果。生產(chǎn)與運作計劃課件四、零件在加工過程中的移動方式（一）順序移動

一批零件在上道工序全部加工完畢后才整批地轉(zhuǎn)移到下道工序繼續(xù)加工。n——零件加工批量ti——第i工序的單件工序時間m——零件加工的工序數(shù)

生產(chǎn)與運作計劃課件工序單件加工時間時間（分）123410512.57.5t1t2t3t4

T順=nt1+nt2+nt3+nt4=n(t1+t2+t3+t4)=nti

=4×(10+5+12.5+7.5)=4×35=140分鐘 例11.4：生產(chǎn)與運作計劃課件（二）平行移動

每個零件在前道工序加工完畢后，立即轉(zhuǎn)移到后道工序去繼續(xù)加工，形成前后工序交叉作業(yè)。tL為最長的單件工序時間。生產(chǎn)與運作計劃課件工序單件加工時間時間（分）123410512.57.5t1t2t3t4

公式：T平=（t1+t2+t3）+（n－1）t3+t4=ti+（n-1)t長

T平=35+（4–1）×12.5=72.5(分)例5：生產(chǎn)與運作計劃課件（三）平行順序移動

平行順序移動方式要求每道工序連續(xù)進行加工，但又要求各道工序盡可能平行地進行加工。（1）當時，零件按平行移動方式轉(zhuǎn)移；（2）當時，以i工序最后一個零件完工時間為基準，往前推移作為零件在（i+1）工序的開始加工時間。生產(chǎn)與運作計劃課件工序單件加工時間時間（分）123410512.57.5t1t2t3t4XYZ公式：T平順=4×（t1+t2+t3+t4）－（n－1）×t2－（n－1）×t2－（n－1）×t4=ti+（n－1)（t較長－t較短）

T平順=35+3×（10+12.5-5）=87.5（分鐘）例6：生產(chǎn)與運作計劃課件§11.3單件作業(yè)排序問題

單件作業(yè)的排序問題是是最一般的排序問題，也是最復雜的一種排序問題。一、問題的描述

對于一般單件作業(yè)的排序問題，每個工件都有其獨特的加工路線，工件沒有一定的流向。對于一般單件作業(yè)的排序問題，要描述一道工序要用3個參數(shù)：i,j和k。加工描述矩陣如下：生產(chǎn)與運作計劃課件二、一般的n/m/G/Fmax問題的啟發(fā)是算法（一）兩種作業(yè)計劃的構(gòu)成1、半能動作業(yè)計劃各工序都按最早可能開工時間安排的作業(yè)計劃稱為~。2、能動作業(yè)計劃任何一臺機器的每段空閑時間都不足以加工一道可加工工序的半能動計劃稱為~。3、無延遲作業(yè)計劃沒有任何延遲出現(xiàn)的能動計劃稱為~。生產(chǎn)與運作計劃課件（二）三類啟發(fā)式算法1.優(yōu)先調(diào)度法則（1）SPT法則——最短作業(yè)時間法則（2）FCFS法則——先到先服務(wù)法則（3）EDD法則——最早交貨期法則（4）MWKR法則——優(yōu)先選擇余下加工時間最長的工件。（5）LWKR法則——優(yōu)先選擇余下加工時間最短的工件。（6）MOPNR法則——優(yōu)先選擇余下工序數(shù)最多長的工件。（7）SCR法則——優(yōu)先選擇臨界比最小的工件。（8）RANDOM法則——隨機法2.隨機抽樣法3.概率調(diào)度法生產(chǎn)與運作計劃課件§11.4生產(chǎn)作業(yè)控制一、實施生產(chǎn)作業(yè)控制的原因和條件實際偏離計劃原因：（1）加工時間估計不準。

（2）隨機因素影響。（3）加工路線的多樣性。（4）企業(yè)環(huán)境的動態(tài)性。實施生產(chǎn)控制有三個條件