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

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

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

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

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

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

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

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

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

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

10、工序總時(shí)間.派工單 派工單dispatch list或稱調(diào)度單，是一種面向任務(wù)中心闡明加工優(yōu)先級(jí)的文件，闡明任務(wù)在一周或一個(gè)時(shí)期內(nèi)要完成的消費(fèi)義務(wù)。 闡明哪些任務(wù)曾經(jīng)到達(dá)，正在排隊(duì)，該當(dāng)什么時(shí)間開場(chǎng)加工，什么時(shí)間完成，加工單的需用日期是哪天，方案加工時(shí)數(shù)是多少，完成后又應(yīng)傳給哪道工序。 闡明哪些工件即將到達(dá)，什么時(shí)間到，從哪里來(lái)。 根據(jù)派工單，車間調(diào)度員、任務(wù)中心操作員對(duì)目前和即將到達(dá)的義務(wù)一目了然。.數(shù)量需用 完成派工單的典型格式方案進(jìn)度開場(chǎng)日期 完工日期物料號(hào)物料稱號(hào)任務(wù)中心：8513稱號(hào)：車床加工單號(hào)工序號(hào)數(shù)量需用 完成時(shí)間預(yù)備 加工上工序下工序正加工的工件已加工的工件將到達(dá)的工件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 入庫(kù)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、.任務(wù)中心特征和重要性 任務(wù)中心是消費(fèi)運(yùn)營(yíng)中的個(gè)區(qū)域，在這個(gè)區(qū)域中，組織消費(fèi)資源來(lái)完成任務(wù)。任務(wù)中心可以是一臺(tái)機(jī)器、一一組機(jī)器或完成某一類型任務(wù)的一個(gè)區(qū)域，這些任務(wù)中心可以按工藝專業(yè)化的普通作業(yè)車間組織，或者按產(chǎn)品流程、裝配線、成組技術(shù)單元構(gòu)造進(jìn)展組織。 在工藝專業(yè)化情況下，工件需按規(guī)定道路在各個(gè)按功能組織的任務(wù)中心之間挪動(dòng)。作業(yè)排序涉及決議工件加工順序以及分配相應(yīng)的機(jī)器來(lái)對(duì)這些工件加工。 一個(gè)作業(yè)排序系統(tǒng)區(qū)別于另一個(gè)作業(yè)排序系統(tǒng)的特征是：在進(jìn)展作業(yè)排序時(shí)是如何思索消費(fèi)才干的。.有限負(fù)荷方法和無(wú)限負(fù)荷方法 無(wú)限負(fù)荷 指的是當(dāng)將任務(wù)分配給一個(gè)任務(wù)中心時(shí)，只思索它需求多少時(shí)間，而不直接思索完成這項(xiàng)

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

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

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

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

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

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

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

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

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

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

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

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