生產(chǎn)第十一章

第十一章

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

每道工序只在一臺(tái)機(jī)器上完成；

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

每臺(tái)機(jī)器同時(shí)只能加工一個(gè)工件。（2）部分符號(hào)：

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

Mj——機(jī)器j，j＝1，2，…，m

pij——Ji在Mj上的加工時(shí)間，

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

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

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

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

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

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

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

2.1最長流程時(shí)間Fmax的計(jì)算例1：

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

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

T順

:順序移動(dòng)方式的加工周期；

n

:零件加工批量；

ti:

第i

道工序的單件工時(shí)；

m

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