1、现代制造系统,第6章 制造系统的控制（2） 东北大学秦皇岛分校 黄亮 n-xyz,第6章 制造系统的控制 6.1 高级生产计划 6.2 高级生产调度 6.2.1 生产调度问题的高级扩展 6.2.2 生产调度问题的高级求解,6.2.1 生产调度问题的高级扩展,调度问题的研究领域： 制造系统中的调度，称为生产调度问题，是研究最多的调度问题。 交通系统中的调度，公路、铁路和机场等不同环境下的问题具有不同的特点。 计算机系统中的调度，主要指在合理分配线程在CPU中的处理次序。,生产调度问题的分类： 传统上按所调度的车间类型划分，分为 流水车间调度问题和作业车间调度问题。 也可按设备数量和关联划分，分为
2、 单机问题、多机问题和并行机问题等。 通常将作业和设备数量都大于10的调度问题称为大规模调度问题；也有的文献将这一标准提高到大于50个作业并且大于20台设备。,生产调度与生产计划的关系： 生产调度可看做是第4个层次的计划。 其计划对象是作业（一个或一批相同零件的一道工序），制定部门为车间，执行部门为车间所辖的工作中心或制造单元，有时是具体设备，计划期间通常不超过1周。 与生产计划的表达形式不同，生产调度给出的结果不以计划期别的形式表达，而是直接给出作业的生产顺序，因此也称为生产排产或生产排程问题。,我们经常使用甘特图（Gantt chart）来表达生产调度的结果： 其横坐标表示时间，纵坐标表示
3、不同的工作中心或设备，以各种颜色的横线表示不同工件的各道工序。有的地方也将其称为横道图或条状图（bar chart）。,调度问题中的习惯用语： 一个工件的一道工序称为作业（job）， 一个工件的全部工序称为任务（task）。,有时我们还使用双代号活动网络图形式的有向图来表达生产调度的结果： 以结点表示作业的开始和结束状态，以有向弧表示作业以及作业之间的制约关系。 在调度领域，这种有向图通常被称为析取图（disjunctive graph）。,相关概念图论： 图论（graph theory）是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来
4、描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 图论在多个科学领域都有广泛的应用，也是制造系统的建模、分析与优化领域所依据的重要理论体系之一。 第4.2.2.4节中活动网络图中的邻接矩阵和可达矩阵的计算方法，即为图论中的知识。,相关概念图论： 图论的起源于数学家欧拉（Euler）1736年的哥尼斯堡（Konigsberg）之行。,欧拉在哥尼斯堡发现当地的市民正从事一项非常有趣的消遣活动。哥尼斯堡城中有一条河流横经其中，这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。这就是著名的七桥问题。 欧拉
5、将七桥问题转化成图形表达的数学问题，并证明上述任务不可能完成。,相关概念图论： 在七桥问题的研究过程中，欧拉不仅圆满地回答了哥尼斯堡居民提出的问题，而且得到并证明了更为广泛的有关一笔画的三条结论，人们通常称之为“欧拉定理”。,凡是由偶点组成的连通图，一定可以一笔画成。画时可以把任一偶点为起点，最后一定能以这个点为终点画完此图。 凡是只有两个奇点的连通图（其余都为偶点），一定可以一笔画成。画时必须把一个奇点为起点，另一个奇点为终点。 其他情况的图都不能一笔画出。,上述研究提供了一个新的研究方向，开创了一个新的数学分支图论。,狭义上，生产调度的通用描述形式： 已知某段时间内需要完成一定数量的作业（
6、由上级生产计划提供），指明各个设备上哪个作业先做，哪个后做？即作业排序问题。 广义上，生产调度也考虑作业在设备之间的分配问题，成为零件（P）、机床（M）和时间（T）三个维度上的组合问题。,对狭义上的生产调度问题进行各种扩展，形成更复杂的问题都可称为高级生产调度问题。,生产调度问题作为一个极具实际应用价值，并且有学术挑战性的经典问题，目前仍是研究的热点。 当前的研究从多个角度将生产调度问题进行扩展，主要包括以下几个思路： （1）研究特殊生产环境下的调度问题的新特点。例如装配作业车间、可重入作业车间和混流生产线上的调度问题。 （2）将与基本制造过程中的调度问题相关的辅助制造、制造服务以及附属产品制
7、造过程中的调度问题一并考虑，统一优化。 （3）根据生产实际，构造新的目标函数，或加入更多的约束条件。 上述扩展后问题均可称为高级生产调度问题。,特殊环境下出现的新调度问题举例： 混流生产线上所关注的车辆排序问题（car sequencing problem，CSP），其定义为 要求混流生产线上，每s个车辆队列里最多有ri辆车选择i操作，应如何将车辆排序？ 可选操作包括颜色、有无天窗、座椅类型等。,提出这种限制的目的在于让混流生产线针对不同产品的不同设备都有机会“休息一下”，有时间进行更换刀具、补充原料以及设备维护等操作。,可以与基本的调度问题一起优化的问题包括： 工件投放控制问题，也称为负荷控
8、制问题（workload control, WLC）。 看板系统就是一种最简单的负荷控制策略（参考第3.1节）。,较新的研究不满足于根据经验设计固定的最大看板数量，而是根据制造系统的实际负荷动态地调整最大看板数量，因此这种方式被称为可变看板或动态看板。,可以与基本的调度问题一起优化的问题包括： 工艺路线调度问题，通常出现在柔性制造系统（FMS）中（参考第3.4节）； 物料运输调度，包括物流设备的分配和路线的选择； 刀具调度，包括刀具监测、分配，以及刀具运输和装夹能力的分配。 以及其它相关生产资源的调度等等。 上述问题如与基本的调度问题一起考虑，通常被称为是调度问题的子问题。,调度问题的评价标准
9、： （1）某种情况下， 产品的生产供不应求， 生产速度越快越好。 制造系统无需考虑外界订单情况， 称为闭环制造系统。 此时的评价标准为 平均通过时间（mean flow time，MFT）。 通过时间包括直接加工时间和等待时间。,调度问题的评价标准： （2）更一般的情况为， 产品需求由定单决定， 要求保证适度生产速度。 制造系统按时交货即可， 称为开环制造系统。 此时的评价标准为 平均延误时间（mean lateness，ML）。 延误时间为通过时间超出交货期的部分。 以上为基本的评价标准，在一些特殊行业还有扩展的评价标准。应用扩展评价标准的调度问题可称为高级调度问题。,调度问题的扩展评价标准
10、： （3）在某些开环生产系统中， 若产品可提前发货给用户。 则在满足交货不延期的基础上， 还应尽量减少平均通过时间， 降低在制品库存成本。 此时的评价标准为 平均延误时间（ML）与平均通过时间（MFT）的加权求和。,调度问题的扩展评价标准： （4）在某些开环生产系统中， 若成品的库存成本 明显高于原料的成本 （例如食品加工行业）， 同时不允许提前交货。 则在保证不延期的同时， 应尽量避免提前完成。 此时的评价标准为 平均延误时间（ML）与 平均提前时间（mean earliness，ME） 的加权求和。,此外，对调度问题评价标准的扩展主要还体现在 通过加权的方式细致评价不同任务通过时间、延误时
11、间和提前时间的变化带来的成本损失。 以延误时间为例，根据不同合同的规定，不同产品延期交货带来的惩罚也不相同，因此不能以平均延误时间来计量，而改以每个任务延误加权延误时间求和来计量。 同时，一个任务延期带来的惩罚也可能不是沿时间线性增长的，而可能是阶梯增长的，并且有一个最大惩罚值封顶。,除了扩展调度问题的评价标准外，有的研究还通过增加约束条件来扩展调度问题。 例如，考虑工序相关性的调度问题 传统上的工序关系总是描述成一道工序结束后另一道工序才可以开始，而实际生产中存在着更复杂的关系： 一道工序进行到一定程度后，尚未全部完成，后一道工序即可开始，两道工序同时开展。例如某些大型机械的装配。 一道工序
12、完成后，还要经过一段时间，后一道工序才可以开始。例如油漆后需要等待其晾干。,一般调度问题都是以时间相关变量作为评价标准，而一类以质量相关变量为评价标准零件组合问题也属于广义上的调度问题。 该问题一般称为选择装配（selective assembly）问题，或简称为选配问题，或称为分组装配问题。 即在加工精度限制的情况下，通过合理的零件配对，提高装配体的装配精度。,选择装配问题举例： 某采用过盈配合的连接件，其零件由一个轴和一个套组成。 设计尺寸为 轴直径35.01mm， 套直径35.00mm， 过盈量0.01mm。 由于加工设备的精度不够， 加工完成后的零件尺寸普遍存在着一定的误差。,选择装配
13、问题举例： 当存在多组零件时，通过一定的方法进行对轴、套进行重新配对组合，使组合后的过盈量更接近于设计尺寸。,选择装配问题的解法： （1）只有两个尺寸匹配，并且标准唯一时。 采用逆序法，分别计算两个零件的实际尺寸误差对配合尺寸造成的影响，以配合误差计量，包含正负值。 然后一个零件按配合误差从大到小排列，另一个零件按配合误差从小到大排列，按排列顺序一一配对组合。 最终多个装配体的配合尺寸整体上最接近设计值。,举例，3个轴和3个套配合。 轴的设计尺寸为35.01mm，1、2和3号轴的实际尺寸分别为35.012mm, 35.001mm和35.017mm， 其配合误差分别为0.002mm，-0.009
14、mm和0.007mm。3个轴按配合误差从小到大的顺序排列为2号轴、1号轴和3号轴。 套的设计尺寸为35.00mm，1、2和3号套的实际尺寸分别为35.005mm，34.987mm和34.998mm， 其配合误差分别为-0.005mm、0.013mm和0.002mm。3个套按配合误差从大到小的顺序（逆序）排列为2号套、3号套和1号套。 所以配套关系为2号轴配2号套，1号轴配3号套， 3号轴配1号套，最终过盈量的误差为0.004mm，0.004mm和0.002mm。,选择装配问题的解法： （2）两个以上尺寸匹配，并且标准唯一时。 例如，两个齿轮的配合传动，以下三个尺寸应符合条件： 轴间距 = A齿
15、轮分度圆半径（中径） + B齿轮分度圆半径（中径）。,两个以上尺寸匹配，并且标准唯一时的解法： 优先选出配合误差最小的一组零件， 排除掉上述被选出的零件， 在剩余零件中再选出配合误差次小的一组零件， 重复上述步骤直到所有零件被组合完成。 此问题等价于 数学规则问题中的指派问题， 除了枚举法和隐枚举之外， 匈牙利算法是该问题的有效解法。,选择装配问题的解法： （3）两个或两个以上尺寸匹配，标准不唯一时。 例如，内燃机四种零件五个位置的间隙配合。,两个或两个以上尺寸匹配，标准不唯一时的选择装配问题属于复杂的组合优化问题。 此时主要使用近似优化算法求解，包括 启发式算法： 参考原则1，优选选择配合误
16、差较小的组合； 参考原则2，优先满足可行方案较少的标准； 等等。 亚启发式算法： 遗传算法， 模拟退火算法， 等等。,第6章 制造系统的控制 6.1 高级生产计划 6.2 高级生产调度 6.2.1 生产调度问题的高级扩展 6.2.2 生产调度问题的高级求解,6.2.2 生产调度问题的高级求解,大规模生产调度问题是至今尚未能很好解决的经典问题，一些较新的研究都可以称为调度问题的高级求解。主要有以下几个方面： （1）从调度模型简化方面入手，降低问题的求解难度； （2）从优化算法入手，在保证一定速度的前提下提高求解的质量； （3）从调度系统的设计方案入手，通过实际案例训练，逐步提高系统的调度能力。,
17、（1）调度模型的简化。 （1.1）传统调度模型的简化。 传统上直接使用多项式描述调度问题的目标函数和约束条件，尽管多项式模型的描述公式比较简单，但需要通常多步迭代才能计算出某种调度方案的运行结果，当问题规模较大时一样难以求解。 一类研究从时间、设备或工件角度将大规模调度问题分解成若干个小问题分别求解，从而降低求解难度，得到原问题的近优解。 另一类研究将优化问题中的强约束进行松弛，利用拉格朗日乘子将其转移到目标函数中，构成求解起来相对简单的拉格朗日对偶问题，称为拉格朗日松弛法（Lagrangian relaxation）。,对问题进行分解可以极大地提高问题的求解速度： 例如，某日某作业车间需要给
18、在3台设备上调度10个工件，相当于在每台设备上对10个作业进行排序，总方案数为 若计算机一秒钟可以评价1000个方案，那遍历全部方案找到最优方案大概需要1.5亿年。 如果将10个工件强制分解成上午、下午各5个，则总方案数为 虽然搜索空间仍然很大，但比分解前缩小了约6万倍。 对问题进行分解会排除掉一些可行的搜索方案，所以有可能会错过最优解，只能得到近优解。 实际应用时应结合具体问题具体分析，尽量避免优秀的解被排除掉。,（1）调度模型的简化。 （1.2）过程模型的简化。 利用过程模型可以更加细致地描述调度问题，特别是其中的随机性时间参数（参考第4.2节）。 分析类模型可以通过等价化简等手段简化问题
19、的描述，从而减低求解的难度，但其应用范围存在很大的限制。 仿真类模型具有很强大的描述能力，但模拟时间长，不适合与同样需要耗费大量时间的亚启发类算法结合。 最新的研究提供了可以从仿真模型中运行过程中快速提取目标函数近似梯度的方法，与综合梯度策略和进化策略的混合算法结合，可以明显提高问题的求解速度。,（2）调度算法的改进。 除了少数简单的调度问题可以使用数学规划或一些特殊的算法（例如1954年针对双机流水车间提出的Johnson法）求解，大部分复杂调度问题只能通过启发式或亚启发式算法求解。 启发式算法主要包括 调度规则（dispatching rule）和移动瓶颈法（shifting bottle
20、neck procedures，SBP）等。 亚启发式算法主要包括 遗传算法、模拟退火算法、蚁群算法等。,（2）调度算法的改进。 （2.1）调度规则的改进。 调度规则（dispatching rule），也称为优先调度规则、规则调度或基于规则的调度，指通过一定的规则改变等待工件队列中各个工件的排列顺序，从而达到优化调度目标的目的。 注意：调度规则只改变已经位于等待队列中的工件的次序，尚未达到的工件不参与排序，否则可能导致调度死锁。 尽管调度规则的调度效果很不稳定，但由于其非常优秀的计算时间，仍是当前企业实际生产中最常用的调度方法。,调度规则有很多种，1977年学者Panwalkar就总结出11
21、3种基本的调度规则，时至今日，各种文献提出的调度规则更是数不胜数。 目前，最常用的调度规则有 FCFS（first come first server），或称为FIFO（first in first out），先到先服务，无能力进行更细致的调度时采取的简单方法； SPT（shortest processing time），加工时间最短的作业先加工，比较适合以平均通过时间为评价标准的调度问题； EDD（earliest due date），交货期近的任务优先，比较适合以平均误期时间为为评价标准的调度问题； STR（slack time remaining），或称为SLACK，剩余松弛时间少的优先
22、，松弛时间=交货期-当前时刻-任务的剩余工作量，是一种比EDD考虑更周全的规则。,调度规则的最新研究： 一是针对各种扩展调度问题，通过加权等方式不断提出更复杂的调度规则； 二是将基本调度规则进行组合，产生新的组合调度规则。组合的方法有以下几种： 首先是设置主次调度规则，仅当主规则计算两个或两个以上工件的顺序得分出现平局（break ties）的情况下使用次规则计算，并按次规则得分排序； 其次是根据一定的概率随机使用多个调度规则； 最后是根据不同的生产状况（例如设备负荷大或小两种情况，或者平均交货期近或远两种情况等），选择不同的调度规则应对。这种方法是目前研究的主流。,案例1，调度规则的组合应用
23、。 8个作业、一台设备，数据如下： 分别使用最小加工时间（SPT）规则、最早交货期（EDD）规则以及前述两者的组合规则共3种规则进行调度。 实践证明，在有些情况下，由简单调度规则组合产生的组合规则比组合前的简单规则都更有效。,方法1，采用最小加工时间（SPT）规则， 按各任务加工时间的大小，从小大到排序。 利用本规则可实现平均通过时间最小（已有学者证明过），但可能出现延期交货。,平均通过时间：,平均延误时间和最大延误时间：,方法2，采用最早交货期规则(EDD)， 按任务规定的交货期先后，从小到大排序。 可减小交货延误时间，但平均通过时间相对较大，平均在制品数较大。,平均通过时间：,平均延误时间
24、：0,方法3，采用EDD-SPT综合规则， 按EDD规则排序所的方案的基础上，按SPT规则对其调整。在保证不延期的基础上，尽量缩短平均通过时间，减少在制品库存成本。 步骤1，按EDD调度，得初始方案。,步骤2，找出最大流程时间maxFi ; 找出满足条件djmaxFi的任务，当满足条件的任务只有一项时，该任务不调整，当满足条件的任务有多项时，对这些任务按SPT规则调整。,之后，去掉已调整的任务，对剩余任务反复用步骤2直至所有任务调整完。,平均通过时间：,平均延误时间：0,对于复杂的调度问题， 调度规则、移动瓶颈法等启发式算法的求解质量可能不能令人满意， 这时应用亚启发式算法的求解质量可能会更好
25、，但求解所花费时间更长。 案例2，模拟退火算法在调度问题中的应用。 设有10个零件（记有10个任务），每个零件有3道工序（共记30个作业），分别使用3台设备加工，追求平均延误时间最小，求可行且优秀的调度方案。,亚启发算法的应用： 案例2，分析：此问题等价于在3台设备中的每台设备上对10个作业的排序问题，则总方案数为 若计算机一秒钟可以评价1000个方案，那遍历全部方案找到最优方案大概需要1.5亿年。 因此，不能直接枚举，而是使用一定技巧搜索。 应用模拟退火算法求解： 第一步，产生初始解， 随机产生或用启发式算法产生。 例如，本案例使用SPT规则产生初始解。,第二步，对初始解进行编码， 存在多种
26、编码方式，本案例采用直接编码方式。 编码有30位，每10位对应一台设备的排序方案，通过一个10位字符串表达。 例如SPT规则产生的初始解编码前10位为 769512348X，表示设备1上零件的加工顺序为：零件7零件6零件9零件5零件1零件2零件3零件4零件8零件10（标识为X）。 由于存在3台设备，所以初始解共有30位这样的编码，含义以此类推。,第三步,设置算法运行参数。 初始温度： 本算例为1； 最终温度： 本算例为0.3； 冷却率： 本算例为0.9； 冻结限制： 本算例为100。 上述参数主要用于控制算法的循环次数和收敛性。,第三步，设置算法运行参数。 初始温度经过若干次冷却后， 若低于最
27、终温度，则运算结束。 本算例 故需要冷却12次，存在12阶段的温度（包括初始温度，不包括第12次冷却后的温度）， 而每阶段温度下循环次数由冻结限制决定， 则本算例共循环12100=1200次。,第四步，随机改变解的部分编码。 类似于遗传算法的变异算子，每次随机选择相邻的2位编码，然后对换这两位字符的顺序。 例如，前10位编码原为“769512348A”，变异后为“769152348A”，表示设备1上零件5和零件1的加工顺序对调。,变异的原理： 根据连续性假设，优秀解的邻接解很大可能也是优秀解，而变异后的解属于邻接解。,第五步，判断是否接受新解。 若变异后的新解优于原解，则接受新解； 若新解劣于
28、原解， 以一定概率 接受， Z为新解和原解目标函数值差的绝对值，新解越差则接受概率越低。 T为当前温度，因此温度越低接受概率越低。 通过这种方式使该算法有一定概率跳出局部最优。,第六步，降温，判断是否结束。 重复第四和五步， 每循环若干次（由冻结限制决定）， 下降一次温度， 新温度=当前温度冷却率。 若新温度结束温度， 则算法结束； 否则回到第四步。,在模拟退火算法搜索过程中，当前最优解目标函数值的变化情况（此图例中目标函数值为越大越好）。 可以看出，模拟退火算法找到的解的质量是波动地提高。,（2）调度算法的改进。 （2.2）亚启发式算法的改进。 首先是通过反复调试算法参数提供优化算法的性能。
29、例如调节遗传算法中的交叉率和变异率等参数。 其次是将不同的亚启发式算法组合，发挥其各自的优点。例如有的文献提出免疫遗传算法、遗传模拟退火算法等。 最后是将梯度策略与亚启发式算法中的进化策略相结合。如果调度模型能够提供梯度或近似梯度支持，这将成为一个最有前途的研究方向。,（3）调度系统的改进。 改变调度规则或者改变亚启发式算法的参数能够提高调度问题的优化质量，但需要大量的实验来获得经验指导。 因此，调度系统是一个不断完善的系统。 最新的研究引入人工智能领域的方法，通过专家系统或人工神经网络等方法，经过大量实际案例训练系统获得经验、知识，实现调度规则的智能切换和动态组合，以及亚启发式算法参数的智能
30、调节。,某基于多Agent的生产调度系统模型：,课程要求（6.2.1）,简单了解调度问题的研究领域（3个）和分类； 知道生产调度与生产计划的层次关系。 知道生产调度中作业和任务的含义； 知道调度问题的主要表示方法：甘特图、析取图。 简单了解CSP问题的定义； 简单了解调度问题的子问题主要有哪些（4类）。 知道各种情况下调度方案的评价标准（4种）。 知道选择装配的目的和3种问题类型，知道每类问题的求解方法，掌握逆序法。,课程要求（6.2.2）,知道主要的启发式调度算法： 调度规则和移动瓶颈法。 知道4种基本的调度规则： FCFS、SPT、EDD、STR。 知道主要的亚启发调度算法： 遗传算法、模拟退火算法和蚁群算法。 理解模拟退火算法的运算过程。,
