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

这篇具有很好参考价值的文章主要介绍了工序排序问题--约翰逊法精讲。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

什么是约翰逊法?

约翰逊法是作业排序中的一种排序方法。选出最短加工时间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工件之前。

  式中:t1kt2k:k工件第1工序、第2工序的加工时间;

  t2kt1k: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步。文章来源地址https://www.toymoban.com/news/detail-482705.html

到了这里,关于工序排序问题--约翰逊法精讲的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构入门精讲 | 第九篇】考研408排序算法专项练习(一)

    前面几篇文章介绍的是排序算法,现在让我们开始排序算法的专项练习。 1.希尔排序是稳定的算法。(错) 解析:稳定性是指如果两个元素在排序前后的相对顺序保持不变,那么这个排序算法就是稳定的。对于具有相同的元素,排序后它们的相对位置应该保持不变。

    2024年02月03日
    浏览(50)
  • 什么是堆,如何实现?(附堆排序,TOP-K问题)

    欢迎来到 Claffic 的博客   💞💞💞 “春风里,是谁 花一样烂漫?” 前言: 二叉树给大家讲解的差不多了,接下来就是二叉树的实际应用了:这期我们来讲堆,它是一种顺序结构的特殊二叉树,可以实现排序等功能,那就让我们开始吧! 目录 🌸Part1: 何为堆 1.堆的概念 2.堆

    2023年04月11日
    浏览(36)
  • 【面试题精讲】什么是websocket?如何与前端通信?

    有的时候博客内容会有变动,首发博客是最新的,其他博客地址可能会未同步,认准 https://blog.zysicyj.top 首发博客地址 系列文章地址 WebSocket是一种在Web应用程序中实现双向通信的协议。它允许在客户端和服务器之间建立持久的、全双工的连接,以便实时地发送数据。 传统的

    2024年02月10日
    浏览(45)
  • 【面试精讲】Java有哪些垃圾回收器?工作原理都是什么?它们有什么区别?

    【面试精讲】Java有哪些垃圾回收器?工作原理都是什么?它们有什么区别? 目录 本文导读 一、垃圾回收器概览 Serial GC工作原理概览 Parallel GC工作原理概览 CMS回收器工作原理概览 G1回收器工作原理概览 2、选择适合的垃圾回收器 二、串行垃圾回收器(Serial GC) 工作原理 工

    2024年04月16日
    浏览(36)
  • 【面试题精讲】标识符和关键字的区别是什么

    “ 有的时候博客内容会有变动,首发博客是最新的,其他博客地址可能会未同步,认准 https://blog.zysicyj.top ” 首发博客地址 [1] 面试题手册 [2] 系列文章地址 [3] 标识符 :在编程语言中,标识符是用来表示变量、函数、类等命名实体的名称。它由一系列字符组成,可以包含字母

    2024年02月07日
    浏览(52)
  • APS中零件工序间的移动方式解析

    在加工装配的成批生产类型企业里,由于零件多种多样,工艺路线、加工方法和技术装备千差万别,因而,产品有多种流转方式。一般来说,零件在各道工序间的移动方式主要有 顺序移动、平行移动和平行顺序(平顺)移动 三种方式。 假设某客户订单产品,批量为4件,需经

    2024年02月01日
    浏览(46)
  • 多工序多基地钢铁铁前数字智能协同制造项目案例

           本项目案例后台采用.NET6(C#)开发,前端采用ReactReact Native,数字孪生采用3DMAXU3D。 工厂级示范基地 (一)兴澄特钢炼铁大数据平台 本项目覆盖配矿-烧结-高炉大炼铁产线,综合运用“物、大、智、云、移”技术,采用云-边-端工业互联网架构,设备端基于工业传感器和

    2024年02月05日
    浏览(46)
  • 【面试精讲】Java动态代理是如何实现的?JDK Proxy 和 CGLib 有什么区别?

    Java动态代理是如何实现的?JDK Proxy 和 CGLib 有什么区别? 一、Java动态代理的实现 1、使用JDK Proxy实现动态代理 2、使用CGLib实现动态代理 二、JDK Proxy 与 CGLib 的区别 三、Spring中的动态代理 四、 Lombok代理原理 总结 本文深入探讨了Java动态代理的实现机制,分别介绍了使用JDK

    2024年03月14日
    浏览(46)
  • Unity入门案例(约翰的密室逃脱)

    CameraFollow1.cs  PlayMovement.cs GameEnding.cs  Observer.cs  WayPointsPatrol.cs PS:根据b站教程完成 

    2024年02月12日
    浏览(31)
  • C++知识精讲15 | 三类基于贪心思想的区间覆盖问题【配套资源详解】

      博主主页:Yu·仙笙 配套资源:三类基于贪心算法覆盖问题-C++文档类资源-CSDN下载 专栏:C++知识精讲 目录 三类基于贪心思想的区间覆盖问题 情形1:区间完全覆盖问题 描述: 样例: 解题过程: 例题: 题意: 例题: 例题二: 思路: 情形2:最大不相交区间数问题 例题:

    2023年04月09日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包