大学精品课件：现代制造系统(v4.1)11A 高级计划.ppt

1、现代制造系统,第11章 现代制造系统的控制（1） 东北大学秦皇岛分校 黄亮 n-xyz,第11章 现代制造系统的控制,控制与设计都是制造系统的综合问题， 区别在于设计决定的方案通常都有长期遵守，属于长期决策问题； 而控制给出的措施通常只在中短期应用，并且还要随着实际生产情况的变化随时调整。 进一步细分，中期控制问题通常称为生产计划，而短期控制问题通常称为生产调度。 为了避免与之前课程的重复，本课程从生产计划和调度问题的高级扩展与高级求解两方面进行介绍。,第11章 现代制造系统的控制 11.1 高级生产计划 11.2 高级生产调度,回顾，生产计划的层次划分？ 尽管不同企业、甚至不同文献给出划分都

2、不一致，但按照其计划的对象大体可划分成三个层次： （1）主生产计划（master production schedule，MPS），计划对象为产品， 制定部门为经营部门或主生产会， 执行部门为整个企业， 计划期间为1-3年，计划期别为季度、半年或年。,11.1 高级生产计划,生产计划的层次划分： （2）物料需求计划（material requirement planning，MRP），计划对象为部件、零件或原料， 制定部门为企业计划部门，执行部门为车间， 计划期间为1-3月，计划期别为旬、半月或月。 （3）能力需求计划（capacity requirement planning，CRP），计划

3、对象为工序， 制定部门为车间计划部门， 执行部门为工段、工作中心或班组， 计划期间为1月，计划期别为周或旬。 生产调度可以看成是第4个层次的计划。,除了上述层次划分外，企业在实际生产中出现的各种计划名词非常多，主要有 产品研发计划、市场开拓计划、技术改进计划、销售计划、资金计划、利润计划等，都属于企业的长期发展战略，在主生产计划层之上，为企业的经营决策部门所制定。有时为了方便区分，也将上述计划称为规划。 产品装配计划（final assembly schedule，FAS），通常比主生产计划更细致一些，计划期间和期别类似于物料需求计划。 采购计划、库存计划、厂级作业计划，属于物料需求计划层次，

4、为不同部门的不同习惯叫法。 粗能力计划（rough cut capacity planning，RCCP），仅考虑能力需求，还没有根据负荷现状进行调节的计划，为能力需求计划的准备阶段。 车间作业计划，通常指能力需求计划或生产调度。,生产计划的通用描述形式： 一定种类、数量的任务（产品、部件、零件或工序） 在什么时间段内（年、季度、月、半月、旬或周） 在什么地点（企业、车间、制造单元或工作中心）生产。,生产计划的样式举例 某装配车间某月的物料需求计划：,生产计划的形象理解： 生产计划问题=将石块装进罐子。 “罐子”指按时间和空间划分的可选项； “石块”为一批待生产的产品。,生产计划问题的优化目标

5、： 首先，不要让“罐子”溢出， 溢出意味通过正常生产方式不能完成计划，要通过一些措施临时增加生产能力。 这些临时措施主要有 （1）加班，需要支付额外的薪水； （2）临时外协，需要给外协厂一定的利润。 由于上述临时措施通常要比正常生产方式成本更高。因此要尽量避免临时增加生产能力，以降低成本。,生产计划问题的优化目标： 其次，不要让“罐子”装不满， 装不满意味着存在闲置生产能力。这会导致企业在一段期间内生产的产品数量减少，而期间成本不变，从而间接导致单位产品成本上升。 总之，生产计划是在满足订单要求的情况下，尽量给每个部门每个期间（“罐子”）安排满生产任务（“石块”），尽量减少能力闲置，同时也要尽

6、量减少加班或外协生产。,生产计划问题的扩展问题： 除了上述生产计划问题的传统优化目标，对于一些特定的企业，可能还要特殊的要求，这可称为生产计划问题的扩展问题。 例如，对于有的车间（多为生产线的形式），需要花费一定的时间才能切换所生产的产品。因此，一段时间内计划规定生产的产品种类越少越好，即在每个“罐子”中所装的“石头”类型越一致越好。 为了与传统生产计划问题区分，当生产计划考虑扩展优化目标或存在扩展约束时，可称为高级生产计划问题。,高级生产计划问题举例： 扩展问题1： 假如两种设备完成单件产品的费用不同。 是让便宜的设备加班完成任务？ 还是让贵的设备正常生产完成任务？ 扩展问题2： 假如外协单

7、件成本比加班单件成本低， 但外协有最小批量限制。 负荷超出标准能力时，是外协还是加班？,高级生产计划问题举例： 扩展问题3： 假如某些任务可以拆分成2个小任务， 拆分任务后方便分配，能够避免加班或外协， 但是需要额外支付批次成本，是否应该拆分？ 扩展问题4和5： 假如有些任务要求必须上半月完成。 假如有些任务要求必须在其它某个任务前完成。 应如何分配？,生产计划问题的求解方法： 若只追求传统上的生产计划优化目标，并且生产批量较小（即“石块”较碎），则生产计划可转化成线性规划问题，使用单纯形等方法求解； 若生产批量较大，则为整数规划问题，规模不大时可采用分支定界法等方法求解； 但当问题规模过大，

8、或者额外考虑了一些扩展的优化目标，则传统的数学规划方法可能难以求解，这时通常采用遗传、模拟退火等智能搜索算法近似求解。,高级生产计划与排程 （advanced planning and scheduling，APS） 或译作高级生产计划与排产、高级生产计划与调度，指一种应用先进技术解决复杂生产计划问题的软件系统。 所谓“复杂”通常指额外考虑了扩展优化目标的大规模生产计划问题； 所谓“先进技术”主要指智能搜索算法，也包括应用先进制造模式和生产过程模型等方面。 APS可以是企业资源计划（ERP）或制造执行系统（MES）的一部分，若单独作为一个系统，其层次通常位于两者之间，主要为企业的生产计划部门所

9、使用。,生产计划问题的求解： 高级生产计划问题或规模较大的传统生产计划问题都可能需要使用智能搜索算法进行近似求解。 区别于传统数学规划方法的智能搜索算法求解方法可称为生产计划问题的高级求解。 本节以最常见的智能搜索算法遗传算法为例，介绍智能搜索算法在高级生产计划问题中的应用。,案例1，高级生产计划问题的遗传算法求解： 某装配车间有A和B两个工段。,案例1，继续： A工段所对应的零件族简记作零件族A； B工段所对应的零件族简记作零件族B； 此外，还有一些零件与工段不存在严格的对应关系，而是根据负荷临时分配，简记作零件族C。 回顾第4.1节中准成组单元的概念。,案例1，继续： 该车间每月生产什么种

10、类各多少数量的零件，由企业的计划部门确定（已知信息）。 根据企业计划部门的计划，车间内部每个工段下半月和下半月分别生产什么种类多少数量的零件，由车间计划员决定（决策变量）。 本案例中，该车间每月的生产计划存在2个时间段和2个空间分段，故存在4个“待装罐子”。,案例1，继续： 假设某月该车间有10批零件加工任务： 出于经济加工批量等方面的考虑，这些任务都不可拆分，即存在10个待装入罐子的东西。,案例1，继续： 假设该车间所有零件单件所需生产能力相同， 工段A每半个月能生产零件50件， 工段B每半个月能生产零件60件。 超出上述部分需要加班完成，并支付额外的加班成本。 标准生产能力（件）,案例1，

11、继续： 本案例生产计划的评价标准初始为100分， 由于加班会产生额外的成本， 所以每加班生产10件零件扣5分； 能力闲置会造成固定成本的浪费， 所以每闲置10件零件的能力扣2分， 一个时间段生产不同种类的零件需要切换生产线，所以若一个时间段内只生产1种零件不扣分，每多生产一种扣1分。跨时间段切换零件不扣分。 在实际生产中，以上打分标准来源于详细的成本核算数据。,案例1，继续：某个的生产计划， 表中1(A30)表示1号任务，其生产零件族A的零件的30个。其它标识的含义以此类推。 此计划打分为：工段B上半月加班扣5分，工段B下半月闲置扣2分，各工段各时段换线各扣1分，合计扣4分，最终得分为100-

12、5-2-4=89分。,案例1，继续：另一个更好的生产计划， 注：蓝色为经过调整的任务。 此计划打分为：无加班不扣分，无闲置不扣分，工段A各时段换线各扣1分，合计扣2分，工段B时段内无换线，不扣分，最终得分为100-2=98分。,案例1，继续：总共有多少种计划？ 本案例中， 对于1至5号任务，与工段之间存在严格的对应关系，只有上或下半月两个时间段可选择，即只存在2种选择； 对于6至10号任务，即可选择A或B两个工段，又可选择上或下两个时间段，即存在4种选择。 综合考虑上述情况， 各种选择进行组合后共存在32768种计划。,高级生产计划的优化方法： 组合问题通过求解空间巨大，难以枚举。 除少数可用

13、数学规划方法处理外， 高级生产计划由于约束较多， 通常使用启发式或亚启发式方法直接求解。 方法1，一种启发式算法： 第一步，给待分配的任务排序。 参考原则1：先选能力需求大的任务， 例如优先选择生产50个C零件10号任务。 参考原则2：先选分配约束严格的任务， 例如对于3号和9号任务，优先选择3号任务。,第一步，给待分配的任务排序。 根据上述两个原则， 本案例任务的选择顺序建议如下：,第二步，指定各个任务的工段和加工时间。 参考原则1：优先分配给剩余能力较多的时间段。 参考原则2：尽量将任务安排在靠前的时间段。 参考原则3：保持同一时间段内的零件种类一致。 例如，首先10号任务分配给工段B的上

14、半月， 其次1号任务分配给工段A的上半月， 再次2号任务分配给工段A的下半月， 再次3号任务分配给工段B的下半月。,方法1，一种启发式算法。 重复上述两个步骤直到全部任务分配完成， 可获得近优的生产计划。 注1：每一步中的两个原则出现矛盾时，可优先遵守主要原则，再遵守次要原则，或两原则加权综合评价。原则的主次关系或权值根据实际情况拟定。 注2：上述原则只是参考，还存在其它启发式原则。,高级生产计划的优化方法： 对于复杂问题， 启发式算法的求解质量可能不能令人满意。 亚启发式算法的求解质量可能会更好， 但所花费求解时间明显增加。 方法2，一种亚启发式算法遗传算法。 第一步，产生初始解的种群。 随

15、机产生或用启发式算法产生， 例如，本案例随机产生3个初始计划解。,第二步，对初始解进行编码。 存在多种编码方式。 本案例采用直接编码方式， 编码有10位（10个任务）， 每位编码有2或4个选择（表示不同的时间段）。 编码符号与所表示的时间段的对应关系为：,初始解1的编码（2,2,3,4,4,3,1,2,1,3），得70分。 初始解2的编码（2,2,4,4,4,1,1,3,4,3），得78分。 初始解3的编码（1,2,1,4,3,2,2,4,1,3），得74分。,第三步，计算适应度。 适应度即为解所对应目标函数值的好坏。 本案例中，初始解1的得分为70， 初始解2的得分为78，初始解2的得分为7

16、4。 这个评分可当作适应度。 注：适应度计算方法有很多， 本案例仅是其中一种。,第四步，从种群中选择2个解（选择算子）。 选择算子有很多种， 本案例使用最常见的轮盘赌策略。,轮盘赌策略： 根据3个解的适应度决定其所占轮盘比例。 由于3个解合计打分为70+78+74=222分，则产生一个1至222的随机数，根据随机数所在轮盘位置选择1个解。,轮盘赌策略： 设首次产生的随机数是91， 则根据轮盘位置，选择2号解。,轮盘赌策略： 然后，去除所选择的2号解，重新划分轮盘。 此时所剩2个解合计打分为70+74=144分，则再产生一个1至125的随机数，根据随机数所在轮盘位置选择另1个解。,轮盘赌策略：

17、设这次产生的随机数是65， 根据轮盘位置，选择1号解。,本案例首轮最终选择的是2号解和1号解。 轮盘赌策略总结： （1）选择算子优先选择适应度较好的解， 目的在于保留优秀的基因。 （2）同时选择算子具有一定的随机性， 不总是选择最好的解， 目的在于扩展基因范围。,第五步，随机交换所选解的部分基因（交叉算子）。 交叉系数=交叉位占全部位的比例。 本案例固定交叉系数设为0.1， 基因编码总共10位，因此每次随机选择1位交叉。 交叉的目的： 将两个较优秀解进行组合，尝试找到更好的解。 交叉的原理： 根据连续性假设，优秀解的邻接解很大可能也是优秀解，而交叉后的解属于邻接解。 在不同解之间交换编码称为交

18、叉，而同一解内部交换编码的顺序称为倒位；由于编码形式的限制，本案例不适合进行倒位运算。,本案例中的交叉计算： 1号解编码为（2,2,3,4,4,3,1,2,1,3）； 2号解编码为（2,2,4,4,4,1,1,3,4,3）。 产生一个1至10的随机数，本次为3， 则交换第3位，得到2个新的基因编码为 （2,2,4,4,4,3,1,2,1,3）、 （2,2,3,4,4,1,1,3,4,3）。,第六步，随机改变解的部分基因（变异算子）。 变异系数=变异位占全部位的比例。 本案例固定变异系数为0.2， 基因编码总共10位，每次随机选择2位变异。 变异范围为原有编码的邻接值。 通常情况下，是对交叉后的

19、解再进行变异操作。 变异的目的： 寻找遗传基因以外的新基因，避免原地踏步。 变异的原理： 根据连续性假设，优秀解的邻接解很大可能也是优秀解，而变异后的解也属于邻接解。,本案例中的变异计算： 经过上一步交叉后的2个解编码为 （2,2,4,4,4,3,1,2,1,3）、 （2,2,3,4,4,1,1,3,4,3）。 产生两个个1至10的随机数，本次为1和7。 在原有编码的邻接范围内随机改变第1位和第7位，得到2个新的基因编码为 （1,2,4,4,4,3,2,2,1,3）、 （3,2,3,4,4,1,2,3,4,3）。,第七步，根据适应度判断是否以新解取代旧解。 对新产生解进行反编码，计算适应度。

20、若新解的适应度优于旧解， 则使用新解取代旧解； 否则， 继续保留旧解。 注意保持种群数量。 本案例对新产生的2个解的反编码结果见下页。 新解1得98分，则取代得70分的1号旧解； 新解2得59分，低于全部旧解，故舍去。,对新产生解进行反编码： 对于新解1的编码（1,2,4,4,4,3,2,2,1,3）， 反编码成生产计划如下，得98分。 对于新解2的编码（3,2,3,4,4,1,2,3,4,3）， 反编码成生产计划如下，得59分。,第八步，检验是否达到结束条件。 结束条件可为： （1）固定遗传若干次， 例如本案例计划遗传100次。 （2）当连续若干次没有更好的解时结束。 还存在其它结束条件。

21、如果达到结束条件， 则结束循环， 选择此时种群中的最优解作为最终方案； 否则， 回到第四步选择算子，重复上述过程。,本案例仅有3万多种可选计划，故使用简单的遗传算法进行几百至几千次迭代搜索往往就能找到一个较好的计划方案。 而在实际生产中，同时要分配的任务往往有几百个，而可分配的时间段也经常有十几个，其组合出的可选方案集合，称为状态空间，也是搜索空间，是十分庞大的。 例如20个任务分给10个时间段就会产生1020大小的搜索空间，即使计算机每秒搜索10000个方案也会需要约3亿年。,对于这种搜索空间随问题规模（任务数和时间段数）急速增长的大规模问题，即使使用邻域搜索类算法也很难找到接近最优的结果，

22、现实中往往退而求其次，找到一个可行并且较优秀的方案即可。 相关概念P问题和NP问题： 如果一个问题可以在多项式时间内被判定，就可以被称为是P（polynomial）问题，译作多项式问题。 例如，排序算法中的冒泡法（bubble sort）的算法复杂度为O(n2)。即n个数排序只需搜索和比较n2就可完成，而n2为n的多项式，则该问题属于P问题。,相关概念P问题和NP问题： 有些问题很难找到多项式时间的算法（或许根本不存在），但如果给出该问题的一个答案，我们可以在多项式时间内判断这个答案是否正确，则称这些问题为NP（non-deterministic polynomial）问题，译作非确定多项式问

23、题。 例如，旅行商问题（travel salesman problem，TSP），又译作旅行推销员问题、货郎担问题：假设一个推销员需要从广州出发，经过北京、上海等n个城市，最后返回广州。任意两个城市之间都有飞机直达，但票价不等。假设公司只给报销C元钱，问是否存在一个行程安排，使他能遍历所有城市，而且总路费小于C元？,相关概念P问题和NP问题： 旅行商问题显然是NP问题。因为若给出任意一个行程安排，都可以很容易算出旅行总开销，并判断其是否小于C元。 但是，要想知道一条总路费小于C元的行程是否存在，在最坏情况下，必须检查所有可能的旅行安排！在保证每次都直达的情况下，可选的路径也有 这经常是个天文数

24、字。,旅行商问题是至今仍在研究的一个经典优化问题。,相关概念P问题和NP问题： 1971年，斯蒂文考克（Stephen Cook）给出并证明了一类问题，它具有如下性质： （1）这类问题中任意一个问题至今仍未找到多项式时间的算法； （2）如果这类问题中存在一个问题有多项式时间算法，则这类问题都有多项式时间算法。 若上述问题属于NP问题，这类问题就是所谓的NP完全（NP-complete，NPC）问题，否则称为NP困难（NP-hard，NPH）问题。 目前，很多复杂的生产计划和调度问题以及被证明属于NPC或NPH问题。,相关概念P问题和NP问题： P、NP、NPC和NPH问题的关系如下图所示 斯蒂

25、文考克在1971年还提出了一个猜想。这个猜想可以简单表示为：是否存在一种算法将任何一个NP问题转化成P问题求解，简记作“NP=P？”问题。,相关概念P问题和NP问题： 美国克雷数学研究所（Clay Mathematics Institute, CMI）于2000年5月24日公布了7个数学猜想，被称为千禧年大奖难题（millennium prize problems）, 又称世界七大数学难题。 根据克雷数学研究所订的规则，任何一个猜想的解答，需要发表在具有世界声誉的数学期刊上，并经过两年的验证期，解决者就会被颁发一百万美元奖金。,其中， “NP=P？”位列其中，尽管不断有人声称已证明该问题，但至

26、今尚未有学术界认可的证明过程。,相关概念P问题和NP问题： 如果有人证明了NP=P，那无疑会给优化算法领域带来翻天覆地的变化。以复杂生产计划和调度问题为例的许多难题求解都会得到改进。,2002年，美国某机构对于100位该领域的知名研究者进行调查，61人相信答案是否定的，9个相信答案是肯定的，22个不确定，而8个相信该问题可能和现在所接受的公理独立，所以不可能证明或证否。,总结高级生产计划： 考虑了扩展优化目标的大规模生产计划问题（例如考虑生产的平稳性），或者使用较新方法求解的生产计划问题（例如使用遗传算法求解），都可以成为高级生产计划问题。 由于生产计划问题所给出的结果相对粗糙，求解难度相对生产调度问题较低，所以对生产计划问题的高级扩展或高级求解的研究相对较少，而对生产调度问题的高级扩展和高级求解的研究则较多。,课程要求（11.1）,知道生产计划问题的层次划分，知道各层次计划的计划对象，简单了解各层次计划的制定部门、执行部门、计划期间和计划期别。 简单了解APS的定义（2点）。 简单了解高级生产计划的求解（本节案例1）， 简单了解简单的启发式算法， 理解遗传算法的运算过程。 简单了解P、NP、NPC和NPH问题的定义。,