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

痛定思痛。 2023-09-24 18:01 22阅读 0赞

### **什么是约翰逊法?** ###

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

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

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

**表1 加工工时表**

![bbfe377ac275eb6ed6ca5b0a00fd1573.gif][]

### **约翰逊法具体步骤** ###

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

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

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

1.约翰逊法的排列规则

如果满足min*t*1*k*;*t*2*k* < min*t*2*k*;*t*1*k*

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

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

*t*2*k*、*t*1*k*：h工件第2工序、第1工序的加工时间。

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

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

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

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

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

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

**表：零件的工序矩阵**

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

(1)按前工序最小的选出2号工件及后工序最小的选出3号工件前，3号排在后。从原工件矩阵中消去2号及3号零件，见下表。

<table style=""> 
 <tbody> 
 <tr> 
 <td style="width:105px;vertical-align:top;height:52px;"><a style="color:#0A6CFF;" href="https://wiki.mbalib.com/wiki/%E9%A1%B9%E7%9B%AE" rel="nofollow">项目</a></td> 
 <td colspan="2" style="width:186px;vertical-align:top;height:52px;">新工序矩阵</td> 
 <td colspan="4" style="width:286px;vertical-align:top;height:52px;">原工序矩阵</td> 
 </tr> 
 <tr> 
 <td style="width:105px;vertical-align:top;height:52px;">工件号</td> 
 <td style="width:66px;vertical-align:top;height:52px;">2</td> 
 <td style="width:60px;vertical-align:top;height:52px;">3</td> 
 <td style="width:180px;vertical-align:top;height:52px;">1</td> 
 <td style="width:69px;vertical-align:top;height:52px;">4</td> 
 <td style="width:71px;vertical-align:top;height:52px;">5</td> 
 <td style="width:73px;vertical-align:top;height:52px;">5</td> 
 </tr> 
 <tr> 
 <td style="width:105px;vertical-align:top;height:52px;">第1工序M1</td> 
 <td style="width:66px;vertical-align:top;height:52px;">2</td> 
 <td style="width:60px;vertical-align:top;height:52px;">9</td> 
 <td style="width:180px;vertical-align:top;height:52px;">6</td> 
 <td style="width:69px;vertical-align:top;height:52px;">4</td> 
 <td style="width:71px;vertical-align:top;height:52px;">4</td> 
 <td style="width:73px;vertical-align:top;height:52px;">5</td> 
 </tr> 
 <tr> 
 <td style="width:105px;vertical-align:top;height:52px;">第2工序M2</td> 
 <td style="width:66px;vertical-align:top;height:52px;">3</td> 
 <td style="width:60px;vertical-align:top;height:52px;">3</td> 
 <td style="width:180px;vertical-align:top;height:52px;">8</td> 
 <td style="width:69px;vertical-align:top;height:52px;">5</td> 
 <td style="width:71px;vertical-align:top;height:52px;">8</td> 
 <td style="width:73px;vertical-align:top;height:52px;">4</td> 
 </tr> 
 </tbody> 
</table>

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

<table style=""> 
 <tbody> 
 <tr> 
 <td style="width:92px;vertical-align:top;height:52px;"><a style="color:#0A6CFF;" href="https://wiki.mbalib.com/wiki/%E9%A1%B9%E7%9B%AE" rel="nofollow">项目</a></td> 
 <td colspan="4" style="width:420px;vertical-align:top;height:52px;">新工序矩阵</td> 
 <td colspan="3" style="width:446px;vertical-align:top;height:52px;">原工序矩阵</td> 
 </tr> 
 <tr> 
 <td style="width:92px;vertical-align:top;height:52px;">工件号</td> 
 <td style="width:60px;vertical-align:top;height:52px;">2</td> 
 <td style="width:60px;vertical-align:top;height:52px;">4</td> 
 <td style="width:60px;vertical-align:top;height:52px;">6</td> 
 <td style="width:60px;vertical-align:top;height:52px;">3</td> 
 <td style="width:420px;vertical-align:top;height:52px;">1</td> 
 <td style="width:60px;vertical-align:top;height:52px;">5</td> 
 <td style="width:60px;vertical-align:top;height:52px;"></td> 
 </tr> 
 <tr> 
 <td style="width:92px;vertical-align:top;height:52px;">第1工序M1</td> 
 <td style="width:60px;vertical-align:top;height:52px;">2</td> 
 <td style="width:60px;vertical-align:top;height:52px;">4</td> 
 <td style="width:60px;vertical-align:top;height:52px;">5</td> 
 <td style="width:60px;vertical-align:top;height:52px;">9</td> 
 <td style="width:420px;vertical-align:top;height:52px;">6</td> 
 <td style="width:60px;vertical-align:top;height:52px;">4</td> 
 <td style="width:60px;vertical-align:top;height:52px;"></td> 
 </tr> 
 <tr> 
 <td style="width:92px;vertical-align:top;height:52px;">第2工序M2</td> 
 <td style="width:60px;vertical-align:top;height:52px;">3</td> 
 <td style="width:60px;vertical-align:top;height:52px;">5</td> 
 <td style="width:60px;vertical-align:top;height:52px;">4</td> 
 <td style="width:60px;vertical-align:top;height:52px;">3</td> 
 <td style="width:420px;vertical-align:top;height:52px;">8</td> 
 <td style="width:60px;vertical-align:top;height:52px;">8</td> 
 <td style="width:60px;vertical-align:top;height:52px;"></td> 
 </tr> 
 </tbody> 
</table>

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

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

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

<table style=""> 
 <tbody> 
 <tr> 
 <td style="width:105px;vertical-align:top;height:52px;">项目</td> 
 <td colspan="6" style="width:660px;vertical-align:top;height:52px;">新工序矩阵</td> 
 </tr> 
 <tr> 
 <td style="width:105px;vertical-align:top;height:52px;">工件号</td> 
 <td style="width:60px;vertical-align:top;height:52px;">2</td> 
 <td style="width:60px;vertical-align:top;height:52px;">4</td> 
 <td style="width:60px;vertical-align:top;height:52px;">5</td> 
 <td style="width:60px;vertical-align:top;height:52px;">1</td> 
 <td style="width:60px;vertical-align:top;height:52px;">6</td> 
 <td style="width:60px;vertical-align:top;height:52px;">3</td> 
 </tr> 
 <tr> 
 <td style="width:105px;vertical-align:top;height:52px;">第1工序M1</td> 
 <td style="width:60px;vertical-align:top;height:52px;">2</td> 
 <td style="width:60px;vertical-align:top;height:52px;">4</td> 
 <td style="width:60px;vertical-align:top;height:52px;">6</td> 
 <td style="width:60px;vertical-align:top;height:52px;">5</td> 
 <td style="width:60px;vertical-align:top;height:52px;">9</td> 
 <td style="width:60px;vertical-align:top;height:52px;"></td> 
 </tr> 
 <tr> 
 <td style="width:105px;vertical-align:top;height:52px;">第2工序M2</td> 
 <td style="width:60px;vertical-align:top;height:52px;">3</td> 
 <td style="width:60px;vertical-align:top;height:52px;">5</td> 
 <td style="width:60px;vertical-align:top;height:52px;">8</td> 
 <td style="width:60px;vertical-align:top;height:52px;">8</td> 
 <td style="width:60px;vertical-align:top;height:52px;">4</td> 
 <td style="width:60px;vertical-align:top;height:52px;">3</td> 
 </tr> 
 </tbody> 
</table>

对于同顺序排序问题，可以通过表上作业，计算全组零件的最大流程时间*Fmax*见表

**最大流程时间*F*max计算表**

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

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

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

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

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

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

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

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

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

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

![103ab2decc32842df9d6952095af9495.bmp][]

![565beb2e9e67134388bc7680e7a34879.bmp][]

![a5b449be6f5143c3976b3c136f4f0241.bmp][]

![f5d20a44e10d2a0001183cd79a6ac32a.bmp][]

![3f1bc640040f7722eafeff7b1a2e7439.bmp][]

![571151b75dbefcefb68cbb197206ac10.bmp][]

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

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

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

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

![ba6960c919f8340e70a06d4b22c88ce8.png][]

**详细解题过程**

**(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。

![8f7ce0e74dd2803f683607dba4fc9623.png][]

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

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

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

**Johnson算法解题思路**

**1**、选择最短的作业时间

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

**3**、重复1、2步。

[bbfe377ac275eb6ed6ca5b0a00fd1573.gif]: https://img-blog.csdnimg.cn/img_convert/bbfe377ac275eb6ed6ca5b0a00fd1573.gif
[Link 1]: https://wiki.mbalib.com/wiki/%E5%B7%A5%E5%BA%8F
[Link 2]: https://wiki.mbalib.com/wiki/%E7%94%9F%E4%BA%A7%E8%BF%87%E7%A8%8B
[103ab2decc32842df9d6952095af9495.bmp]: https://img-blog.csdnimg.cn/img_convert/103ab2decc32842df9d6952095af9495.bmp
[565beb2e9e67134388bc7680e7a34879.bmp]: https://img-blog.csdnimg.cn/img_convert/565beb2e9e67134388bc7680e7a34879.bmp
[a5b449be6f5143c3976b3c136f4f0241.bmp]: https://img-blog.csdnimg.cn/img_convert/a5b449be6f5143c3976b3c136f4f0241.bmp
[f5d20a44e10d2a0001183cd79a6ac32a.bmp]: https://img-blog.csdnimg.cn/img_convert/f5d20a44e10d2a0001183cd79a6ac32a.bmp
[3f1bc640040f7722eafeff7b1a2e7439.bmp]: https://img-blog.csdnimg.cn/img_convert/3f1bc640040f7722eafeff7b1a2e7439.bmp
[571151b75dbefcefb68cbb197206ac10.bmp]: https://img-blog.csdnimg.cn/img_convert/571151b75dbefcefb68cbb197206ac10.bmp
[ba6960c919f8340e70a06d4b22c88ce8.png]: https://img-blog.csdnimg.cn/img_convert/ba6960c919f8340e70a06d4b22c88ce8.png
[8f7ce0e74dd2803f683607dba4fc9623.png]: https://img-blog.csdnimg.cn/img_convert/8f7ce0e74dd2803f683607dba4fc9623.png