POM生产与运作管理Production & Operation Management主讲：方青2007-1-7武汉科技大学管理学院1
POM第十一章制造业作业计划与控制Operatiions Schedulliing and Controlllliing学习本章后，你将能够•了解：–生产作业计划、单台机器的排序问题•熟悉：–排序问题的基本概念–生产作业控制•掌握:–流水线作业排序问题–单件作业排序问题2007-1-7武汉科技大学管理学院2
POM本章主要内容•生产作业计划•排序问题的基本概念•单台机器的排序问题•流水作业排序问题•单件作业排序问题•生产作业控制2007-1-7武汉科技大学管理学院3
POM第一节生产作业计划(Scheduling)•一、生产作业计划的内容•生产作业计划的主要任务是将主生产计划或MRP中的零部件投入出产计划细化，他是MRP的具体执行计划，具体、详细地规定了各车间、工段、班组以至每个工作地在较短的时间内（月、旬、周、日、轮班、小时）的生产运作任务。2007-1-7武汉科技大学管理学院4
POM•生产作业计划工作由作业计划编制与作业计划控制两部分组成。•作业计划编制包括：–制定期量标准、开展生产运作能力核算与平衡、编制各种形式的生产作业计划等•作业计划控制包括：–生产运作调度、生产运作作业统计与分析等内容。2007-1-7武汉科技大学管理学院5
POM二、生产作业计划的含义与作用•1、作业计划(Scheduling)的含义–作业计划是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。•2、作业计划的作用–满足交货期要求Meet Due Dates–使在制品库存最小Minimize work-in-process inventory2007-1-7武汉科技大学管理学院6
POM–使平均流程时间最小Minimize the average flow time through the system–提供准确的工件状态信息Provide for accurate job status information–提高机器/工人的时间利用率Provide for high machine/worker time utilization(Minimizeworker idle time)–减少调整准备时间Reduce setup times–使生产和人工成本最低Minimize production and worker costs 2007-1-7武汉科技大学管理学院7
POM三、制定作业计划的主要原则z工件流动(物流)带来价值= 现金流z物流通过车间的速度= 效率z将工件流安排成一个连续过程–流程上一步接一步z避免工作中断z动态安排作业计划z未完成任务要能够及时反馈z投入工作地的任务与能力要匹配z发现瓶颈–动态特征z找出工程设计与制造执行过程之间的不相容性2007-1-7武汉科技大学管理学院8
POM四、作业计划的种类•大量生产类型的作业计划(Scheduling in High-Volume Systems) •成批生产类型的作业计划(Scheduling in Intermediate-Volume Systems)•单件小批生产类型作业计划(Scheduling in Low-Volume Systems)2007-1-7武汉科技大学管理学院9
POM其他分类：–车间作业计划(Job Floor scheduling)–人力计划(Personnel Scheduling)–设施计划(Facilities Scheduling)–车辆调度计划(Vehicle Scheduling)–供应商计划(Vendor Scheduling)–工程项目计划(Project Scheduling)–动态计划和静态计划(Dynamic versus Static Scheduling) 2007-1-7武汉科技大学管理学院10
POM五、制定作业计划的影响因素z工件到达的方式(The job arrival pattern)z车间内机器的数量(Number and variety of machines in the shop)z车间拥有的人力资源(Number of workers in the shop)z工件移动方式(Particular flow patterns)z不同调度准则的评价(Evaluations of alternative rules)2007-1-7武汉科技大学管理学院11
POM六、作业计划与控制的关系•作业计划：–给生产活动(Production Activities)制定详细时间表•生产控制：–以生产计划和作业计划为依据，检查、落实计划执行情况，发现偏差即采取纠正措施，保证实现各项各项计划目标。2007-1-7武汉科技大学管理学院12
POM第二节排序问题的基本概念一、名词与术语•排序(Sequencing)–确定工件在机器上的加工顺序。•作业计划(Scheduling)–作业计划是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。•编制作业计划与排序的概念和目的都是不同的。但是，编制作业计划的主要工作之一就是要确定出最佳的作业顺序。2007-1-7武汉科技大学管理学院13
POM•要确定出最佳的作业顺序看似容易，只要列出所有的顺序，然后再从中挑出最好的就可以了，但要实现这种想法几乎是不可能的。35–例如，考虑32项任务（工件），有32！≈×10种方案,假定计算机每秒钟可以检查1 billion个顺序, 全部检15验完毕需要×10个世纪.–如果只有16个工件, 同样按每秒钟可以检查1 billion个顺序计算, 也需要2/3年.•以上问题还没有考虑其他的约束条件, 如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。•所以，很有必要去寻找一些有效算法，解决管理中的实际问题。2007-1-7武汉科技大学管理学院14
POM名词与术语•调度(Controlling)包括派工(Dispatching)和赶工(Expediting)。–派工指依据作业计划将具体任务安排到具体的机床加工–赶工指实际进度落后于计划时采取的资源调配行动•编制作业计划是加工制造发生之前的活动；调度是在加工制造发生这后的活动，是发现实际生产进度已经偏离预定计划而采取的调配资源的行动。调度是实行控制所采取的行动。2007-1-7武汉科技大学管理学院15
POM排序问题的基本术语•机器——服务者–机器可以是机床、维修工人，可以是轮船要停靠的码头，也可以是计算机中央处理单元、存贮器和输入、输出单元。•工件——服务对象–工件可以是单个零件，也可以是一批相同的零件•加工路线是工件加工的工艺过程决定的、是工件加工在技术上的约束。•加工顺序是表示每台机器加工n个工件的先后顺序，是排序要解决的问题。2007-1-7武汉科技大学管理学院16
POM二、假设条件与符号说明•1、假设条件：–一个工件不能同时在几台不同的机器上加工。–工件在加工过程中采用平行移动方式（无等待）。–不允许中断。即一个工件一旦开始加工，必须一直进行到完工，不得中途停止、插入其他工件。–每道工序只在一台机器上完成。–工件数、机器数和加工时间已知，且与加工顺序无关。–每台机器同时只能加工一个工件。2007-1-7武汉科技大学管理学院17
POM2、符号说明¾J为工件i，i=1,2,···,n;i¾M为机器j，j=1,2,···,m;j¾P为J在M上的加工时间，J的总加工时间为P=∑Pijijiiij¾r为J的到达时间，指J从外部进入车间，可以开始加iij工的最早时间；¾d为J的完工期限；ii¾C为J的完工时间，C=∑(W+ P)= r+ W+ P；iiiijijiii¾C为最长的完工时间，C=max｛C｝maxmaxi¾F为J的流程时间，即工件在车间的实际停留时间，iiF= C-r= W+ Piiiii2007-1-7武汉科技大学管理学院18
POM符号说明：¾F为最长的流程时间，F=max｛F｝maximaxi¾L为工件的延迟时间i ¾W为J在M上加工之前的等待时间ijij¾W为J在加工过程中总的等待时间ii¾α为J的允许停留时间ii¾L= C-d= r+ P+W-d=(P+W)-(d-r)= F–αiiiii iii iiiii¾当L>0(正延迟)，说明J的实际完工时间超过了完工期ii限；当L<0(负延迟)，说明J提前完工；当L=0(零延iii迟)，说明J按期完工i¾L为最长延长时间，L=max｛L｝maxmaxi2007-1-7武汉科技大学管理学院19
POM四、排序问题的分类和表示方法•1、排序问题的分类：•①根据机器数的多少–单台机器的排序问题–多台机器的排序问题•②根据加工路线的特征–单件作业排序(Job Shop)单件车间排序问题的基本特征：每个工件都有其独特的加工路线，工件没有一定的流向。–流水作业排序(Flow Shop)2007-1-7武汉科技大学管理学院20
POM排序问题的分类（续）•流水车间排序问题的基本特征：–每个工件的加工路线都一样。如车—铣—磨。这里指的是工件的加工流向一致，并不要求每个工件必须在每台机器上加工。如有的工件为车—磨，有的为铣—磨。–不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为排列排序（同顺序排序）。如工件排序为：J1—J3—J2，则表示所有机器都是先加工J1，然后加工J3，最后加工J2。2007-1-7武汉科技大学管理学院21
POM排序问题的分类（续）•③根据工件到达系统的情况–静态排序：排序时工件都已到达–动态排序：工件陆续到达，要随时安排它们的加工顺序•④根据参数的性质–确定型排序：加工时间和其他参数是已知确定的定量–随机型排序：加工时间和有关参数是为随机变量•⑤根据要实现的目标–单目标排序–多目标排序2007-1-7武汉科技大学管理学院22
POM2、排序问题的表示方法¾康威(Conway) 方法¾这种方法只用4种参数就可以表示大多数不同的排序问题n/m/A/B¾其中, n-----工件数；¾m-----机器数；¾A----车间类型¾F代表流水型排序；¾P代表排列排序¾G为一般类型,即单件型排序，¾当m=1时，则A处为空白，因为单台机器无所谓加工路线问题。)¾B-----目标函数，通常是使其值最小2007-1-7武汉科技大学管理学院23
POM第三节单台机器的排序问题n个工件全部经由一台机器处理J1J2离开系统J机器3（机器）Jn到达系统工件的集合2007-1-7武汉科技大学管理学院24
POM一、常见单台机器排序问题的目标函数1) 平均流程时间最短n_1为n个零件经由一台机器的平均流程时间。定义: F=F∑ini=1n_1目标函数min F=F∑ini=12）最大延期量最小T=maxT为最大延期量。{}定义: maximin T目标函数max2007-1-7武汉科技大学管理学院25
POM根据排序目标的不同，可以选择不同的排序规则，有时又称为确定优先权(Priorities)。常见的优先权规则(Priority rules)有：SPT---Shortest Process Time,EDD---Earliest Due DateFCFS---First Come First ServedCR---Critical Rate等, 分别用于解决不同的问题。2007-1-7武汉科技大学管理学院26
POM几种调度准则的比较FCFS -First-Come-看似“公平”，但是没有运用已有信息. 通First-Served常用于服务业的排对系统(银行, 商店)LCFS -Last-Come-该准则通常是缺省情况下发生的，到达的First-Served工件被依次放到最上面.SPT -Shortest 在给定的时间内能完成最多的任务，并且Processing Time能使平均等待最小. 但是使有些任务大大推迟完成.EDD -Earliest Due 试图达到平均延期和最大延期最小. 但是需Date要正确的交货期.STR -Slack Time 使任何任务（订单）最大延期最小. 动态Remaining计算CR -Critical Ratio该比值表明订单是超前(CR > 1), 准时(CR =1) 还是延迟(CR < 1).STR/OP –Slack Time 与STR类似, 但是着眼于将来的作业活动per Remaining Operation2007-1-7武汉科技大学管理学院27
POM二、求平均流程时间最短的排序问题•求平均流程时间最短的作业顺序，采用SPT原则。按工件加工时间的长短，按不减的顺序从小到大安排各项作业。•例：一个车间有一台加工中心，现有5个工件需要该机器加工。相关的加工时间和要求完成时间（交货期）如下表所示，求平均流程时间最短的作业顺序。JJJJJ1234511293112加工时间6145313332交货期2007-1-7武汉科技大学管理学院28
POM解：根据SPT原则，得出：J-J-J-J-J45123有关项目的计算：完成时间加工时间交货期延迟J113304J233205J11146101J29434502J317431433n_1F=F=135/5=∑ini=12007-1-7武汉科技大学管理学院29
POM三、求最大延期量最小的排序问题求最大延期量最小的作业顺序采用EDD原则。EDD(Earliest Due Date): Jobs are sequenced in increasing order of their due dates.例：借用上面的例子，求最大延期量最小的作业顺序。解：根据EDD原则，得出：J-J-J-J-J35421加工时间完成时间交货期延迟J31313103J2333215J1343314J296345182J1174611312007-1-7武汉科技大学管理学院30
POMn_1F=F=235/5=∑ini=1平均延迟=33/5= T=18max进一步考虑：在最大延期量不变的情况下，如何使平均流程时间缩短？如果想同时满足这两个目标，就是多目标排序。2007-1-7武汉科技大学管理学院31
POM四、综合原则例: 在一台设备上安排6个工件的加工任务，每项任务的作业时间和交货期如下表所示。JJJJJJ123456作业时间324865交货期要求6310202830在满足Tmax最小的情况下，使平均流程时间最小。2007-1-7武汉科技大学管理学院32
POM1、首先使用EDD规则排序JJJJJJ2134562、求出所有作业的总操作时间T T=28 3、求出交货期不小于T的任务项，然后按其加工时间的大小调整，将加工时间上的任务调整到后面。如本例，J，J满足要求，因为t> t, 所以：5656JJJJJJ2134654、去掉已调整的任务，重复2-4步。最后得最优解：JJJJJJ213465F=-1-7武汉科技大学管理学院33
POM第四节流水作业排序问题•流水线是流水车间(Flow shop)典型的代表，每个零件的加工路线都一致，即工件的流向一致。•只要加工路线一致：MM,M，…，M,不要求123m每个零件都经过每台机器加工•一般的流水作业排序问题：工件在机器上的加工顺序可能不一致2007-1-7武汉科技大学管理学院34
POM•流水作业的排列排序问题（同顺序排序问题）则是所有工件在各台机器上加工顺序都相同的排序。•排列排序问题的最优解：在2~3台机器时为流水作业排序问题的最优解，一般为较优解2007-1-7武汉科技大学管理学院35
POM一、最长流程时间F的计算max¾本节所讨论的是n/m/P/F问题，目标函数是使max最长流程时间最短。•最长流程时间：–又称加工周期，从第一个工件在第一台机器上开始加工算起，到最后一个工件在最后一台机器上完成加工时间为止所经过的时间，等于排在末尾的工件在车间的停留时间。–由于假设所有工件的到达时间都为零，所以F等于max排在末位加工的工件在车间的停留时间，也等于一批工件的最长完工时间Cmax2007-1-7武汉科技大学管理学院36
POM•设n个零件的加工顺序为S=(S, S,···,S)1 2 n–S为排在第i位加工的工件代号i–C表示工件S在机器M上的完工时间kiksi–p表工件S在M上的加工时间siikk–k=1,2,..,m; i=1,2,...,n•则C可按以下公式计算：ksi•C= C+ p, 11sisisi-1 1 •C=max {C,C}+ pk(k-1)ksisisi si-1 k•k=2,3,···,m; i=1,2,···,n,•当r=0，i=1,2,···,n时，F= Cimaxmsn2007-1-7武汉科技大学管理学院37
POM例：有一个6/4/P/F问题，其加工时间如表11-1max所示。当按顺序S=(6,1,5,2,4,3)加工时，求Fmax表11-1加工时间矩阵i1 2 3 4 5 6P4 2 3 1 4 2i1P4 5 6 7 4 5i2P5 8 7 5 5 5i3P4 2 4 3 3 1i42007-1-7武汉科技大学管理学院38
POM解：最长流程时间F的计算max•按S的顺序列出加工矩阵•第一行第一列加工时间等于其右上角的完工时间•第一行其他列完工时间等于其前一列完工时间加上其加工时间•第二行以下,第一列完工时间等于其前一行完工时间加上其加工时间；其他列完工时间等于其前一列完工时间加上其加工时间i6152432610121316p244213i171115202733p544576i2121722303542p555857i3132125323846p143234i42007-1-7武汉科技大学管理学院39
POM二、/// n/2/F/ F问题的最优算法maxn项任务在两台机器的排序问题Scheduling n Jobs on Two Machinesn个工件都必须经过机器1和机器2的加工，即工艺路线是一致的。离开系统（J1机器1机器2机器）J2J3Jn到达系统工件的集合2007-1-7武汉科技大学管理学院40
POM两台机器排序问题的目标•两台机器排序的目标是使最大完成时间(总加工周期)Fmax最短。F的含义见如下的甘特图(Gantt Chart)。max在机器A上的作业时间机器AB总加工周期F时间max•多台机器排序的目标一般也是使最大完成时间（总加工周期）F最短。max2007-1-7武汉科技大学管理学院41
POMJohnson算法:•对于n/2/F/Fmax问题，.约翰森()于1954年提出了一个有效算法，即著名的(Johnson)算法。•1、首先介绍该方法中所用符号的含义：工件：J，Jij机器：M，M1 2路线：MM1 2加工时间：a表示J在M上的加工时间ii1b表示J在M上的加工时间ii22007-1-7武汉科技大学管理学院42
POM加工时间矩阵工件JJij机器Maa1ijMbb2ij2、Johnson法则•如果：min(ai, bj)<min(aj, bi) ()•则J应该排在J之前。如果中间为等号，则工ij件J既可排在工件J之前，也可排在它之后。ij•这样可确定两个工件相对位置，但比较麻烦。2007-1-7武汉科技大学管理学院43
POM3、Johnson算法：•①从加工时间矩阵中找出最短的加工时间。•②若最短的加工时间出现在M上，则对应的零1件尽可能往前排；若最短加工时间出现在M2上，则对应零件尽可能往后排。然后，从加工时间矩阵中划去已排序零件的加工时间。若最短加工时间有多个，则任挑一个•③若所有零件都已排序，停止。否则，转步骤①2007-1-7武汉科技大学管理学院44
POM例：求表11-3所示的6/2/F/Fmax问题的最优解i1 2 3 4 5 6a5 1 8 5 3 4ib7 2 2 4 7 4i•解：将工件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=282007-1-7武汉科技大学管理学院45
POM21 53 64 15 45 3822 57 64 17 44 32示意图2007-1-7武汉科技大学管理学院46
POMJohnson算法的改进算法：–将所有a≤b的工件按a值不减的顺序排成iii一个序列A–将所有a>b的工件按b值不增的顺序排成iii一个序列B–将A放到B之前即构成最优加工顺序•Johnson法则所得到的最优顺序中任意去掉一些工件，余下的仍构成最优顺序2007-1-7武汉科技大学管理学院47
POM改进算法i1 2 3 4 5 6ai5 1 8 5 3 4bi7 2 2 4 7 4i2 5 6 1 4 3ai1 3 4 5 5 8bi2 7 4 7 4 2•序列A为(2,5,6,1),序列B为(4,3)，构成最优顺序为(2,5,6,1,4,3),与Johnson算法结果一致。2007-1-7武汉科技大学管理学院48
POM注意：•Johnson法则只是一个充分条件，不是必要条件。不符合这个法则的加工顺序，也可能是最优顺序。•如对例11-2顺序(2,5,6,4,1,3)不符合Johnson法则，但它也是一个最优顺序2007-1-7武汉科技大学管理学院49
POM两台机器排序问题算法的扩展(Extensiion to Three Machiines)一般情况下当机器数为3台以上时，就很难找到最优解了但是，对于n个工件由三台机器流水作业时，在满足某些条件后可以采用Johnson’s Law解决问题。设：A、B、C为三台机器，如果工件在三台机器上的加工时间满足以下条件，则可以转化为两台机器的排序问题：min A>=max Biior min C>= max Bii定义：A’= A+ B, B’= B+Ciiiiii例: 考虑以下问题. 5个工件由3台机器加工, 作业时间见下表. 求: 总加工周期最短的作业顺序.2007-1-7武汉科技大学管理学院50
POM•例: 考虑以下问题. 5个工件由3台机器加工, 作业时间见下表. 求: 总加工周期最短的作业顺序.1 2 3 4 5413212732机器A49865919233036机器B562341729354253机器C8106711解: 检查上表, 发现:min A= 4 i max B= 6 i min C= 6i因此,满足以上条件, 建立两台机器的作业时间表: 2007-1-7武汉科技大学管理学院51
POM1 2 3 4 5机器A’9 15 10 9 9机器B’13 16 8 10 15应用Johnson法则，得出：１－４－５－２－３总加工周期为：1 4 5 2 341015 2432机器A46598913193034机器B534621724354551机器C87111062007-1-7武汉科技大学管理学院52
POM三、一般n/m/P/ F问题的启发式算法max•对于3台机器的流水车间排序问题，只有几种特殊类型的问题找到了有效算法。•对于一般的流水车间排列排序问题，可以用分支定界法。•对于实际生产中规模较大的问题，计算量相当大，以至连计算机也无法求解。同时考虑经济性，所以该方法很少用•为了解决生产实际中排序问题，人们提出了各种启发式算法。启发式得法以小的计算量得到足够好的结果，因而实用。下面介绍求一般n/m/P/F问题近优解(Near optimal maxsolution)的启发式算法。2007-1-7武汉科技大学管理学院53
POM1、Palmer法•1965年，.帕尔玛()提出按斜度指标排列工件的启发式算法，称之为(Palmer)法。工件的斜度指标可按下列公式计算：mλ=[k−(m+1)2]p,k=1,2,L,n∑iiki=1pM式中，m为机器数；为工件在上的加工时间,ikik按照各工件λ不增的顺序排列工件，可得到令人i满意的顺序。2007-1-7武汉科技大学管理学院54
POM例///：有一个4/3/F/Fmax问题，其加工时间如下表所示，用lPalmer法求解。i1 2 3 4P1 2 6 3 i1P8 4 2 9 i2P4 5 8 2 i3•解：计算λ。对于本例，i3λ=[k−(3+1)2]p,k=1,2,3∑iiki=1λ=−p+pii1i32007-1-7武汉科技大学管理学院55
POM于是，λ=−p+p=−1+4=311113λ=−p+p=−2+5=322123λ=−p+p=−6+8=233133λ=−p+p=−3+2=−144143•按λ不增的顺序排列工件，得到加工顺序i(1,2,3,4)和(2,1,3,4)，恰好这两个顺序都是最优顺F=28序。在最优顺序下，max2007-1-7武汉科技大学管理学院56
POM2、关键工件法•1983年陈荣秋提出•计算步骤为–计算每个工件的总加工时间P，找出最长的工件iC，将其作为关键工件JC–对其它工件，将所有p<p的工件按p值不减的顺i1imi1序排成一个序列S；将所有p>p的工件按p值不ai1imim增的顺序排成一个序列S除J外，将满足p=p的b；Ci1im工件，排在J的前面或者后面。C–（S，C，S）为满意顺序ab2007-1-7武汉科技大学管理学院57
POM例：用关键工件法求上例.的近优解解：求P，i=1,2,3,4,如下表所示。ii1 2 3 4P1 2 6 3 i1P8 4 2 9 i2P4 5 8 2i3P13 111614 i•总加工时间最长的为3号工件，P≤P的工件i1i3为1 和2，按P不减的顺序排成Sa=(1,2)，i1P>P的工件为4号工件，S=(4)，这样得到i1i3b加工顺序为(1,2,3,4)2007-1-7武汉科技大学管理学院58
POM例：有一个6/5/F/Fmax问题，其加工时间如下表所示，用关键工件法求解。JJJJJJ123456机器1p5541210i1机器2p5553610i2机器3p833474i3机器4p282156i4机器5p5212810i5 252315112840总和得到的加工顺序为：J4 –J5 –J6–J1 –J2 –J3 或J4 –J5 –J1–J6–J2 –J32007-1-7武汉科技大学管理学院59
POM3、CDS法•康坎贝尔—杜得克—史密斯(Campbell-Dudek-Smith)三人提出了一个启发式算法,简称CDS法。他们把Johnson算法用于一般的n/m/P/Fmax问题，得到(ｍ－1)个加工顺序，取其中优者。•具体做法中，对加工时间：lmp 和 p,l=1,2,L,m−1∑∑ikikk=1k=m+1−lJohnson(ｍ－1)用算法求次加工顺序，取其中最好的。结果2007-1-7武汉科技大学管理学院60
POM•求m-1个加工顺序中的第l个（l=1,2,…m-1）时将前l台机器和后m-l台机器分别看成两个机器群体，并对其加工时间分别进行求和lmP 和 P, l=1,2,...,m−1∑∑ikikk=1k=m+1−l加工顺序A加工时间 B加工时间 1 t t 1m2 t+t+t 12m-1m3 t+t+t t+t+t 123m-2m-1m… …… …… m-1 t+t+…+tt+…+t+t 12m-1 2m-1m 2007-1-7武汉科技大学管理学院61
POM例：用.CDS法求上例的近优解lmp 和 p,l=1,2解：求如下表所示。∑∑ikikk=1k=m+1−li1 2 3 4P1 2 6 3 i1L=1P4 5 8 2i3P+P9 6 8 12i1 i2L=2P+P12 9 10 11i2 i3L＝1Johnson(1,2,3,4), •当时，按算法得到加工顺序Fmax＝28 ；L＝2(2,3,1,4),Fmax＝29•当时，得到加工顺序。(1,2,3,4)•所以，取顺序。这就是最优顺序。2007-1-7武汉科技大学管理学院62
POM四、相同零件不同移动方式下加工周期的计算•排序问题针对的是不同的零件，如果n个零件相同，则没有排序问题。•但零件在加工过程中采取的移动方式不同，会导致一批零件的加工周期不同。•零件在加工过程中可以采用三种典型的移动方式：–顺序移动–平行移动–平行顺序移动2007-1-7武汉科技大学管理学院63
POM(一 ) 顺序移动方式•概念：一批零件在上道工序全部加工完毕后才整批地转移到下道工序继续加工。工序nt1nt2ttttM11111nt3tttt2222M2nt4tttt3333M3tttt4444M4时间0T顺2007-1-7武汉科技大学管理学院64
POMT采用顺序移动方式，一批零件的加工周期为：顺mT=nt∑顺ii=1n零件加工批量式中，ti第个工序的单件工序时间im零件加工的工序数2007-1-7武汉科技大学管理学院65
POMn=4，t=10分钟，t=5分钟，例，如下图所示，已知12t 。求t=10分钟，t=15分钟，43顺工序10M15M215M310M4t020 40 60 80 100 120 140 160解：t=4×(10+5+15+10)=160(分钟)顺2007-1-7武汉科技大学管理学院66
POM(二)平行移动方式•概念：每个零件在前道工序加工完毕后，立即转移到后道工序去继续加工，形成前后工序交叉作业。工序t1M1t2M2t3M3t4M4时间t(n−1)tttt132342007-1-7武汉科技大学管理学院67
POMT采用平行移动方式，一批零件的加工周期为：平mT=nt+(n−1)t∑平iLi=1式中，n零件加工批量ti第个工序的单件工序时间im零件加工的工序数t最长的单件工序时间L2007-1-7武汉科技大学管理学院68
POMt=5分钟，例，如下图所示，已知n=4，t=10分钟，21t 。求t=10分钟，t=15分钟，平34工序1工序2工序3工序4t20 40 60 80 85 100t=(10+5+15+10)+(4－1)×15=85(分钟)解：平2007-1-7武汉科技大学管理学院69
POM(三)平行顺序移动方式1、概念：即一批零件或产品,既保持每道工序的平行性，又保持连续性的作业移动方式。2、具体做法以：t<t①当时，零件按平行移动方式转移；ii+1it≥t②当时，以工序最后一个零件的完工时间ii+1(i+1)(n−1)×ti+1为基准，往前推移作为零件在工序的开始加工时间2007-1-7武汉科技大学管理学院70
POM工序10M1t≥tii+1x5M2t<t，所以平行移动ii+1y15M3t≥tzii+110M40 10 20 30 40 50 60 70 80 90 100时间25 45mT=nt−(x+y+z)∑平顺ii=12007-1-7武汉科技大学管理学院71
POM采用平行顺序移动方式，一批零件的加工周期T平顺为：mm−1T=nt−(n−1)min(t,t)∑∑平顺ijj+1i=1j=1式中，n零件加工批量ti第个工序的单件工序时间im零件加工的工序数将上例数值代入该公式，得：t=4×(10+5+15+10)−(4－1)×(5+5+10)=100(分钟)平顺2007-1-7武汉科技大学管理学院72
POM▲三种移动方式的优缺点比较比较项目平行移动平顺移动顺序移动生产周期短较短长运输次数多较多少设备利用差好好组织管理中复杂简单※可以用平行系数P来表示生产过程平行性的程度P=1-(一批零件加工周期/顺序移动方式下零件加工周期)2007-1-7武汉科技大学管理学院73
POM选择移动方式应考虑的因素①零件的大小②零件加工时间的长短③批量的大小④生产单位专业化的形式2007-1-7武汉科技大学管理学院74
POM第五节单件作业排序问题•一、问题的描述•每个工件都有其独特的加工路线，工件没有一定的流向•用加工描述矩阵描述所有工件的加工要求。矩阵的行表示不同的工件；列表示不同的工序；每个元素用一个(i,j,k)三元组表示工件i的第j道工序在机器k上加工•一般n/m/G/ F问题无有效算法，通常应用一些启发式max算法2007-1-7武汉科技大学管理学院75
POM单件作业排序问题/// (n/m/G/ F)max•加工描述矩阵D的每一行描述一个工件的加工，每一列的工序序号相同。•加工时间矩阵T：与D相对应。1,1,1 1,2,3 1,3,2D=2,1,3 2,2,1 2,3,24 6 3T=5 7 42007-1-7武汉科技大学管理学院76
POM单件作业排序问题/// (n/m/G/ F)max•加工顺序矩阵S：每一行与机器相对应，每一列与工件相对应。1,1,1 1,2,3 1,3,2D=2,1,3 2,2,1 2,3,21,1,1 2,2,1S=1,3,2 2,3,22,1,3 1,2,32007-1-7武汉科技大学管理学院77
POM单件作业排序问题/// (n/m/G/ F)max•用方块图表示：1,1,1 2,2,11,1,1 1,2,3 1,3,24 6 31,3,2 2,3,2D=T=S=2,1,3 2,2,1 2,3,25 7 42,1,3 1,2,3M11,1,12,2,11,3,22,3,2M2M32,1,31,2,32007-1-7武汉科技大学管理学院78
POM二、一般n/// /m/G/ F问题的启发示算法max•(一)两种作业计划的构成•半能动作业计划–各工序都按最早可能开(完)工时间安排的作业计划•能动作业计划–任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动作业计划•无延迟作业计划–没有任何延迟出现的能动作业计划–延迟指有工件等待加工时，机器出现空闲2007-1-7武汉科技大学管理学院79
POM1、能动作业计划的构成•各工序都按最早可能开(完)工时间安排且任何一台机器的每段空闲时间都不足以加工一道可加工工序。•符号说明：–步：把每安排一道工序称作一“步”–{O} 第t步可以排序的工序的集合t–{S} t步之前已排序的工序构成的部分作业计划t–T为{O}中工序O的最早可能开工时间ktk’–T为{O}中工序O的最早可能完工时间ktk2007-1-7武汉科技大学管理学院80
POM能动作业计划的构成步骤①设t＝1，{S}为空，{O}为各工件第一道工序的集合。t t*’*②求最小的最早完工时间T= min{T},并找到出现T的机k*器M，若有多台，任选一台。③从{O}中看挑出满足以下两条件的工序Otj*–需要机器M加工；*–T< Tj④将确定的O放入{S}，从{O}中消去O，并将O的紧后jt tjj工序放入{O}中，使t=t+1。t⑤若还有未安排的工序，转步骤②；否则，停止。2007-1-7武汉科技大学管理学院81
POM例：一个2/3/G/F问题 max1,1,11,2,31,3,2241⎛⎞⎛⎞⎜⎟⎜⎟D= T= ⎜⎟⎜⎟2,1,32,2,12,3,2345⎝⎠⎝⎠**t′{O}TOTMtkjTk11,1022M1,1,112,1,30321,23262,1,3033M2,1,3331,23377M1,2,332,2,137M141,32782,2,1377M2,2,1151,32788M1,3,222,3,271262,3281313M2,3,222007-1-7武汉科技大学管理学院82
POM1,1,1 2,2,1得到加工顺序矩阵：1,3,2 2,3,2S=2,1,3 1,2,3M11,1,12,2,1231,3,22,3,2M27813M32,1,31,2,372007-1-7武汉科技大学管理学院83
POM2、无延迟作业计划①设t＝1，{S}为空，{O}为各工件第一道工序的集合。tt**②求最小的最早完工时间T= min{T},并找到出现T的k*机器M，若有多台，任选一台。③从{O}中跳出满足以下两条件的工序Otj*–需要机器M加工；*–T= Tj④将确定的O放入{S}，从{O}中消去O并将O的紧后工jjttj序放入{O}中，使t=t+1。t⑤若还有未安排的工序，转步骤②；否则，停止。2007-1-7武汉科技大学管理学院84
POM例：一个2/3/G/F问题 max1,1,11,2,31,3,2241⎛⎞⎛⎞⎜⎟⎜⎟D= T= ⎜⎟⎜⎟2,1,32,2,12,3,2345⎝⎠⎝⎠**t ′{O} T O T M tkjT k11,1 0 2 0 M 1,1,1 12,1,3 0 3 0 M3 21,23 2 6 2,1,3 0 3 0 M2,1,3 3 31,23 3 7 3 M1,2,3 3 2,2,1 3 7 3 M1 41,32 7 8 2,2,1 3 7 3 M2,2,1 1 51,32 7 8 7 M 2,3,2 22,3,2 7 12 7 M2 62,3,2 8 13 12 M1,3,2 2 2007-1-7武汉科技大学管理学院85
POM1,1,1 2,2,1得到加工顺序矩阵：2,3,2 1,3,2S=2,1,3 1,2,3M11,1,12,2,1232,3,21,3,2M271213M32,1,31,2,372007-1-7武汉科技大学管理学院86
POM（二)启发式算法•能动作业计划和无延迟作业计划尽管不一定是最优作业计划，但一般是较好的作业计划，特别是无延迟作业计划能提供令人满意的解。•一般能动作业计划和无延迟作业计划都有多个，可用启发式方法从中选择结果较好的作业计划。•一般来说，以构成无延迟作业计划的步骤为基础的启发式算法比以构成能动作业计划的步骤为基础的启发算法的效果要好。2007-1-7武汉科技大学管理学院87
POM1、优选调度法则•SPT (Shortest Processing Time)法则：优先选择加工时间最短的工序。•FCFS (First Come First Served)法则：优先选择最早进入可排工序集合的工件。•EDD (Earliest Due Date)法则：优先选择完工期限紧的工件。•MWKR (Most Work Remaining)法则：优先选择余下加工时间最长的工件。•LWKR (Least Work Remaining)法则：优先选择余下加工时间最短的工件。•MOPNR (Most Operations Remaining)法则：优先选择余下工序数最多的工件。2007-1-7武汉科技大学管理学院88
POM•⑦SCR (Smallest Critical Ratio)法则：优先选择临界比最小的工件。临界比为工件允许停留时间与工件余下加工时间之比。•⑧RANDOM法则：随机地挑一个工件2007-1-7武汉科技大学管理学院89
POM优选调度法则•按SPT法则可使工件的平均流程时间最短，从而减少在制品量。•FCFS法则来自排队论，它对工件较公平。•EDD法则可使工件最大延误时间最小。•SCR也是保证工件延误最少的法则。•MWKR法则使不同工作量的工件的完工时间尽量接近。LWKR法则，使工作量小的工件尽快完成。•MOPNR法则与MWKR法则类似，只不过考虑工件在不同机器上的转运排队时间是主要的。2007-1-7武汉科技大学管理学院90
POM2、随机抽样法•用穷举法或分支定界法求一般单件车间排序问题的最优解时，实际上比较了全部能动作业计划；采用优先调度法则求近优解时，只选择了一种作业计划。•随机抽样法介于这两个极端之间。•它从全部无延迟作业计划之中抽样，得出多个作业计划，从中选优。•应用随机抽样法时，实际上是对同一个问题多次运用RANDOM法则来决定要挑选的工序，从而得到多个作业计划。2007-1-7武汉科技大学管理学院91
POM3、概率调度法•随机抽样法是从k个可供选择的工序以等概率方式挑选，每个工序被挑选的概率为1／k，这种方法没有考虑不同工序的特点，有一定盲目性。•例如，在构在无延迟作业计划的第③步有3道工序，A、B和C可挑选，这3道工序所需的时间分别为3，4和7。如果按RANDOM法则，每道工序挑选上的概率都是1／3；如果按SPT法则，则只能挑选工序A。现按目标函数的要求，选择了SPT法则。按概率调度法，将这3道工序按加工时间从小到大排列，然后给每道工序从大到小分配一个被挑选的概率，比如A、B和C的挑选概率分别为6／14、5／14和3／14。2007-1-7武汉科技大学管理学院92
POM第六节生产作业控制一、实行生产作业控制的原因和条件1、原因–加工时间估计不准确–随机因素的影响–加工路线的多样性–企业环境的动态性2、条件–要有一个标准–要取得实际生产进度与计划偏离的信息–要能采取纠正偏差的行动2007-1-7武汉科技大学管理学院93
POM二、不同生产类型生产控制的特点不同生产类型的典型特点特点单件小批生产大量大批生产零件的流动没有主要的流动路线单一的流动路线瓶颈经常变动稳定设备通用设备，有柔性高效专用设备调整准备费用低高工人操作多少工人工作的范围宽窄工作节奏的控制由工人自己和工长由机器和工艺过程在制品库存高低产品库存很少较高供应商经常变化稳定编制作业计划不确定性高，变化大不确定性低，变化少2007-1-7武汉科技大学管理学院94
POM(一)单件小批生产•单件小批生产是为顾客生产特定产品或提供特定服务的，因此，产品品种千差万别，零件种类繁多。•每一种零件都有其特定的加工路线，整个物流没有什么主流。•各种零件都在不同的机器前面排队等待加工。各个工作地之间的联系不是固定的，有时为了加工某个特定的零件，两个工作地才发生联系，该零件加工完成之后，也许再也不会发生什么联系了。•这种复杂的情况使得没有任何一个人能够把握如此众多的零件及其加工情况。为此，需要专门的部门来进行控制。2007-1-7武汉科技大学管理学院95
POM工件的生产提前期的构成：移动时间排队时间调整准备时间加工时间等待运输时间•(1)移动时间。为从上道工序加工完成后转送到本工序途中所需时间。这个时间取决于运输工具和运输距离，是相对稳定的。•(2)排队时间。由于本工序有很多工件等待加工，新到的工件都需排队等待一段时间才能加工。排队时间的变化最大，单个工件的排队时间是优先权的函数，所有工件的平均排队时间与计划调度的本平有关。2007-1-7武汉科技大学管理学院96
POM•(3)调整准备时间。–为加工本工件需作的调整准备所花的时间。它与技术和现场组织管理水平都有关。•(4)加工时间。–是按设计和工艺加工，改变物料形态所花的时间。加工时间取决于所采用的加工技术和工人的熟练程度，它与计划调度方法无关。•(5)等待运输时间。–加工完毕，等待转下一道工序所花的时间。它与计划调度工作有关。2007-1-7武汉科技大学管理学院97
POM•对于单件小批生产，排队时间是主要的，它大约占工件加工提前期的80%～95％。排队时间越长，在制品库存就越高。•如果能够控制排队时间，也就控制了工件在车间的停留时间。要控制排队时间，实际是控制排队队长的问题。因此，如何控制排队的队长，是生产控制要解决的主要问题。•通过输入/输出控制，可以控制队长。输入输出控制将在“漏斗模型”中详细介绍。2007-1-7武汉科技大学管理学院98
POM（二）大量大批生产•大量大批生产的产品是标准化的，通常采用流水线或自动线的组织方式生产。•在流水线或自动线上，每个工件的加工顺序都是确定的，工件在加工过程中没有排队现象．没有派工问题，也无优先权问题。•因此，控制问题比较简单。主耍通过改变工作班次，调整工作时间和工人数来控制产量。•但是，在组织混流生产时，由于产品型号、规格、花色的变化，也要加强计划性．使生产均衡2007-1-7武汉科技大学管理学院99
POM不同生产类型生产控制的特点•单件小批生产–工件生产提前期：移动时间、排队时间、调整准备时间、加工时间、等待运输时间–其中，排队时间是主要的，占工件加工提前期的80%到95%–控制排队的队长是生产控制要解决的主要问题•大量大批生产–每个工件的加工顺序是确定的，没有排队现象，没有派工问题，也无优先权问题，因此，控制问题比较简单。–主要通过班次，调整工作时间和工为数量来调整产量。–混流生产时，产品型号、规格、花色的变化，也要加强计划性2007-1-7武汉科技大学管理学院100
POM三、车间作业控制的主要功能是•确定车间作业指令•获取在制品占用信息•将车间作业状况信息反馈给上级及有关部门提供实际产出信息•提供成本核算所需要的车间生产和在制品信息•提供人力、设备等的利用率、效率和生产率信息2007-1-7武汉科技大学管理学院101
POM2007-1-7武汉科技大学管理学院102
POM四、生产作业控制的主要工具•实际生产中，有不少工具可以用来进行生产作业控制，这些工具容易通过运用适当的软件来生成，主要包括：–调度单–日报、月报–例外报告、异常报告–甘特图–输入/输出（Input/output control，I/O）报告2007-1-7武汉科技大学管理学院103
POM甘特图•按照时间绘制任务，图中的内容既显示了作业所需要的时间，也显示了作业执行的顺序•亨利·L·甘特（Henry L·Gantt）于20世纪初首先把图表用于企业进度安排中，监控每个作业具体的完成情况DayJobSMTWTFSJob AJob BRepairJob CToday2007-1-7武汉科技大学管理学院104
POM输入//输出控制•对工作中心的作业流和序列程度进行控制，是制造计划和控制系统的一个主要特征•主要原则：工作中心的输入永远不能超过工作中心的输出•目的：分析输入与输出之间的差异，找到问题的来源，采取适当的控制措施，从而有效地控制生产作业，使工作中心的输入和输出达到完美的平衡2007-1-7武汉科技大学管理学院105
POM一个输入//输出报告12345130130130100120计划输入15012512098127实际偏差+20−5−10−2+7累计+20+15+5+3+10140140140100145计划140135135104146实际输出0偏差−5−5+4+10累计−5−10−6−540504025190积压偏差=实际−计划；每一期的积压=（本期实际输入−本期实际输出）+上期积压2007-1-7武汉科技大学管理学院106
POM五、“漏斗”模型——输入/输出控制•德国汉诺威大学的Bechte和Wiendall等人在80年代初提出了“漏斗模型”（Funnel model)。•所谓“漏斗”是为了方便地研究生产系统而作出的一种形象化描述。一台机床、一个班组、一个车间乃至一个工厂，都可以看作是一个“漏斗’。•作为“漏斗”的输入，可以是上道工序转来的加工任务，也可以是来自用户的订货；作为“漏斗”的输出，可以是某工序完成的加工任务，也可以是工厂制成的产品。而“漏斗”中的液体，则表示累积的任务或在制品。液体的量则表示在制品量，如图11一7所示。2007-1-7武汉科技大学管理学院107
POM“漏斗”模型——输入/输出控制•模型介绍–德国汉诺威大学的Bechte和Wiendall等人于20世纪80年代初在实施输入/输出控制时提出了漏斗模型（Funnel Model）。•漏斗模型的基本原则：–工作中心的输入永远不能超过工作中心的输出。当工作中心的输入超过输出，就会拖欠订单，结果将会出现作业推迟、客户不满、下游作业或相关作业的延期。2007-1-7武汉科技大学管理学院108
POM工作量期末库存内的参输考入时间段输入曲线到达的工件输入[小时]内的参输考出时间段库存水平期初库存任务输出曲线库存(小时)时间参考时间段完成的任务输出[小时]2007-1-7武汉科技大学管理学院109
POM1、输入输出图•在图11一7左部漏斗的开口大小表示生产能力，它是可以调整的。液面高低表示累积任务量的大小。•图11一7右部为输入输出图。该图包括输入曲线和输出曲线，它们分别描述工件的到达情况和完成情况。•横坐标为时间，通常以工作日为单位；纵坐标为工作负荷，通常以小时表示。•曲线的垂直段表示某天到达或完成的一个或多个工件所包含的工作量；水平段表示相邻两个到达或完成的任务之间的时间间隔。如果运输时间不变，输入曲线与上道工序的输出曲线相对应。2007-1-7武汉科技大学管理学院110
POM•输入曲线和输出曲线表示在一定观察期内任务到达的累计情况和任务完成的累计情况．它们可以从过去任何一天开始构造到现在。实际上，几周时间巳足够。•两条曲线任一时刻垂直方向的距离表示该时刻在制品占用量（以工作量表示），而条曲线的水平距离表示相应工作任务在该工作地停留的时间(按FIFO规则) 2007-1-7武汉科技大学管理学院111
POM2、基本公式L=λ/(μ−λ)平均队长2L=λ/μ(μ−λ)平均队列队长g平均通过时间T=1/(μ−λ)平均等待时间T=λ/μ(μ−λ)w式中，为平均到达率（单位时间到达工件的平均数）λμ为平均完工率（单位时间完成的平均工件数）μ>λ平均通过时间＝平均在制品库存/单位时间平均产量2007-1-7武汉科技大学管理学院112
POM3、控制规则•在一段较长的时间内（如数周）内，若工况稳定，输入输出两条曲线可以近似地用两条直线来表示，其斜率（平均生产率）等于平均在制品库存/平均通过时间，即：平均通过时间＝平均在制品库存/单位时间平均产量。2007-1-7武汉科技大学管理学院113
POM•实际实践中，可以采用四个规则来调整输入、输出、在制品库存和通过时间：–若希望保持在制品库存稳定，要使单位时间内平均输入等于平均输出–若希望改变在制品库存量，可暂时增加或减少输入。–若希望平均通过时间在所控制的范围内，则适当调整平均在制品库存与生产率的比例。–要使各个工件的平均通过时间稳定，可以采用FIFO规则来安排各工件的加工顺序。2007-1-7武汉科技大学管理学院114
