第八章-生产计划与控制PPT_时春明版

,第八章制造业作业计划与控制第一节排序问题的基本概念第二节流水作业生产调度问题第三节成组加工进度计划第四节加工车间的作业计划第五节生产调度算法综述第六节生产作业计划第七节生产作业控制第八节面向负荷的生产控制,第一节排序问题的基本概念一、编制作业计划与排序的关系一般来说，编制作业计划（Scheduling）与排序（Sequencing）不是同义语。排序只是确定工件在机器上的加工顺序，可以通过一组工件的代号的一种排列来表示该组工件的加工顺序。而编制作业计划，则不仅包括确定工件的加工顺序，而且还包括确定机器加工每个工件的开始时间和完成时间。二、假设条件与符号说明(1)误工记数（unitpenality）Uj：如果Cjdj，那么Uj=0；如果Cjdj，那么Uj=1。(2)等待时间（waitingtime）Wjk，是从工件Jj的第（k-1）各工序加工结束（当k=1时是从工件Jj的就绪时间rj）到第k个工序开始加工之间，此工件在等待加工时间。,(3)最大完工时间Cmax=maxCj1jn，最大完工时间又称为加工时间全长（makespan）或时间长度（schedulelength）；(4)最大延迟Lmax=maxLj1jn；(5)最大延误Tmax=maxTj1jn等。(6)平均流程时间。三、排序问题的分类和表示法生产调度系统的分类方法很多，主要有以下几种：1根据加工系统的复杂度，可分为单机、多台并行机、Flow-shop和Job-shop。2根据性能指标，分为基于调度费用和调度性能的指标两大类。3根据生产环境的特点，可将调度问题分为确定性调度和随机性调度问题。4根据作业的加工特点和按工件到达车间的情况不同，可将调度问题分为静态调度和动态调度。,5按目标函数的情况，还可以划分为单目标的排序问题与多目标的排序问题。6按参数的性质，还可以划分为确定型排序问题与随机型排序问题。不同的排序问题可用四参数表示法：n/m/A/B其中，n工件数；m机器数；A车间类型。,第二节流水作业生产调度问题一、单机排序问题（工件排序问题）准备时间与工序顺序无关的单机进度计划。定理8-1对于单机进度计划问题，如从加工时间最短的工件开始顺序排序最短加工时间（SPT）规则，则平均流程时间最小。定理8-2对于单机进度计划问题，如从交货期最短的工件开始顺序进行排序最早交货期（EDD）规则，则最大交货期延迟Lmax或最大交货期延误Tmax最小。定理8-3对于单机进度计划问题，如有Tmax的工件存在，在此条件下，在交货期比尚未排序的所有工件的作业时间之和不小的工件中，将加工时间最大的工件放在最后位置，反复比较，可以得到在Tmax为零的条件下，使最小的最优工件顺序（Smith规则）。,二、流水作业排序问题所有工件在各台机器上的加工顺序都相同的情况就是排列排序问题。（一）最长流程时间Fmax计算流水车间调度问题一般可以描述为个工件在台机器上加工，每个工件需要经过道工序，每道工序要求不同的机器，个工件在台机器上的加工顺序相同。工件在机器上的加工时间是给定的，设n个工件的加工顺序S(S1，S2，Sn)，其中Si为排第i位的加工的工件的代号。Ck(si)表示工件Si在机器Mk上的完工时间，pski表示工件Si在Mk上的加工时间，k1,2，m；i1，2，n，则Cksi可按以下公式计算：C1(si)C1(si-1)+psi1Ck(si)maxC(k1)si，Ck(ski1)psik(k2，3，m；i1，2，n)当ri0，i1，2，n时，FmaxCm(sn),（二）n/2/F/Fmax问题的最优算法Johnson算法：（1）从加工时间矩阵中找出最短的加工时间。（2）若最短的加工时间出现在M1上，则对应的工件尽可能往前排；如最短加工时间出现在M2上，则对应工件尽可能往后排。然后，从加工时间矩阵中划去已排序工件的加工时间。若最短加工时间有多个，则任挑一个。（3）若所有工件都已排序，停止。否则，转步骤（1）。（三）n/3/F/Fmax问题的最优算法至今还没有一个多项式复杂性的全局优化算法，只能对快速求解问题的次优解进行研究。,一般n/m/P/Fmax问题近优解的启发式算法。1Palmer算法1965年，DSPalmer提出按斜度指标排列工件的启发式算法，称之为Palmer算法。工件的斜度指标可按下式计算：ik=1，2，n式中，m为机器数，pik为工件I在Mk上加工的时间。按照个工件i不增的顺序排列工件，可得出令人满意的顺序。2关键工件法关键工件法的步骤取如下：计算每个工件的总加工时间Pipij，找出加工时间最长的工件C（jm），将其作为关键工件。对于余下的工件，若pi1pim，则按pi1不减的顺序排成一个序列Sa；若pi1pim，则按pim不增的顺序排成一个序列Sb。顺序（Sa，C，Sb）即为所求顺序。,3CDS法还有一种启发是算法，就是把Johnson算法用于一般的n/m/P/Fmax问题，得到（m1）个加工顺序，取其中优者。具体的做法是，对加工时间和，l1，2，m1，用Johnso算法求（m1）次加工顺序，取其中最好的结果。4仿约翰逊算法若n个工件均按相同次序经过机器1、2、3，在符合下列条件下，可应用约翰逊算法，其条件为：或两者有一个相符合时即可用约翰逊算法排序。算法步骤如下：第一步，令第二步，将三部机器视为两部机器按约翰逊算法排序。,（四）n/m/F/Fmax问题的最优算法n个工件在m部机器的排序方法，一般采用最小排序系数法，求得近似最优解，其步骤如下：第一步，确定中间机器或中间线。当机器数为奇数时，用标明中间机器；当机器为偶数时，用标明中间线。第二步，计算排序系数Ks。排序系数为某个工件在前半部分机器上的加工时间同在后半部分机器上的加工时间的比值。若机器数为奇数，则中间机器的加工时间平分于前后各半。第三步，按最小排序系数，由小到大进行排序。,（五）Flow-shop调度问题的遗传智能算法（1）编码设计：在Flow-shop调度问题中，用染色体表示工件的加工顺序，第个染色体为VK=1,2,3,4,5，表示五个工件的加工顺序为：j1,j2,j3,j4,j5（2）初始种群的产生:根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。先随机产生一定数目的个体，然后从中挑选最好的个体加入到初始群体中，这种过程不断循环，直到初始群体中的个体数目达到预先确定的规模。采用以上策略就可以产生较好的个体，从而得到比较满意的结果。（3）适应度函数设计：n个工件m台机器的Flow-shop调度问题的适应度取为：,表示个染色体的最大流程时间.,（4）选择操作：选择操作是按适应度在子代种群中选择优良个体的算法，个体适应度越高被选择概率就越大。主要有：适应度比例法(fitnessproportionalmodel)、繁殖池选择法（breedingpoolselection）、最佳个体保存法（elitistmodel）等。这里采用的是适应度比例方法即赌轮选（roulettewheelselection），该方法中个体选择概率与其适应度值成比例。当群体规模为N，个体i的适应度为fi时，个体被选择的概率为,（5）交叉操作:交叉方法是模仿自然生态系统的双亲繁殖机理而获得新个体的方法，它可使亲代不同的个体进行部分基因交换组合产生新的优良个体。交叉概率Pc较大时可以增强算法开辟搜索区域的能力，但会增加优良子代被破坏的可能性。交叉概率较低时又会使搜索陷入迟钝状态，研究结果表明，Pc应取为0.25-1.00之间。为了使子代能自动满足优化问题的约束条件，采用部分匹配交叉（PMX）与顺序交叉（OX）和循环交叉（CX）混合使用的方法来保留双亲染色体中不同方面的特征，达到获得质量较高后代的目的。（6）变异操作：变异的目的是维持解群体的多样性，同时修复和补充选择、交叉过程中丢失的遗传基因，在遗传算法中属于辅助性的搜索操作。变异算子是对个体串中基因座上的基因值作改变，同时为防止群体中重要的基因丢失，变异概率Pm一般不能太大。高频度的变异将导致算法趋于纯粹的随机搜索。这里主要使用互换变异（SWAP）与逆转变异（INV）相结合的方法。,第三节成组加工进度计划一、单机成组加工进度计划定理8-4单机成组加工计划问题，如果从组加工时间最短的组开始顺序排列组的加工顺序，并且在各组按作业时间最短的工件开始顺序排列工件加工顺序，则工件的平均停留时间F小。,二、二级成组加工进度计划步骤1：对于各组内的工件采用约翰逊算法确定工件顺序；步骤2：对于步骤1已确定的工件顺序的各组，按如下方式计算X和Y值；（1）对于各组，用G1从1到其工件数k的各部u值，按下式计算Xu和Yu值；（2）按下式计算X、Y指：式中，pij、qij分别为工件Jij(Gi组第j个工件)的第一工序和第二工序的工件作业时间。步骤3：有步骤2得到的各组X、Y值，分别作为第一工序和第二工序的加工时间，用约翰逊算法确定组加工顺序。,第四节加工车间的作业计划一、一般n/m/P/Fmax问题的启发式算法加工车间作业排序问题。用加工描述矩阵的形式来描述所有工件的加工。加工描述矩阵D的每一行描述一个工件的加工，每一列的工序序号相同。第一行描述工件1的加工，第二行描述工件2的加工。它表明，工件1的第1道工序在M1上进行，第2道工序在M3上进行，第3道工序在M2上进行；工件2的第1道工序在M3上进行，第2道工序在M1上进行，第3道工序在M2上进行。启发式算法是求解一般单件车间排序问题使用最多的方法。,二、两机排序问题定理8-5n2加工车间进度计划问题使总需要时间最小的最优进度计划排序如下：1机械M1上按AB、A、BA的顺序排序；2机械M12上按BA、A、AB的顺序排序；3AB组内的工件，按工艺顺序为M1M2的流水车间型进度计划问题用约翰逊方法排序；4BA组内的工件，按工艺顺序为M2M1的流水车间型进度计划问题用约翰逊方法排序。,三、三机排序问题吉弗劳和汤普森算法，又称为缩小所需总时间和启发式排序法。这种方法是编排与工件数和机器数相应的表格（包括加工顺序和作业时间），排在前面的工件，从最先结束的作业开始；如果结束时间相同，则从工件编号小的开始。在同一机器加工的作业时期内，如有其它工件加工重复时，为了避免重复，则推迟某一个工件的开始时刻。这时，在推迟的那一个工件上，标上计划代号的识别符号，按重复的工件双方情况，编排顺序。每当发生重复就推迟重复工件中的其中一个，先行排序一个，并做上识别记号的计划代号（亦即先行排序的方案）；对推迟的工件，另编上计划代号（即后行排序方案），后续排序。如此反复进行，直到排完全部工件为止，最后从中选出所需时间为最小的排序方法。,四、一般n/m/G/Fmax问题的三类启发式算法1优先调度法则十三个常用的优先调度规则：（1）FCFS（先到先服务）；（2）SOT（最短作业时间）；（3）EDD(Earliestduedate)规则；（4）开始日期；（5）STR（剩余松弛时间）；（6）STR/OP（每个作业剩余的松弛时间）；（7）CR（关键比率，criticalratio）；（8）QR（排队比率，queueratio）；（9）LCFS（后到先服务）；（10）WKR(Mostworkremaining)规则；（11）WKR(Leastworkremaining)规则；（12）MOPNR(Mostoperationsremaining)规则；（13）RANDOM规则。,第五节生产调度算法综述一、生产调度的环境特征生产调度环境的五个特征：（1）边界条件：生产调度通常是在一个有限的时间区域里进行的，系统的最优解（或次优解）亦是在限定的边界范围内来获取。（2）分批大小和调整费用：将任务分成多批进行，并考虑改变已有调度结果所付出的代价（调整费用）。（3）加工路径：在实际生产中，作业的加工路径可能需要动态改变，工艺顺序可能是半有序的(semiorder)。（4）随机事件和扰动：比如，出现关键作业、设备损坏、加工操作失败、原料短缺、加工时间/到达时间/交货期的改变等。（5）性能指标和多目标：追求不同的性能指标往往会得到不同的优化解，同时，系统目标也以多目标为主。,二、调度问题的特点1复杂性；2动态随机性；3多目标。三、调度问题的研究方法1运筹学方法运筹学方法是将生产调度问题简化为数学规划模型，采用基于枚举思想的分枝定界法或动态规划算法进行解决调度最优化或近优化问题，属于精确方法。2基于规则的方法对生产加工任务进行调度的最传统的方法是使用调度规则（Dispatchingrules），已经有许多调度规则被应用，按形式分为三类：简单规则、复合规则、启发式规则。,3系统仿真的方法基于仿真的方法不单纯追求系统的数学模型，侧重对系统中运行的辑关系的描述，能够对生产调度方案进行比较评价，分析系统的动态性能，并选择系统的动态结构参数。4解析模型方法用研究离散事件系统的解析模型和方法去探讨车间调度问题，针对FMS中一类特殊的DEDS，利用了极大代数方法对其进行建模，并进行了系统的稳定性分析。,5基于排序的方法该方法是先有可行性加工顺序，然后才确定每个操作的开工时间，并对这个顺序进行优化，它虽然属于近似算法，但有可能达到最优的调度方案。这类方法包括局部探索（LocalSearch）、模拟退火法（SimulatedAnnealing）、列表寻优法（TableSearch），遗传算法（GeneticAlgorithms）、基于智能的调度方法。五、调度方法存在的问题,第六节生产作业计划生产作业计划是根据年度生产计划规定的产品品种、数量及大致的交货期的要求对每个生产单位（车间、工段、班组等），在每个具体时期（月、旬、班、小时等）内的生产任务做出详细规定，使年度生产计划得到落实。生产作业计划具有三个方面的显著特点：（1）计划期短；（2）计划内容具体；（3）计划单位小。生产作业计划的主要任务包括：生产作业准备的检查；制定期量标准；生产能力的细致核算与平衡。,一、期量标准的制定期量标准，又称作业计划标准。所谓期量标准就是为制造对象（产品、部件、零件等）在生产期限和生产数量方面所规定的标准数据。大量流水生产的期量标准有：节拍、流水线工作指示图表、在制品定额等。成批生产的期量标准有：批量、生产间隔期、生产周期、提前期、在制品定额等。单件生产的期量标准有：产品生产周期、提前期等。,某产品的生产周期产品进度计划典型网络图,钢材准备,焊接生产,焊接工艺,钢材准备,包装发运,装配,冷加工,热加工,热工艺,冷加工工艺,外购件采购,（一）批量和生产间隔期批量就是相同产品（或工件）一次投入和出产的数量。生产间隔期（又称生产重复期），就是前后两批生产（或工件）投入或产出的时间间隔。批量=生产间隔期*平均日产量平均日产量等于计划期产量除以计划期工作日数。（二）生产周期产品的生产周期是指产品从原材料投入生产起，一直到成品出产为止的全部日历时间（或工作日数）。（三）生产提前期定义：指产品（零件）在各生产环节出产（投入）的时间同成品出产时间相比所要提前的时间。提前期可以分为投入提前期和出产提前期。车间投入提前期=本车间出产提前期+本车间生产周期车间出产提前期=后车间投入提前期+保险期,（四）在制品定额指在一定的技术组织条件下，各生产环节上为了保证生产线节所必需的、最低限度的在制品储备量。二、生产作业计划编制方法（一）在制品定额法在制品定额法适用于流水生产或大批大量生产企业的生产作业计划编制方法。按照在制品数量经常保持在定额水平上的要求，来计算各生产环节的投入和生产任务，以保证生产过程连续协调进行。,（二）提前期法提前期法，又称为累计编号法。这种方法适用于成批轮番生产的企业，特别是生产大型高价产品的企业。采用提前期法规定车间任务的具体方法和步骤是：1.计算产品在各车间计划期末应达到的累计生产和投入的号数。计算公式：某车间出产累计号数=成品出产累计号数+该车间出产提前期*成品的平均日常量某车间投入累计号数=成品出产累计号数+该车间投入提前期*成品的平均日常量2.进一步计算各车间在计划期内应完成的出产量和投入量。计算公式：计划出产（投入）量=计划期末出产（投入）累计号数-计划期初已出产（投入）的累计号数3.如果是严格按照批量进行生产的话，则计算出的车间出产量和投入量，还应按各种零件的批量进行修正。,（三）生产周期法此种方法适用于根据订货组织生产的单件小批生产企业。这类企业在编制作业计划时，关键问题是使这一种（或一批）产品在各车间出产和投入时间能够相互衔接起来，保证成品的交货期限。步骤：1.首先，为每一批订货编制一份产品生产周期进度表；2.在此基础上，根据合同规定的交货期限，为每一项订货编制一份订货生产说明书，其中规定该产品以及产品的各成套部件在各车间投入与出产的时间；3.根据订货生产说明书，编制月度作业计划，将计划月份应该投入和产出的部分摘出来按车间归类，并将各批订货的任务汇总起来，这就是计划月份各车间的投入、产出任务。,第七节生产作业控制一、生产作业控制的内容和功能1.主要内容：（1）确定工艺流程，这是生产作业控制的起点和基础。（2）安排生产进度计划，这是生产作业控制的前提。（3）下达生产指令，这是生产作业控制的重要手段。（4）生产进度控制，这是生产作业控制成败的关键。2.功能（1）进度管理。（2）剩余能力管理。（3）实物管理。（4）信息管理。,二、生产作业控制的方法1生产进度控制通常利用坐标图、条形图和倾向分析等工具进行管理和控制。坐标图计划当日产量实际当日产量计划累计产量实际累计产量,条形图,实施生产进度控制应做好以下几个方面：（1）投入进度控制。（2）出产进度控制。（3）工序进度控制2生产均衡性控制按照生产的均衡性，不仅要求企业按时完成任务，而且要求企业每个生产环节和每种产品都能按日、按旬、按月完成生产任务，即实现均衡生产。检查分析生产均衡性常用以下方法：（1）图表法；（2）均衡系数法。3生产成套性控制对于加工装配式企业来说，生产进度控制的另一个重要任务，就是保证零件出厂的成套性。加工装配式企业生产的产品是由许多零部件组装而成的，只有保证成套出产各种零部件，才能按计划使整机产品装配出厂。这种控制模式包括成套性投料控制和成套性出产控制。,（三）生产调度1.任务：以生产作业计划为依据，检查、监督和协助有关部门做好各项生产准备工作，全面掌握生产活动的过程，组织各方面的力量为生产服务，并根据实际情况，灵活机动的组织日常生产，迅速及时的处理生产过程中的各种问题和矛盾，充分利用多余的生产能力，克服薄弱环节，必要时对生产作业计划作适当的调整和补充，从而使各生产各环节能协调的进行，保证生产任务的完成。2.内容：（1）计划开始执行时的生产调度（2）计划执行过程中的生产调度（3）计划期末的生产调度3.原则：（1）计划性原则（2）统一性原则（3）预见性原则（4）及时性原则（5）群众性原则,4.措施（1）建立健全调度工作制度值班；报告；会议；现场办公