生產(chǎn)管理-Charpt-08-作業(yè)排序

1、消費與運作管理Production & Operation Management.作業(yè)排序.第七章 作業(yè)排序 根本概念 最長流程時間 n/2/F/Fmax問題的算法 普通n/m/P/ Fmax問題的啟發(fā)式算法.一、根本概念1、排序排序就是要將不同的任務義務安排一個執(zhí)行的順序，使預定的目的最優(yōu)化。實踐上就是要處理如何按時間的先后，將有限的人力、物力資源分配給不同任務義務，使預定目的最優(yōu)化的問題。.排序中常用的幾個概念工件Job：效力對象；機器Machine、Processor：效力者。如：n個零件在機器上加工，那么零件是工件，設備是機器；工人維修設備，出缺點的設備是工件，工人是機器。. 所以，作

2、業(yè)排序也就是要確定工件在機器上的加工順序，可用一組工件代號的一種陳列來表示。 如可用1，6，5，4，3，2表示加工順序：J1J6J5J4J3J22。.2、作業(yè)方案Scheduling作業(yè)方案與排序不是一回事，它不僅要確定工件的加工順序，而且還要確定每臺機器加工每個工件的開工時間和完工時間。假設按最早能夠開完工時間來編排作業(yè)方案，那么排序完后，作業(yè)方案也就確定了。.3、排序問題的分類與表示1單臺機器與多臺機器的排序問題。2流水車間與單件車間排序問題。.流水車間排序問題的根本特征：每個工件的加工道路都一樣。如車銑磨。這里指的是工件的加工流向一致，并不要求每個工件必需在每臺機器上加工。如有的工件為車

3、磨，有的為銑磨。不僅加工道路一致，而且一切工件在各臺機器上的加工順序也一樣，這種排序稱為陳列排序同順序排序。如工件排序為：J1J3J2，那么表示一切機器都是先加工J1，然后加工J3，最后加工J2。.單件車間排序問題的根本特征：每個工件都有其獨特的加工道路，工件沒有一定的流向。.3表示方法 普通正規(guī)的表示方法為：n/m/A/B n：工件數(shù)；m：機器數(shù)； A：車間類型F、P、G；B：目的函數(shù).4普通來說，陳列排序問題的最優(yōu)解不一定是相應流水車間排序問題的最優(yōu)解，但普通是比較好的解。而對于僅有2臺或3臺機器的情況，那么陳列排序問題的最優(yōu)解一定是相應流水車間排序問題的最優(yōu)解。.二、最長流程時間最長流程

4、時間加工周期：從第一個工件在第一臺機器上加工起到最后一個工件在最后一臺機器上加工終了為止所經(jīng)過的時間。假定一切工件的到達時間都為0，那么Fmax等于排在末位加工的工件在車間的停留時間。.計算Fmax的幾個假定條件：機器M1不會發(fā)生空閑；對其它機器，能對某一工件加工必需具備2個條件：機器必需完成排前一位的工件的加工；要加工的工件的上道工序曾經(jīng)完工。.三、n/2/F/Fmax問題的算法Johnson算法：假定：ai為工件Ji在機器M1上的加工時間，bi為工件Ji在機器M2上的加工時間，每個工件按M1M2的道路加工。.Johnson算法的步驟：從加工時間矩陣中找出最短的加工時間假設最短時間出如今M1

5、上，那么對應的工件盡能夠往前排假設最短時間出如今M2上，那么對應的工件盡能夠往后排假設最短時間有多個，那么任選一個劃去已排序的工件假設一切工件都已排序，那么停頓，否那么反復上述步驟.四、普通n/m/P/ Fmax問題的啟發(fā)式算法 對于普通的n/m/P/Fmax問題，可以用分支定界法求得最優(yōu)解，但計算量很大。實踐中，可以用啟發(fā)式算法求近優(yōu)解。.關鍵工件法的步驟：計算Pi= Pij ，找出Pi最長的工件，將之作為關鍵工件C。對其他工件，假設Pi1Pim ，那么按Pi1不減的順序排成序列SA。假設Pi1 Pim ，那么按Pim不增的順序排成序列SB。順序SA，C，SB即為近優(yōu)解。.Shop Floo

6、r Activity Management車間作業(yè)管理POM 2002. 車間作業(yè)管理的根本概念 車間作業(yè)排序 車間作業(yè)控制.典型的作業(yè)排序和控制功能以下職能必需在對作業(yè)排序和控制時完成： 分配訂單、設備和人員到各任務中心或其他規(guī)定的地方 決議訂單順序即建立訂單優(yōu)先級 對已排序作業(yè)開場安排消費，通常稱之為調(diào)度 車間作業(yè)控制或消費作業(yè)控制，包括： 在作業(yè)進展過程中，檢查其形狀和控制造業(yè)的速度 加快為期已晚的和關鍵的作業(yè) 方案員的決策取決于以下要素：每個作業(yè)的方式和規(guī)定的工藝順序要求，每個任務中心上現(xiàn)有作業(yè)的形狀，每個任務中心前作業(yè)的排隊情況，作業(yè)優(yōu)先級，物料的可得性，當天較晚發(fā)布的作業(yè)訂單，任務

7、中心資源的才干 .車間作業(yè)管理的信息源 方案文件 工程主文件記錄全部有關零件的信息 工藝道路文件記錄消費零件的加工順序 任務中心文件記錄任務中心數(shù)據(jù) 控制文件 車間文物主文件為每個消費中的義務提供一條記錄 車間義務詳細文件記載完成每個車間義務所需工序 從任務人員得到的信息.方案文件數(shù)據(jù)概要方案文件文件中的內(nèi)容工程主文件工藝道路文件任務中心文件 零件號 零件稱號 消費提早期 現(xiàn)有庫存 已分配量 已定貨量 批量 工序號 工序稱號 預備時間 加工時間 任務中心號 才干數(shù)據(jù) 交換任務中心 排隊時間.控制文件文件中的信息車間義務 主文件車間義務 細文件 車間義務號 義務數(shù)量 完工數(shù)量 廢品數(shù)量 支付數(shù)量

8、 交貨日期 本錢信息 優(yōu)先級 未完成量 車間義務 工序號 任務中心 方案預備時間/實踐預備時間 方案加工工時/實踐加工工時 方案數(shù)量/完工數(shù)量 廢品數(shù)量 開工日期/完工日期.加工單 知道需求經(jīng)過哪些加工工序(工藝道路) 知道需求什么工具、資料、才干的提早期 確定工具、資料、才干和提早期的可用性 處理工具、資料、才干和提早期短缺問題 最后將義務下達、盡能夠滿足方案要求 發(fā)放工具、資料和義務的有關文件給車間加工單work order 或車間定單shop order是一種面向加工件闡明物料需求方案的文件，可以跨車間甚至廠際協(xié)作。加工單的格式同工藝道路報表類似。.方案進度開場日期 完工日期 任務中心

9、規(guī)范時間(小時) 編號 稱號 預備 加工 機器加工單的典型格式定單號：970215需用數(shù)量：100件方案日期：970630物料稱號：C物料號：111000需用日期：970901102030405060下料車削熱處置磨削電鍍檢驗010010203006010020529000108015鋸床車床電爐磨床(外協(xié))質(zhì)檢0.51.01.21.0.0.251.252.000.105.00.25.5126.06.2201.0(240)10.0970710970715970725970729970815970829970712970724970726970814970828970830M432工序工序稱號本

10、工序總時間.派工單 派工單dispatch list或稱調(diào)度單，是一種面向任務中心闡明加工優(yōu)先級的文件，闡明任務在一周或一個時期內(nèi)要完成的消費義務。 闡明哪些任務曾經(jīng)到達，正在排隊，該當什么時間開場加工，什么時間完成，加工單的需用日期是哪天，方案加工時數(shù)是多少，完成后又應傳給哪道工序。 闡明哪些工件即將到達，什么時間到，從哪里來。 根據(jù)派工單，車間調(diào)度員、任務中心操作員對目前和即將到達的義務一目了然。.數(shù)量需用 完成派工單的典型格式方案進度開場日期 完工日期物料號物料稱號任務中心：8513稱號：車床加工單號工序號數(shù)量需用 完成時間預備 加工上工序下工序正加工的工件已加工的工件將到達的工件758

11、31 D 97087 20 16 20 970504 970504 1.0 1028 860188501 C 97098 50 20 970504 970506 0.2 15 1028 8603 51888 F 97120 40 40 970506 970507 0.2 10 8420 入庫16877 G 97376 20 30 970507 970507 0.1 5.0 8510 852337414 D 97087 25 15 970510 970511 0.1 8.0 7100 8200 88501 C 97098 10 10 970512 970512 0.1 3.0 7200 8532

12、.任務中心特征和重要性 任務中心是消費運營中的個區(qū)域，在這個區(qū)域中，組織消費資源來完成任務。任務中心可以是一臺機器、一一組機器或完成某一類型任務的一個區(qū)域，這些任務中心可以按工藝專業(yè)化的普通作業(yè)車間組織，或者按產(chǎn)品流程、裝配線、成組技術單元構造進展組織。 在工藝專業(yè)化情況下，工件需按規(guī)定道路在各個按功能組織的任務中心之間挪動。作業(yè)排序涉及決議工件加工順序以及分配相應的機器來對這些工件加工。 一個作業(yè)排序系統(tǒng)區(qū)別于另一個作業(yè)排序系統(tǒng)的特征是：在進展作業(yè)排序時是如何思索消費才干的。.有限負荷方法和無限負荷方法 無限負荷 指的是當將任務分配給一個任務中心時，只思索它需求多少時間，而不直接思索完成這項

13、任務所需的資源能否有足夠的才干，也不思索在該任務中，每個資源完成這項任務時的實踐順序。通常僅檢查一下關鍵資源，大體上看看其能否超負荷?？梢愿鶕?jù)各種作業(yè)順序下的調(diào)整和加工時間規(guī)范來計算出一段時間內(nèi)所需的任務量來斷定。 有限負荷 實踐上是用每一訂單所需的調(diào)整時間和運轉(zhuǎn)時間對每一種資源詳細方案。提早期由期望作業(yè)時間調(diào)整和運轉(zhuǎn)時間加上由于資料運輸和等待訂單執(zhí)行而引起的期望排隊延期時間而估算出。從實際上將，當運用有限負荷時，所由的方案都是可行的。.前向排序和后向排序 前向排序 指的是系統(tǒng)接受一個訂單后對訂單所需作業(yè)按從前向后的順序進展排序，前向排序系統(tǒng)才干通知我們訂單能完成的最早日期。 后向排序 是從未

14、來的某個日期能夠是一個商定交貨日期開場，按從后向前的順序?qū)λ枳鳂I(yè)進展排序。后向排序通知我們?yōu)榱税匆?guī)定日期完成，一個作業(yè)必需開場的最晚時間。區(qū)分作業(yè)排序的另一個特征是基于前向排序還是后向排序。在前向排序和后向排序中，最常用的是前向排序。.消費工序類型和方案方法 類型 產(chǎn)品 特征通常的方案方法單一工序大批量消費中等批量消費小批量消費化工產(chǎn)品、鋼、金屬、液體產(chǎn)品等汽車、摩托車、家用設備工業(yè)用品、最終消費品定做的或規(guī)范的設備、公用儀器等全自動化，產(chǎn)品中勞動力本錢低，設備公用于一種產(chǎn)品自動化配備，半自動化傳動安裝或挪動裝配線成組技術單元，專業(yè)化小工廠按消費功能組織的機器中心，通用設備換裝時間相當長等有

15、限符合，前向排序，機器有限 消費線有限負荷，前向排序，機器有限，準時化消費無限負荷，前向排序，有限調(diào)度控制，常勞動力有限但有時機器有限無限負荷，前向排序，.車間作業(yè)排序的目的 滿足交貨期 極小化提早期 極小化預備時間或本錢 極小化在制品庫存 極大化設備或勞動力的利用注：最后一個目的是有爭議的，由于僅僅依托堅持一切設備/或員工處于忙碌的形狀能夠不是在工序中管理消費的最有效方法.作業(yè)方案和排序的關系 編作業(yè)方案scheduling與排序sequencing不是同義語。排序只是確定工件在機器上的加工順序?？梢越?jīng)過一組工件的代號的一種陳列來表示該組工件的加工順序。而編制造業(yè)方案，那么不僅包括確定工件的

16、加工順序，而且包括確定機器加工每個工件的開場時間和完成時間。因此，只需作業(yè)方案才干指點每個工人的消費活動。 由于編制造業(yè)方案的主要問題是確定各臺機器上工件的加工順序，而且，在通常情況下都是按最早能夠開 完工時間來編排作業(yè)方案。因此，當工件的加工順序確定之后，作業(yè)方案也就確定了。所以，人們經(jīng)常不加區(qū)別地運用“排序與“編作業(yè)方案。.作業(yè)排序的十大優(yōu)先規(guī)那么 FCFS先到先效力，F(xiàn)irst Come First Server：按訂單送到的先后順序進展加工。 SOT最短作業(yè)時間：所需加工時間最短的作業(yè)首先進展，然后是加工時間第二最短的，如此等等。這個規(guī)那么等同于SPT最短加工時間規(guī)那么。 DDate交

17、貨期：最早交貨期最早加工。將交貨期最早的作業(yè)放在第一個進展。 開場日期：交貨期減去正常的提早期最早開場的作業(yè)第一個進展。. STR剩余松弛時間：STR是交貨期前所剩余時間減去剩余的加工時間所得的差值。STR最短的義務最先進展。 STR/OP每個作業(yè)剩余的松弛：STR/OP最短的義務最先進展。STR/OP的計算方法為： CR緊迫系數(shù)：緊迫系數(shù)是用交貨期減去當前日期的差值除以剩余的任務日數(shù)。緊迫系數(shù)最小的義務先進展。STR/OP =交貨提早期所剩的時間-剩余的加工時間剩余的作業(yè)數(shù)緊迫系數(shù)CR=需用日期-今日日期剩余的方案提早期.CR=負值闡明曾經(jīng)脫期CR=1闡明剩余時間剛好夠用CR1剩余時間有富有

18、CR1剩余時間不夠CR值小者優(yōu)先級高。一個工件完成后，其他工件的CR值會有變化，應隨時調(diào)整 QO排隊比率：排隊比率是用方案中剩余的松弛時間除以方案中剩余的排隊時間，排隊比率最小的先進展。 LCFS后到先效力：該規(guī)那么經(jīng)常作為缺省規(guī)那么運用。由于后來的工單放在先來的上面，操作人員通常是先加工上面的工單。 隨機規(guī)那么.作業(yè)排序的評價在某機器上或某任務中心決議哪個作業(yè)首先開場任務的過程稱為排序或優(yōu)先調(diào)度排序。在進展作業(yè)排序時，需用到優(yōu)先調(diào)度規(guī)那么。這些規(guī)那么能夠很簡單，僅需根據(jù)一種數(shù)據(jù)信息對作業(yè)進展排序。這些數(shù)據(jù)可以是加工時間、交貨期貨到達的順序。以下作業(yè)排序規(guī)范可用于評價優(yōu)先規(guī)那么滿足顧客或下一道

19、工序作業(yè)的交貨期極小化流程時間作業(yè)在工序中所耗費的時間極小化在制品庫存極小化設備和工人的閑置時間.排序問題的分類與表示法按機器的種類和數(shù)量分：單臺機器排序問題和多臺機器排序問題按加工道路的特征分：單件車間排序問題和流水車間排序問題按工件到達車間的情況不同分：靜態(tài)排序問題和動態(tài)排序問題按目的函數(shù)分：平均流程時間最短或誤期完工的工件數(shù)最少按參數(shù)的性質(zhì)分：確定型排序問題與隨機型排序問題Conway等人提出的排序法：n/m/A/B其中：n 工件數(shù)m機器數(shù)A車間類型F表示流水車間排序，P流水車間陳列排序問題 ， G表示單件車間B目的函數(shù).N個作業(yè)單臺任務中心的排序這類問題被稱作“n個作業(yè)單臺任務中心的問

20、題或“n/1，實際上，排序問題的難度隨著任務中心數(shù)量的添加而增大，而不是隨著作業(yè)數(shù)量的添加而增大，對n的約束是其必需是確定的有限的數(shù)例：n個作業(yè)單臺任務中心排序問題。在一周的開場，有5位顧客提交了他們的訂單。原始數(shù)據(jù)為：訂單以到達的順序 加工時間/天 交貨期/天ABCDE3426156792.方案一利用FCFS規(guī)那么，其流程時間的結果如下： 加工順序 加工時間 交貨日期 流程時間ABCDE34261567920+3=33+4=77+2=99+6=1515+1=16總流程時間=3+7+9+15+16=50天平均流程時間=50/5=10天將每個訂單的交貨日期與其流程時間相比較，發(fā)現(xiàn)只需A訂單能按時

21、交貨。訂單B，C，D和E將會延期交貨，延期時間分別為1,2,6,14天。每個訂單平均延期1+1+2+6+14/5=4.6天。.方案二利用SOT規(guī)那么，流程時間為： 加工順序 加工時間 交貨日期 流程時間ECABD12346275690+1=11+2=33+3=66+4=1010+6=16總流程時間=1+3+6+10+16=36天平均流程時間=36/5=7.5天SOT規(guī)那么的平均流程時間比FCFS規(guī)那么的平均流程時間小。另外，訂單E和C將在交貨日期前完成，訂單A僅延期1天。每個訂單的平均延期時間為0+0+1+4+7/5=2.4天。. 加工順序 加工時間 交貨日期 流程時間EABCD1342625

22、6790+1=11+3=44+4=88+2=1010+6=16總流程時間=1+4+8+10+16=39天平均流程時間=39/5=7.8天在這種情況下，訂單B，C和D將會延期，平均延期時間為0+0+2+7/5=2.4天。方案三 利用DDate規(guī)那么，排序結果為：. 加工順序 加工時間 交貨日期 流程時間EDCBA16243297650+1=11+6=77+2=99+4=1313+3=16總流程時間=1+7+9+13+16=46天平均流程時間=46/5=9.2天平均延期=4.0天方案四利用LCFS規(guī)那么，估計流程時間為：. 加工順序 加工時間 交貨日期 流程時間DCAEB62314975260+6

23、=66+2=88+3=1111+1=1212+4=16總流程時間=6+8+11+12+16=55天平均流程時間=55/5=11天平均延期=5.4天方案五利用隨機規(guī)那么，排序結果為：. 加工順序 加工時間 交貨日期 流程時間EABD6=61+3=44+4=88+6=1414+2=16總流程時間=6+4+8+14+16=43天平均流程時間=43/5=8.6天平均延期=3.2天方案六利用STR規(guī)那么，排序結果為：. 規(guī)那么 總的完成時間 平均完成時間 平均延期FCFSSOTDDateLCFS隨機STR503639465343107.27.89.210.68.64.62.42

24、.44.05.43.2很明顯，此例中SOT比其他的規(guī)那么都好，但情況總是這樣的嗎？答案是一定的。另外，從數(shù)學上可以證明，在n/1情況下，用其他的評價準那么，如等待時間均值和完成時間均值最小，SOT規(guī)那么也是最優(yōu)方案?，F(xiàn)實上，這個簡單被稱為“在整個排序?qū)W科中最重要的概念.N個作業(yè)兩臺任務中心排序略微復雜的n/2排序情況，被稱為約翰遜Hohnson規(guī)那么或方法， 這是S.M.Johnson于1954年提出的，其目的是極小化從第一個作業(yè)開場到最后一個作業(yè)為止的全部流程時間，以ai表示Ji在M1上加工時間，以bi表示Ji在M2上的加工時間。每個工件都按M1M2的道路加工。Johnson的算法法那么是：假設Min(ai,bj)IaIp=IaIpOaIa=OaIaOaOp=OaOpOa加工件推遲到達加工件按方案到達加工件提早到達在制品添加在制品維持不變在制品減少任務中心落后方案任務中心按