第十一章制造业作业计划与控制

1《生产运作管理》第十一章制造业作业计划与控制2引导案例-忙碌，不代表有效率某忙碌的制造企业的生产准备会议史黛西（生产主管）坐在会议桌旁，前面堆了一大堆文件，她手上拿着一张名单，似乎已经准备好应付围攻。她说：“对，已经查出来了。事实上，昨天晚上我一直忙着追踪和查证这些资料。结果，我发现出问题的零件有三十种。”钟纳说：“你确定原材料都发出去了吗？”“没错，”史黛西说，“他们已经根据时间表，把原材料发出去了，但是在最后装配部还看不到这些零件，零件卡在新瓶颈那里了。”“等一等，你怎么知道那真的是瓶颈呢？”她说：“因为这些零件被耽搁了，我觉得一定是······”思考目前现状大量（超过30种）零部件延迟，未按期交货；可能设备生产能力出现瓶颈，但生产能力事先已知；生产过程存在一定的约束，包括人力、时间、设备等；基于一定的优先策略，零部件的加工存在优先顺序；假定排除设备故障等意外情况发生，问题出在哪里？任务分配作业排序生产作业计划与控制出了问题！生产作业计划生产控制战略管理文化管理项目及网络计划产品R&D

生产系统选址和布置BPRJIT、LN、OPT等先进生产方式质量管理设备管理库存管理市场分析需求预测订单生产计划MRP主要内容作业计划问题基本概念流水车间的作业计划问题单件车间的作业计划问题生产作业控制1作业计划问题基本概念MRP->零部件投入出产计划车间生产作业计划；落实车间生产任务到班组、工作地、工人；涉及到任务分配和作业排序的问题。作业计划问题任务分配、资源分配和作业排序约束编制作业计划要解决的问题编制作业计划要解决的问题任务分配：每个工人、每个工作地的日生产任务；生产排序：通过排序方法编制生产计划，提高生产效率。作业计划与作业排序是一回事么？否作业计划与作业排序二者含义差别作业计划是安排零部件的出产数量、设备及人工使用、投入时间及出产时间。分配资源给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。排序，给出零部件在一台或一组设备上加工的先后顺序的工作。编制作业计划与排序的概念和目的都是不同的。但是，编制作业计划的主要工作之一就是要确定出最佳的作业顺序。举例-工艺专业化9钻床仓库车床压床铣床铣床车床车床铣床铣床钻床磨床焊接油漆磨床装配装配焊接焊接仓库如何进行任务分配?很困难!举例-产品专业化机器k-1机器k机器k-1机器k第一种情况第二种情况SiSi-1SiSi-1两种零件不同在流水线上各机器的生产时间也不相同如何进行排序?很困难!根据排序规则对每一个到达的工件安排作业顺序工作地工件排队等待加工来自上游工作地的工件加工完毕的工件流向下一工作地排序的概念排序的概念(续)生产作业排序就是指对于等候某个设备或工作中心加工的多个任务，确定这些任务加工的先后次序。目的：提高设备或工作中心的效率减少在制品占用量缩短生产周期保证按期交货排序问题的分类排序问题分类按机器单台机器排序问题多台机器排序问题单件作业排序问题流水线作业排序问题按零件到达车间的情况静态的排序问题动态的排序问题按目标函数的性质分类按参数确定型排序问题随机型排序问题单台机器的排序问题n个工件全部经由一台机器处理J1J2J3Jn机器到达系统工件的集合离开系统（机器）

为实现任务总等待时间最短的目标，保证尽可能多的对象早日加工出来，加速资金周转，只需根据最短加工时间准则对加工对象排序即可。n项任务在两台机器的排序问题n个工件都必须经过机器1和机器2的加工，即工艺路线是一致的。

15机器1到达系统工件的集合离开系统（机器）J1J2J3Jn机器2作业计划问题的相关概念若干名词和概念排序、调度、派工、赶工、控制；机器：服务者；零件：服务对象；加工路线：由加工工艺过程决定（既定的）；加工顺序：每台机器加工N个零件的先后顺序（是待解决的问题）。加工路线示意图排序问题的参数表示方法返回目录2流水车间的作业计划问题流水车间的作业计划问题问题的描述n个不同零件要按相同的加工路线经过m台机器加工，目标是使这批零件的加工周期最短（加工路线确定，对不同的零件，根据目标求各个零件的加工次序）问题的表示加工周期加工周期是指第一个零件在第一台机器上开始加工到最后一个零件在最后一台机器上完成加工为止，所需要的时间。假设n个零件的加工顺序为S=(S1,S2……,Sn)

Si为排在i位加工的零件代号表示零件Si在机器Mk上的完工时间表示零件Si在Mk上的加工时间k=1,2,3,……,m，i=1,2,3,……,n加工周期的计算【例】有一个6/4/P/Fmax问题，其加工时间如表所示。当按顺序S＝(6，1，5，2，4，3)加工时，求Fmax。加工周期的计算结果加工周期又称为最长流程时间；若零件的到达时间都为0，加工周期等于排在末尾加工的零件在车间的停留时间，也等于一批零件的最长完工时间。2台机器的排序问题求解算法描述和表示描述：n个零件经过2台机器加工，使加工周期最短的流水作业排序问题表示：求解方法Johnson算法Johnson算法Johnson算法的求解步骤：①从加工时间矩阵中找出最短的加工时间；②若最短的加工时间出现在机器M1上，则对应的零件尽可能往前排；若最短加工时间出现在机器M2上，则对应零件尽可能往后排。然后，从加工时间矩阵中划去已排序零件的加工时间。若最短加工时间有多个，则任挑一个；③若所有零件都已排序，停止。否则，转步骤①。Johnson算法举例【例】求如下6/2/P/Fmax问题的最优解。求解过程如下：Johnson算法步骤的改进把Johnson算法作些改变，改变后的算法按以下步骤进行：①将所有ai≤bi的零件按ai值不减的顺序排成一个序列A；②将所有ai＞bi的零件按bi值不增的顺序排成一个序列B；③将A放到B之前，就构成了最优加工顺序。一般n/m/P/Fmax问题的启发式算法一般的流水车间排列排序问题如想求得精确解可用分支界定法：但计算量比较大，以至于计算机也无法求解，因此常用一些启发式算法求近似解。作为一般生产实际中的排序问题，近优解能够满足需要。Palmer法关键零件法CDS法Palmer法按零件的斜度指标排列零件的启发式算法零件的斜度指标算法规则：按照各零件λi不增的顺序排列零件，可得出令人满意的顺序，如果排列的结果有多个，可以通过计算Fmax，取其中最优Fmax对应的排序作为排序结果。Palmer法举例【例】有一个4/3/P/Fmax问题，其加工时间如下表所示，试用Palmer法求解。关键零件法1找出关键零件C，序号为m。2对余下的零件，若pi1≤pim，则按照pi1不减的顺序排序为Sa，否则按pim不增的顺序排序为Sb。3

顺序（Sa，C，Sb）即为近优解。CDS法Campbell-Dudek-Smith

三人提出了一个启发式算法,简称CDS法。把Johnson算法用于一般的n/m/P/Fmax问题，得到(m-1)个加工顺序，取其中优者。具体做法是对加工时间用Johnson算法求m-1次加工顺序，取其中最好的结果。CDS法举例对l=1,2,…,m-1分别排序，取最优者。当l＝1时，按Johnson算法得到加工顺序(1，2，3，4)，Fmax＝28；当l＝2时，得到加工顺序(2，3，1，4)。对于顺序(2，3，1，4)，相应的Fmax＝29；所以，取顺序(1，2，3，4)。这就是最优顺序。返回目录3单件作业计划问题是十分复杂的一种作业计划问题，内容和方法。描述n个零件在m台机器上进行作业，使加工时间最短的单件作业排序结果。表示实质是任务分配问题：匈牙利算法。任务分配的匈牙利算法从加工时间（费用）矩阵中寻找每一行的最小元素将每一行元素减去该行最小元素从加工时间（费用）矩阵中寻找每一列的最小元素将每一列元素减去该列最小元素划出能覆盖尽可能多的零元素的直线线条数等于矩阵的行数？从仅有一个零的行或列开始，找出零元素对应的分配方案，每行和每列仅能确定一个元素，最后使每行和每列都有一个零元素是零元素对应的就是最优分配方案矩阵中未被线条穿过的元素中减去这些元素中的最小值，并将这个最小值加到直线交叉的元素上，其余元素不变否任务分配的匈牙利算法举例【例】如左上表，请用匈牙利法求出任务分配。任务分配的匈牙利算法举例(续)结果矩阵表示：零件1由机器3加工(J1—M3)零件2由机器2加工(J2—M2)

零件3由机器4加工(J3—M4)

零件4由机器1加工(J4—M1)单件作业排序问题描述一般的单件作业排序问题中单个工件可以描述为：工件i的第j道工序是在机器k上进行【例】下列加工矩阵所代表的含义？

一般n/m/G/Fmax问题的启发式算法可以采用分支定界法或整数规划法求得最优解。但都是效率较低的算法，不能用于生产实际中；启发式方法是求解一般单件车间排序问题使用最多的方法。两种作业计划三种启发式算法两种作业计划两种作业计划的构成半能动作业计划：各工序都按最早可能开工时间安排的作业计划；能动作业计划：任何一台机器的每段空闲时间都不足以加工一道可加工工序的半能动计划；无延迟作业计划：没有任何延迟出现的能动作业计划。若干算法符号假设：{St}——t道工序之前已排序工序构成的部分作业计划；{Ot}——第t道工序可以安排的工序集合；Tk——{Ot}中工序Ok最早可能开工时间；Tk′——{Ot}中工序Ok最早可能完工时间。能动作业计划的构成步骤设t=1，{S1}为空集，{O1}为各工件第一道工序的集合求T*=min{Tk′}和T*出现的机器M*M*是多台？从{Ot}中挑出满足条件（需要机器M*加工且Tj′<T*）的工序Oj将确定的工序Oj放入{St}从{Ot}中消去Oj并将Oj的紧后工序放入{Ot}是否还有未安排的工序？结束否否t=t+1能动作业计划的构成算例【例】有一个2/3/G/Fmax问题，其加工描述矩阵D和加工时间矩阵T，分别为能动作业计划的计算结果设t=1，{S1}为空集，{O1}为各工件第一道工序的集合求T*=min{Tk}和T*出现的机器M*M*是多台？从{Ot}中挑出满足条件（需要机器M*加工且Tj=T*）的工序Oj将确定的工序Oj放入{St}从{Ot}中消去Oj并将Oj的紧后工序放入{Ot}是否还有未安排的工序？结束否否t=t+1无延迟作业计划的构成步骤无延迟作业计划的构成举例三类启发式算法优先调度法SPT：优先选择加工时间最短的工序；平均流程时间最短FCFS：优先选择最早进入可排工序集合的工件；对工件较为公平EDD：优先选择完工期限紧的工件；使工件的最大延误时间最小MWKR：优先选择余下加工时间最长的工件；使不同工作量的工件完工时间尽量接近三类启发式算法(续)优先调度法(续)LWKR：优先选择余下加工时间最短的工件；使工作量小的工件尽快完成MOPNR：优先选择余下工序数最多的工件；SCR：优先选择临界比最小的工件（临界比为工件允许停留时间与工件余下加工时间之比）；RANDOM：随机地挑一个工件。有时是多种优先调度法的有序组合。三类启发式算法(续)随机抽样法从全部能动作业计划或无延迟作业计划中随机抽样，得到多个作业计划，从中选优；计算量小。概率调度法结合随机抽样和优先调度法则。返回目录4生产作业控制实行生产作业控制的原因加工时间估计不准确随机因素的影响加工路线的多样化企业环境动态性生产作业控制的条件控制标准：生产计划和生产作业计划控制信息：实际生产进度和计划的偏离信息控