生产运作管理chapt11制造业作业计划教案.doc

第11章 制造业作业计划与控制Scheduling and Controlling for Manufacturing11.1 作业计划问题的基本概念11.2 流水作业排序问题11.3 单件作业的排序问题11.4 生产作业控制 教学要求： 1. 了解排序问题的术语、假设条件基本符号、分类和表示法； 2. 掌握流水作业排序问题最长流程时间Fmax的计算和n/2/F/Fmax问题的最优算法，理解n/2/P/Fmax问题的启发式算法；理解相同零件不同移动方式下加工周期的计算； 3. 掌握单件作业排序问题的能动作业计划和无延迟作业计划及其构成方法，理解三类启发式算法； 4. 了解生产作业控制，理解不同生产类型生产控制的特点和“漏斗模型”。教学重点： 1. Fmax的计算和n/2/F/Fmax问题的最优算法（Johnson算法）； 2. 能动作业计划和无延迟作业计划的构成方法11.1作业计划问题的基本概念11.1.1基本概念l 编制作业计划要解决的问题编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间问题。由于每台机器都可能被分配了多项任务，而这些任务受到加工路线的约束，就带来了零件在机器上加工的顺序问题。l 有关的名词术语编制作业计划或日程安排(Scheduling)排序(Sequencing)派工(Dispatching)控制(Controlling)赶工(Expediting) “调度”是作业计划编制后实施生产控制所采取的一切行动，“编制作业计划”是加工制造发生之前的活动 “机器”，可以是工厂里的各种机床，也可以是维修工人；可以是轮船要停靠的码头，也可以是电子的计算机中央处理单元、存贮器和输入、输出单元。一句话，表示“服务者” “零件”代表“服务对象”。零件可以是单个零件，也可以是一批相同的零件 “加工路线”是零件加工的工艺过程决定的，它是零件加工在技术上的约束 “加工顺序”则表示每台机器加工n个零件的先后顺序，是排序和编制作业计划要解决的问题11.1.2假设条件与符号说明为了便于分析研究，有必要做以下假设和符号说明1）一个工件不能同时在几台不同的机器上加工2）工件在加工过程中采取平行移动方式，即当上道工序完工后，立即送下道工序加工3）不允许中断。当一个工件一旦开始加工，必须一直进行到完工，不得中途停止加入其它工件。4）每道工序只在一台机器上完成5）工件数、机器数和加工时间已知，加工时间与加工顺序无关。6）每台机器同时只能加工一个工件。部分符号：Ji工件i，i1，2，nMj机器j，j1，2，mpijJi在Mj上的加工时间，Ji的总加工时间为PipijCmax最长完工时间，Cmaxmax Ci Fmax最长流程时间，Fmaxmax Fi Lmax最长延迟时间，Lmaxmax Li 11.1.3排序问题的分类和表示法排序问题，按照机器、工件和目标函数的特征等，可以进行很多的分类，在我们的课程中我们要求掌握流水作业排序问题中的最长流程时间最短的计算和单件作业排序问题 （多机排序又按加工路线的特征分为：单件作业排序和流水作业排序问题）表示法：康威用4个参数的排序问题表示法： n/m/A/B 其中，n为工件数；m为机器数； A为车间类型，有“F”类，“P”类，“G”类等。F表示流水作业排序问题（工件在不同机器上的加工顺序不一致），P表示流水作业排列排序问题（即所有工件在各台机器上的加工顺序都相同的情况），G表示一般单件作业排序问题；B为目标函数，通常是使其值最小11.2 流水作业排序问题流水车间(Flow shop):工件的加工路线都一致，典型的如流水线11.2.1 最长流程时间的计算 11.2.2 两台机器排序问题的最优算法 11.2.3 多台机器排序问题的启发式算法11.2.4 相同零件、不同移动方式下加工周期的计算11.2.1 最长流程时间Fmax（又称加工周期）的计算 最长流程时间Fmax（又称加工周期）是从第一个工件在第一台机器开始加工时算起，到最后一个工件在最后一台机器上完成加工时为止所经过的时间。例子 见课本P301例11.1：有一个6/4/p/Fmax问题，其加工时间如下表，当按顺序S（6，1，5，2，4，3）加工时，求Fmax。11.2.2 n/2/F/Fmax （两台机器流水作业排序）问题的最优算法 当机器数是2的时候，每个工件都从M1M2的顺序加工，也就是n/2/F/Fmax问题。对于这个问题，SMJohnson于1954年提出了一个有效的算法，也就是现在著名的Johnson算法。 约翰森法则：如果Min(ai, bj) pim 则按pim不增的顺序排成一个序列Sb;3）顺序（Sa,C,Sb）即为所求顺序。 CDS法（Johnson算法的扩展应用）11.2.4 相同零件不同移动方式下加工周期的计算 当n个零件相同，则无排序问题。但不同移动方式下的加工周期不同 三种典型的移动方式顺序移动方式：一批零件全部加工完成后，整批移动到下道工序加工平行移动方式：单个零件加工完成后，立即移动到下道工序加工平行顺序移动方式：两者混合 顺序移动方式设零件批量为n（件），工序数目为m，一批零件不计算工序间运输时间，只考虑加工时间，设其加工的周期为T（分钟），零件在i道工序的单件工时为 （分钟/件），i=1.2n. 则该批零件的加工周期为： 例子 见课本P306例11.4 平行移动方式零件平行移动的加工周期为： 例子 见课本P307例11.4 平行顺序移动方式特点：既保持一批零件顺序加工，有尽可能使相邻工序加工时间平行进行。具体做法：1） 当titi+1时，零件按平行移动方式转移；2） 当titi+1时，以i工序最后一个零件的完工时间按为基准，往前推移（n-1） ti+1作为零件在（i+1）工序的开始加工时间。平行顺序移动加工周期计算 例子 见课本P307例11.411.3 单件作业排序问题11.3.1 问题的描述11.3.2 两种作业计划的构成11.3.3 求解一般n/m/G/Fmax问题的启发式方法11.3.1 问题的描述 每一个工件都有自己的加工路线，对每个工件都要进行单独的排序的问题。 很多的工件同时在分别在不同的机器上进行各工序的加工。 那么，单件作业排序问题就涉及到三个参数：i，j，k。i表示工件号，j表示工序号，k表示机器号，是指完成工件i的第j道工序的机器代号为k。例如，（1，1，1）表示工件1，在第1道工序，在M1上加工。(工件、工序、机器) 加工描述矩阵D描述所有工件的加工（每一行描述一个工件的加工，每一列的工序序号相同），与加工时间矩阵T对应D=1,1,1 1,2,3 1,3,22,1,3 2,2,1 2,3,2 T=2 4 13 4 511.3.2 两种作业计划的构成l 单件作业排序问题中，有2个重要的作业计划，即：能动作业计划和无延迟作业计划。 能动作业计划：各工序都按最早可能开（完）工时间来安排；并且保证任何一台机器的每段空闲时间都不足以加工一道可加工工序的作业计划。 无延迟作业计划：各工序都按最早可能开（完）工时间来安排；并且保证有工件等待加工时，没有任何一台机器有空闲时间的作业计划。l 符号说明：每安排一道工序称为一“步”St:t步之前已排序工序构成的部分作业计划；Ot:t步可排序工序的集合；Tk为Ot中工序Ok的最早可能开始时间；Tk为Ot中工序Ok的最早可能完成时间。 l 能动作业计划的构成步骤（1）设t=1,S1为空集，O1为各工件第一道工序的集合。（2）求T* = minTk,并求出T*所出现的机器M*。如果M*有多台，则任选一台。（3）从Ot中选出满足以下两个条件的工序Oj：需要M*加工，且Tj T* 。（4）将选定的工序Oj放入St,从Ot中消去Oj,并将Oj的紧后工序放入Ot ，使t=t+1.（5）若还有未安排的工序，转步骤（2）；否则，停止。例子见课本P310例11.5l 无延迟作业计划的构成步骤（1）设t=1,S1为空集，O1为各工件第一道工序的集合。（2）求T* = minTk,并求出T*所出现的机器M*。如果M*有多台，则任选一台。（3）从Ot中选出满足以下两个条件的工序Oj：需要M*加工，且Tj=T* 。（4）将选定的工序Oj放入St,从Ot中消去Oj,并将Oj的紧后工序放入Ot ，使t=t+1.（5）若还有未安排的工序，转步骤（2）；否则，停止。例子见课本P312表11-10和图11-511.3.3 三类启发式算法（1）优先调度法则 构成两种作业计划的第（3）步一般都有多道工序可以满足，按不同的优先调度法则来选择工序，可以得出满足不同目标函数的作业计划 计算量小 已经提出100多种优先调度法则常用的优先调度法则：FCFS（first come, first served）选择最早进入可排序集合的工序SPT( shortest processing time）选择加工时间最短的工序EDD（earliest due date）选择完工期限最紧的工序SCR(smallest critical ratio)选择临界比最小的工件MWKR(most work remaining)选择余下加工时间最长的工件LWKR(least work remaining)选择余下加工时间最短的工件MOPNR(most operations remaining)选择余下工序数最多的工件RANDOM 随机挑选一个工件Rush 即紧急订单或重要顾客优先（2）随机抽样法 从全部能动计划或无延迟计划中随机抽样，得出多个作业计划，从中取优。 一般，随机抽样法比用优先调度法则得到的结果要好一些（3）概率调度法 将优先调度法则与随机抽样法结合 对不同工件将优先调度法则分配不同的挑选概率，效果较随机抽样法好11.4 生产作业控制11.4.1实行生产作业控制的原因和条件11.4.2不同生产类型生产控制的特点11.4.3利用“漏斗模型”进行生产控制11.4.1实行生产作业控制的原因和条件l 实行生产作业控制的原因生产计划在实施的时候容易出现一些偏离，一般是以下的原因： 加工时间估计不准确 随机因素影响 加工路线的多样性 企业环境的动态性当实际情况和计划出现偏离，就要采取措施，也就是控制问题。l 实施控制的3个条件： 要有一个标准 要取得实际生产进度与计划偏离的信息 要能采取纠正偏差的行动l 生产作业控制的程序 制定生产作业监控体系 监控实际生产过程 评估偏差情况 采取纠偏措施l 生产作业控制的功能 为每个车间的工单指派优先级 维护车间在制品数量 将车间工单信息传送到相应办公室 提供实际产出数据来为能力控制服务 根据车间工单对机位的要求，为在制品库存管理提供数量信息 测量人员和设备的效率、利用率和产量。l 生产作业控制的主要工具实际生产中，有不少工具可以用来进行生产作业控制，这些工具容易通过运用适当的软件来生成，主要包括：1) 调度单2) 日报、月报3) 例外报告、异常报告4) 输入/输出（Input/output control，I/O）报告11.4.2不同生产类型生产控制的特点l 工件生产的提前期可以分成5个部分：移动时间、排队时间、调整准备时间、加工时间、等待运输时间。l 单件小批量生产的工件，排队时间是主要的，所以，控制的主要问题就是排队的问题。具体的调节方法通过调节输入/输出，“漏斗模型”能很好地解释这一控制方法。l 大量大批生产，流水线是自动的，就没有排队的问题；一般是通过改变工作班次，调整工作时间、调整工人数量等来控制产量。11.4.3利用“漏斗模型”进行生产控制l 模型介绍 德国汉诺威大学的Bechte和Wiendall等人于20世纪80年代初在实施输入/输出控制时提出了漏斗模型（Funnel Model）。 漏斗模型的基本原则：工作中心的输入永远不能超过工作中心的输出。当工作中心的输入超过输出，就会拖欠订单，结果将会出现作业推迟、客户不满、下游作业或相关作业的延期。l 控制规则在一段较长的时间内（如数周）内，若工况稳定，输入输出两条曲线可以近似地用两条直线来表示，其斜率（平均生产率）等于平均在制品库存/平均通过时间实际实践中，可以采用四个规则来调整输入、输出、在制品库存和通过时间： 若希望保持在制品库存量，可暂时增加或减少输