什么是约翰逊法?
约翰逊法是作业排序中的一种排序方法。选出最短加工时间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、如果最短时间的作业在第一个加工中心,则安排在最前面,若在第二个加工中心,则安排在最后面。在等待的队列中,将该作业删除文章来源:https://www.toymoban.com/news/detail-482705.html
3、重复1、2步。文章来源地址https://www.toymoban.com/news/detail-482705.html
到了这里,关于工序排序问题--约翰逊法精讲的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!