章作业排序ppt课件.ppt

《章作业排序ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第11章　制造作业计划与控制第一节排序问题的基本概念第二节流水作业排序问题第三节单件作业排序问题第四节生产作业控制第一节作业计划和排序问题的基本概念作业计划与作业排序是一回事么？作业计划是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。排序，给出零部件在一台或一组设备上加工的先后顺序的工作。编制作业计划不仅包括确定工件的加工顺序，而且包括确定机器加工每个工件的开始时间和完成时间。因此，只有作业计划才能指导每个工人的生产活动。根据排序规则对每一个到达的工件安排作业顺序工作地工件排队等待加工来自上游工作地的工件加工完毕的工件流向下一工作地排序的概念排序的

2、概念生产作业排序就是指对于等候某个设备或工作中心加工的多个任务，确定这些任务加工的先后次序。目的：提高设备或工作中心的效率减少在制品占用量缩短生产周期保证按期交货名词术语(略)“零件”则代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件“加工路线”是零件加工经过不同机器构成的路线。比如，某零件要经过车、钻、冲、磨的路线加工，我们可以用M1,M2,M3,M4来表示。“加工顺序”则表示每台机器加工n个零件的先后顺序，是排序要解决的问题排序问题分类按机器单台机器排序问题多台机器排序问题单件作业排序问题流水线作业排序问题按零件到达车间的情况静态的排序问题动态的排序问题按目

3、标函数的性质分类按参数确定型排序问题随机型排序问题排序问题的分类参数表示法:n/m/A/B。其中,n──零件数；m──机器数；A──作业类型；在A的位置若标以“F”，则代表流水作业排序问题。若标以“P”，则表示流水作业排列排序问题,即同顺序排序，所有零件在每台机器上的加工顺序相同。若标以“G”，则表示一般单件作业排序问题。当m＝1，则A处为空白B──目标函数，通常是使其值最小。参数表示法:n/m/P/Fmax所有零件在每台机器上的加工顺序相同。如在M1上都是第一道工序，M2上都是第二道工序。n/m/F/Fmax不同零件在每台机器上的加工顺序不同。如零件1在M1上不加

4、工，在M2上才是第一道工序；而零件2在M1上是第一道工序。第二节流水作业排序问题流水作业排序问题的基本特征是每个零件的加工路线都一致。即工件流向一致.只要加工路线一致：M1，M2,M3，…..，Mm,不要求每个零件都经过每台机器加工我们要讨论的是排列排序问题。它不是流水线排序问题的最优解，但是比较好的解。一、最长流程时间Fmax的计算最长流程时间又称作加工周期例题：6/4/p/Fmax问题，当按顺序S＝(6,1,5,2,4,3)加工时，求Fmax.表1加工时间矩阵-i123456Pi1423142Pi2456745Pi3587555Pi4424331加工周期为46表2顺序S

5、下的加工时间矩阵i615243i1P2246410212113316i2P57411415520727633Pi3512517522830535742Pi4113421325232338446Pi1P一、最长流程时间Fmax的计算加工周期为37表3顺序S下的加工时间矩阵i123456i1P3336410212113316i2P25511415318725631Pi3510415520727532436Pi4111217323229335137Pi1P课堂作业：求Fmax.二、n/2/F/Fmax问题的最优算法（一）Johnson算法：①　从加工时间矩阵中找出最短的加工时间。

6、　　②　若最短的加工时间出现在M1上，则对应的零件尽可能往前排；若最短加工时间出现在M2上，则对应零件尽可能往后排。然后，从加工时间矩阵中划去已排序零件的加工时间。若最短加工时间有多个，则任挑一个　　③　若所有零件都已排序，停止。否则，转步骤①。例题：求表11-3所示的6/2/F/Fmax问题的最优解。将零件2排第1位2将零件3排第6位23将零件5排第2位253将零件6排第3位2563将零件4排第5位25643将零件1排第4位256143最优加工顺序为S=（2，5，6，1，4，3）。最优顺序下的Fmax=28表11-3加工时间矩阵i123456bi72247451853

7、4ai课堂作业：P345第1题（二）算法步骤的改进把Johnson算法作些改变，改变后的算法按以下步骤进行：①　将所有ai≤bi的零件按ai值不减的顺序排成一个序列A。②　将所有ai＞bi的零件按bi值不增的顺序排成一个序列B。③　将A放到B之前，就构成了最优加工顺序序列A为(2，5，6，1)，序列B为(4，3)，构成最优顺序为(2，5，6，1，4，3)，与Johnson算法结果一致。表11-4改进算法i123456ai518534bi722474i13ai58bi212537644724454ai＞bi，bi值不