約翰遜法是作業(yè)排序中的一種排序方法。選出最短加工時間i*，若最短加工時間有多個，任選1個.若i*出現(xiàn)在機床1，它對應的工件先安排加工，否則放在最后安排，安排后劃去該工件,重復上兩個步驟，直到所有工件都排序完畢。

約翰遜法適用的條件是：n個工件經(jīng)過二、三臺設備（有限臺設備）加工，所有工件在有限設備上加工的次序相同。

舉例說明:有五個工件在二臺設備上加工，加工順序相同，現(xiàn)在設備1上加工，再在設備2上加工，工時列于下表1中，用約翰遜法排序。

表1 加工工時表

第一步，取出最小工時t12=2。如該工時為第一工序的，則最先加工；反之，則放在最后加工。此例是A工件第二工序時間，按規(guī)則排在最后加工。

第二步，將該已排序工作劃去。

第三步，對余下的工作重復上述排序步驟，直至完畢。此時t21=t42=3，B工件第一工序時間最短，最先加工；D工件第二工序時間最短，排在余下的工件中最后加工。最后得到的排序為：B-C-E-D-A。整批工件的停留時間為27分鐘。

這是一種適用于n/2/P/F_max排序問題的靜態(tài)排序方法約翰遜法的目標是要求得到全組的零件具有最短的生產(chǎn)周期的生產(chǎn)進度表。數(shù)學上可以證明，應用約翰遜法所得的排序結(jié)果是最優(yōu)解。

1.約翰遜法的排列規(guī)則

如果滿足mint_1k;t_2k < mint_2k;t_1k

則將k工件排在h工件之前。

式中：t_1k、t_2k：k工件第1工序、第2工序的加工時間；

t_2k、t_1k：h工件第2工序、第1工序的加工時間。

2.約翰遜排序法的進行步驟

(1)列出零件組的工序矩陣；

(2)在工序矩陣中選出加工時間最短的工序。如果改工序?qū)儆诘?工序，則將該工序所屬工件排在前面。反之，最小工序是第2工序，則將該工序所屬的工件排在最后面。若最小的工序又多個，可任選其中的一個；

(3)將已排序的工件從工序矩陣中消去；

(4)繼續(xù)按步驟(1)、(2)、(3)進行排序，若所有工件都已排定投產(chǎn)順序，排序即告結(jié)束。

例：有6中零件，其工序矩陣見表

表：零件的工序矩陣

根據(jù)約翰遜法的排序步驟：

(1)按前工序最小的選出2號工件及后工序最小的選出3號工件前，3號排在后。從原工件矩陣中消去2號及3號零件，見下表。

(2)對原工件矩陣繼續(xù)步驟(1)、(2)、(3)，前工序最小的有4和5號兩工件可任選其一，后工序最小的為6號工件。選出該兩工件，并按前述規(guī)則排列，插入新工序矩陣見下表。

(3)按規(guī)則繼續(xù)進行排序，5號工件排在前，1號工件拍在后。

工序矩陣。表是按約翰遜法排序后的新工藝矩陣。

按約翰遜法排序后的新工藝矩陣

對于同順序排序問題，可以通過表上作業(yè)，計算全組零件的最大流程時間F_max見表

最大流程時間F_max計算表

表中斜線右方的數(shù)字是到該工序結(jié)束時的流程時間，它的計算方法如下：

到該工序結(jié)束時間的流程時間=該工序的開始時間+該工序的加工時間

在生產(chǎn)過程中一個工序的開始時間取決于兩個因素：

• 該工序前一道工序的結(jié)束時間；

• 該工序所用的設備上緊前工件的加工結(jié)束時間。該工序的開始時間應取上述兩數(shù)中之大者。例如，1號工件第2工件結(jié)束時的流程時間，應為F_j1m2=max{16;19}+8=27。

根據(jù)上表中的數(shù)據(jù)可得到一張1至6號工件的生產(chǎn)進度表，有每個工件在各臺設備上的開工時間與完工時間。

本例中第4和第5號工件在被選時，由于前工序均為最小工序，當時任選了4號。如果選了5號結(jié)果有如何呢？見下表。

本例不同排序方案的最大流程計算

根據(jù)上面兩表的計算結(jié)果，說明對于條件等價的條件，任選其中之一，不影響最后結(jié)果。按約翰遜法所排出的結(jié)果應為最優(yōu)解，這里說明最優(yōu)解可能不止一個，可以有多個等值的最優(yōu)解。

約翰遜法只適用于兩工序工件的排序問題，所以它的使用范圍受到很大的限制。