生產(chǎn)管理課件第十二章

1、 第八章第八章 生產(chǎn)運作能力規(guī)劃生產(chǎn)運作能力規(guī)劃 第九章第九章 生產(chǎn)運作計劃生產(chǎn)運作計劃 第十章第十章 獨立需求庫存管理獨立需求庫存管理 第十一章第十一章 從屬需求資源管理從屬需求資源管理 第十二章第十二章 作業(yè)排序管理作業(yè)排序管理 第十三章第十三章 項目進度控制項目進度控制 第十四章第十四章 先進制造方式與管理模式先進制造方式與管理模式作業(yè)排序的基本概念、分類作業(yè)排序的基本概念、分類制造業(yè)中的作業(yè)排序制造業(yè)中的作業(yè)排序服務(wù)業(yè)中的作業(yè)排序服務(wù)業(yè)中的作業(yè)排序?qū)W習目標：學(xué)習目標：關(guān)鍵詞關(guān)鍵詞排序（排序（Sequencing）后向排序（后向排序（Backward sequencing ）前向排序（前

2、向排序（ Forward sequencing ）調(diào)度（調(diào)度（Dispatching）約翰遜約翰遜-貝爾曼規(guī)則（貝爾曼規(guī)則（ Johnson-Bellmans Rule ） 具體到確定每臺設(shè)備、每個人員每天的工具體到確定每臺設(shè)備、每個人員每天的工作任務(wù)和工件在每臺設(shè)備上加工順序的過程。作任務(wù)和工件在每臺設(shè)備上加工順序的過程。什么叫作業(yè)排什么叫作業(yè)排序？序？綜合計劃綜合計劃 主生產(chǎn)計劃主生產(chǎn)計劃 排序排序12.1 排序問題概述排序問題概述M生產(chǎn)計劃與排序生產(chǎn)計劃與排序 生產(chǎn)計劃（生產(chǎn)計劃（scheduling）與排序（）與排序（sequencing）是不同的，排序只是確定工件在機器上的加工順是不

3、同的，排序只是確定工件在機器上的加工順序，而作業(yè)計劃不僅包括確定工件的加工順序，序，而作業(yè)計劃不僅包括確定工件的加工順序，還包括確定機器加工每個工件的開始時間和完成還包括確定機器加工每個工件的開始時間和完成時間。時間。M目標：目標： 使完成時間最短使完成時間最短 使設(shè)備利用率最高使設(shè)備利用率最高 使在制品庫存量最小使在制品庫存量最小 使顧客等待時間最少使顧客等待時間最少n在編制作業(yè)計劃時，有時一個工件的某道工序完成之在編制作業(yè)計劃時，有時一個工件的某道工序完成之后，執(zhí)行它下一道工序的機器還在加工其他工件，這后，執(zhí)行它下一道工序的機器還在加工其他工件，這時，工件要等待一段時間才能開始加工，這種情

4、況稱時，工件要等待一段時間才能開始加工，這種情況稱為為“工件等待工件等待”。n有時，一臺機器已經(jīng)完成對某個工件的加工，但隨后有時，一臺機器已經(jīng)完成對某個工件的加工，但隨后要加工的工件還未到達，這種情況稱為要加工的工件還未到達，這種情況稱為“機器空閑機器空閑”。 M排序問題的分類排序問題的分類n1）按機器的種類和數(shù)量不同）按機器的種類和數(shù)量不同 單臺機器的排序問題單臺機器的排序問題 多臺機器的排序問題多臺機器的排序問題l 單件作業(yè)排序問題單件作業(yè)排序問題(Job-Shop)l 流水作業(yè)排序問題流水作業(yè)排序問題(Flow-Shop)n2）按工件到達車間的情況不同）按工件到達車間的情況不同 靜態(tài)排序

5、問題靜態(tài)排序問題 零件一次性到達車間，一次性排序零件一次性到達車間，一次性排序 動態(tài)排序問題動態(tài)排序問題 零件陸續(xù)到達車間，隨時排序零件陸續(xù)到達車間，隨時排序n3）按目標函數(shù)的性質(zhì)不同）按目標函數(shù)的性質(zhì)不同 單目標排序問題單目標排序問題 多目標排序問題多目標排序問題 目標函數(shù)：平均流程時間最短、誤期完工時間目標函數(shù)：平均流程時間最短、誤期完工時間最少等最少等n4）按參數(shù)的性質(zhì)不同）按參數(shù)的性質(zhì)不同 確定型排序問題確定型排序問題 隨機型排序問題隨機型排序問題 參數(shù)：指加工時間和其他相關(guān)參數(shù)參數(shù)：指加工時間和其他相關(guān)參數(shù)12.2 制造業(yè)中的作業(yè)排序制造業(yè)中的作業(yè)排序1、 排序問題的假設(shè)排序問題的假

6、設(shè) 一個工件不能同時在幾臺機器上加工。一個工件不能同時在幾臺機器上加工。 每臺機器同時只能加工一個工件。每臺機器同時只能加工一個工件。 每道工序只在一臺機器上完成。每道工序只在一臺機器上完成。 工件在加工過程中采取平行移動方式。工件在加工過程中采取平行移動方式。 工件在加工過程中不允許中斷。工件在加工過程中不允許中斷。 工件數(shù)、機器數(shù)和加工時間已知，加工時間與工件數(shù)、機器數(shù)和加工時間已知，加工時間與加工順序無關(guān)。加工順序無關(guān)。12.2.1 排序問題的假設(shè)及表示方法排序問題的假設(shè)及表示方法m/n/A/B其中，其中， m 加工設(shè)備數(shù)加工設(shè)備數(shù)n 工件數(shù)工件數(shù)A 排序問題類型排序問題類型/車間類型車

7、間類型B 評價尺度評價尺度/目標函數(shù)目標函數(shù)2、排序問題的表示方法、排序問題的表示方法F流水作業(yè)排序問題流水作業(yè)排序問題R非流水作業(yè)排序問題非流水作業(yè)排序問題G一般單件排序問題一般單件排序問題當當m1時，時，A處為空白。因為單臺設(shè)備的排序問題，處為空白。因為單臺設(shè)備的排序問題，無所謂加工路線問題，也談不上流水型或單件作業(yè)。無所謂加工路線問題，也談不上流水型或單件作業(yè)。例：例：2/6/F/Fmax 6個工件在個工件在2個工作中個工作中心上的流水排序問題，心上的流水排序問題，求最長流程時間最短。求最長流程時間最短。12.2.2 作業(yè)排序方案的評價標準作業(yè)排序方案的評價標準總流程時間總流程時間最短最

8、短平均流程時間最短平均流程時間最短最大延遲時間或最大誤期時間最短最大延遲時間或最大誤期時間最短平均延遲或平均誤期最短平均延遲或平均誤期最短平均在制品占用量最小平均在制品占用量最小總調(diào)整時間最少總調(diào)整時間最少12.2.3 作業(yè)排序的優(yōu)先規(guī)則作業(yè)排序的優(yōu)先規(guī)則（1）FCFS（first come first served） 最短加工時間優(yōu)先最短加工時間優(yōu)先規(guī)則：優(yōu)先選擇最進進入可排序集合的工件。規(guī)則：優(yōu)先選擇最進進入可排序集合的工件。（2）SPT（shortest processing time）規(guī)則：優(yōu)先選擇加）規(guī)則：優(yōu)先選擇加工時間最短的工件。工時間最短的工件。（3 ）EDD（earliest

9、 due date）規(guī)則：優(yōu)先選擇完工期）規(guī)則：優(yōu)先選擇完工期限最緊的工件。限最緊的工件。優(yōu)先調(diào)度規(guī)則優(yōu)先調(diào)度規(guī)則調(diào)度方法：運用若干預(yù)先規(guī)定的優(yōu)先順序規(guī)則，順調(diào)度方法：運用若干預(yù)先規(guī)定的優(yōu)先順序規(guī)則，順次決定下一個應(yīng)被加工的工件的排序方法。次決定下一個應(yīng)被加工的工件的排序方法。（4）SCR（smallest critical ratio）規(guī)則：優(yōu)先選擇）規(guī)則：優(yōu)先選擇臨界比最小的工件。臨界比為工作允許停留時臨界比最小的工件。臨界比為工作允許停留時間和工件余下加工時間之比。間和工件余下加工時間之比。（5）MWKR（most work remaining）規(guī)則：優(yōu)先）規(guī)則：優(yōu)先選擇余下加工時間最長

10、的工件。選擇余下加工時間最長的工件。（6）LWKR（least work remaining）規(guī)則：優(yōu)先選）規(guī)則：優(yōu)先選擇余下加工時間最短的工件。擇余下加工時間最短的工件。（7）MOPNR（most operations remaining）規(guī)則：）規(guī)則： 優(yōu)先選擇余下工序數(shù)最多的工件。優(yōu)先選擇余下工序數(shù)最多的工件。（8）RANDOM規(guī)則：隨機地挑選下一件工件。規(guī)則：隨機地挑選下一件工件。12.2.4 生產(chǎn)作業(yè)排序方法生產(chǎn)作業(yè)排序方法 實質(zhì)上是實質(zhì)上是n n項任務(wù)的一個全排列問題。項任務(wù)的一個全排列問題。無論何種排序，無論何種排序，n n項任務(wù)中的最大流程時間項任務(wù)中的最大流程時間（加工周期）

11、總是一個固定值。（加工周期）總是一個固定值。(一一) 單臺設(shè)備排序問題單臺設(shè)備排序問題1、單臺設(shè)備排序問題的實質(zhì)、單臺設(shè)備排序問題的實質(zhì)作業(yè)時間、加工時間作業(yè)時間、加工時間流程時間、總流程時間、平均流程時間流程時間、總流程時間、平均流程時間等待時間、總等待時間、平均等待時間等待時間、總等待時間、平均等待時間加工周期、最大流程時間加工周期、最大流程時間2、有關(guān)概念、有關(guān)概念Fi：流程：流程(Flow Time) wi+tinwi：i工件的等待時間工件的等待時間nti：i工件的加工時間工件的加工時間 n平均流程平均流程 Fn總流程：最大流程總流程：最大流程Fmax=max(Fi)n優(yōu)化目標：平均流

12、程最短優(yōu)化目標：平均流程最短3、平均流程時間最短、平均流程時間最短（SPT，Shortest Processing Time SOT，Shortest Operating Time） 1）目標：使平均流程時間最短或）目標：使平均流程時間最短或平均等待時間最短。平均等待時間最短。2）方法：按任務(wù)所需時間長短，從）方法：按任務(wù)所需時間長短，從短到長順序排列。短到長順序排列。按按SPT優(yōu)先規(guī)則，加工順序為：優(yōu)先規(guī)則，加工順序為： 例例12.1 某生產(chǎn)小組只有一臺大型加工設(shè)備，計某生產(chǎn)小組只有一臺大型加工設(shè)備，計劃期初接到六項任務(wù)，所需加工時間劃期初接到六項任務(wù)，所需加工時間及預(yù)定交貨期如表及預(yù)定交貨

13、期如表12.1。試確定最優(yōu)加。試確定最優(yōu)加工順序。工順序。生產(chǎn)任務(wù)編號生產(chǎn)任務(wù)編號JiJ1J2J3J4J5J6加工時間加工時間ti(天天)482593預(yù)定交貨期預(yù)定交貨期di(天天) 2423863213-J1J3-J6-J5-J2-J49854J5J2J4J13J62J3 加工時間加工時間ti(天天) 生產(chǎn)任務(wù)編號生產(chǎn)任務(wù)編號Ji654321 加工順序加工順序008000 交貨延期交貨延期Di 22149520 等待時間等待時間wi312214952 流程時間流程時間Fi3223624138 預(yù)定交貨期預(yù)定交貨期di(天天)(8 .13)312214952(616161天平均流程時間iiFF

14、)(8Lmax天最大延期量)(33. 168天平均延期量)(31 天最大流程時間：)(22 天最大等待時間：)(67. 86)22149520(天平均等待時間2）方法：按預(yù)定交貨期（生產(chǎn)任務(wù)規(guī)定完成時）方法：按預(yù)定交貨期（生產(chǎn)任務(wù)規(guī)定完成時刻）的先后，從先到后次序排列，即按預(yù)訂刻）的先后，從先到后次序排列，即按預(yù)訂交貨期非減的次序排列。交貨期非減的次序排列。4、使最大交貨延期量最小、使最大交貨延期量最小 （EDD規(guī)則，規(guī)則，Early Delivery Date）1）目標：使最大交貨延期時間最小。）目標：使最大交貨延期時間最小。按按EDD優(yōu)先規(guī)則，加工順序為：優(yōu)先規(guī)則，加工順序為： -J6J4

15、-J3-J5-J1-J2生產(chǎn)任務(wù)編號生產(chǎn)任務(wù)編號JiJ1J2J3J4J5J6加工時間加工時間ti(天天)482593預(yù)定交貨期預(yù)定交貨期di(天天) 2423863213000000交貨延期交貨延期Di3122181075流程時間流程時間FiJ5J1J2J6J3J4生產(chǎn)任務(wù)編號生產(chǎn)任務(wù)編號Ji654321加工順序加工順序948325加工時間加工時間ti(天天)3224231386預(yù)定交貨期預(yù)定交貨期di(天天)(0Lmax天最大延期量)(0 天平均延期量)(31 天最大流程時間：)(5 . 51)3122811075(616161天平均流程時間iiFF1）目標：使完成任務(wù)的總流程時間最短。）目

16、標：使完成任務(wù)的總流程時間最短。2）方法：約翰遜貝爾曼規(guī)則（）方法：約翰遜貝爾曼規(guī)則（Johnson-Bellmans Rule）。）。(二二) 流水型排序問題流水型排序問題1、2/n/Fn種工件在兩臺設(shè)備上的加工，它們的工藝順序相同種工件在兩臺設(shè)備上的加工，它們的工藝順序相同方案方案1：-J2J4-J1-J5-J3方案方案2：-J3J1-J2-J4-J5首先進行排序：首先進行排序：有有2個方案。個方案。零件編號零件編號Ji加工時間加工時間(h)J1J2J3J4J5tiA681237tiB119534例例12.2 設(shè)有五種零件，均須先在車床設(shè)有五種零件，均須先在車床A上加工，再到銑床上加工，再

17、到銑床B上加上加工，車床與銑床各有一臺。各零件在機床上加工所需時間：工，車床與銑床各有一臺。各零件在機床上加工所需時間：459113tiBtiA712863方案方案1：J4J1 J2 J3 J5J5J3J2J1J4零件編號零件編號Ji加工時間加工時間(h)39172936620293440總流程時間總流程時間 Fmax=40(h)其次計算加工周期：其次計算加工周期：解法二，甘特圖解法二，甘特圖解法一，矩陣表法解法一，矩陣表法 1）目標：加工周期最短，即總流程時間最小。）目標：加工周期最短，即總流程時間最小。2）方法：約翰遜貝爾曼擴展法。）方法：約翰遜貝爾曼擴展法。3）使用條件：若）使用條件：若

18、min tiAmax tkB 或或min tiCmax tkB，可，可得最優(yōu)解，否則較優(yōu)解。得最優(yōu)解，否則較優(yōu)解。2、3/n/Fn種工件在三臺設(shè)備上的加工，其工藝順序均相同種工件在三臺設(shè)備上的加工，其工藝順序均相同 零件零件編號編號Ji加工時間加工時間/hJ1J2J3J4AtiA158612BtiB3156CtiC41057例例12.3 設(shè)有四種零件在三臺機床上加工，工藝順序相同，各設(shè)有四種零件在三臺機床上加工，工藝順序相同，各機床只有一臺。各零件在機床上加工所需時間：機床只有一臺。各零件在機床上加工所需時間：min tmin tiAiA=6max t=6max tiBiB=6=6可轉(zhuǎn)換可轉(zhuǎn)換

19、零件零件編號編號Ji加工時間加工時間/hJ1J2J3J4GtiG1891118HtiH7111013加工順序為：加工順序為：J2 J4J3J1零件編號零件編號JiJ2J4J3J1AtiA8812206261541BtiB19626531344CtiC1019733538448總流程時間總流程時間 Fmax=48(h) 最優(yōu)解最優(yōu)解3、m/n/F n種工件在種工件在m臺機床上加工的流水型排序問題及解法臺機床上加工的流水型排序問題及解法 （Scheduling n Jobs on m Machines）n組合原則為：組合原則為： t tiAiA= =(h=1, 2, (h=1, 2, ,m,m1)

20、1)t tiBiB= ,m= ,mk+1k+1n共組合共組合m m1 1次，每一次組合對應(yīng)一個順序，從次，每一次組合對應(yīng)一個順序，從m m1 1種順序的加工周期中挑最小的。種順序的加工周期中挑最小的。h1kikth1kit方法一：約翰遜貝爾曼規(guī)則的擴展法方法一：約翰遜貝爾曼規(guī)則的擴展法n把總工時（把總工時（ ）最大的零件作為關(guān)鍵零件，記為）最大的零件作為關(guān)鍵零件，記為J Jc c, ,n若若Max( )= , Max( )= , 則則k k零件為零件為J Jc c1) 1) 除除J Jc c外，凡外，凡t ti1i1t timim的零件，按的零件，按t ti1i1從小到大排從小到大排在在J J

21、c c前前 ; ;2) 2) 除除J Jc c外，凡滿足外，凡滿足t ti1i1t timim的零件，按的零件，按t timim從大到從大到小排在小排在J Jc c后。后。3) 3) 若若t ti1i1=t=timim，相應(yīng)零件既可排在，相應(yīng)零件既可排在J Jc c前，又可排前，又可排在在J Jc c后后 , ,得到多個方案，從中選最優(yōu)。得到多個方案，從中選最優(yōu)。m1jijtm1jkjtm1jijt方法二：關(guān)鍵零件法（方法二：關(guān)鍵零件法（Key Parts Model） 零件零件機床工時機床工時J1J2J3J4M1ti11263M2ti28429M3ti34582 51jijt13111614

22、計算計算tit1+t2+t3總加工時間最長的工件為總加工時間最長的工件為J3，故關(guān)鍵零件為，故關(guān)鍵零件為J3ti1ti3的零件為的零件為J4故故排序為排序為J1 - J2 J3 J4方法三：最小排序系數(shù)法方法三：最小排序系數(shù)法mmijimijijttk12,21,按按 kj 大小，從小到大排序。上例按最大小，從小到大排序。上例按最小排序系數(shù)法，可得到較優(yōu)加工順序。小排序系數(shù)法，可得到較優(yōu)加工順序。 當設(shè)備數(shù)為單數(shù)時，把中間設(shè)備的加工當設(shè)備數(shù)為單數(shù)時，把中間設(shè)備的加工時間，平分后加到前后兩部分設(shè)備上去。時間，平分后加到前后兩部分設(shè)備上去。0.320.430.71.01.21.061.291.07

23、 kjt1jt1jt1jt1jt2jt1j679232J87311324J7983626J6819765J5361462J4196485J3923657J2284375J1M6M5M4M3M2M1 任務(wù)任務(wù) 設(shè)備設(shè)備故故排序為排序為J8 J7 J6 J5 J3 J1 J4 J2nN N項任務(wù)，經(jīng)項任務(wù)，經(jīng)M M臺設(shè)備加工，各任務(wù)工藝順序臺設(shè)備加工，各任務(wù)工藝順序不同。不同。n這類問題的排序方案共有這類問題的排序方案共有 (N!)(N!)m m個個，顯然，顯然，這類問題的排序，用解析法求最優(yōu)方案幾乎這類問題的排序，用解析法求最優(yōu)方案幾乎是不可能的。是不可能的。n實踐中多采用排序規(guī)則的方法，分別為每一實踐中多采用排序規(guī)則的方法，分別為每一生產(chǎn)設(shè)備排序。或采用仿真方法進行排序。生產(chǎn)設(shè)備排序?；虿捎梅抡娣椒ㄟM行排序。(三三)非流水型排序問題非流水型排序問題 J1 A(2) B(1) C(8) D(2) J2 A(1) D(4) B(1) C(4)J24141CBDACBDA21820J1abcdeba比較兩條線路長：比較兩條線路長： O-a-b-c-d-e F1=2+1+8+2+2=15小時小時; O-a-b-c-d-e F2=1+4+1+6+4=16小時小時; 選擇選擇o-a