運營管理排序和控制

1、Operations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃第九章第九章作業(yè)排序和控制作業(yè)排序和控制 Operations ManagementOperations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃（1）了解作業(yè)排序的含義）了解作業(yè)排序的含義（2）掌握流水線作業(yè)的基本模型，）掌握流水線作業(yè)的基本模型， 成批加工成批加工零件的移動順序零件的移動順序（3）掌握生產(chǎn)作業(yè)控制內(nèi)容和方法）掌握生產(chǎn)作業(yè)控制內(nèi)容和方法學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo)主要內(nèi)容主要內(nèi)容9.1 排序的基本概念排序的基本概念9.2 流水作業(yè)排序問題流水作業(yè)排序問題9.3 生產(chǎn)作業(yè)控制生產(chǎn)作業(yè)控制Opera

2、tions Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.1 排序的基本概念排序的基本概念術(shù)語術(shù)語排序：確定工件在機床（工作地，服務(wù)臺）上的加工排序：確定工件在機床（工作地，服務(wù)臺）上的加工（服務(wù)）順序。（服務(wù)）順序。A工序工序工件工件B工序工序C工序工序D工序工序E工序工序確定誰先誰后確定誰先誰后我先我先！我先我先！Operations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.1 排序的基本概念排序的基本概念術(shù)語術(shù)語派工：按作業(yè)計劃要求，將具體生產(chǎn)任務(wù)安排到具體派工：按作業(yè)計劃要求，將具體生產(chǎn)任務(wù)安排到具體的機床上加工。的機床上加工。趕工：實際進(jìn)度落后于計劃

3、進(jìn)度采取的行動。趕工：實際進(jìn)度落后于計劃進(jìn)度采取的行動。調(diào)度：運營過程的現(xiàn)場指揮。調(diào)度：運營過程的現(xiàn)場指揮。編制作業(yè)計劃（車間，工段）：確定工件的加工順序，編制作業(yè)計劃（車間，工段）：確定工件的加工順序，以及確定機床加工每個工件的開始時間和完成時間。以及確定機床加工每個工件的開始時間和完成時間。注意：編制作業(yè)計劃和排序的關(guān)系注意：編制作業(yè)計劃和排序的關(guān)系Operations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.1 排序的基本概念排序的基本概念假設(shè)條件假設(shè)條件一個工件不能同時在幾臺不同的機器上加工一個工件不能同時在幾臺不同的機器上加工工件采取平行移動方式工件采取平行移動方

4、式連續(xù)加工，一個工件開始加工必須一直進(jìn)行到完工，連續(xù)加工，一個工件開始加工必須一直進(jìn)行到完工，不得中途停止（工序間和工序內(nèi)）不得中途停止（工序間和工序內(nèi)）每到工序只在一臺機器上完成每到工序只在一臺機器上完成工件數(shù)、機器數(shù)、加工路線和工件在每工序（機器）工件數(shù)、機器數(shù)、加工路線和工件在每工序（機器）的加工時間確定，工件在每工序（機器）的加工時間的加工時間確定，工件在每工序（機器）的加工時間與加工順序無關(guān)。與加工順序無關(guān)。每臺機器同時只能加工一個工件每臺機器同時只能加工一個工件Operations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.1 排序的基本概念排序的基本概念符號說明

5、符號說明Ji為工件為工件i，i=1,2,3，nMj為機器為機器j，j=1,2,3，mpij為為Ji工件在工件在Mj機器上的加工時間，機器上的加工時間，Ji的總加工時間為的總加工時間為Pi，wij為為Ji工件在工件在Mj機器的等待加工時間或運輸時間（延遲加工時間），機器的等待加工時間或運輸時間（延遲加工時間），Wi為為Ji工件總延遲加工時間，工件總延遲加工時間，ri為為Ji的到達(dá)時間，指的到達(dá)時間，指Ji從外部進(jìn)入加工地（車間或機器），可以開從外部進(jìn)入加工地（車間或機器），可以開始加工的最早時間始加工的最早時間di為為Ji的完工期限的完工期限Ci為為Ji的完工時間，的完工時間，Cmax為最長完工

6、時間，為最長完工時間，Cmax=maxCi（ i=1,2,3，n）kjiji pP1kjiiiijijiiPWrpwrC1）（kjijiwW1Operations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.1 排序的基本概念排序的基本概念符號說明符號說明Fi為為Ji的流程時間（在車間的實際停留時間），的流程時間（在車間的實際停留時間），F(xiàn)i = Ciri = Wi+PiFmax為最長流程時間，為最長流程時間， Fmax=maxFiLi為工件的延遲時間。為工件的延遲時間。Li0（正延遲，（正延遲，Ji工件實際完工時間超過了完工期限）；工件實際完工時間超過了完工期限）； Li0（

7、負(fù)延遲，（負(fù)延遲，Ji工件實際完工時間早于完工期限）；工件實際完工時間早于完工期限）； Li = 0 （零延遲，（零延遲，Ji工件實際完工時間等于完工期限）工件實際完工時間等于完工期限）Lmax為最長延遲時間為最長延遲時間，Lmax= maxLi （ i =1,2,3，n）iiiiiiiiiiiiia-Fr -d-WPd-WPrd-CL）（）（Operations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.1 排序的基本概念排序的基本概念排序問題分類排序問題分類單臺機器排序單臺機器排序多臺機器排序多臺機器排序排序問題排序問題機器的種類和數(shù)量機器的種類和數(shù)量單件作業(yè)排序單件作業(yè)

8、排序（job-shop）流水作業(yè)排序流水作業(yè)排序（flow-shop）工件加工線路工件加工線路靜態(tài)排序問題靜態(tài)排序問題動態(tài)排序問題動態(tài)排序問題排序問題排序問題工件到達(dá)加工地情況工件到達(dá)加工地情況確定型排序問題確定型排序問題隨機型排序問題隨機型排序問題排序問題排序問題參數(shù)性質(zhì)參數(shù)性質(zhì)平均流程時間最短平均流程時間最短誤期完工工件數(shù)最少誤期完工工件數(shù)最少排序問題排序問題目標(biāo)函數(shù)性質(zhì)目標(biāo)函數(shù)性質(zhì)多目標(biāo)排序多目標(biāo)排序單目標(biāo)排序單目標(biāo)排序目標(biāo)函數(shù)數(shù)量目標(biāo)函數(shù)數(shù)量Operations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.1 排序的基本概念排序的基本概念排序表示法（康威法排序表示法（康

9、威法Conway）n / m / A / B工件數(shù)工件數(shù)機器數(shù)機器數(shù)作業(yè)類型：作業(yè)類型：F和和p流水線，流水線，G單件單件目標(biāo)函數(shù)目標(biāo)函數(shù)6/8/p/Fmax？10/5/G/Cmax？Operations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.2 流水作業(yè)排序流水作業(yè)排序注意兩個順序注意兩個順序不同工件的加工工藝決定的在不同機器之間的加工先后順序不同工件的加工工藝決定的在不同機器之間的加工先后順序加工加工工藝順序工藝順序不同工件在同一臺機器上的加工先后順序不同工件在同一臺機器上的加工先后順序-加工順序加工順序（假設(shè)不同工（假設(shè)不同工件在每一臺機器上的加工先后順序相同）件在

10、每一臺機器上的加工先后順序相同）機器機器A機器機器B機器機器C機器機器D加工順序加工順序1-3-2加工順序加工順序1-3-2加工順序加工順序1-3-2加工順序加工順序1-3-2加工工藝順序加工工藝順序A-B-C-DOperations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.2 流水作業(yè)排序流水作業(yè)排序最長流程時間最長流程時間Fmax的計算的計算n/m/p/Fmax問題，目標(biāo)函數(shù)是最長流程時間（加工周期）最短問題，目標(biāo)函數(shù)是最長流程時間（加工周期）最短因為：因為：ri=0，所以：，所以： Fmax= Cmax設(shè)：設(shè)：n個工件的加工順序為個工件的加工順序為S =（S1、S2、

11、S3、Sn），其中），其中Si為為排在排在i位加工的工件代號。位加工的工件代號。Cksi表示工件表示工件Si在機器在機器Mk上的完工時間，上的完工時間，pksi表示工件表示工件Si在機器在機器Mk上的加工時間。上的加工時間。機器數(shù)：機器數(shù)：k=1，2，3，4，m；工件數(shù)：；工件數(shù)：i=1，2，3，n遞推計算公式：遞推計算公式：（1）C1si=C1（si-1）+psi1（Si工件在機器工件在機器1的完工時間）的完工時間）（2）Cks1=C（k-1）1+ps1k（S1工件在機器工件在機器k的完工時間）的完工時間）（3）Cksi=maxC（k-1）si，Ck（si-1）+psik其中：其中：k=2，

12、3，4，m；工件數(shù)：；工件數(shù)：i=2，3，nFmax= ri+Cmsn當(dāng)當(dāng)ri = 0時，時， Fmax= Cmsn（最后加工工件（最后加工工件n在最后機器在最后機器m的完工時間）的完工時間）Operations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.2 流水作業(yè)排序流水作業(yè)排序最長流程時間最長流程時間Fmax的計算的計算例：有一個例：有一個6/4/p/Fmax問題，其加工時間如表所示。當(dāng)按順序問題，其加工時間如表所示。當(dāng)按順序S=（6,1,5,2,4,3）加工時，求）加工時，求 Fmax=？i123456psi1442639110414216psi24851361972

13、6430535psi3513821728533538543psi4417223432336341144加工時間矩陣（加工時間矩陣（1,2,3,4,5,6）機器（順序由技術(shù)工藝要求決定）機器（順序由技術(shù)工藝要求決定）工件加工先后順序工件加工先后順序Operations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.2 流水作業(yè)排序流水作業(yè)排序最長流程時間最長流程時間Fmax的計算的計算i615243psi12246410212113316psi257411415520727633psi3512517522830535742psi4113421325232338446加工時間矩陣（加

14、工時間矩陣（6,1,5,2,4,3）機器（順序由技術(shù)工藝要求決定）機器（順序由技術(shù)工藝要求決定）工件加工先后順序工件加工先后順序結(jié)論：工件加工先后順序（排序）不同，結(jié)論：工件加工先后順序（排序）不同， Fmax也不同。也不同。Operations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.2 流水作業(yè)排序流水作業(yè)排序n/2/F/Fmax問題的最優(yōu)算法問題的最優(yōu)算法Johnson法則（法則（S.M.Johnson，1954年）年）ai表示工件表示工件Ji在機器在機器M1上的加工時間，上的加工時間，bi表示工件表示工件Ji在機器在機器M2上的上的加工時間，每個工件加工工藝線路相同

15、：加工時間，每個工件加工工藝線路相同：M1M2如果：如果：min（ai，bj）min（aj，bi），則工件），則工件Ji排在排在Jj之前；如果之前；如果min（ai，bj）= min（aj，bi），則工件），則工件Ji和和Jj之間任意順序。之間任意順序。（i、j為兩兩比較的工件號）為兩兩比較的工件號）Johnson算法算法（1）從加工時間矩陣中找出最短加工時間）從加工時間矩陣中找出最短加工時間（2）若最短加工時間出現(xiàn)在）若最短加工時間出現(xiàn)在M1上，則對應(yīng)的工件盡量往前排；若上，則對應(yīng)的工件盡量往前排；若最短加工時間出現(xiàn)在最短加工時間出現(xiàn)在M2上，則對應(yīng)工件盡可能往后排。如最短加上，則對應(yīng)工件盡

16、可能往后排。如最短加工時間有多個，則任選一個。工時間有多個，則任選一個。（3）在加工時間矩陣中劃去已排序的工件，剩余工件重復(fù)上述過）在加工時間矩陣中劃去已排序的工件，剩余工件重復(fù)上述過程至所有工件完成排序。程至所有工件完成排序。Operations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.2 流水作業(yè)排序流水作業(yè)排序n/2/F/Fmax問題的最優(yōu)算法問題的最優(yōu)算法Johnson改進(jìn)算法改進(jìn)算法（1）將所有）將所有aibi的工件按的工件按ai值不減的順序排成一個加工順序值不減的順序排成一個加工順序A。（2）將所有）將所有aibi的工件按的工件按bi值不增的順序排成一個加工順序

17、值不增的順序排成一個加工順序B。（3）最優(yōu)加工順序：）最優(yōu)加工順序：A+B一般一般n/mP/Fmax問題的啟發(fā)式算法（近優(yōu)解）問題的啟發(fā)式算法（近優(yōu)解）Palmer法（法（D.S.Palmer ，1965年）年）按斜度指標(biāo)（按斜度指標(biāo)（l l i）排列工件加工順序）排列工件加工順序（1）計算工件斜度指標(biāo)：）計算工件斜度指標(biāo)：（2）按各工件）按各工件l l i不增的順序排列工件。不增的順序排列工件。符號含義：符號含義：m為機器數(shù)，為機器數(shù)，pik為工件為工件i在機器在機器Mk上的加工時間。上的加工時間。ikmkip/mk-121 ）（k=1,2，nOperations Management第七章

18、綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.2 流水作業(yè)排序流水作業(yè)排序一般一般n/mP/Fmax問題的啟發(fā)式算法（近優(yōu)解）問題的啟發(fā)式算法（近優(yōu)解）關(guān)鍵工件法（關(guān)鍵工件法（D.S.Palmer ，1965年）年）（1）計算每個工件的總加工時間：）計算每個工件的總加工時間：（2）選擇加工時間最長的工件作為關(guān)鍵工件）選擇加工時間最長的工件作為關(guān)鍵工件C。（3）對于余下的工件，將所有工件在）對于余下的工件，將所有工件在M1機器上的時間胡和機器上的時間胡和Mm機機器上的時間比較。如器上的時間比較。如pi1pim，則按，則按pi1不減的順序排成一個序列不減的順序排成一個序列Sa；如如pi1pim，則按，則按pi

19、m不增的順序排成一個序列不增的順序排成一個序列Sb。（4）順序（）順序（Sa，C，Sb）為近優(yōu)解。）為近優(yōu)解。CDS法（法（Campbell-Dudek-Smith）Johnson算法在一般算法在一般n/mP/Fmax問題的應(yīng)用問題的應(yīng)用（1）將）將m臺機器轉(zhuǎn)化成臺機器轉(zhuǎn)化成m-1個個n/2/F/Fmax問題，形成的問題，形成的n/2/F/Fmax問題的加工時間為：問題的加工時間為：ijmjipP 1iklkp 1ikm-lmkp 1和和1.21m-，,l 其中：Operations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.2 流水作業(yè)排序流水作業(yè)排序一般一般n/mP/Fm

20、ax問題的啟發(fā)式算法（近優(yōu)解）問題的啟發(fā)式算法（近優(yōu)解）CDS法（法（Campbell-Dudek-Smith）（2） 用用Johnson算法得出（算法得出（m-1）個加工順序，取其中最好結(jié)果。）個加工順序，取其中最好結(jié)果。例：有一個例：有一個6/4/p/Fmax問題，其加工時間矩陣如下所示。用問題，其加工時間矩陣如下所示。用CDS法法求解最優(yōu)順序。求解最優(yōu)順序。i123456pi1423142pi2456745pi3587555pi4424331Operations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.2 流水作業(yè)排序流水作業(yè)排序一般一般n/mP/Fmax問題的啟發(fā)式

21、算法（近優(yōu)解）問題的啟發(fā)式算法（近優(yōu)解）CDS法（法（Campbell-Dudek-Smith）（1）求解：）求解：得出兩個機器工件加工時間組合方式：得出兩個機器工件加工時間組合方式：l =1時為（時為（pi1，pi4）；）；l =2時為（時為（pi1+ pi2 ，pi3+ pi4）；）；l =3時為（時為（pi1+ pi2 +pi3 ，pi2 + pi3 + pi4）iklkp 1ikm-lmkp 1和和321，,l ：其中l(wèi)組合方式組合方式123456l =1pi1423142pi4424331l =2pi1+ pi2879887pi3+ pi491011886l =3pi1+ pi2 +

22、pi3131516131312pi2 + pi3 + pi4131517151211Operations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.2 流水作業(yè)排序流水作業(yè)排序一般一般n/mP/Fmax問題的啟發(fā)式算法（近優(yōu)解）問題的啟發(fā)式算法（近優(yōu)解）（2）用）用Johnson算法得出：算法得出：l =1近優(yōu)解為（近優(yōu)解為（4，2，3，1，5，6）；）； l =2近優(yōu)解為（近優(yōu)解為（2，1，4，5，3，6）；）； l =3近優(yōu)解為（近優(yōu)解為（1，4，2，3，5，6）（3）分別計算近優(yōu)排序的）分別計算近優(yōu)排序的Fmax，選擇選擇Min（ Fmax）的排序。的排序。Operat

23、ions Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.2 流水作業(yè)排序流水作業(yè)排序相同工件、不同移動方式下加工周期的計算相同工件、不同移動方式下加工周期的計算工件移動方式指工件在生產(chǎn)過程中的運送組織方式問題。工件移動方式指工件在生產(chǎn)過程中的運送組織方式問題。移動方式：移動方式：順序移動、平行移動和平行順序移動順序移動、平行移動和平行順序移動順序移動方式順序移動方式:整批移動。例見教材整批移動。例見教材P306為工序數(shù)目。工序單件工序時間；為工件在第為工件加工批量；其中：順mitntTimii， 1工序工序T順順時間時間020406080100120140160M1M2M3M4t

24、1t2t3t4Operations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.2 流水作業(yè)排序流水作業(yè)排序平行移動方式平行移動方式:單件立即移動。例見教材單件立即移動。例見教材P307為最長單件工序時間。其中：平LLmiittn-tT，）（ 11T平平工序工序時間時間020406080100120140160M1M2M3M4t1t2t3t4Operations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.2 流水作業(yè)排序流水作業(yè)排序平行順序移動方式：平行順序移動方式：（1）titi+1，工件按平行移動方式轉(zhuǎn)移；，工件按平行移動方式轉(zhuǎn)移； titi+1，以以i工

25、序最后一個零件的完工時間為基準(zhǔn)，往前推移（工序最后一個零件的完工時間為基準(zhǔn)，往前推移（n-1） ti+1作作為工件在（為工件在（i+1）工序開始時間）工序開始時間。例見教材。例見教材P307-308 1111min1miiimii，ttn-tnT）（）（平順T平順平順工序工序時間時間020406080100120140160M1M2M3M4t1t2t3t4Operations Management第七章綜合生產(chǎn)計劃第七章綜合生產(chǎn)計劃9.2 流水作業(yè)排序流水作業(yè)排序平行順序移動方式：平行順序移動方式：各工序作業(yè)開始時間各工序作業(yè)開始時間T平順平順工序工序時間時間020406080100120140160M1M2M3M4t1t2t3t4），（1