前言：中文期刊网精心挑选了数学建模启发式算法范文供你参考和学习，希望我们的参考范文能激发你的文章创作灵感，欢迎阅读。
数学建模启发式算法范文1
关键词：需求可拆分车辆路径问题；分支；国内现状
一.引言
传统的VRP一直是网络最优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重大价值，多年以来，受到国内外广泛关注。传统的VRP假定每个客户端的需求只能由一辆车来完成，即需求不可以被拆分，但实际应用中，有可能会存在相当一部分任务点的需求量比较大，此时，如果仍然要求每个客户点只能由一辆车来完成服务，势必会造成车辆的空载率提高，浪费运输资源。1989年Dror & Trudeau首次提出了SDVRP的概念[1]，并指出 SDVRP 是一种约束松弛的 VRP，即每个客户点的需求由传统VRP中的只能由一辆车满足，扩展为可以由多辆车满足，这可使得车辆数量和路线总长得到节约。
二.SDVRP的分类
根据研究重点的不同，SDVRP 有多种分类方式。虽然诸如带时间窗、带集货和配送的VRP在传统VRP问题中已经被大量研究，但是，在SDVRP情况下，仍然会得出一些有意义的结论。根据对国内外文献进行归纳，常见的SDVRP的分支主要有以下几类：
（一）带时间窗限制（SDVRPTW）。
带时间窗限制，意味着订单必须在顾客规定的时间段内到达，带时间窗限制的车辆路径问题（VRPTW）属于传统VRP分支。Archetti et al.提出了第一个求解SDVRPTW的精确算法 [2]。他们运用禁忌搜索算法和新的有效不等式对子问题分别求解，一种新的启发式算法则被用于寻找最优拆分点。实验结果表明，该求解方法对顾客规模为100的SDVRPTW同样具有良好的求解效果。目前，基于禁忌搜索求解SDVRPTW的启发式算法，是由Ho & Haugland提出的[3]，该算法将SDVRPTW的求解规模扩大至100以上。
（二）带集货和配送限制（SDVRPPD）。
在SDVRPPD中，无时间窗和最大车辆路线限制，但每一节点只能被一辆车访问一次，且每一节点可能同时具有收货和配送两种需求，任一节点的需求都可能超过车辆容量。其目标函数是通过最小化车辆使用数目来最小化总运输成本。这一应用在实际生活中非常常见，如快递员在送货的过程中，经常也会收到客户寄送货物的需求.Nowak et al.通过研究证明[3]，在同一地理分布的顾客群下，当订均大小为车载容量一半时，拆分能够获得最大的收益。
（三）利润最大化
一般情况下，SDVRP的目标函数是最小化车辆行驶路线或运输成本，有时也对使用成本进行优化。但是，由于需求可拆分，可能带来额外收益。Brnmo et al.通过数学规划模型并整合分区的方法对此类问题进行求解[3]，结果证明允许拆分可以提高物流企业利润率。
（四）库存和生产
自从供应链管理的观念提出以来，库存路径问题已为很多学者关注。由于库存的概念是基于时间、库存成本以及库存容量之上，时间成为SDVRP中考虑的一个重要因素。在这些问题中，一个顾客通常在特定的时间范围可以被访问多次，但是一个配送日内只能访问一次。同时，库存路径模型还会考虑生产制造策略。
（五）其他
除了以上四种主要的SDVRP分支以外，考虑最小损耗率、混合车辆编队、随机性、需求的离散性以及弧路径的SDVRP分支也逐渐出现在国内外研究中，限于文章篇幅不在此一一赘述。
三.国内研究现状
当前，国内对SDVRP的研究尚不多见。隋露斯，唐加福等用蚁群算法求解SDVRP[4]，给出了基于整数规划的描述方法；通过仿真实验发现，该算法对车辆数目和运输距离的改进显著。鲁强等用遗传算法求解K-SDVRP[5]，数值试验表明，某些条件下，SDVRP较VRP车辆使用数和车辆运输距离更少。孟凡超等通过改进传统的数学模型[6]，建立SDVRP数学模型，利用禁忌搜索算法对SDVRP进行求解。算例结果表明，该模型可以节省车辆数目、缩短路线长度、提高车辆装载率。杨亚璪等等对SDVRPPD进行研究[7]，算例结果表明，所设计的算法可以得到合理的车辆路径，特别当集货需求的总量小于送货需求的总量时，优化效果更好。
无论是使用蚁群算法、禁忌搜索算法还是遗传算法，隋露斯、鲁强、孟凡超以及杨亚璨等人关于可拆分车辆路径问题的研究，都是在需求确定的情况下研究SDVRP，并未考虑客户的时间窗以及需求的随机性。
四.结论
在对SDVRP的主要分支以及常用求解方法进行总结的基础上，我们发现目前对SDVRP的求解方法主要是通过混合整数规划建模并整合精确或者启发式算法对问题进行求解，但随着问题规模的扩大，其求解面临着维数灾难的问题。计算机仿真作为一种新的建模方法，随着计算机技术的发展，使研究者可以通过搜索海量解空间找到问题的次优解或者最优解，为求解SDVRP提供了一种新的解决途径。（作者单位：深圳大学）
参考文献
[1]Dror， M.， Trudeau， P.， 1989. Savings by split delivery routing. Transportation Science 23， 141–145.
[2]Archetti， C.， Bouchard， M.， Desaulniers， G. Enhanced branch-and-price-and-cut for vehicle routing with split deliveries and time windows. Transportation Science.2011.
[3]Archetti C.， M. G. Speranza. Vehicle routing problems with split deliveries. International Transactions in Operational Research. 19（2012）：3-22
[4]隋露斯，唐加福. 用蚁群算法求解需求可拆分车辆路径问题[C]. 中国控制与决策会议. 2008：997-1001
[5]鲁强，唐加福等. 用遗传算法求解可拆分运输的车辆路径问题[C].第二届中国智能计算大会论文集，洛阳，2008年8月3-7日， pp1-5
数学建模启发式算法范文2
【关键词】重心法；P-中值模型；覆盖选址模型；反町氏法
1 物流配送中心选址问题的划分
对于物流配送中心选址问题的划分，较经典的划分方法如下：
1.1 按照设施选址的数量划分，可以将选址问题分为单个设施选址和多个设施选址
1.1.1 单个设施选址问题
单个设施选址是指只建立一个配送中心，由一个配送中心来完成整个配送过程。对于单个设施选址模问题，成本是首要考虑的条件。因为只有一个配送中心，所以管理的成本势必会下降，但是配送中心的工作必然会加重。
1.1.2 多个设施选址问题
对于大部分的企业来说一般需要决定两个或多个的设施的选址，而且它们之间不是相互孤立的，要考虑彼此之间的影响，因此问题的解决就变的相对复杂了。
1.2 按照选址目标区域的特征，可将选址问题分为连续选址、网格选址及离散选址[1]。
1.2.1 连续选址，可选址区域是一个连续的平面，不去过多地考虑其它结构及现实因素，在这个连续的平面中可能的选址位置的数量是无限的[2]。连续选址模型的可选址区域是连续的，因此可以在连续的区域内进行建模求解，一般可以求得最优解。这个问题的缺点是只是简g的进行最优解的求解，而没有考虑现实问题，求解出的地点很可能是并不适合建立物流配送中心的点，如求解出的点很可能就是一片海洋。
1.2.2 网格选址，可选区域是一个平面，这个平面被细分为许多相等面积的区域，通常情况下是被细分为许多面积相等的正方形。可选址的数量通常是有限的，相比连续性选址较少，但是总的来说数量也还是相当大。网格选址存在一个问题，就是进行相关的计算和数据收集的成本较高。
1.2.3 离散选址，可选区域一般是已经给定的几个离散的可选点，它是一个离散的候选位置的集合，可选点的数量较少且是有限的。在选址的前期就已经对可选址的地点进行了初步的确定，也就是缩减了可选点的范围，再在给定的范围内选择较优的可建地址。这个问题优点是前期已经对可选区域进行了筛检，因此后期的计算量较小并且这种模型较切合实际的，这个模型的缺点是需要花费大量的资金进行数据资料的收集。
2 解决选址问题的方法
近年来，物流业迅速发展，无论国内国外都取得了长足的发展，于此同时物流理论也得到了进一步完善，加之信息技术的发展尤其是计算机的使用，对于物流选址方法不断地完善，终结归纳起来大致可以分为如下四种方法[3]：
2.1 专家选择法
专家选择法是由专家进行分析研究，依靠专家自身的知识和经验，对可选址的社会环境和客观背景进行分析评估。它的评定结果更多的会受到专家自身能力的限制，结果的准确性往往会由专家的自身的水平所决定，因此这种方法更具有主观性，带有较浓厚的个人色彩。在专家选择法中，我们经常用到的有因素评分法和德尔菲法。
2.2 解析法
解析法不同于前面所说的专家选择法，解析法更注重精确性，通常是利用客观的数据进行说话。这种方法主要是建立数学模型，并对模型进行求解，根据得到的数据进一步确定物流中心的建设点。模型的建立根据求解目的的不同进行划分，可以分为两类：1）基于成本的模型，2）基于收益的模型。现实生活中我们遇到的物流配送中心的模型建立求解，更多的是基于成本的模型。如较经典模型中的重心法模型、p-中值模型。利用解析法的优点是进行建模求解，利用数据说话，对于选择合适的可选点更有说服力。同样，模型的建立和求解往往并不是那么简单。
2.3 模拟法
模拟方法的兴起和发展离不开计算机的产生和应用。对于一个实际的问题可以用数学方法和一些逻辑关系进行抽象表达，然后利用计算机强大的计算和模拟功能，对实际问题进行模拟，给人一种更为直观的感觉。选址时，可以利用计算机模拟多种不同的组合方式，从而确定最佳组合。模拟方法不只可以用于选址中，现实生活中其他方面也有很广泛的应用，比如地震破坏例分析、房屋受力分析等。利用数学方法和逻辑关系对问题的表述越接近现实，结果越可信，分析者预定的组合方案越接近最佳组合，结果越趋近于最优。
2.4 启发式算法
启发式算法其实是模型求解的方法，是针对模型求解而言的，它是经过反复的运算判断，不断地向最优解逼近的求解方法。求出一个解，按照一定的方法要求进行修改，然后再此基础上继续进行求解计算，直到获得相对满意的结果。在这里我们可以看到，求得的解并非是最优解，而是趋近于最优解的解。启发式算法模型简单，求解方便且更接近于实际，因此受到越来越多的学者的青睐。我们看一下常用的启发式算法的分类构造算法、不完全优化算法、两阶段法和改进算法。其中对于改进算法又进行了细分包括常用的遗传算法、人工神经网络算法、模拟退火算法、爬山算法、贪心算法、蚁群算法及禁忌搜索算法[4]。
3 经典选址的模型
物流中心的位置选在什么地方，对于企业来说是一个非常重要的问题：准确的物流选址能够节约企业物流成本，让物流中心的效应最大化。接下来我们根据连续性选址问题和非连续性选址问题对应的模型来看几个经典选址的模型。
3.1 连续型选址问题的经典模型
3.1.1 重心法
重心法是较简单处理选址问题的方法，它适用于静态、连续的选址问题[5]。
重心法选址解决的问题是就将一新的设施布置到与现在设施有关的这样一个二维空间去[6]。
我们根据原有设施所在地建立一坐标系，将原有设施所在点，抽象成坐标系内对应的一点，用Pi（xi，yi）标注出原有设施的位置，对于所要求的设施位置，我们利用P0（x0，y0）来表示。利用中心法确定P0（x0，y0）的具置，计算如下：
3.1.2 交叉中值模型
交叉中值模型也是一种解决连续型选址问题的模型，它是利用加权的城市距离最小这一原则就行的建模求解。其目标函数为：
3.2 离散型选址问题的经典模型
3.2.1 P-中值模型
它是指需求点的位置和数量是确定的，各选点给定的是有限的位置。模型建立是按照满足所选点到需求点的运输费用最低这一原则，为p个设施寻求最合适的位置，并为需求点指派一个合适的设施与之对应。目标函数及约束条件：
3.2.2 覆盖选址模型
覆盖问题[7]，是指设施对于需求点的覆盖问题。设施i对于需求点j的覆盖是指设施i能在规定的时间或距离内满足需求点j的需求。
覆盖问题分为两大类，集合覆盖问题及最大覆盖问题。集合覆盖和最大覆盖解决的问题不同，集合覆盖是解决全部覆盖所有的需求点，在这一前提下需要安置多少设施这一问题；而最大覆盖解决的问题是设施的数目已经确定，如何选择合适的点来安置这些设施，使其尽可能多的覆盖需求点。在现实生活中最大覆盖问题更符合实际因此也更为人们所关注。
3.2.3 反町氏法
利用反町氏法进行选址问题的求解过程是首先利用线性规划运输法确定各个配送中心的市场占有率，求出它们的重心。其次确定配送中心各自的位置，这里采用的方法是混合整数规划法。目标函数与约束条件如下：
上述模型行先确定个目标函数，进而建立约束条件进行求解，根据求解的结果确定较佳的各选址作为配送中心的建设点。但是这种模型考虑的因素过于单一，成本最低或运距最短只是配送中心所要满足的一个要求。配送中心的目的是实现盈利，使顾客满意。但上述模型中并不能体现顾客的满意度。此外上述模型的求解计算均是利用的精确值，因此也就存在一定的局限性，二方面简单的利用精确值进行表述，使实际问题过于简单化、精确化偏离事实，另一方面限制了求解的范围，使求解范围狭隘化。
【参考文献】
[1]Daskin M S. Network and discrete location：models， algorithms and applications [M]. New York Wiley Interscience，1995.
[2]邱法聚，张予川.易荃物流配送中心连续型选址模型的推广[J].物流科技，2007：16-19.
[3]孙焰.现代物流管理技术――建模理论及算法设计[M].上海：同济大学出版社，2005.
[4]肖美华，王命延，王洪发，彭正文，等.基于遗传算法和模拟退火算法的布局问题研究计算[J].机工程与应用，2003，36：70-72.
[5]吴清一.物流管理[M].北京：中国物资出版社，2003：237-259.
数学建模启发式算法范文3
关键词：第Ⅱ类装配线；遗传算法；负荷平衡；成组技术
中图分类号：F253.9 文献标识码：A
Abstract： The emergence of personalized demand， resulting in multi-species， small batch of assembly line balance imbalance problem. Aiming at the balance problem of the second assembly line， the correspondence between the group technology and the minimum beat is analyzed. Combining the grouping technique and the genetic algorithm to establish the mathematical model， the genetic algorithm is used to encode， decode and construct the adaptive function. Group technology is a combinatorial optimization problem， and genetic algorithm is one of the effective methods to solve the combinatorial optimization. Therefore， this paper combines group technology with genetic algorithm， and proposes a process grouping method based on genetic algorithm.
Key words： class Ⅱ assembly line； load balancing； genetic algorithm； group technology
0 引 言
对于日新月异的社会发展，随之企业的装配线负荷平衡就成为瓶颈问题。装配线的失衡会严重造成企业生产效率大大降低，装配线负荷平衡可以有效解决工人、机器等待问题，并使工作站之间负荷均衡，以保证生产效率的提高。从根本上讲，装配线平衡就是组合优化问题，但是该问题涉及到产品设计研发和制造过程，这也就决定工作站先后顺序以及作业元素逻辑关联。市场需求多样性的变化对装配线的柔性要求增强，但在实际生产过程中由于工序的排列不合理、工作站负荷不均衡等一些因素导致装配线不能顺畅进行。针对装配线平衡目标的不同，单一型装配线平衡分四种：第Ⅰ类：已知装配线节拍C，优化工作站数N；第Ⅱ类：已知装配线工作站数N，优化节拍T；第Ⅲ类：已知装配线工作站数N，优化均衡指数SI；第Ⅳ类：已知装配线工作站数N，优化相关指数SN。
装配线平衡（Assembly Line Balance，ALB）是个组合优化问题，属于典型的NP-hard问题，到目前为止没有公认的最优算法。Salveson[1]首次提出ALB的线性规划模型；Dooyoung[2]采用0-1整数规划同时优化装配线工作站节拍问题；Tonge[3]提出了一种启发式算法优化装配线；Rubinovitz[4]等人研究了结合启发式算法的装配线平衡的遗传算法。不过上述算法多为理论值，没有完全结合实际状况，导致可信度差；采用单纯的遗传算法（Genetic Algorithm，GA）优化装配线平衡问题，因不满足实际约束的可行解使最优解不可行。
本文提出了一种结合成组技术的遗传算法来优化第Ⅱ类装配线的数学模型，运用工序成组结合传统的遗传算法，既保留了原始遗传算法的空间搜索能力又仅在可行解空间搜索。本文针对第Ⅱ类装配线采用该方法进行优化。
1 遗传算法
遗传算法（GA）是Holland受自然界生物进化论启发而提出来的，它是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局化概率搜索算法。随着GA的开启可以克服启发式方法的规则困难，同时提出了一种新的有效决策支持工具，而之前启发式方法的产生主要是因为现实建模的需求但没有万能的启发式规则。GA依一定的概率进行全局搜索，并且可以较大概率求得最优解，GA过程中的适应度函数的选择，编码和译码规则对装配线平衡都有影响，鉴于此本文采用工序成组的非标准遗传算子，保证解的可行性，同时采取最优策略避免最优解的丢失，其可定义为8元组[5]：
GA=（C，E，P ，M，Φ，Γ，ψ，T），T） （1）
上述式中8元组依次表示个体编码方法、适应度函数、群体范围、选择算子、交叉算子、变异算子、终止条件，本文处理每个单元的规则将结合装配线实际情况具体操作。
2 设计装配线遗传算法模型
装配线平衡（ALB）问题的研究就是产品装配过程中每个工作站工序的分配，使其作业元素按照一定的装配操作顺序进行装配，运用遗传算法（GA）就是每个工作站的工时接近节拍T或者差距最小。因此分配工序任务时需要降低工作站之间的空闲时间，平衡其作业时间。在运用GA时需要结合实际约束，这些约束用数学表达如下：
（1）S ∪S ∪…S =D k=1，2，…，m；――工作站中工序的约束。
（2）S ∩S =φ i≠j；i，j=1，2，…，m；――工作站之g工序的约束。
（3）TS ≤T k=1，2，…，m；――工作站时间与节拍的约束。
（4）若M =1， i∈S ， j∈S ， 则x≤y， M=M 为优先矩阵；――工序顺序约束。
D表示工序集合，M表示工作站数k=1，2，…，m，S 表示第i个工作站工序集合。上述为装配线基本约束，目标一般就是衡量装配线的指标，尽量减少工作站之间的空闲时间，最终达到每个工作站总工时均衡，提升生产效率。
2.1 成组工序的装配线遗传算法模型
本文主要针对成组工序的第Ⅱ类装配线平衡问题进行研究[6]，运用成组技术将工序集中分类安排，使节拍T最小化，工序相似度最大，提高装配线效率。用数学模型描述该装配线问题如下：
w 为某一个工序的某一特征的权重系数；x为工序代号；k为零件的特征要素数，k=1，2，…，s；i，j为待分类的工序数，i，j
=1，2，…，m；针对工序成组特征本文选取5M1E（人，机，料，法，测，环）六个方面，每个特征方面依据工艺及工作站要求赋予权重。权重系数反应每个工序之间的相似度，需要满足归一条件，即∑wx =1k=1，2，…，6。余弦值越接近1，就表明夹角越接近0度，也就是两个工序越相似，夹角等于0，即两个工序相等。
2.2 编 码
遗传算法的优化结果受编码规则的影响，在实际装配线生产过程中约束较多，一般的二进制编码会影响整个算法的每一步，因此在这里并不适用，所以需要选择特殊的编码方式。针对装配线平衡问题，由于受装配线工序先后顺序以及工艺设计的约束，所以可用装配工序图表示现有的流程制造。图1是某装配线的工序流程约束图，连接点的弧表示工序顺序，节点上方数字表示工序时间，装配线的排列顺序也就是成为一种优化组合问题，使工序先后逻辑顺序编码符合实际约束更为简单[7]。在排列工序时应结合成组技术，按照工序的相似度进行配列，最大可能分配同一个工作站，提高装配线作业效率，降低工序之间的空闲时间。因此，本文采用工序成组的方法对染色体进行编码，每个工序对应一个基因，每个工作站对应一段基因位，按顺序排好。图2为图1工序约束图下的一个染色体。每个工作站的总工时不能超过节拍T。
2.3 译 码
编码后的染色体要按照一定的规则进行译码，该过程是将工序编码表示的染色体（成组工序）中的每个基因（工序）顺序分配各个工作站。在工作站给定的情况下，依据染色体中工序号顺序最小化节拍T（最大化生产效率P）和工序的相似度最大[8]。首先在给定满足工作站数的条件下，依照染色体的工序号，运用模糊聚类分析法――夹角余弦法对每个工序进行分类，再依据给定的工作站数以及工艺要求进行分配，然后依据工作站上所分配工序求其时间。在此过程需要满足以下条件：
（1）每个工作站的工时不能超过节拍时间，即TS ≤T；
（2）一个工序只能分配一个工作站；
（3）考虑到节拍的约束，若一个工序不能被分配到工作站，但该工序的紧后工序可以分配，则该工序优先分配到工作站。
在译码过程需要借助平衡指数SI= 来衡量成组工序分配情况，即∑s 值的合理性。
2.4 适应函数的构造
由于该适应函数是求极大值的过程，但是平衡指数是极小值问题，因此需要进一步转化SI也为极大值。本文借助指数函数构造适应函数如下：
fi= +e
其中：SI= ，因此就有指数函数越小，相似度越大，节拍越小的染色体使适应函数越大。
2.5 初始群体的选取
为保持最优解的可行性和计算结果的精确性，本文采取的可行解都是在装配线可操作的工序条件下进行筛选。因此依据工序流程图采用图论中随机拓扑排序方法生成初始群体，具体步骤如下：
（1）使当前初始化染色体序列为空；
（2）随机从工序流程图中选择一个无紧前工序安插在当前序列尾部；
（3）在图中删除该节点以及所连接的边，若已无节点则输出当前作业序列，否则转（2）。
成组工序顺序的输出是建立在装配线实际情况之上，可排列组合出新的成组工序，并生成初始群体。
2.6 选择策略的确定
因需要适应值较大的个体保留在群体中，本文采用确定式采样选择方法（Deterministic Simpling）。其具体操作过程如下：
（1）群体中每个个体在下一代中期望生存数目N ： N =M i=1，2，…，M。
（2）用N 的整数部分 N 确定每个对应个体在下一代群体中生存数目，其中 N 表示取不大于x的最大整数。由该步可确定下一代群体中的∑ N 个个体。
（3）按照N 的小数部分对个体进行降序排列，顺序取前M-∑ N 个个体加入到下一代群体中，至此完全确定出下一代群体中的M个个体，保持总的群体数量不变。
上述的选择方法保证了较大的适应群体被保留，避免最优解流失，也就是最优的可行性解的保留。
2.7 交叉和变异准则
单点交叉算子（One-point Crossver）：它是指个体编码随机选取某个交叉点，然后互换该点后的部分染色体，是一种最常用和最基本的一个交叉方式。由于初始群体是可行解，经过单点交叉后产生的新一代个体也是可行解。初始群体具体操作方式如下：
（1）初始群体中随机选取两个进行配对。若该群体数量为M，则有 M/2 对进行配对；
（2）对于每个相互配对的个体，随机设置某基因后的位置为交叉点。若染色体长度为n，则共有n-1个交叉点数[9]；
（3）依据设定的交叉率（一般0.4～0.99）进行交叉互换部分基因，从而产生两个新的个体。
用上面两个染色体说明单点交叉操作，随机选取交叉点：position 1=5，产生的新个体见图3。
基本位变异算子（Simple Mutation）：依据变异率p 对当前染色体上基因位进行变异操作，本文为保证可行解的持续，采用位移变异方式。随机选择一个关系进行变异操作，将其插入约束条件下的任意位置，而它的紧随工序按照原来的顺序排列，这也就保证了变异后的可行解持续性[10]。取工序6进行变异，将其插入第十个位置，则8，10，7，9工序向前平移一个位置，工序11位置保持不变。具体操作过程如图4：
2.8 终止代数
鉴于本文工序数目较少，终止代数取100，即进化100代后结束运算。
3 实例分析
基于第Ⅱ类装配线结合遗传算法的叙述，本文采用仿真软件Matlab2016a基于处理器为Intel（R）Core（TM）i5-4256U/2.4GHz，操作系统为64位四核window10平台进行模拟，交叉概率0.8，变异概率0.2。选取一条十一个工序四个工作站的装配线为例，其总工时为46s，优化结果如表1至表3：
目前装配线平衡率P =P =P = =95.83%；minT为11S；均衡指数SI = =1.4；SI =SI
= =2即SI
4 结束语
针对第Ⅱ类装配线工序相关因素（5M1E）分析，提出了成组工序的作业序列，在此基础运用遗传算法。该方法既保留了原有的GA遗传算法搜索能力，又依据实际情况选择初始群体和构造交叉算子、变异算子，重要的是只在可行解范围内进行搜索最优可行解。交叉算子一般取0.4～0.99，变异过程中算子的随机选取范围0.3～0.5。在适应度函数方面考虑了各个工序之间的相似度和装配线的平衡率以及平衡指数，可以用来比较不同工作站内工序相似度，增加工序的聚集度，提高工作效率。由于本算法中的相似度根据5M1E需要赋予相应的权重，该过程会涉及到主管因素，所以在结果上会产生差异性，结合实例可见该算法以及相关指数还是取得相对满意的结果。本文的成组工序遗传算法的提出，为提高装配线效率和改进装配线技术提出了参考依据。
参考文献：
[1] Salveson M E. The assembly line balancing problem[J]. Journal of industrial Engineering， 1955，6（3）：18-25.
[2] Dooyoung Shim， Hobey Min. Flexible Line balancing practices in a just-in-timeenvionment[J]. Production and inventory management Journa1， 1991（4）：38-41.
[3] Tonge F M. Summary of a Heuristic line balancing Procedure[J]. Management Science， 1960，7（11）：21-42.
[4] Levitin， Rubinovitz， Jacob， et al. A genetic algorithm for robotic assemblyline balancing[J]. European Journal of Operational Research， 2006，168（3）：811-825.
[5] 周明，O树栋. 遗传算法原理及应用[M]. 北京：国防工业出版社，1999：19-20.
[6] 皮兴忠，范秀敏，严隽琪. 用基于可行作业序列的遗传算法求解第二类装配线平衡问题[J]. 上海交通大学学报，2005，39（7）：1123-1127.
[7] 朱会霞，王福林，张勇，等. 改进遗传算法优化非线性规划问题[J]. 数学的实践与认识，2013（7）：117-125.
[8] 梁燕，金烨. 基于工位约束快速启发式算法的混合装配线分段优化[J]. 上海交通大学学报，2007，41（9）：1501-1505.
[9] 鞠彦兵，李桂芬，王爱华. 基于遗传算法的车间作业计划仿真研究[J]. 数学的实践与认识，2006（10）：79-85.
[10] 吴君华，夏巨谌，曹山河. ALB问题的数学模型及其优化算法的研究[J]. 系统学报，1999，11（5）：358-361.
数学建模启发式算法范文4
关键词：P比特光网络；多故障定位；蚁群优化
随着超大容量(P比特级)光网络规模的扩大和传输速率的提高，使得网络遭受自然灾害破坏、人工操作失误和软件配置错误等多重故障的概率增加，将降低光网络带宽提供的可靠性，增加保护恢复资源配置冗余和调度的复杂性。超大容量(P比特级)光网络采用基于时空标记的分类服务方法，从时空角度对网络资源(包括路由、波长、链路、节点等)进行整合与优化。多业务端到端服务质量(Qos)需求与光网络时空多重故障生存性之间存在复杂的关系。由于光网络元素(节点、链路)的故障能够向业务流的下游节点进行传播，而使时空多重故障情况下故障管理中心收到大量的告警包。其中包含大量的冗余告警包，造成故障管理中心告警包数目急剧增多。理论已经证明，依据收到的告警包进行多故障的甄别属于非多项式完全问题(NP－compJete)问题：通常情况下得不出准确的故障发生的数目和故障发生的位置。光网络多故障定位困难可以描述为：可以在多项式时间内判定一个故障的集合是不是观测到的检测设备发出告警的原因，但是无法在多项式时间内根据观测到的告警集合推断出故障的集合。
网络拓扑复杂化和承载业务的多样性是P比特级光网络两个基本的特点，而多故障定位NP－complete问题的困难与网络拓扑和网络承载的业务相关。在P比特级光网络里多故障定位的NP－complete属性：更难寻找包含故障元素最少的故障集合和寻找包含故障元素最少的故障集合的时间与网络拓扑的输入规模成指数增长关系。由于多故障定位属于NP－compJere问题，很难得到故障的准确的数目和位置。默认的约定是：在保证推断出的故障集合一定能产生故障管理中心收到的告警情况下认为故障集合中的元素越少越是最有可能发生。已有的故障定位机制最后给出的故障集合都是在这种约束下给出的，但在这种约束条件下得到的故障集合并不一定是网络真实发生的故障，而且在这种约束下网络存在一些故障情况使得任何故障定位算法都无法处理。
1、多故障定位算法
多故障定位机制主要分为集中式和分布式，应用的光网络类型为非全光网和全光网。在非全光网中光路的中间节点对光信号进行光电转化，能够检测到故障并且可以屏蔽某些类型的故障向下游的传播。全光网中只有光路的宿节点或者所经过域的边界节点才对信号进行光电转换，才能检测到故障。一般情况下，集中式方法需要详细的网络元素模型用于故障定位，分布式机制依靠持久连接(Keep－alive)或通知消息甄别出故障的根源。
表1列出了已有的故障定位机制，透明的故障定位算法(层1)、推理算法(层1)、运行长度探测算法(层1)、启发式生成树M－cycle算法(层1、2、31属于集中式的故障定位算法，链路管理协议(层3)、端到端故障检测和定位协议(层3)、有限区域向量匹配协议(LVM)协议属于分布式故障定位协议。
研究透明光网络中故障管理的常规问题，对网络中的设备进行建模，得到每个设备可能检测到的故障和可能屏蔽的故障，然后根据得到的告警包去遍历一个告警的二叉树，最后得到可能的故障元素。该算法可应付4种故障：功率下降、波长错误部署、带内干扰、带外干扰。
研究真实环境中的多故障定位(观察到的告警可以是不可靠的)。核心问题为离散优化问题。目标是要找到故障集合和告警集合，最小化成本函数。提出了启发式算法的解决方案。该算法的复杂度集中在一个预先计算阶段，需要遍历一个二叉树。
链路管理协议(LMP)是通用多协议标记交换(GMPLS)协议栈的重要组成部分，通过在一对节点之间交换活动状态通道(Channel Active)和失效状态通道(channel FatD消息来实现不透明或透明网络中的故障定位，而不必关心编码格式。LMP协议并不单一运行在一个平面，涉及到控制平面和数据平面的协同工作。
LVM协议的核心是如果两条光路同时经过一段链路，若这两个业务的目的节点都检测到故障，就认为这个故障的链路就是这个共享风险的链路。这个协议为单故障定位设计。扩展的LVM协议支持多故障定位。
2、多故障定位问题描述
对于超大容量(P比特级)光网络，影响到故障定位复杂度的因素主要包括：多故障时空随机出现、网络复杂度(无标度网络、随机网络)、承载业务的多样性(业务种类、业务级别、QOS)。通常情况下多故障定位的目标是根据得到的告警指示，找出可能的故障集合，并且认为得到的集合(f)的故障数目越少越好。下面描述一般意义下故障定位的困难，然后阐述解决NP－complete在P比特级光网络中变得更加困难，且随着网络规模的增大定位的计算复杂度和计算时间与网络的输入规模成指数增长关系。
多故障定位的线性规划形式：
f时刻可能出现的故障集合F(t)F1，F2，F3，F4……
t时刻故障管理中心收到的告警集合A(t)：a，b，c，d，e，f，g，h……
约束条件：A(Ft)＋A(F2)+A(F3)＋A(F4)+……=A(t)其中函数A(F)表示仅仅故障F触发的告警的集合。
目标函数：main(CTF)，C＝(1，O，1……)。C中元素为1或者0的列向量，目的是寻找一个包含故障数日最少的集合。
根据光网络拓扑和网络中的业务分布，我们得到如图1所示故障和告警关系的二部图。图的下面是故障管理中心收到的告警的集合，上面是可能的故障元素。故障定位的任务是根据关系图，找到一个故障的集合，使得故障集合中的故障数日最少。多故障定位可分两阶段完成：
(1)获得故障和告警的关系图。这个关系图有两个约束：光网络拓扑的约束和承载业务的分布约束。
(2)根据得到的关系图，运用有效的算法得到包含故障数最少的故障集合，其中第二阶段中寻找最少数目
的故障集合属于NP－eomplete问题。
多故障定位的目标是寻找包含故障数目最少的故障集合。即使能够寻找到计算性能优良的启发式算法解决了NP－complete的困难，但是最少数目的故障集合可能不止一个，如何选择和处理这些集合仍困难。况且最少数目的故障集合并不一定是真实网络中一定发生的故障，网络管理者只是认为最少数目的故障集合更有理由发生。
多故障时空随机出现、网络复杂化(无标度网络、随机网络)、承载业务的多样性是P比特级光网络的显著特征。其中网络复杂化(无标度网络、随机网络)、承载业务的多样性增加了多故障定位第一个阶段的复杂度，使得获得的故障和告警的关系图更加复杂、耗时，而且得到的关系图不再是静态而是动态变化的。多故障时空随机出现增加了多故障定位的第二个阶段的复杂度，因为收到的告警包是随机达到故障管理中心的，不同的告警集合及故障集合有着明显的区别，如何处理告警包的随机性，成为研究的关键。
3、模糊故障定位和蚁群优化
为了解决P比特级光网络对多故障定位两阶段带来的影响，本文针对每个阶段提出了各自的优化策略：故障和告警关系的模糊化(第一阶段)、蚁群优化算法(第二阶段)。
由于承载业务的多样性使得获得的故障和告警的关系图更加复杂并且是动态变化的，此时故障和告警的关系不再是确定性的必然事件。我们用模糊数学的隶属关系来描述故障和告警，告警是在一定程度上隶属于触发它的故障，得出这样的结论的依据是：
(1)承载业务的多样性、业务动态的拆建使得故障管理中心无法实时地得到下游的节点告警，告警和故障的关系不再是确定性关系。而根据业务到达的分布，可以得到告警和故障的隶属度。
(2)网络复杂化(无标度网络、随机网络)使得业务的路由多样化。相同源和宿业务的路由在不同时刻有着不同的路由，使得故障和告警的关系图动态变化。基于路由的多样性，可以得到告警和故障的隶属度。
(3)随着网络的运行时间的增长，伴随着故障定位问题的成功和失败，可以根据以往成功的经验建立专家系统。这个专家系统需要能够很好地描述网络故障和告警的关系。
隶属函数是模糊故障定位的基石，已有隶属函数的确定方法：
(1)模糊统计法
模糊统计法的基本思想是对论域上的一个确定元素是否属于论域上的一个可变动的清晰集合做出清晰的判断。
(2)例证法
例证法的主要思想是从已知有限个μA的值，来估计论域μ上的模糊子集A的隶属函数。
(3)专家经验法
专家经验法是根据专家的实际经验给出模糊信息的处理算式或相应权系数值来确定隶属函数的一种方法。在许多情况下，经常是初步确定粗略的隶属函数，然后再通过学习和实践检验逐步修改和完善，而实际效果正是检验和调整隶属函数的依据。
这样在得到的故障和告警的关系图中，故障和告警之间不再是确定的关系，每条故障和告警之间的连接都将赋予一个隶属度(0～1)，这个隶属度反映网络拓扑和业务分布在一段时间内对告警和故障关系的影响。我们采用例证法来进行隶属度的计算。蚁群算法(ACO)是一种基于种遍历所有告警群的启发式仿生进化算法。ACO已经成功用于解决许多组合优化问题，最早的应用就是解决旅行推销员、货郎问题(TSP)问题。蚁群算法是对自然界蚂蚁的觅食寻路方式进行模拟而得出的一种仿生算法，充分利用了选择、更新和协调的优化机制。即通过个体之间的信息交流与相互协作最终找到最优解，使它具有很强的发现较优解的能力。假如将告警作为图的节点，而故障作为经过的链路，多故障定位很容易转化为旅行售货商问题。蚂蚁经过一个告警并为这个告警选择相应的产生此告警的故障。当所有蚂蚁遍历所有的告警后，就得到故障的一个集合。蚂蚁释放的信息素与故障集合的元素的个数成反比，故障元素的数目越少。释放的信息素越多。启发式信息与每个故障节点的度成正比。
4、仿真验证
本文在波长交换光网络(WSON)仿真平台上实现模糊隶属关系和蚁群优化算法的多故障定位。平台基本功能采用了IETF的GMPLS协议。COST239仿真拓扑如图2所示。有11个物理链路节点和25条物理链路。网络类型为全光网(只有每条光路的宿节点或者域的边界节点可以检测到故障)。仿真仅仅考虑链路故障。1～25条物理链路上随机的3条链路出现故障。产生故障的光路的宿节点都能够检测到故障。物理拓扑上任意两个节点承载的业务采用泊松分布。业务的路由采用D算法实现，不考虑资源约束。方案旨在验证多故障定位方案。仿真结果如图3所示，分别进行了蚁群多故障和扩展的LvM协议多故障定位。红黑曲线计算多故障定位成功率的方式为故障数目和定位的故障与预先设置的故障数目和故障完全一致则认为多故障定位成功，否则失败。蓝绿曲线计算多故障定位成功率的方式为成功的故障数目除以得到的故障集合的故障数目。左边的仿真结果图为3故障，右边的仿真结果图为4故障，从成功率对比可以看出，随着故障数目的增加，蚁群要逐渐优于扩展的LVM协议，在大规模和多故障情况下，蚁群算法能取得更优的性能。
数学建模启发式算法范文5
摘 要：针对ASAP和ALAP算法的缺陷，将生态捕食者―被捕食者模型应用于云计算的主任务调度算法中,建立一种基于生态捕食者―被捕食者模型的主任务调度算法，该算法通过生态差分方程动态调整节点内采用相应算法的任务数量，经过仿真试验证明了算法的有效性。
关键词：主任务调度；生态差分方程；ASAP；ALAP
中图分类号： TP393 文献标识码：A
The Research for Optimization of the Main Task Scheduling Algorithm in Cloud Computing
LU Xiaoxia,ZHOU Zhonghe
(Hunan planing and designing institute of post and telecommunications Co., LTD，Changsha 410001)
Abstract:Aimed at the defects of ALAP and ASAP algorithm, establishing a main task scheduling algorithm based on ecological predatorsprey model, the algorithm dynamic adjustment the number of tasks of corresponding algorithm using ecological difference equations. The validity of the proposed algorithm have proved through the simulation experiment.
Key words:main task scheduling；ecological difference equation；ASAP；ALAP
1 引 言云计算的本质是一种商业模式，是将各种计算资源租用给需要的用户，并且根据这些用户的要求提供准备好的环境；在用户使用这些环境后，提供这种资源的服务商，按照服务级别协定进行收费；当用户使用完后，提供重用环境备份和回收资源的用户和资源管理的手段。由于它有着非常广泛的应用前景，在目前复杂的网络情况下,如何解决拥塞问题,怎么保证提供给用户的服务稳定性,特别是对任务有着很强的时间、资源和容错需求，如何使任务按需完成得到保证，是目前云计算需要研究的。近年来，通过大量专家学者们的共同努力，以不同指标为标准,涌现了多种多样的算法，比如研究独立任务为主的最小最小算法、最大最小算法、快速贪吃算法 ［1］ 、最大时间跨度算法等。尽可能早调度算法（ASAP）［4］和尽可能迟调度算法（ALAP）［5,6］，这两种算法是最简单也是速度最快的调度算法,大多的研究都是基于这两种经典算法，如Kaya等人提出的一种基于文件共享独立任务的启发式算法［2］，Jones等人在文献［3］提出的一种以带宽为中心的任务调度模型与启发式算法。但是，在ASAP调度算法中，任务可能过多集中于较早的控制步（指系统控制一个任务操作的基本时序单位，在同步系统中，通常对应于一个或几个时钟周期）中；在ALAP调度算法中，任务可能过多集中于较迟的控制步中。无论是集中于较早的控制步还是较长的控制步,都导致了任务的分布不平衡，甚至引起过量的资源需求,造成资源浪费，还可能使任务的拒绝率过高。因此,从调度的效果出发，上述两种算法都不是好的调度算法。
为了调整任务在控制步中的分布情况,提高任务的接受率,本文将生态捕食系统的捕食―被捕食算法［7,8］ 引入主任务调度算法中,提出一种基于生态捕食系统的捕食―被捕食算法［7,8］。
2 基于捕食者―被捕食者模型的主任务
调度算法
该算法的设计思想是：在主任务调度算法中，引入种群生态学中的捕食者―被捕食者模型，利用生态捕食系统的周期性变，动态地调整采用主任务调度算法的任务，对于每个刚到的任务，根据其紧迫程度不同，将生态系统的种群，即将捕食者和被捕食者分别对应到节点中采用ASAP和ALAP的任务，将生态系统的种群规模对应到采用ASAP和ALAP的任务的多少，建立一种基于生态捕食者―被捕食者模型的主任务调度算法。
2.1 两种群捕食者―被捕食者模型的差分方程在主任务调度算法中的应用
本文直接将两种群的生态捕食者―被捕食者模型应用于主任务调度算法: 设x1为采用ASAP调度算法的任务队列即被捕食者， x2为采用ALAP调度算法的任务队列即捕食者，且任务队列x1尚以其他任务为生，则两队列的差分方程数学模型如下：
x1,n+1=x1,n+hx1,na10－a11x1,n－a12x2,nx2,n+1=x2,n+hx2,n－a20+a21x1,n－a22x2,n （1）
其中，节点内作用系数a11，a22都等于0(不考虑种群内密度制约)，其他参数均为正数，且a21=αa12，0＜α＜1。方程组中各项具体含义如下：x1,n，x2,n分别表示在时刻T队列 x1，x2的任务信息，h 为时间区间长度， a10、a20分别为队列x1、x2的自身任务信息变化率，x1,n+1、x2,n+1 分别表示在T+1 时刻节点x1、x2的任务队列信息，a21为节点x1转移给x2任务信息后x2的任务信息增长率，a12为队列x1转移给x2的任务信息比例。
2.2 队列结构
在云计算系统中，为了存储与其他队列交流的任务信息以及更新系统信息，支持动态任务决策，队列xm需要建立队列信息表，见表1。从表1中，可以看到信息表由本队列状态表、相邻队列状态表和系统状态表组成。本队列状态表记录队列xm 在T 时刻的任务利用率、信息包数和更新次数；相邻队列表记录相邻队列xj的任务数；系统状态表记录系统利用率。队列xm的处理能力为单位时间内能处理的最多任务量，用um表示，xm,n+1表示时间间隔h 后队列xm的任务数，n 为系统内队列总数，此处，n=2，定义队列xm的利用率Lm为： Lm=xm,n+1hum（2）
表1 队列信息表
信息表
状态值
本队列状态表
队列名xm
,利用率Lm
，任务信息xm,n
，更新次数k
相邻队列状态表
队列名xj
,任务信息xj,n
系统状态表
系统S，系统利用率L
因此，系统利用率L 为：
L=∑2m=1xm,n+1h∑2m=1um （3）
2.3 算法步骤
算法利用生态捕食者―被捕食者模型的动态周期性变化动态地调整各队列的任务信息，达到主任务调度的目的，定义λ为任意小的正数。算法步骤如下：
初始化节点中各任务队列信息；
DO
｛
根据生态差分方程模型更新队列x1、x2；
计算队列的利用率Lm及系统利用率L；
IF（L－Lm＜λ）
break；
ELSE
更新任务队列x1、x2；
｝WHILE （进化代数＞最大进化代数）
3 实验及分析
假设任务的到达服从参数为λ的泊松分布，任务的执行时间服从参数为1μ的指数分布。那么，可以定义工作量为λμ，并定义该任务的计算时间＝该任务在处理机上执行时间／该处理机的处理能力。假设云计算环境中有50000个有依赖关系的任务到达，处理机的数量分别选为30，50，100，500，1000和2000，这些处理机拥有不同的处理能力，统一分布在区间 ［1，10］。每个有依赖关系的任务由一系列的任务组成(记为n)，假定这些任务数在集合{20，40，60，50，100，200，300，400}中随机选取。记t为整个作业的执行时间，则每个任务的平均执行时间为tn。假设每个作业的最后期限平均值为t1+η•2t5.5,其中t1为作业的到达时间，η为小于1的权重参数，5.5为处理机的平均处理速度。在实验中，η的取值范围为0.1-0.26，通过试验验证η的变化对算法性能的影响.仿真结果如下图所示：
图1和图2分别为在独立任务和依赖任务下，这几种算法的拒绝率。从图中我们可以看到，无论是独立任务还是依赖任务，改进算法与传统经典算法ALAP和ASAP相比，有更低的拒绝率。因为在ALAP调度算法中，任务将集中于较迟的控制步中；在ASAP调度算法中，任务将集中于较早的控制步中。由于任务在节点中的分布并不均匀，使任务过分集中堆积，导致资源需求增加，造成资源的过度浪费。改进算法将两节点的生态捕食者―被捕食者模型应用于主任务的调度算法中，动态的调整任务在各控制步中的分布，使之动态平衡，从而达到合理利用资源、提高资源利用率的目的。
4 结 论
针对传统算法ASAP和ALAP的缺陷，将节点的生态捕食者―被捕食者模型应用于主任务的调度算法中，建立一种基于生态捕食者―被捕食者模型的主任务调度算法，该算法通过生态差分方程动态调整节点内采用相应算法的任务数量，使采用这两种算法的任务数量动态平衡，使任务不过分堆积，达到合理利用资源，提高资源利用率的目的。经过仿真试验证明了算法的有效性。
参考文献
［1］ GuiXL.GridComputing Technology［R］. Beijing:Beijing University of Posts and Telecommunications Press，2005:144-169.
［2］ KAYA K,UEAR B, AYKANAT C. Heuristics for scheduling filesharing tasks on heterogeneous systems with distributed repositories［J］. Journal of Parallel Distriboted ComPuting,2007,67(3):271-285.
［3］ WILLIAM J, WALTER L, Louis P, Daniel S. Characterization of bandwidthawaremetasehedulers for coallocating jobs across multiple clusters［J］.Journal ofSupercomputing，2005,34(2):135-163.
［4］ Q.Zheng, B.Veeravalli, C.K.Tham. On the design of faulttolerant strategies using primarybackup approach for computational grids with replication costs［Jl. IEEE TRANSACTIONS ON COMPUTERS, 2009，58(3):380-393.
［5］ Q.Zheng, B.Veeravalli. On the design of communicationaware faulttolerant scheduling algorithms for precedence constrained tasks in grid computing systems with dedicated communication deviees［J］. J.Parallel Distrib. Comput. 2009，69:282-294
［6］ 清华大学.数字系统设计自动化［EB/OL］. 省略/qinghua/27/text/chap5/sec3/part3/index1_1.htm ［18July2008］
［7］ LENZITTI B,TEGOLO D, Valenti C.Preypredator strategies in a multiagent system［C］//IEEE Proceedings of the Seventh International Workshop on Computer Architecture for Machine Perception，2005.
［8］ 马知恩.种群生态学的数学建模与研究［M］.合肥：安徽教育出版社，2000.
数学建模启发式算法范文6
关键词：CAN总线技术；实时性；电网调度；静态调度
中图分类号：TP315 文献标识码：A 文章编号：1009-2374（2009）01-0071-02
随着经济的发展，现代电网结构日趋复杂，电网容量不断扩大，对电网运行的可靠性要求也越来越高。而电力系统对变电站又提出了减员增效的要求，这两者之间的矛盾可以通过CAN总线技术来解决。
一、现场总线及其特点
现场总线是一种应用于生产现场，在现场设备之间、现场设备与控制装置之间实现双向、串行、多节点数字通信的技术。它的产生是自动化仪表发展的必然趋势，同时也是企业综合自动化发展的需要[1]。
和以往的控制系统相比，现场总线具有以下特点：
全数字通信、多分支结构、现场设备状态可控、互操作性和互换性、控制分散等等特点简化了系统结构，提高了系统的可靠性、自治性和灵活性。
CAN（Controller Area Network）是控制器局域网的简称，它属于现场总线的范畴，是德国Bosch公司在1986年为解决现代汽车中众多测量控制部件之间的数据交换问题而开发的一种串行数据通信总线，支持分布式控制或实时控制。已经被列入ISO国际标准，称为ISO11898。今天，CAN已成为工业数据通信的主流技术之一。
经过十余年的发展，出现了CAN，FF，P rofibus，Lonworks等多种现场总线产品，其中CAN总线因为具有执行成本低，高可靠性和实时性等特点，广泛应用于工控自动化，过程控制等领域，成为主流现场总线之一。
二、CAN总线及其特点
CAN总线协议建立在国际标准化组织的开放系统互连参考模型基础上，但是，其模型结构只有两层，即只取OSI底层的物理层和数据链路层。CAN总线协议的数据链路层主要分为逻辑链路控制子层（LLC）和媒体访问控制子层（MAC） [2]。
和其他现场总线相比，CAN总线具有以下特点：
CAN总线通信机制――仲裁场、节点不分主从通信方式灵活、CSMA/CA、多种方式传送接收数据、传输距离远通信速率高、采用短帧结构、通信介质选择灵活。
三、CAN总线的实时性
尽管CAN具有诸多优点，但也存在许多不足。基本的CAN总线协议中采用的是固定优先级机制，它比较适合于确定性硬实时系统中的消息调度，但灵活性较差，即只适用于系统时间特性固定不变的系统，如果网络中某个节点传输消息的时间特性发生变化，则会造成整个静态调度的重新构建；同时，如果网络中初始优先级较高的任务较多，就会导致优先级较低的任务总也得不到机会发送，直至被丢弃，这就降低了系统的执行性能，甚至可能造成严重错误；CAN总线通信协议采用事件触发机制，而在工业控制中同时存在时间触发和事件触发信息，且以时间触发为主，这就需要我们对CAN总线设计合理有效的调度策略，消除或减小信号抖动，降低网络时延，提高系统的实时性[3]。
在CAN总线应用于实际系统的过程中，实时性是一个非常关键的问题。实时是指信号的输入、运算和输出都要在极短的时间内完成，并根据生产过程工况的变化及时地进行处理。而实时系统指在事件或数据产生的同时，能够在规定的时间内给予响应，以足够快的速度处理，及时地将处理结果送往目的地的一种处理系统。研究CAN协议的实时性问题，采取合理的措施克服CAN协议中固定优先级机制的缺陷，提高CAN总线通信系统的实时性具有重要的应用价值。设计一种有效的优化调度方式与算法实现，提高CAN总线在工控领域的通信实时性[4]。
首先以CAN总线通信机制为基础对系统进行数学建模，采用有效的调度方案与算法实现通信信息的实时调度，以便消除或减小信号抖动，降低网络时延，通过仿真实验验证其有效性；设计CAN总线硬件平台，编写相关算法，进行试验测试、分析与改进。以CAN总线通信机制为基础，应用实时调度理论和优化算法，提出一种基于CAN总线的有效的工控优化调度方案与算法，消除或减少信号抖动，降低网络时延，提高控制系统的实时性。根据CAN总线对应用层开放的特点，应用SCM芯片设计硬件平台，编写和验证所提优化调度方案与算法的有效性。进一步将TTCAN（Time-triggered CAN）和容错控制算法引入到研究中。
基于CAN总线的实时调度算法有多种分类方式，整体上可以分为两类：静态调度算法和动态调度算法，其中动态调度算法又包括混合调度算法。
静态优先级是指系统中需要调度的各任务的优先级是事先固定的，在运行过程中不再发生变化，因此，静态优先级调度算法也可以称为固定优先级调度算法[5]。
静态优先级调度算法的缺点是不灵活，缺少对系统运行过程中突发事件的实时处理能力，需要事先考虑系统中各种可能出现的情况；并且可能出现低优先级信息等待时间过长、总也得不到发送机会的情况，这对实际系统的运行是非常不利的。因此，我们需要考虑采用更加灵活的调度算法：动态优先级调度算法。
动态优先级是指系统中需要调度的各任务的优先级，是随时间推移而动态变化的，在动态优先级调度算法中，任务的调度优先级随着系统中任务运行而变化，任务优先级不仅仅与任务自身有关系，而且与系统中的其他任务有关。这使得系统应用的灵活性大大提高。
将动态调度算法与静态调度算法相结合，同时将神经网络、启发式算法等思想融入其中，称为混合调度算法。
综上所述，对于一个CAN总线的应用系统，通常都混合有实时和非实时的信息，所以需要根据实际系统的要求，仔细分析上述各种调度算法的优缺点，选定一种合理的调度算法满足信息传输的实时性与可预测性要求。
参考文献
[1]阳宪惠．工业数据通信与控制网络[M]．清华大学出版社，2003．
[2]冯冬芹，等．以太网与现场总线[J]．自动化仪表．2003，24（6）．
[3]Jean Pierre Thomesse， Intelligent Components， The Fieldbus， Proceedings of the International Symposium on The and Instruments for Control Application， 1997．
[4]David A．Glanzer， Interoperable Fieldbus Devices: A Technical Overview， ISA Transaction 1996，34(2)．
