第十章作业计划与控制ppt课件.ppt
第十章 作业计划与控制,丁秋雷,2,通过MRP确定了各车间零部件的投入出产计划，将全厂性的生产计划变成了各车间的生产任务。各车间要完成既定的生产任务，还必须将零部件投入出产计划转变为车间生产作业计划，即：将车间的生产任务变成各个工段、班组、工作地的任务。将任务安排到工作地，就涉及到任务分配和作业排序等问题。,1.1 作业计划的必要性,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,3,一个排序的例子,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,4,（a）装配顺序为ABCD，总装配时间为48小时,（b）装配顺序为CBDA，总装配时间为45小时,（c）装配顺序为DCAB，总装配时间为51小时,5,排序给出零部件在一台或一组设备上加工的先后顺序，实质上是要解决如何按时间的先后，将有限的资源分配给不同的工作任务使预定的目标最优化的问题。编制作业计划不仅要解决先加工哪个工件、后加工哪个工件的加工顺序问题，还包括确定机器加工每个工件的开始时间和完成时间。编制作业计划与排序的概念和目的都是不同的。但是，在工件的加工顺序确定以后，作业计划也就确定了，因此往往将“排序”和“编制作业计划”等同。,1.2 排序与编制作业计划的差别,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,6,确定出最佳的作业顺序看似容易，只要列出所有的顺序，然后再从中挑出最好的就可以了，但要实现这种想法几乎是不可能的。例如，考虑32项任务（工件），有32！种方案，假定计算机每秒钟可以检查1 billion个顺序,全部检验完毕需要8.41015个世纪。以上问题还没有考虑其他的约束条件,如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间更无法想象了。所以，很有必要去寻找一些有效算法，解决管理中的实际问题。,1.3 排序的难度,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,7,根据排序规则对每一个到达的订单安排作业顺序,工作地,工件排队等待加工,来自上游工作地的订单,加工完毕的订单流向下一工作地,单件车间制定作业计划示意图,8,作业计划：不仅要确定工件的加工顺序，而且还要确定机器加工每个工件的开始时间和完成时间。通常情况下都是按最早可能开（完）工时间来编制作业计划，是加工制造发生之前的活动。排序：确定零件在机器上的加工顺序。派工：按作业计划的要求，将具体生产任务安排到具体的机床上加工。调度：是作业计划编制后实施生产控制所采取的行动。,2.1 名词术语,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,9,一个零件不能同时在几台不同的机器上加工，每台机器同时只能加工一个零件；零件在加工过程中采取平行移动方式，即上一道工序完工后，立即送下道工序加工；不允许中断，零件一旦开始加工，必须一直进行到完工，不得中途停止并插入其它零件；每道工序只在一台机器上完成；零件数、机器数和加工时间已知。,2.2 假设条件,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,10,2.3 排序的分类,排序问题分类,按目标函数的性质,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,11,按机器的种类和数量不同，分为单台机器的排序问题和多台机器的排序问题对于多台机器排序，根据加工路线的特征，分成：单件作业排序(Job-Shop)问题流水作业排序(Flow-Shop)问题,2.3 排序的分类,工件的加工路线不同，是单件作业排序问题的基本特征；,所有工件的加工路线完全相同，是流水作业排序问题的基本特征。也就是说，每个零件都顺序地经过线上不同机器加工，它们的加工路线一致。,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,12,排序问题常用四个符号来描述:n/m/A/B其中：n工件数m机器数A车间类型B目标函数，通常使其值最小，如B=Fmax，是使最长流程时间最短。例如：4/2/P/Fmax表示4个工件在2台机器上流水作业时以最长流程时间最短为目标的排序。,2.4 排序问题的一般表示方法,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,13,2.5 生产调度问题优化的主要目标,1,基于经济的调度目标：生产费用最小，利润最大，库存费用最少等,2,最大能力指标：包括最大生产率、最短的生产周期等,3,客户满意度指标：包括最短的延迟，最小提前或者拖后惩罚，平均延迟时间小等,目标之间往往相互冲突，即某个目标性能的改善可能导致另一个或者另几个目标性能的降低,14,n个工件全部经由一台机器处理,3.1 定义,J1J2Jn,机器,到达系统工件的集合,离开系统（机器）,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,15,平均流程最短最大延期量最小,3.2 常见单台机器排序问题的目标函数,定义:为n个零件经由一台机器的平,流程时间，流程时间=等待时间+加工时间,目标函数：,定义:,为最大延迟量。,目标函数：,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,16,根据排序目标的不同，可以选择不同的排序规则，有时又称为确定优先权(Priorities)。常见的优先权规则(Priority rules)有：SPT-Shortest Process Time,EDD-Earliest Due Date 等,分别用于解决不同的问题。按什么样的准则来选择，对排序方案的优劣有很大影响。,3.2 常见单台机器排序问题的目标函数,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,17,SPT（Shortest processing time）法则优先选择加工时间最短的工序使工件的平均流程时间最短，从而减少在制品量EDD（Earliest due date）法则优先选择交货期最早的工件可使工件的平均延期时间最小FCFS（First come first served）法则优先选择最早进入可排工序集合的工件来自排队论，对工件较公平CR（Critical Ratio）法则CR是用交货日期减去当前日期的差值除以剩余的工作日数。关键比率最小的任务先执行。保证工件的延期数量最小,3.3 常用的优先顺序规则,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,18,MWKR（Most work remaining）法则优先选择余下加工时间最长的工件不同工作量的工件的完工时间尽量接近LWKR（Least work remaining）法则优先选择余下加工时间最短的工件使工作量小的工件尽快完成STR（Slack Time Remaining）法则：STR是交货期前所剩余时间减去剩余的加工时间所得的差值。STR最短的任务最先进行。使任何任务（订单）最大延期最小RANDOM法则：随机地挑一个工件,3.3 常用的优先顺序规则,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,19,例：一个加工车间负责加工发动机机壳，现在共有5个机壳等待加工。只有一名技工在岗，做此项工作。现在已经估算出各个机壳的标准加工时间，顾客也已经明确提出了他们所希望的完工时间，采用SPT法则和EDD法则，求工件的加工顺序。,20,21,EDD规则（优先选择完工期限最紧的工作）排序结果,比较SPT规则和EDD规则的排序结果，用SPT规则排序，其平均流程时间更短，减少在制品量，但平均延迟较大。用EDD规则，可以给顾客提供更好的服务（平均延迟时间较少），它也提供了更低的总库存水平，但平均流程时间较长。,22,流水车间(Flow shop)：工件的加工路线都一致。在流水线上制造不同的零件，即流水作业的排序问题。上面说的加工线路一致，是指工件的流向一致，并不是指每个工件必须经过加工线路上的每台机器加工。如果某些工件不经某些机器加工，则设相应的加工时间为零。本节主要考虑：（1）最长流程时间的计算（2）两台机器排序问题的最优算法,4.1 前言,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,23,n/m/P/Fmax问题，其中n为工件数，m为机器数，P表示流水作业的排序问题，Fmax为目标函数。n个零件要按相同的加工路线经过m台机器加工，目标是使这批零件的最长流程时间最短。最长流程时间又称加工周期，它是从第一个零件在第一台机器开始加工时算起，到最后一个零件在最后一台机器上完成加工时为止所经过的时间。假设：所有工件的到达时间都为零,4.2 最长流程时间的计算,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,24,例：6/4/P/Fmax问题，加工时间如表所示。当按顺序S=(6,1,5,2,4,3)加工时，求Fmax。,序号为3的工件在序号为2的机器上的加工时间为6,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,25,例：6/4/P/Fmax问题，加工时间如表所示。当按顺序S=(6,1,5,2,4,3)加工时，求Fmax。,按顺序S=(6,1,5,2,4,3)列出加工时间矩阵。,6 1 5 2 4 3,Pi1 2 4 4 2 1 3Pi2 5 4 4 5 7 6Pi3 5 5 5 8 5 7Pi4 1 4 3 2 3 4,2,7,12,13,4+max7,6=11,11,15 20 27 33,17 22 30 35 42,21 25 32 38 46,6 10 12 13 16,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,26,约翰森算法（1）从加工时间矩阵中找出最短加工时间；（2）若最短加工时间出现在机器M1 上，则对应工件应该尽可能往前排；若最短加工时间出现在机器M2 上，则对应工件应该尽可能往后排。然后从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个，则任挑一个。（3）若所有工件都已排序，停止。否则，转步骤1。,4.3 两台机器排序问题的最优算法,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,27,例：,将工件2排在第1位 2将工件3排在第6位 2 3将工件5排在第2位 2 5 3将工件6排在第3位 2 5 6 3将工件4排在第5位 2 5 6 4 3将工件1排在第4位 2 5 6 1 4 3最优加工顺序为S=(2,5,6,1,4,3),Fmax=28,I 1 2 3 4 5 6,Ai 5 1 8 5 3 4Bi 7 2 2 4 7 4,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,28,约翰森算法的改进（1）将所有ai bi的工件按ai值不减的顺序排成一个序列A；（2）将aibi的工件按bi值不增的顺序排成一个序列B；（3）将A放到B之前，就构成了一个最优加工顺序。,4.3 两台机器排序问题的最优算法,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,29,例：,工件号 1 2 3 4 5 6,ai 5 1 8 5 3 4,bi 7 2 2 4 7 4,最优顺序 2 5 6 1 4 3,1 3 4 5 5 8 2 7 4 7 4 2,4 8 13 18 26,3 11 15 22 26 28,ai,bi,最优顺序下的加工周期为28,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,30,4.4 n/m/P/Fmax问题的排序,只能：启发式算法,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,31,精确算法与启发式算法驾驶汽车到达某人的家，写成算法是这样的：沿长张高速公路北行至太子庙；从西北出口出来后往山上开4.5公里；在一个杂货店旁边的红绿灯路口右转，接着在第一个路口左转；从左边褐色大房子的车道进去，就是桃源路714号。用启发式方法来描述则可能是这样：找出上一次我们寄给你的信，照着信上面的寄出地址开车到这个镇；到了之后你问一下我们的房子在哪里。这里每个人都认识我们肯定有人会很愿意帮助你的；如果你找不到人，那就找个公共电话亭给我们打电话，我们会出来接你。,4.4 n/m/P/Fmax问题的排序,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,32,所提供的产品类型服务过程有人参与，作业计划对他们有直接影响；生产作业计划对产品的最终使用者没有直接影响排序内容服务业中，排序要定义服务交易的时间和消耗点；生产作业计划仅仅定义产品生产的操作步骤过程控制服务业中顾客参与服务过程，并且对全部操作过程施加影响；生产作业计划中，顾客不直接影响生产过程人员规模服务业中，服务的输出与劳动力的最佳规模之间的关系难以确定；生产作业中，两者关系密切,服务业作业计划与生产作业计划的差别,关键内容:1.引言2.排序问题的基本概念3.单台机器的排序问题4.两台（或多台）机器流水作业的排序问题5.服务业的作业计划,
