什么是約翰遜法?
約翰遜法是作業(yè)排序中的一種排序方法。選出最短加工時間i*，若最短加工時間有多個，任選1個.若i*出現(xiàn)在機床1，它對應(yīng)的工件先安排加工，否則放在最后安排，安排后劃去該工件,重復(fù)上兩個步驟，直到所有工件都排序完畢。
約翰遜法適用的條件是：n個工件經(jīng)過二、三臺設(shè)備（有限臺設(shè)備）加工，所有工件在有限設(shè)備上加工的次序相同。
舉例說明:有五個工件在二臺設(shè)備上加工，加工順序相同，現(xiàn)在設(shè)備1上加工，再在設(shè)備2上加工，工時列于下表1中，用約翰遜法排序。
表1 加工工時表
約翰遜法具體步驟
第一步，取出最小工時t12=2。如該工時為第一工序的，則最先加工；反之，則放在最后加工。此例是A工件第二工序時間，按規(guī)則排在最后加工。
第二步，將該已排序工作劃去。
第三步，對余下的工作重復(fù)上述排序步驟，直至完畢。此時t21=t42=3，B工件第一工序時間最短，最先加工；D工件第二工序時間最短，排在余下的工件中最后加工。最后得到的排序為：B-C-E-D-A。整批工件的停留時間為27分鐘。
1.約翰遜法的排列規(guī)則
如果滿足mint1k;t2k < mint2k;t1k
則將k工件排在h工件之前。
式中：t1k、t2k：k工件第1工序、第2工序的加工時間；
t2k、t1k：h工件第2工序、第1工序的加工時間。
2.約翰遜排序法的進行步驟
(1)列出零件組的工序矩陣；
(2)在工序矩陣中選出加工時間最短的工序。如果改工序?qū)儆诘?工序，則將該工序所屬工件排在前面。反之，最小工序是第2工序，則將該工序所屬的工件排在最后面。若最小的工序又多個，可任選其中的一個；
(3)將已排序的工件從工序矩陣中消去；
(4)繼續(xù)按步驟(1)、(2)、(3)進行排序，若所有工件都已排定投產(chǎn)順序，排序即告結(jié)束。
例：有6中零件，其工序矩陣見表
表：零件的工序矩陣
工件號 |
1 |
2 |
3 |
4 |
5 |
6 |
第1工序M1 |
6 |
2 |
9 |
4 |
4 |
5 |
第2工序M2 |
8 |
3 |
3 |
5 |
8 |
4 |
根據(jù)約翰遜法的排序步驟：
(1)按前工序最小的選出2號工件及后工序最小的選出3號工件前，3號排在后。從原工件矩陣中消去2號及3號零件，見下表。
項目 |
新工序矩陣 |
原工序矩陣 |
||||
工件號 |
2 |
3 |
1 |
4 |
5 |
5 |
第1工序M1 |
2 |
9 |
6 |
4 |
4 |
5 |
第2工序M2 |
3 |
3 |
8 |
5 |
8 |
4 |
(2)對原工件矩陣?yán)^續(xù)步驟(1)、(2)、(3)，前工序最小的有4和5號兩工件可任選其一，后工序最小的為6號工件。選出該兩工件，并按前述規(guī)則排列，插入新工序矩陣見下表。
項目 |
新工序矩陣 |
原工序矩陣 |
|||||
工件號 |
2 |
4 |
6 |
3 |
1 |
5 |
|
第1工序M1 |
2 |
4 |
5 |
9 |
6 |
4 |
|
第2工序M2 |
3 |
5 |
4 |
3 |
8 |
8 |
|
(3)按規(guī)則繼續(xù)進行排序，5號工件排在前，1號工件拍在后。
工序矩陣。表是按約翰遜法排序后的新工藝矩陣。
按約翰遜法排序后的新工藝矩陣
項目 |
新工序矩陣 |
|||||
工件號 |
2 |
4 |
5 |
1 |
6 |
3 |
第1工序M1 |
2 |
4 |
6 |
5 |
9 |
|
第2工序M2 |
3 |
5 |
8 |
8 |
4 |
3 |
對于同順序排序問題，可以通過表上作業(yè)，計算全組零件的最大流程時間Fmax見表
最大流程時間Fmax計算表
工件號 |
2 |
5 |
4 |
1 |
6 |
3 |
第1工序M1 |
2/2 |
4/6 |
4/10 |
6/16 |
5/21 |
9/30 |
第2工序M2 |
3/5 |
5/11 |
8/19 |
8/27 |
4/31 |
3/34 |
表中斜線右方的數(shù)字是到該工序結(jié)束時的流程時間，它的計算方法如下：
到該工序結(jié)束時間的流程時間=該工序的開始時間+該工序的加工時間
在生產(chǎn)過程中一個工序的開始時間取決于兩個因素：
該工序前一道工序的結(jié)束時間；
該工序所用的設(shè)備上緊前工件的加工結(jié)束時間。該工序的開始時間應(yīng)取上述兩數(shù)中之大者。例如，1號工件第2工件結(jié)束時的流程時間，應(yīng)為Fj1m2=max{16;19}+8=27。
根據(jù)上表中的數(shù)據(jù)可得到一張1至6號工件的生產(chǎn)進度表，有每個工件在各臺設(shè)備上的開工時間與完工時間。
本例中第4和第5號工件在被選時，由于前工序均為最小工序，當(dāng)時任選了4號。如果選了5號結(jié)果有如何呢？見下表。
本例不同排序方案的最大流程計算
工件號 |
2 |
5 |
4 |
1 |
6 |
3 |
第1工序M1 |
2/2 |
4/6 |
4/10 |
6/16 |
5/21 |
9/30 |
第2工序M2 |
3/5 |
8/14 |
5/19 |
8/27 |
4/31 |
3/34 |
根據(jù)上面兩表的計算結(jié)果，說明對于條件等價的條件，任選其中之一，不影響最后結(jié)果。按約翰遜法所排出的結(jié)果應(yīng)為最優(yōu)解，這里說明最優(yōu)解可能不止一個，可以有多個等值的最優(yōu)解。
約翰遜法只適用于兩工序工件的排序問題，所以它的使用范圍受到很大的限制。
某公司在一次火災(zāi)中損壞了5臺儀器，這些儀器的修復(fù)需要經(jīng)過如下兩道工序：
（1）將損壞的儀器運至修理車間，拆卸開；
（2）清洗儀器部件，更換報廢部分，裝配，測試，并送回原車間。
每臺儀器在兩個工序的各自所需時間如表所示。兩道工序分別由不同的人擔(dān)當(dāng)。由于原車間沒有這5臺儀器就無法恢復(fù)生產(chǎn)，所以希望找到一個較好的排序方案，使全部修理時間盡可能短。每臺儀器在兩個工序的各自所需時間如表所示。兩道工序分別由不同的人擔(dān)當(dāng)。由于原車間沒有這5臺儀器就無法恢復(fù)生產(chǎn)，所以希望找到一個較好的排序方案，使全部修理時間盡可能短。
詳細解題過程
(1)①選出最短時間為Y3工序2，時間為 3個單位
②Y3工序2在第二道工序，排在最后即第5位，隊列中去掉Y3。
最后一道作業(yè)為 Y3工序。
(2) 剩余作業(yè)中最短時間工序為Y2工序1，用時4個單位，在第一道工序，所以Y2作業(yè)排在第1位，等待序列中去掉Y2。
(3) 剩余作業(yè)中最短時間工序為Y5工序2，用時8個單位，在第二道工序，所以Y5作業(yè)排在第4位，等待隊列中去掉Y5。
(4) 剩余作業(yè)中最短時間工序為Y1工序1，用時12個單位，在第一道工序，所以Y1作業(yè)排在第2位。
(5) 剩余作業(yè)Y4作業(yè)排在第3位。
所以作業(yè)順序為 Y2 Y1 Y4 Y5 Y3。
原則：1、找最小值min，如果min是前道工序，則該作業(yè)放最前；
若min是后道工序，則該作業(yè)放最后。從等待隊列刪除該作業(yè)。
2、如果有多個值相等，則可以任意選擇。
Johnson算法解題思路
1、選擇最短的作業(yè)時間
2、如果最短時間的作業(yè)在第一個加工中心，則安排在最前面，若在第二個加工中心，則安排在最后面。在等待的隊列中，將該作業(yè)刪除文章來源：http://www.zghlxwxcb.cn/news/detail-482705.html
3、重復(fù)1、2步。文章來源地址http://www.zghlxwxcb.cn/news/detail-482705.html
到了這里，關(guān)于工序排序問題--約翰遜法精講的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
