生產(chǎn)第十一章

第十一章

制造業(yè)作業(yè)計劃與控制第一節(jié)作業(yè)計劃問題的基本概念第二節(jié)流水作業(yè)排序問題第三節(jié)單件作業(yè)排序問題本章結(jié)構(gòu)1.1基本概念第一節(jié)作業(yè)計劃問題的基本概念編制作業(yè)計劃或日程安排排序派工控制趕工調(diào)度機器零件1.2假設(shè)條件與符號說明（1）假設(shè)條件：一個工件不能同時在幾臺不同的機器上加工；工件在加工過程中采取平行移動方式；不允許中斷；

每道工序只在一臺機器上完成；

工件數(shù)、機器數(shù)和加工時間已知，加工時間與加工順序無關(guān)；

每臺機器同時只能加工一個工件。（2）部分符號：

Ji——工件i，i＝1，2，…，n

Mj——機器j，j＝1，2，…，m

pij——Ji在Mj上的加工時間，

Ji的總加工時間為Pi＝ΣpijCmax——最長完工時間，Cmax＝max{Ci}Fmax——最長流程時間，F(xiàn)max＝max{Fi}

Lmax——最長延遲時間，Lmax＝max{Li}1.3排序問題的分類和表示法（1）排序問題的分類：按行業(yè)分：制造業(yè)的作業(yè)排序服務(wù)業(yè)的作業(yè)排序按機器種類和數(shù)量不同分：單機排序多機排序多機排序又按加工路線的特征分為：

單件作業(yè)排序和流水作業(yè)排序問題。（2）表示法：

康威用4個參數(shù)的排序問題表示法：n/m/A/Bn：工件數(shù)；m：機器數(shù)；

A：車間類型，有“F”類，“P”類，“G”類等?！綟表示流水作業(yè)排序問題；

P表示流水作業(yè)排列排序問題；G表示一般單件作業(yè)排序問題】；B：目標(biāo)函數(shù)，通常是使其值最小。第二節(jié)流水作業(yè)排序問題（1）流水作業(yè)排序問題的基本特征:是每個工件的加工路線都一致。前置內(nèi)容:（2）流水作業(yè)的排序問題主要包括：

最長流程時間的計算;兩臺機器排序問題的最優(yōu)算法;多臺機器排序問題的啟發(fā)式算法;相同零件、不同移動方式下加工周期的計算。

2.1最長流程時間Fmax的計算例1：

有一個6/4/p/Fmax問題，其加工時間如下表，當(dāng)按順序S＝（6，1，5，2，4，3）加工時，求Fmax。表2.1加工時間矩陣i123456Pi1423142Pi2456745Pi3587555Pi4424331解法：按所求順序列出加工時間矩陣；將每個工件的完工時間標(biāo)在其加工時間的右上角；最后一個工件在最后一臺機器上的完工時間即是最長流程時間Fmax。2.2

n/2/F/Fmax問題的最優(yōu)算法（兩臺機器流水作業(yè)排序）例2：：求下下表表所所示示的的6/2/F/Fmax問題題的的最最優(yōu)優(yōu)解解。。i123456ai518534bi722474表2.2加工工時時間間矩矩陣陣解法法（約翰翰森森算算法法））：：從加加工工時時間間矩矩陣陣中中找找出出最最短短加加工工時時間間；；若最最短短加加工工時時間間出出現(xiàn)現(xiàn)在在機機器器M1上，，則則對對應(yīng)應(yīng)工工件件應(yīng)應(yīng)該該盡盡可可能能往往前前排排；；若若最最短短加加工工時時間間出出現(xiàn)現(xiàn)在在機機器器M2上，，則則對對應(yīng)應(yīng)工工件件應(yīng)應(yīng)該該盡盡可可能能往往后后排排。。然然后后從從加加工工時時間間矩矩陣陣中中劃劃去去已已排排序序工工件件的的加加工工時時間間。。若若最最短短加加工工時時間間有有多多個個，，則則任任挑挑一一個個。。若所所有有工工件件都都已已排排序序，，停停止止。。否否則則，，轉(zhuǎn)轉(zhuǎn)步步驟驟（（1））。。2.3一般n/m/P/Fmax問題的啟發(fā)式算法(多臺機器排列排序)（1））Palmer法（（帕帕爾爾瑪瑪法法））例3:i1234Pi11263Pi28429Pi34582表2.3加工工時時間間矩矩陣陣有一一個個4/3/F/Fmax問題題，，其其加加工工時時間間如如下下表表所所示示，，用用（（Palmer）法法求求解解。。（2）關(guān)關(guān)鍵鍵工工件件法法計算算每每個個工工件件的的總總加加工工時時間間，，將將加加工工時時間間最最長長的的工工件件作作為為關(guān)關(guān)鍵鍵工工件件C；；對于于余余下下的的工工件件，，若若pi1≤pim則按pi1不減的順順序排成成一個序序列Sa,若pi1>pim則按pim不增的順順序排成成一個序序列Sb;順序（Sa,C,Sb）即為所所求順序序。有一個4/3/F/Fmax問題，其其加工時時間如下下表所示示，用關(guān)關(guān)鍵工件件法求解解。例4:表2.4加工時間間矩陣i1234Pi11263Pi28429Pi34582pi13111614（3）CDS法例5:有一個4/3/F/Fmax問題，其其加工時時間如下下表所示示，用CDS法求解。。i1234Pi11263Pi28429Pi34582表2.5加工時間間矩陣表2.6用CDS法求解i1234l=1Pi11263Pi34582l=2Pi1+Pi296812Pi2+Pi312910112.4相相同零零件不同同移動方方式下加加工周期期的計算算零件在加加工過程程中的三種典型型移動方方式：順序移動動方式平行移動動方式平行順序序移動方方式（1）順序移移動方式式1式中：

T順

:順序移動方式的加工周期；

n

:零件加工批量；

ti:

第i

道工序的單件工時；

m

:零件加工的工序數(shù)目。（2）平行移移動方式式2tL——最長長的單件件工序時時間。（3）平行順順序移動動方式3特點：既要求每每道工序序連續(xù)進進行加工工，又要要求各道道工序盡盡可能平平行地加加工。其具體做做法：當(dāng)ti＜ti+1時，零件件按平行行移動方方式移動動；當(dāng)ti≥ti+1時，以i工序最后后一個零零件的完完工時間間為基準(zhǔn)準(zhǔn)，往前前推移（n-1）×ti+1作為零件件在i+1工序的開開始加工工時間。。第三節(jié)單件作業(yè)排序問題3.1問問題題的描述述加工描述述矩陣和加工時間間矩陣1,1,11,2,31,3,22,1,32,2,12,3,2D=241345T=3.2兩兩種種作業(yè)計計劃的構(gòu)構(gòu)成單件作業(yè)業(yè)排序問問題中，，有2個重要的的作業(yè)計計劃:能動作業(yè)業(yè)計劃;無延遲作作業(yè)計劃劃。（1）能動作作業(yè)計劃劃的構(gòu)成成符號說明明：每安排一一道工序序稱為一一“步””；{St}:t步之前已已排序工工序構(gòu)成成的部分分作業(yè)計計劃；{Ot}:t步可排序序工序的的集合；；Tk:為{Ot}中工序Ok的最早可可能開始始時間；；T’k:為{Ot}中工序Ok的最早可可能完成成時間。。例5：有一個2/3/G/Fmax問題，其其加工描描述矩陣陣D和加工時時間矩陣陣T分別為：：1,1,11,2,31,3,22,1,32,2,12,3,2D=241345T=試：構(gòu)成一個個能動作作業(yè)計劃劃？t{Ot}TkT`kT*M*Oj11,1,12,1,300232M11,1,121,2,32,1,320633M32,1,331,2,32,2,133777M3M11,2,341,3,22,2,173877M12,2,151,3,22,3,2778128M21,3,262,3,281313M22,3,2表3.1能動作業(yè)業(yè)計劃的的構(gòu)成（2）無延遲遲作業(yè)計計劃的構(gòu)構(gòu)成例6：有一個2/3/G/Fmax問題，，其加加工描描述矩矩陣D和加工工時間間矩陣陣T分別為為：1,1,11,2,31,3,22,1,32,2,12,3,2D=241345T=試：構(gòu)成一一個無無延遲遲作業(yè)業(yè)計劃劃？t{Ot}TkT`kT*M*Oj11,1,12,1,3002300M1M31,1,121,2,32,1,320630M32,1,331,2,3