生产计划与控制叶春明第八章节

《生产计划与控制叶春明第八章节》由会员分享，可在线阅读，更多相关《生产计划与控制叶春明第八章节（42页珍藏版）》请在金锄头文库上搜索。

1、,第八章 制造业作业计划与控制 第一节 排序问题的基本概念 第二节 流水作业生产调度问题 第三节 成组加工进度计划 第四节 加工车间的作业计划 第五节 生产调度算法综述 第六节 生产作业计划 第七节 生产作业控制 第八节 面向负荷的生产控制,第一节 排序问题的基本概念 一、编制作业计划与排序的关系 一般来说，编制作业计划（Scheduling）与排序（Sequencing）不是 同义语 。排序只是确定工件在机器上的加工顺序，可以通过一组工件的代 号的一种排列来表示该组工件的加工顺序。而编制作业计划，则不仅包括 确定工件的加工顺序，而且还包括确定机器加工每个工件的开始时间和完 成时间。 二、假设

2、条件与符号说明 (1) 误工记数（unit penality）Uj：如果Cj dj ，那么Uj=0；如果 Cj dj ，那么Uj=1。 (2) 等待时间（waiting time）Wjk，是从工件Jj的第（k-1）各工序加工 结束（当k=1时是从工件Jj的就绪时间rj）到第k个工序开始加工之间，此工 件在等待加工时间。,(3)最大完工时间Cmax= maxCj1jn，最大完工时间又称为加工时间 全长（makespan）或时间长度（schedule length）； (4)最大延迟 Lmax= maxLj1jn； (5)最大延误 Tmax= maxTj1jn等。 (6)平均流程时间 。 三、排序

3、问题的分类和表示法 生产调度系统的分类方法很多，主要有以下几种： 1根据加工系统的复杂度，可分为单机、多台并行机、Flow-shop和 Job-shop。 2根据性能指标，分为基于调度费用和调度性能的指标两大类。 3根据生产环境的特点，可将调度问题分为确定性调度和随机性调度问 题。 4根据作业的加工特点和按工件到达车间的情况不同，可将调度问题分 为静态调度和动态调度。,5按目标函数的情况，还可以划分为单目标的排序问题与多目标的排 序问题。 6按参数的性质，还可以划分为确定型排序问题与随机型排序问题。 不同的排序问题可用四参数表示法： n / m / A / B 其中，n工件数； m机器数； A

4、车间类型。,第二节 流水作业生产调度问题 一、单机排序问题（工件排序问题） 准备时间与工序顺序无关的单机进度计划。 定理8-1 对于单机进度计划问题，如从加工时间最短的工件开始顺序排序最短 加工时间（SPT）规则，则平均流程时间最小。 定理8-2 对于单机进度计划问题，如从交货期最短的工件开始顺序进行排序最 早交货期（EDD）规则，则最大交货期延迟Lmax或最大交货期延误Tmax最小。 定理8-3 对于单机进度计划问题，如有Tmax的工件存在，在此条件下，在交 货期比尚未排序的所有工件的作业时间之和不小的工件中，将加工时间最 大的工件放在最后位置，反复比较，可以得到在Tmax为零的条件下，使最

5、小 的最优工件顺序（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)+psi

6、1 Ck(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问题的最优算法 至今还没有一个多项式复杂

7、性的全局优化算法，只能对快速求解问题 的次优解进行研究。,一般n / m / P / Fmax问题近优解的启发式算法。 1Palmer算法 1965年，DSPalmer提出按斜度指标排列工件的启发式算法，称之为 Palmer算法。工件的斜度指标可按下式计算： i k=1，2，n 式中，m为机器数，pik为工件I在Mk上加工的时间。按照个工件i不增的 顺序排列工件，可得出令人满意的顺序。 2关键工件法 关键工件法的步骤取如下： 计算每个工件的总加工时间Pi pij，找出加工时间最长的工件C （jm），将其作为关键工件。 对于余下的工件，若pi1pim，则按pi1不减的顺序排成一个序列Sa；若 p

8、i1pim，则按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 / Fm

9、ax问题的最优算法 n个工件在m部机器的排序方法，一般采用最小排序系数法，求得近似最 优解，其步骤如下： 第一步，确定中间机器或中间线。当机器数为奇数时，用标明中间机 器；当机器为偶数时，用 标明中间线。 第二步，计算排序系数Ks。排序系数为某个工件在前半部分机器上的加 工时间同在后半部分机器上的加工时间的比值。 若机器数为奇数，则中间机器的加工时间平分于前后各半。 第三步，按最小排序系数，由小到大进行排序。,（五）Flow-shop调度问题的遗传智能算法 （1）编码设计：在Flow-shop调度问题中，用染色体表示工件的加工顺 序，第个染色体为VK=1,2,3,4,5，表示五个工件的加工顺序

10、为： j1,j2,j3,j4,j5 （2）初始种群的产生: 根据问题固有知识，设法把握最优解所占空间在整个问题空 间中的分布范围，然后，在此分布范围内设定初始群体。 先随机产生一定数目的个体，然后从中挑选最好的个体加入 到初始群体中，这种过程不断循环，直到初始群体中的个体数目达 到预先确定的规模。采用以上策略就可以产生较好的个体，从而得 到比较满意的结果。 （3）适应度函数设计： n个工件m台机器的Flow-shop调度问题的适应度取为： , 表示个染色体的最大流程时间.,（4）选择操作： 选择操作是按适应度在子代种群中选择优良个体的算法，个体适应度 越高被选择概率就越大。主要有：适应度比例法

11、(fitnessproportional model)、繁殖池选择法（breeding pool selection）、最佳个体保存法 （elitist model）等。这里采用的是适应度比例方法即赌轮选（roulette wheel selection），该方法中个体选择概率与其适应度值成比例。当 群体规模为N，个体i的适应度为fi时，个体被选择的概率为,（5）交叉操作: 交叉方法是模仿自然生态系统的双亲繁殖机理而获得新个体的方法， 它可使亲代不同的个体进行部分基因交换组合产生新的优良个体。交叉概 率Pc较大时可以增强算法开辟搜索区域的能力，但会增加优良子代被破坏 的可能性。交叉概率较低时又

12、会使搜索陷入迟钝状态，研究结果表明，Pc 应取为0.25-1.00之间。为了使子代能自动满足优化问题的约束条件，采用 部分匹配交叉（PMX）与顺序交叉（OX）和循环交叉（CX）混合使用的方法 来保留双亲染色体中不同方面的特征，达到获得质量较高后代的目的。 （6）变异操作： 变异的目的是维持解群体的多样性，同时修复和补充选择、交叉过程 中丢失的遗传基因，在遗传算法中属于辅助性的搜索操作。变异算子是对 个体串中基因座上的基因值作改变，同时为防止群体中重要的基因丢失， 变异概率Pm一般不能太大。高频度的变异将导致算法趋于纯粹的随机搜索。 这里主要使用互换变异（SWAP）与逆转变异（INV）相结合的方

13、法。,第三节 成组加工进度计划 一、单机成组加工进度计划 定理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得到

14、的各组X、Y值，分别作为第一工序和第二工序的加 工时间，用约翰逊算法确定组加工顺序。,第四节 加工车间的作业计划 一、一般n / m / P / Fmax问题的启发式算法 加工车间作业排序问题。 用加工描述矩阵的形式来描述所有工件的加工。加工描述矩 阵D的每一行描述一个工件的加工，每一列的工序序号相同。 第一行描述工件1的加工，第二行描述工件2的加工。它表明，工件1的 第1道工序在M1上进行，第2道工序在M3上进行，第3道工序在M2上进行；工 件2的第1道工序在M3上进行，第2道工序在M1上进行，第3道工序在M2上进行。 启发式算法是求解一般单件车间排序问题使用最多的方法。,二、两机排序问题

15、定理8-5 n2加工车间进度计划问题使总需要时间最小的最优进度计划 排序如下： 1机械M1上按AB、A、BA的顺序排序； 2机械M12上按BA、A、AB的顺序排序； 3AB组内的工件，按工艺顺序为M1M2的流水车间型进度计划问题用约 翰逊方法排序； 4BA组内的工件，按工艺顺序为M2M1的流水车间型进度计划问题用约 翰逊方法排序。,三、三机排序问题 吉弗劳和汤普森算法，又称为缩小所需总时间和启发式排序法。 这种方法是编排与工件数和机器数相应的表格（包括加工顺序和作业 时间），排在前面的工件，从最先结束的作业开始；如果结束时间相同， 则从工件编号小的开始。在同一机器加工的作业时期内，如有其它工件加 工重复时，为了避免重复，则推迟某一个工件的开始时刻。这时，在推迟 的那一个工件上，标上计划代号的识别符号，按重复的工件双方情况，编 排顺序。每当发生重复就推迟重复工件中的其中一个，先行排序一个，并 做上识别记号的计划代号（亦即先行排序的方案）；对推迟的工件，另编 上计划代号（即后行排序方案），后续排序。如此反复进行，直到排完全 部工件为止，最后从中选出所需时间为最小的排序方法。,四、一般n / m / G / Fmax问题的三类启发式算法 1优先调度法则 十三个常用的优先调度规则： （1）FCFS（先到先服务） ； （2）SOT（最短作业时间） ； （3）