工序排序问题--约翰逊法精讲

什么是约翰逊法?

约翰逊法是作业排序中的一种排序方法。选出最短加工时间i*，若最短加工时间有多个，任选1个.若i*出现在机床1，它对应的工件先安排加工，否则放在最后安排，安排后划去该工件,重复上两个步骤，直到所有工件都排序完毕。

　　约翰逊法适用的条件是：n个工件经过二、三台设备（有限台设备）加工，所有工件在有限设备上加工的次序相同。

　　举例说明:有五个工件在二台设备上加工，加工顺序相同，现在设备1上加工，再在设备2上加工，工时列于下表1中，用约翰逊法排序。

　　表1 加工工时表

约翰逊法具体步骤

第一步，取出最小工时t12=2。如该工时为第一工序的，则最先加工；反之，则放在最后加工。此例是A工件第二工序时间，按规则排在最后加工。

　　第二步，将该已排序工作划去。

　　第三步，对余下的工作重复上述排序步骤，直至完毕。此时t21=t42=3，B工件第一工序时间最短，最先加工；D工件第二工序时间最短，排在余下的工件中最后加工。最后得到的排序为：B-C-E-D-A。整批工件的停留时间为27分钟。

1.约翰逊法的排列规则

　　如果满足mint1k;t2k < mint2k;t1k

　　则将k工件排在h工件之前。

　　式中：t1k、t2k：k工件第1工序、第2工序的加工时间；

　　t2k、t1k：h工件第2工序、第1工序的加工时间。

　　2.约翰逊排序法的进行步骤

　　(1)列出零件组的工序矩阵；

　　(2)在工序矩阵中选出加工时间最短的工序。如果改工序属于第1工序，则将该工序所属工件排在前面。反之，最小工序是第2工序，则将该工序所属的工件排在最后面。若最小的工序又多个，可任选其中的一个；

　　(3)将已排序的工件从工序矩阵中消去；

　　(4)继续按步骤(1)、(2)、(3)进行排序，若所有工件都已排定投产顺序，排序即告结束。

　　例：有6中零件，其工序矩阵见表

　　表：零件的工序矩阵

工件号	1	2	3	4	5	6
第1工序M1	6	2	9	4	4	5
第2工序M2	8	3	3	5	8	4

　　根据约翰逊法的排序步骤：

　　(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)对原工件矩阵继续步骤(1)、(2)、(3)，前工序最小的有4和5号两工件可任选其一，后工序最小的为6号工件。选出该两工件，并按前述规则排列，插入新工序矩阵见下表。

项目	新工序矩阵				原工序矩阵
工件号	2	4	6	3	1	5
第1工序M1	2	4	5	9	6	4
第2工序M2	3	5	4	3	8	8

　　(3)按规则继续进行排序，5号工件排在前，1号工件拍在后。

　　工序矩阵。表是按约翰逊法排序后的新工艺矩阵。

　　按约翰逊法排序后的新工艺矩阵

项目	新工序矩阵
工件号	2	4	5	1	6	3
第1工序M1	2	4	6	5	9
第2工序M2	3	5	8	8	4	3

　　对于同顺序排序问题，可以通过表上作业，计算全组零件的最大流程时间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

　　表中斜线右方的数字是到该工序结束时的流程时间，它的计算方法如下：

　　到该工序结束时间的流程时间=该工序的开始时间+该工序的加工时间

　　在生产过程中一个工序的开始时间取决于两个因素：

• 该工序前一道工序的结束时间；

• 该工序所用的设备上紧前工件的加工结束时间。该工序的开始时间应取上述两数中之大者。例如，1号工件第2工件结束时的流程时间，应为Fj1m2=max{16;19}+8=27。

　　根据上表中的数据可得到一张1至6号工件的生产进度表，有每个工件在各台设备上的开工时间与完工时间。

　　本例中第4和第5号工件在被选时，由于前工序均为最小工序，当时任选了4号。如果选了5号结果有如何呢？见下表。

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

工件号	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

　　根据上面两表的计算结果，说明对于条件等价的条件，任选其中之一，不影响最后结果。按约翰逊法所排出的结果应为最优解，这里说明最优解可能不止一个，可以有多个等值的最优解。

　　约翰逊法只适用于两工序工件的排序问题，所以它的使用范围受到很大的限制。

某公司在一次火灾中损坏了5台仪器，这些仪器的修复需要经过如下两道工序：

（1）将损坏的仪器运至修理车间，拆卸开；

（2）清洗仪器部件，更换报废部分，装配，测试，并送回原车间。

每台仪器在两个工序的各自所需时间如表所示。两道工序分别由不同的人担当。由于原车间没有这5台仪器就无法恢复生产，所以希望找到一个较好的排序方案，使全部修理时间尽可能短。每台仪器在两个工序的各自所需时间如表所示。两道工序分别由不同的人担当。由于原车间没有这5台仪器就无法恢复生产，所以希望找到一个较好的排序方案，使全部修理时间尽可能短。

详细解题过程

(1)①选出最短时间为Y3工序2，时间为 3个单位

②Y3工序2在第二道工序，排在最后即第5位，队列中去掉Y3。

最后一道作业为 Y3工序。

(2) 剩余作业中最短时间工序为Y2工序1，用时4个单位，在第一道工序，所以Y2作业排在第1位，等待序列中去掉Y2。

(3) 剩余作业中最短时间工序为Y5工序2，用时8个单位，在第二道工序，所以Y5作业排在第4位，等待队列中去掉Y5。

(4) 剩余作业中最短时间工序为Y1工序1，用时12个单位，在第一道工序，所以Y1作业排在第2位。

(5) 剩余作业Y4作业排在第3位。

所以作业顺序为 Y2 Y1 Y4 Y5 Y3。

原则：1、找最小值min，如果min是前道工序，则该作业放最前；

若min是后道工序，则该作业放最后。从等待队列删除该作业。

2、如果有多个值相等，则可以任意选择。

Johnson算法解题思路

1、选择最短的作业时间

2、如果最短时间的作业在第一个加工中心，则安排在最前面，若在第二个加工中心，则安排在最后面。在等待的队列中，将该作业删除

3、重复1、2步。