生产与运作管理教材(PPT 70页)

1、2021-11-312021-11-32 基本概念 最长流程时间 n/2/F/Fmax问题的算法 一般n/m/P/ Fmax问题的启发式算法2021-11-33 排序就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。实际上就是要解决如何按时间的先后，将有限的人力、物力资源分配给不同工作任务，使预定目标最优化的问题。2021-11-34排序中常用的几个概念排序中常用的几个概念 工件（Job）：服务对象； 机器（Machine、Processor）：服务者。如： n个零件在机器上加工，则零件是工件，设备是机器； 工人维修设备，出故障的设备是工件，工人是机器。2021-11-35 所以，

2、作业排序也就是要确定工件在机器上的加工顺序，可用一组工件代号的一种排列来表示。 如可用（1，6，5，4，3，2）表示加工顺序：J1J6J5J4J3J22。2021-11-36 作业计划与排序不是一回事，它不仅要确定工件的加工顺序，而且还要确定每台机器加工每个工件的开工时间和完工时间。 如果按最早可能开（完）工时间来编排作业计划，则排序完后，作业计划也就确定了。2021-11-371）单台机器与多台机器的排序问题。2）流水车间与单件车间排序问题。2021-11-38流水车间排序问题的基本特征：流水车间排序问题的基本特征： 每个工件的加工路线都一样。如车铣磨。这里指的是工件的加工流向一致，并不要求

3、每个工件必须在每台机器上加工。如有的工件为车磨，有的为铣磨。 不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为排列排序（同顺序排序）。如工件排序为：J1J3J2，则表示所有机器都是先加工J1，然后加工J3，最后加工J2。2021-11-39单件车间排序问题的基本特征：单件车间排序问题的基本特征： 每个工件都有其独特的加工路线，工件没有一定的流向。2021-11-3103）表示方法 一般正规的表示方法为：n/m/A/B n：工件数；m：机器数； A：车间类型（F、P、G）；B：目标函数2021-11-3114）一般来说，排列排序问题的最优解不一定是相应流水车间排序问题的最

4、优解，但一般是比较好的解。而对于仅有2台或3台机器的情况，则排列排序问题的最优解一定是相应流水车间排序问题的最优解。2021-11-312 最长流程时间（加工周期）：从第一个工件在第一台机器上加工起到最后一个工件在最后一台机器上加工完毕为止所经过的时间。 假定所有工件的到达时间都为0，则Fmax等于排在末位加工的工件在车间的停留时间。2021-11-313计算Fmax的几个假定条件： 机器M1不会发生空闲； 对其它机器，能对某一工件加工必须具备2个条件：机器必须完成排前一位的工件的加工；要加工的工件的上道工序已经完工。2021-11-314 假定：ai为工件Ji在机器M1上的加工时间，bi为工

5、件Ji在机器M2上的加工时间，每个工件按M1M2的路线加工。2021-11-315从加工时间矩阵中找出最短的加工时间若最短时间出现在M1上，则对应的工件尽可能往前排若最短时间出现在M2上，则对应的工件尽可能往后排若最短时间有多个，则任选一个划去已排序的工件若所有工件都已排序，则停止，否则重复上述步骤2021-11-316 对于一般的n/m/P/Fmax问题，可以用分支定界法求得最优解，但计算量很大。实际中，可以用启发式算法求近优解。2021-11-317关键工件法关键工件法的步骤： 计算Pi= Pij ，找出Pi最长的工件，将之作为关键工件C。 对其余工件，若Pi1Pim ，则按Pi1不减的顺

6、序排成序列SA。若Pi1 Pim ，则按Pim不增的顺序排成序列SB。 顺序（SA，C，SB）即为近优解。2021-11-318POM 20022021-11-319 车间作业管理的基本概念 车间作业排序 车间作业控制2021-11-320典型的作业排序和控制功能典型的作业排序和控制功能以下职能必须在对作业排序和控制时完成： 分配订单、设备和人员到各工作中心或其他规定的地方 决定订单顺序（即建立订单优先级） 对已排序作业开始安排生产，通常称之为调度 车间作业控制（或生产作业控制），包括： 在作业进行过程中，检查其状态和控制作业的速度 加快为期已晚的和关键的作业 计划员的决策取决于以下因素：每个

7、作业的方式和规定的工艺顺序要求，每个工作中心上现有作业的状态，每个工作中心前作业的排队情况，作业优先级，物料的可得性，当天较晚发布的作业订单，工作中心资源的能力 2021-11-321 计划文件计划文件 项目主文件记录全部有关零件的信息 工艺路线文件记录生产零件的加工顺序 工作中心文件记录工作中心数据 控制文件控制文件 车间文物主文件为每个生产中的任务提供一条记录 车间任务详细文件记载完成每个车间任务所需工序 从工作人员得到的信息从工作人员得到的信息2021-11-322项目主文件工艺路线文件工作中心文件 零件号 零件名称 生产提前期 现有库存 已分配量 已定货量 批量 工序号 工序名称 准备

8、时间 加工时间 工作中心号 能力数据 替换工作中心 排队时间2021-11-323车间任务 主文件车间任务 细文件 车间任务号 任务数量 完工数量 废品数量 支付数量 交货日期 成本信息 优先级 未完成量 车间任务 工序号 工作中心 计划准备时间/实际准备时间 计划加工工时/实际加工工时 计划数量/完工数量 废品数量 开工日期/完工日期2021-11-324 知道需要经过哪些加工工序(工艺路线) 知道需要什么工具、材料、能力的提前期 确定工具、材料、能力和提前期的可用性 解决工具、材料、能力和提前期短缺问题 最后将任务下达、尽可能满足计划要求 发放工具、材料和任务的有关文件给车间加工单（wor

9、k order） 或车间定单（shop order）是一种面向加工件说明物料需求计划的文件，可以跨车间甚至厂际协作。加工单的格式同工艺路线报表相似。2021-11-325计划进度开始日期 完工日期 工作中心 标准时间(小时) 编号 名称 准备 加工 机器定单号：970215需用数量：100件计划日期：970630物料名称：C物料号：111000需用日期：970901102030405060下料车削热处理磨削电镀检验010010203006010020529000108015锯床车床电炉磨床(外协)质检0.51.01.21.0.0.251.252.000.105.00.25.5126.06.22

10、01.0(240)10.0970710970715970725970729970815970829970712970724970726970814970828970830M432工序工序名称本工序总时间2021-11-326 派工单（dispatch list）或称调度单，是一种面向工作中心说明加工优先级的文件，说明工作在一周或一个时期内要完成的生产任务。 说明哪些工作已经达到，正在排队，应当什么时间开始加工，什么时间完成，加工单的需用日期是哪天，计划加工时数是多少，完成后又应传给哪道工序。 说明哪些工件即将达到，什么时间到，从哪里来。 根据派工单，车间调度员、工作中心操作员对目前和即将到达的

11、任务一目了然。2021-11-327数量需用 完成计划进度开始日期 完工日期物料号物料名称工作中心：工作中心：8513名称：车床名称：车床加工单号工序号数量需用 完成时间准备 加工上工序下工序正加工的工件已加工的工件将达到的工件75831 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

12、 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 85322021-11-328工作中心特征和重要性工作中心特征和重要性 工作中心是生产经营中的个区域，在这个区域中，组织生产资源来完成工作。工作中心可以是一台机器、一一组机器或完成某一类型工作的一个区域，这些工作中心可以按工艺专业化的一般作业车间组织，或者按产品流程、装配线、成组技术单元结构进行组织。 在工艺专业化情况下，工件需按规定路线在各个按功能组织的工作中心之间移动

13、。作业排序涉及决定工件加工顺序以及分配相应的机器来对这些工件加工。 一个作业排序系统区别于另一个作业排序系统的特征是：在进行作业排序时是如何考虑生产能力的。2021-11-329 无限负荷 指的是当将工作分配给一个工作中心时，只考虑它需要多少时间，而不直接考虑完成这项工作所需的资源是否有足够的能力，也不考虑在该工作中，每个资源完成这项工作时的实际顺序。通常仅检查一下关键资源，大体上看看其是否超负荷。可以根据各种作业顺序下的调整和加工时间标准来计算出一段时间内所需的工作量来判定。 有限负荷 实际上是用每一订单所需的调整时间和运行时间对每一种资源详细计划。提前期由期望作业时间（调整和运行时间）加上

14、由于材料运输和等待订单执行而引起的期望排队延期时间而估算出。从理论上将，当运用有限负荷时，所由的计划都是可行的。2021-11-330 前向排序 指的是系统接受一个订单后对订单所需作业按从前向后的顺序进行排序，前向排序系统能力告诉我们订单能完成的最早日期。 后向排序 是从未来的某个日期（可能是一个约定交货日期）开始，按从后向前的顺序对所需作业进行排序。后向排序告诉我们为了按规定日期完成，一个作业必须开始的最晚时间。区分作业排序的另一个特征是基于前向排序还是后向排序。在前向排序和后向排序中，最常用的是前向排序。2021-11-331 类型 产品 特征通常的计划方法单一工序大批量生产中等批量生产小

15、批量生产化工产品、钢、金属、液体产品等汽车、电话、摩托车、家用设施工业用品、最终消费品定做的或标准的设备、专用仪器等全自动化，产品中劳动力成本低，设施专用于一种产品自动化装备，半自动化传动装置或移动装配线成组技术单元，专业化小工厂按生产功能组织的机器中心，通用设备换装时间相当长等有限符合，前向排序，机器有限 生产线有限负荷，前向排序，机器有限，准时化生产无限负荷，前向排序，有限调度控制，常劳动力有限但有时机器有限无限负荷，前向排序，2021-11-332 满足交货期 极小化提前期 极小化准备时间或成本 极小化在制品库存 极大化设备或劳动力的利用（注：最后一个目标是有争议的，因为仅仅依靠保持所有

16、设备/或员工处于繁忙的状态可能不是在工序中管理生产的最有效方法）2021-11-333 编作业计划（scheduling）与排序（sequencing）不是同义语。排序只是确定工件在机器上的加工顺序。可以通过一组工件的代号的一种排列来表示该组工件的加工顺序。而编制作业计划，则不仅包括确定工件的加工顺序，而且包括确定机器加工每个工件的开始时间和完成时间。因此，只有作业计划才能指导每个工人的生产活动。 由于编制作业计划的主要问题是确定各台机器上工件的加工顺序，而且，在通常情况下都是按最早可能开（ 完）工时间来编排作业计划。因此，当工件的加工顺序确定之后，作业计划也就确定了。所以，人们常常不加区别地

17、使用“排序”与“编作业计划”。2021-11-334 FCFS（先到先服务，First Come First Server）：按订单送到的先后顺序进行加工。v SOT（最短作业时间）：所需加工时间最短的作业首先进行，然后是加工时间第二最短的，如此等等。这个规则等同于SPT（最短加工时间）规则。w DDate交货期：最早交货期最早加工。将交货期最早的作业放在第一个进行。x 开始日期：交货期减去正常的提前期（最早开始的作业第一个进行）。2021-11-335 STR（剩余松弛时间）：STR是交货期前所剩余时间减去剩余的加工时间所得的差值。STR最短的任务最先进行。z STR/OP（每个作业剩余的松

18、弛）：STR/OP最短的任务最先进行。STR/OP的计算方法为： CR紧迫系数：紧迫系数是用交货期减去当前日期的差值除以剩余的工作日数。紧迫系数最小的任务先进行。STR/OP =交货提前期所剩的时间-剩余的加工时间剩余的作业数紧迫系数（CR）=需用日期-今日日期剩余的计划提前期2021-11-336CR=负值说明已经脱期CR=1说明剩余时间刚好够用CR1剩余时间有富裕CR1剩余时间不够CR值小者优先级高。一个工件完成后，其余工件的CR值会有变化，应随时调整| QO（排队比率）：排队比率是用计划中剩余的松弛时间除以计划中剩余的排队时间，排队比率最小的先进行。 LCFS（后到先服务）：该规则经常作

19、为缺省规则使用。因为后来的工单放在先来的上面，操作人员通常是先加工上面的工单。 随机规则2021-11-337作业排序的评价作业排序的评价在某机器上或某工作中心决定哪个作业首先开始工作的过程称为排序或优先调度排序。在进行作业排序时，需用到优先调度规则。这些规则可能很简单，仅需根据一种数据信息对作业进行排序。这些数据可以是加工时间、交货期货到达的顺序。下列作业排序标准可用于评价优先规则满足顾客或下一道工序作业的交货期极小化流程时间（作业在工序中所耗费的时间）极小化在制品库存极小化设备和工人的闲置时间2021-11-338按机器的种类和数量分：单台机器排序问题和多台机器排序问题按加工路线的特征分：

20、单件车间排序问题和流水车间排序问题按工件达到车间的情况不同分：静态排序问题和动态排序问题按目标函数分：平均流程时间最短或误期完工的工件数最少按参数的性质分：确定型排序问题与随机型排序问题Conway等人提出的排序法：n/m/A/B其中：n 工件数m机器数A车间类型（F表示流水车间排序，P流水车间排列排序问题 ， G表示单件车间）B目标函数2021-11-339N N个作业单台工作中心的排序个作业单台工作中心的排序这类问题被称作“n个作业单台工作中心的问题”或“n/1”，理论上，排序问题的难度随着工作中心数量的增加而增大，而不是随着作业数量的增加而增大，对n的约束是其必须是确定的有限的数例：n个

21、作业单台工作中心排序问题。在一周的开始，有5位顾客提交了他们的订单。原始数据为：订单（以到达的顺序） 加工时间/天 交货期/天ABCDE34261567922021-11-340方案一方案一利用利用FCFSFCFS规则，其流程时间的结果如下：规则，其流程时间的结果如下： 加工顺序 加工时间 交货日期 流程时间ABCDE34261567920+3=33+4=77+2=99+6=1515+1=16总流程时间=3+7+9+15+16=50（天）平均流程时间=50/5=10天将每个订单的交货日期与其流程时间相比较，发现只有A订单能按时交货。订单B，C，D和E将会延期交货，延期时间分别为1,2,6,14

22、天。每个订单平均延期（1+1+2+6+14）/5=4.6天。2021-11-341方案二方案二利用利用SOTSOT规则，流程时间为：规则，流程时间为： 加工顺序 加工时间 交货日期 流程时间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天。2021-11-342 加工顺序 加工时间 交货日期 流程时间EABCD1

23、3426256790+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天。方案三方案三 利用利用DDateDDate规则，排序结果为：规则，排序结果为：2021-11-343 加工顺序 加工时间 交货日期 流程时间EDCBA16243297650+1=11+6=77+2=99+4=1313+3=16总流程时间=1+7+9+13+16=46（天）平均流程时间=46/5=9.2天平均延期=4.0天方案四方案四利用利用LCFSLCFS规则

24、，预计流程时间为：规则，预计流程时间为：2021-11-344 加工顺序 加工时间 交货日期 流程时间DCAEB62314975260+6=66+2=88+3=1111+1=1212+4=16总流程时间=6+8+11+12+16=55（天）平均流程时间=55/5=11天平均延期=5.4天方案五方案五利用随机规则，排序结果为：利用随机规则，排序结果为：2021-11-345 加工顺序 加工时间 交货日期 流程时间EABD6=61+3=44+4=88+6=1414+2=16总流程时间=6+4+8+14+16=43（天）平均流程时间=43/5=8.6天平均延期=3.2天方案

25、六方案六利用利用STRSTR规则，排序结果为：规则，排序结果为：2021-11-346 规则 总的完成时间 平均完成时间 平均延期FCFSSOTDDateLCFS随机STR503639465343107.27.89.210.68.64.62.42.44.05.43.2很明显，此例中SOT比其余的规则都好，但情况总是这样的吗？答案是肯定的。另外，从数学上可以证明，在n/1情况下，用其他的评价准则，如等待时间均值和完成时间均值最小，SOT规则也是最优方案。事实上，这个简单被称为“在整个排序学科中最重要的概念在整个排序学科中最重要的概念”2021-11-347稍微复杂的n/2排序情况，被称为约翰逊（Hohnson）规则或方法， 这是S.M.Johnson于1954年提出的，其目的是极小化从第一个作业开始到最后一个作业为止的全部流程时间，以ai表示Ji在M1上加工时间，以bi表示Ji在M2上的加工时间。每个工件都按M1M2的路线加工。Johnson的算法法则是：如果Min(ai,bj)IaIp=IaIpOaIa=OaIaOaOp=OaOpOa加工件推迟达到加工件按计划达到加工件提前达到在制品增加在制品维持不变在制品减少工作中心落后计划工作中心按计划工作中心超前计划2021-1