生产管理-Charpt-08-作业排序

1、消费与运作管理Production & Operation Management.作业排序.第七章 作业排序 根本概念 最长流程时间 n/2/F/Fmax问题的算法 普通n/m/P/ Fmax问题的启发式算法.一、根本概念1、排序排序就是要将不同的任务义务安排一个执行的顺序，使预定的目的最优化。实践上就是要处理如何按时间的先后，将有限的人力、物力资源分配给不同任务义务，使预定目的最优化的问题。.排序中常用的几个概念工件Job：效力对象；机器Machine、Processor：效力者。如：n个零件在机器上加工，那么零件是工件，设备是机器；工人维修设备，出缺点的设备是工件，工人是机器。. 所以，作

2、业排序也就是要确定工件在机器上的加工顺序，可用一组工件代号的一种陈列来表示。 如可用1，6，5，4，3，2表示加工顺序：J1J6J5J4J3J22。.2、作业方案Scheduling作业方案与排序不是一回事，它不仅要确定工件的加工顺序，而且还要确定每台机器加工每个工件的开工时间和完工时间。假设按最早能够开完工时间来编排作业方案，那么排序完后，作业方案也就确定了。.3、排序问题的分类与表示1单台机器与多台机器的排序问题。2流水车间与单件车间排序问题。.流水车间排序问题的根本特征：每个工件的加工道路都一样。如车铣磨。这里指的是工件的加工流向一致，并不要求每个工件必需在每台机器上加工。如有的工件为车

3、磨，有的为铣磨。不仅加工道路一致，而且一切工件在各台机器上的加工顺序也一样，这种排序称为陈列排序同顺序排序。如工件排序为：J1J3J2，那么表示一切机器都是先加工J1，然后加工J3，最后加工J2。.单件车间排序问题的根本特征：每个工件都有其独特的加工道路，工件没有一定的流向。.3表示方法 普通正规的表示方法为：n/m/A/B n：工件数；m：机器数； A：车间类型F、P、G；B：目的函数.4普通来说，陈列排序问题的最优解不一定是相应流水车间排序问题的最优解，但普通是比较好的解。而对于仅有2台或3台机器的情况，那么陈列排序问题的最优解一定是相应流水车间排序问题的最优解。.二、最长流程时间最长流程

4、时间加工周期：从第一个工件在第一台机器上加工起到最后一个工件在最后一台机器上加工终了为止所经过的时间。假定一切工件的到达时间都为0，那么Fmax等于排在末位加工的工件在车间的停留时间。.计算Fmax的几个假定条件：机器M1不会发生空闲；对其它机器，能对某一工件加工必需具备2个条件：机器必需完成排前一位的工件的加工；要加工的工件的上道工序曾经完工。.三、n/2/F/Fmax问题的算法Johnson算法：假定：ai为工件Ji在机器M1上的加工时间，bi为工件Ji在机器M2上的加工时间，每个工件按M1M2的道路加工。.Johnson算法的步骤：从加工时间矩阵中找出最短的加工时间假设最短时间出如今M1

5、上，那么对应的工件尽能够往前排假设最短时间出如今M2上，那么对应的工件尽能够往后排假设最短时间有多个，那么任选一个划去已排序的工件假设一切工件都已排序，那么停顿，否那么反复上述步骤.四、普通n/m/P/ Fmax问题的启发式算法 对于普通的n/m/P/Fmax问题，可以用分支定界法求得最优解，但计算量很大。实践中，可以用启发式算法求近优解。.关键工件法的步骤：计算Pi= Pij ，找出Pi最长的工件，将之作为关键工件C。对其他工件，假设Pi1Pim ，那么按Pi1不减的顺序排成序列SA。假设Pi1 Pim ，那么按Pim不增的顺序排成序列SB。顺序SA，C，SB即为近优解。.Shop Floo

6、r Activity Management车间作业管理POM 2002. 车间作业管理的根本概念 车间作业排序 车间作业控制.典型的作业排序和控制功能以下职能必需在对作业排序和控制时完成： 分配订单、设备和人员到各任务中心或其他规定的地方 决议订单顺序即建立订单优先级 对已排序作业开场安排消费，通常称之为调度 车间作业控制或消费作业控制，包括： 在作业进展过程中，检查其形状和控制造业的速度 加快为期已晚的和关键的作业 方案员的决策取决于以下要素：每个作业的方式和规定的工艺顺序要求，每个任务中心上现有作业的形状，每个任务中心前作业的排队情况，作业优先级，物料的可得性，当天较晚发布的作业订单，任务

7、中心资源的才干 .车间作业管理的信息源 方案文件 工程主文件记录全部有关零件的信息 工艺道路文件记录消费零件的加工顺序 任务中心文件记录任务中心数据 控制文件 车间文物主文件为每个消费中的义务提供一条记录 车间义务详细文件记载完成每个车间义务所需工序 从任务人员得到的信息.方案文件数据概要方案文件文件中的内容工程主文件工艺道路文件任务中心文件 零件号 零件称号 消费提早期 现有库存 已分配量 已定货量 批量 工序号 工序称号 预备时间 加工时间 任务中心号 才干数据 交换任务中心 排队时间.控制文件文件中的信息车间义务 主文件车间义务 细文件 车间义务号 义务数量 完工数量 废品数量 支付数量

8、 交货日期 本钱信息 优先级 未完成量 车间义务 工序号 任务中心 方案预备时间/实践预备时间 方案加工工时/实践加工工时 方案数量/完工数量 废品数量 开工日期/完工日期.加工单 知道需求经过哪些加工工序(工艺道路) 知道需求什么工具、资料、才干的提早期 确定工具、资料、才干和提早期的可用性 处理工具、资料、才干和提早期短缺问题 最后将义务下达、尽能够满足方案要求 发放工具、资料和义务的有关文件给车间加工单work order 或车间定单shop order是一种面向加工件阐明物料需求方案的文件，可以跨车间甚至厂际协作。加工单的格式同工艺道路报表类似。.方案进度开场日期 完工日期 任务中心

9、规范时间(小时) 编号 称号 预备 加工 机器加工单的典型格式定单号：970215需用数量：100件方案日期：970630物料称号：C物料号：111000需用日期：970901102030405060下料车削热处置磨削电镀检验010010203006010020529000108015锯床车床电炉磨床(外协)质检0.51.01.21.0.0.251.252.000.105.00.25.5126.06.2201.0(240)10.0970710970715970725970729970815970829970712970724970726970814970828970830M432工序工序称号本

10、工序总时间.派工单 派工单dispatch list或称调度单，是一种面向任务中心阐明加工优先级的文件，阐明任务在一周或一个时期内要完成的消费义务。 阐明哪些任务曾经到达，正在排队，该当什么时间开场加工，什么时间完成，加工单的需用日期是哪天，方案加工时数是多少，完成后又应传给哪道工序。 阐明哪些工件即将到达，什么时间到，从哪里来。 根据派工单，车间调度员、任务中心操作员对目前和即将到达的义务一目了然。.数量需用 完成派工单的典型格式方案进度开场日期 完工日期物料号物料称号任务中心：8513称号：车床加工单号工序号数量需用 完成时间预备 加工上工序下工序正加工的工件已加工的工件将到达的工件758

11、31 D 97087 20 16 20 970504 970504 1.0 1028 860188501 C 97098 50 20 970504 970506 0.2 15 1028 8603 51888 F 97120 40 40 970506 970507 0.2 10 8420 入库16877 G 97376 20 30 970507 970507 0.1 5.0 8510 852337414 D 97087 25 15 970510 970511 0.1 8.0 7100 8200 88501 C 97098 10 10 970512 970512 0.1 3.0 7200 8532

12、.任务中心特征和重要性 任务中心是消费运营中的个区域，在这个区域中，组织消费资源来完成任务。任务中心可以是一台机器、一一组机器或完成某一类型任务的一个区域，这些任务中心可以按工艺专业化的普通作业车间组织，或者按产品流程、装配线、成组技术单元构造进展组织。 在工艺专业化情况下，工件需按规定道路在各个按功能组织的任务中心之间挪动。作业排序涉及决议工件加工顺序以及分配相应的机器来对这些工件加工。 一个作业排序系统区别于另一个作业排序系统的特征是：在进展作业排序时是如何思索消费才干的。.有限负荷方法和无限负荷方法 无限负荷 指的是当将任务分配给一个任务中心时，只思索它需求多少时间，而不直接思索完成这项

13、任务所需的资源能否有足够的才干，也不思索在该任务中，每个资源完成这项任务时的实践顺序。通常仅检查一下关键资源，大体上看看其能否超负荷。可以根据各种作业顺序下的调整和加工时间规范来计算出一段时间内所需的任务量来断定。 有限负荷 实践上是用每一订单所需的调整时间和运转时间对每一种资源详细方案。提早期由期望作业时间调整和运转时间加上由于资料运输和等待订单执行而引起的期望排队延期时间而估算出。从实际上将，当运用有限负荷时，所由的方案都是可行的。.前向排序和后向排序 前向排序 指的是系统接受一个订单后对订单所需作业按从前向后的顺序进展排序，前向排序系统才干通知我们订单能完成的最早日期。 后向排序 是从未

14、来的某个日期能够是一个商定交货日期开场，按从后向前的顺序对所需作业进展排序。后向排序通知我们为了按规定日期完成，一个作业必需开场的最晚时间。区分作业排序的另一个特征是基于前向排序还是后向排序。在前向排序和后向排序中，最常用的是前向排序。.消费工序类型和方案方法 类型 产品 特征通常的方案方法单一工序大批量消费中等批量消费小批量消费化工产品、钢、金属、液体产品等汽车、摩托车、家用设备工业用品、最终消费品定做的或规范的设备、公用仪器等全自动化，产品中劳动力本钱低，设备公用于一种产品自动化配备，半自动化传动安装或挪动装配线成组技术单元，专业化小工厂按消费功能组织的机器中心，通用设备换装时间相当长等有

15、限符合，前向排序，机器有限 消费线有限负荷，前向排序，机器有限，准时化消费无限负荷，前向排序，有限调度控制，常劳动力有限但有时机器有限无限负荷，前向排序，.车间作业排序的目的 满足交货期 极小化提早期 极小化预备时间或本钱 极小化在制品库存 极大化设备或劳动力的利用注：最后一个目的是有争议的，由于仅仅依托坚持一切设备/或员工处于忙碌的形状能够不是在工序中管理消费的最有效方法.作业方案和排序的关系 编作业方案scheduling与排序sequencing不是同义语。排序只是确定工件在机器上的加工顺序。可以经过一组工件的代号的一种陈列来表示该组工件的加工顺序。而编制造业方案，那么不仅包括确定工件的

16、加工顺序，而且包括确定机器加工每个工件的开场时间和完成时间。因此，只需作业方案才干指点每个工人的消费活动。 由于编制造业方案的主要问题是确定各台机器上工件的加工顺序，而且，在通常情况下都是按最早能够开 完工时间来编排作业方案。因此，当工件的加工顺序确定之后，作业方案也就确定了。所以，人们经常不加区别地运用“排序与“编作业方案。.作业排序的十大优先规那么 FCFS先到先效力，First Come First Server：按订单送到的先后顺序进展加工。 SOT最短作业时间：所需加工时间最短的作业首先进展，然后是加工时间第二最短的，如此等等。这个规那么等同于SPT最短加工时间规那么。 DDate交

17、货期：最早交货期最早加工。将交货期最早的作业放在第一个进展。 开场日期：交货期减去正常的提早期最早开场的作业第一个进展。. STR剩余松弛时间：STR是交货期前所剩余时间减去剩余的加工时间所得的差值。STR最短的义务最先进展。 STR/OP每个作业剩余的松弛：STR/OP最短的义务最先进展。STR/OP的计算方法为： CR紧迫系数：紧迫系数是用交货期减去当前日期的差值除以剩余的任务日数。紧迫系数最小的义务先进展。STR/OP =交货提早期所剩的时间-剩余的加工时间剩余的作业数紧迫系数CR=需用日期-今日日期剩余的方案提早期.CR=负值阐明曾经脱期CR=1阐明剩余时间刚好够用CR1剩余时间有富有

18、CR1剩余时间不够CR值小者优先级高。一个工件完成后，其他工件的CR值会有变化，应随时调整 QO排队比率：排队比率是用方案中剩余的松弛时间除以方案中剩余的排队时间，排队比率最小的先进展。 LCFS后到先效力：该规那么经常作为缺省规那么运用。由于后来的工单放在先来的上面，操作人员通常是先加工上面的工单。 随机规那么.作业排序的评价在某机器上或某任务中心决议哪个作业首先开场任务的过程称为排序或优先调度排序。在进展作业排序时，需用到优先调度规那么。这些规那么能够很简单，仅需根据一种数据信息对作业进展排序。这些数据可以是加工时间、交货期货到达的顺序。以下作业排序规范可用于评价优先规那么满足顾客或下一道

19、工序作业的交货期极小化流程时间作业在工序中所耗费的时间极小化在制品库存极小化设备和工人的闲置时间.排序问题的分类与表示法按机器的种类和数量分：单台机器排序问题和多台机器排序问题按加工道路的特征分：单件车间排序问题和流水车间排序问题按工件到达车间的情况不同分：静态排序问题和动态排序问题按目的函数分：平均流程时间最短或误期完工的工件数最少按参数的性质分：确定型排序问题与随机型排序问题Conway等人提出的排序法：n/m/A/B其中：n 工件数m机器数A车间类型F表示流水车间排序，P流水车间陈列排序问题 ， G表示单件车间B目的函数.N个作业单台任务中心的排序这类问题被称作“n个作业单台任务中心的问

20、题或“n/1，实际上，排序问题的难度随着任务中心数量的添加而增大，而不是随着作业数量的添加而增大，对n的约束是其必需是确定的有限的数例：n个作业单台任务中心排序问题。在一周的开场，有5位顾客提交了他们的订单。原始数据为：订单以到达的顺序 加工时间/天 交货期/天ABCDE3426156792.方案一利用FCFS规那么，其流程时间的结果如下： 加工顺序 加工时间 交货日期 流程时间ABCDE34261567920+3=33+4=77+2=99+6=1515+1=16总流程时间=3+7+9+15+16=50天平均流程时间=50/5=10天将每个订单的交货日期与其流程时间相比较，发现只需A订单能按时

21、交货。订单B，C，D和E将会延期交货，延期时间分别为1,2,6,14天。每个订单平均延期1+1+2+6+14/5=4.6天。.方案二利用SOT规那么，流程时间为： 加工顺序 加工时间 交货日期 流程时间ECABD12346275690+1=11+2=33+3=66+4=1010+6=16总流程时间=1+3+6+10+16=36天平均流程时间=36/5=7.5天SOT规那么的平均流程时间比FCFS规那么的平均流程时间小。另外，订单E和C将在交货日期前完成，订单A仅延期1天。每个订单的平均延期时间为0+0+1+4+7/5=2.4天。. 加工顺序 加工时间 交货日期 流程时间EABCD1342625

22、6790+1=11+3=44+4=88+2=1010+6=16总流程时间=1+4+8+10+16=39天平均流程时间=39/5=7.8天在这种情况下，订单B，C和D将会延期，平均延期时间为0+0+2+7/5=2.4天。方案三 利用DDate规那么，排序结果为：. 加工顺序 加工时间 交货日期 流程时间EDCBA16243297650+1=11+6=77+2=99+4=1313+3=16总流程时间=1+7+9+13+16=46天平均流程时间=46/5=9.2天平均延期=4.0天方案四利用LCFS规那么，估计流程时间为：. 加工顺序 加工时间 交货日期 流程时间DCAEB62314975260+6

23、=66+2=88+3=1111+1=1212+4=16总流程时间=6+8+11+12+16=55天平均流程时间=55/5=11天平均延期=5.4天方案五利用随机规那么，排序结果为：. 加工顺序 加工时间 交货日期 流程时间EABD6=61+3=44+4=88+6=1414+2=16总流程时间=6+4+8+14+16=43天平均流程时间=43/5=8.6天平均延期=3.2天方案六利用STR规那么，排序结果为：. 规那么 总的完成时间 平均完成时间 平均延期FCFSSOTDDateLCFS随机STR503639465343107.27.89.210.68.64.62.42

24、.44.05.43.2很明显，此例中SOT比其他的规那么都好，但情况总是这样的吗？答案是一定的。另外，从数学上可以证明，在n/1情况下，用其他的评价准那么，如等待时间均值和完成时间均值最小，SOT规那么也是最优方案。现实上，这个简单被称为“在整个排序学科中最重要的概念.N个作业两台任务中心排序略微复杂的n/2排序情况，被称为约翰逊Hohnson规那么或方法， 这是S.M.Johnson于1954年提出的，其目的是极小化从第一个作业开场到最后一个作业为止的全部流程时间，以ai表示Ji在M1上加工时间，以bi表示Ji在M2上的加工时间。每个工件都按M1M2的道路加工。Johnson的算法法那么是：假设Min(ai,bj)IaIp=IaIpOaIa=OaIaOaOp=OaOpOa加工件推迟到达加工件按方案到达加工件提早到达在制品添加在制品维持不变在制品减少任务中心落后方案任务中心按