改进启发式算法（共8篇）
改进启发式算法 篇1
0 引言
在光网络中,生存性技术尤为重要。P圈作为一种有效的光网络生存性保护技术,具有环网保护、快速恢复和网状保护高资源利用率的特点。
P圈的构造算法是P圈的基础,本文针对P圈的Grow算法,提出了NewGrow算法,进行了相关指标的对比分析,并在实际网络拓扑中进行了仿真。
1 P圈算法相关指标
1998年,W.D.Grover和D.Stamatelakis提出了P圈(预置圈)的概念[1],P圈保护是利用网状网中的空闲链路资源预先设置的环形通道。其优势在于具有与环形结构相近的恢复速度以及与网状结构相近的资源利用率。P圈的构造是P圈保护的基础,可以为下一步的P圈配置提供优良的备选圈。P圈的构造是将网络拓扑中可能的基本圈和AE(先验效率)高的扩展圈作为备选圈,常用的启发式P圈构造算法包括SLA(跨接链路算法)、Sp-add(增加跨接链路算法)和Grow算法。
1.1 P圈评价指标
P圈的评价指标包括AE、P圈个数、圈覆盖度以及圈的代价。AE能够直观地体现P圈的保护能力,同时也是评价指标中最重要的部分[2]。AE定义为一个P圈所能提供的保护链路数与该P圈所占链路数之比[2]。其计算公式为
式中,S为该网络拓扑中所有链路的集合;Ck为该P圈上任意一条圈所消耗的代价,即一个波长的空闲容量;Xp,k为该P圈可以为链路k提供的保护波长数。
P圈的个数是P圈构造过程中不能忽视的衡量指标,在覆盖整个网络拓扑的前提下,应保证所构造的P圈数量尽可能少,这样不但可以降低网络管理的复杂度,还可以减少网络节点的负担[3]。
对于链路型P圈而言,圈覆盖度[4]是一个P圈能保护的链路个数与网络中所有链路数N的比值,即,式中,Ap,i表示该P圈能否保护链路i,若i为圈上链路或者跨接链路,则Ap,i为1,若i既不是圈上链路也不是跨接链路,则Ap,i为0。圈覆盖度反应了圈的保护广度,其值越高,说明该P圈的保护范围越广,P圈性能越好。
圈的代价指的是该P圈所占用资源的多少,圈的代价=∑i∈SCi·Fp,i,式中,Ci表示该P圈在链路i上的代价值,Fp,i表示网络拓扑中链路i的权值,即链路i的代价[5]。
1.2 三种经典P圈算法的性能比较
SLA[6]的扩张过程如图1所示。以链路BF构造出基本圈BCFAB,其中包含一条跨接链路BF,计算得AE = (4+2)/4=1.5,圈覆盖度=5/9=55.56%。
Sp-add算法[7]的扩张过程如图2 所示。 对SLA扩张后的基本圈BCFAB中链路CF进行扩张,得到圈BCDFAB,其中包含两条跨接链路BF、CF,计算得AE = (2×2+5)/5=1.8,圈覆盖度=7/9=77.78%。
Grow算法的扩张过程如图3 所示。 对经过Sp-add扩张后的圈BCDFAB中的链路FD继续进行扩张,得到圈BCDEFAB,其中包含3条跨接链路BF、CF和DF,计算得AE = (3×2+6)/6=2,圈覆盖度=100%。
从AE和圈覆盖度两个衡量指标来看,3 种算法构造P圈的性能优越程度依次为:Grow算法>Sp-add算法>SLA。网络拓扑较为复杂时,Grow算法对圈进行扩张的过程中,没有对P圈的AE进行选择,导致AE低的P圈也被扩张,增加了工作时间,同时也使最终构造的备选圈总体质量不高。
2 NewGrow算法
将改进的Grow算法命名为NewGrow算法,NewGrow算法考虑了AE的大小,对Sp-add算法扩张之后P圈的AE进行排序,引入参数K(K代表备选圈中选取的AE较高的P圈个数)。按照AE的大小对K个P圈继续进行扩张,这样可以避免将AE不高的P圈也进行扩张,在减少工作量的同时也提高了P圈的整体性能,使构造出的备选P圈更为优良。NewGrow算法流程如图4所示。
3 算法的仿真结果和性能比较
仿真采用COST239网络拓扑模型(11个节点,26条边),如图5所示。
使用MATLAB软件对COST239网络拓扑进行仿真。通过K值的选取,将NewGrow算法最终构造的P圈质量与Grow算法进行比较,验证New-Grow算法的性能。
图6所示为两种算法P圈个数对比。由图可见,NewGrow算法构造的P圈个数明显少于Grow算法,网络节点负担较轻。图7所示为两种算法平均AE对比。由图可见,当K值取1或2时,New-Grow算法构造出的P圈平均AE要高于Grow算法;当K值取3~5 时,NewGrow算法构造出的P圈平均AE要小于Grow算法。图8反映了当K值为2~4时,NewGrow算法构造的P圈平均覆盖度要高于Grow算法,其中当K值取2时,圈的平均覆盖度最大,表示该P圈提供的保护范围广,性能最好。由图9可知,当K值取1~3时,NewGrow算法构造P圈的单位代价平均AE高于Grow算法。综合图6~9,可判断出当K值取2时,即对AE较高的前两个P圈继续进行扩张后得到的备选圈组的性能要优于Grow算法构造的备选圈组。
4 结束语
本文对光网络中P圈构造算法进行了改进。针对应用较广的Grow算法存在的不足,提出了一种改进的NewGrow算法。NewGrow算法在对圈进行扩张时,以AE作为依据,对AE高的P圈进一步扩张,舍弃AE较低的P圈,提高备选P圈组的整体质量。仿真结果表明,当K值为2,即对备选P圈中AE较高的两个P圈进行进一步扩张后得到的P圈组,整体性能要优于经典Grow算法。
参考文献
[1]Grover W D,Stamatelakis D.Cycle-oriented distributed preconfiguration:ring-like speed With mesh-like capacity for self-planning network restoration[C]//ICC 1998.Atlanta,GA:IEEE,1998:537-543.
[2]Grover W D,Doucette J.Advances in optical network design with p-cycles:Joint optimization and pre-selection of candidate p-cycles[C]//IEEE LEOS Summer Topicals Meetings 2001.MontTremblant,Quebec,Canada:IEEE,2002:49-50.
[3]姚晓宇,徐荣青,李亚玲.一种基于P圈的启发式构造算法的研究[J].光通信技术,2010,34(9):16-19.
[4]张沛,邓宇,黄善国,等.WDM网络中p圈保护算法[J].北京邮电大学学报,2007,30(1):127-131.
[5]江雪敏.WDM光网络及多层网络生存性的研究[D].成都:电子科技大学,2007.
[6]ZHANG H,YANG O.Finding protection cycles in DWDM networks[C]//ICC 2002.New York,USA:IEEE,2002:2756-2760.
[7]Doucette J,He D,Grover W D,et al,Algorithmic Approaches for Efficient Enumeration of Candidate pCycles and Capacitated p-Cycle Network Design[C]//DRCN 2003.Edmonton,Canada:IEEE,2003:212-220.
改进启发式算法 篇2
一种基于启发式算法的等高线局部内插方法
在基于启发式内插等高线算法的`基础上提出了一种局部内插方法.首先利用Douglas-Peucker算法提取等高线的特征点,根据特征点判断等高线之间的相似性程度,找出导致等高线出现异常的特征点;然后将相似性程度很低的两条等高线自动分解为若干简单等高线再进行内插.有效地解决了局部弯曲很大、马鞍型地貌等复杂等高线的内插问题.算法已经在以Microstation为平台的数字制图系统中实现并逐渐实用化.
作 者：安晓亚 孙群 肖强 赵国成 AN Xiao-ya SUN Qun XIAO Qiang ZHAO Guo-cheng 作者单位：信息工程大学,测绘学院,河南,郑州,450052刊 名：测绘科学技术学报 PKU英文刊名：JOURNAL OF GEOMATICS SCIENCE AND TECHNOLOGY年，卷(期)：25(1)分类号：P208关键词：先验知识 等高线 局部内插 自动分解
改进启发式算法 篇3
早期的流水作业调度研究多采用数学规划的方法, 如整数线性规划和分支定界法。此类最优化方法对于大规模的工件调度问题不现实。Johnson提出了一种双机或三机多工件流水作业调度的最优化算法。Johnson算法为后来的多台机器问题的启发式算法提供了基础。从实用的角度来看, 启发式算法因其易于实现、计算复杂度低等原因, 在实际中得到了比较广泛的应用, 并且不断涌现出许多新的调度规则。启发式算法可分为三类:简单规则、复杂规则、启发式规则。启发式算法的缺点是一般不具有全局优化的特点。比较好的启发式算法包括:CDS启发式方法、Palmer启发式方法、快速进入启发式方法 (RA) 和NEH方法等。文章所解决的问题是传统的流水作业调度问题, 目标函数为最小化完工时间。鉴于所涉及的复杂性, 更实际的方法是使用调度规则和启发式算法, 如先入先服务, 后入先服务, 以及快速进入等。笔者改进了快速进入启发式算法以提高原算法的求解质量。
1 快速进入启发式算法
快速进入 (Rapid Access, RA) 启发式方法由Dannenbting在1977年提出, 和其他很多启发式算法相似, RA启发式方法也是受到了Johnson算法的启发。Johnson算法通过下列简单的规则给出了2台机器流水调度的最短生产周期的产品序列。假设有n个工件, 在第一台机器和第二台机器上的加工时间分别为ti1, ti2, i=1, …, n, 其最优调度由下列Johnson规则确定。
如果min{ti1, ti2}≤min{tj2, tj1}, 则将工件i排在工件j之前。直接利用这个规则构造最优调度, 具体步骤为:一是将n个工件分成P和Q两组。分组原则是, P组工件在第二台机器上比在第一台机器上加工时间长的产品, 其余的产品归Q组。二是将P组工件按他们在第一台机器上加工的时间递增顺序排列, 将Q组工件按它们在第二台机器上的加工时间递减顺序排列。三是将P组工件顺序和Q足工件顺序连接在一起, 构成的就是生产周期最短的最优产品顺序。
RA启发式方法用Johnson规则求解一个模拟双机问题, 其工件的虚拟加工时间按下式确定
其中, 权重定义为
例如, 设n=4, m=3, 即4个工作在3台机器上的排序。各工作在各机器上的加工时间见表1。
根据式 (1) 、式 (2) 和权重表达式 (3) 、式 (4) 计算各工作在2台虚拟机上的虚拟加工时间。利用2台虚拟机上的虚拟加工时间用Johnson方法求出排序 (见表2) 。最终的排序结果为工作2→工作1→工作3→工作4。
2 改进的快速进入法
原来的RA启发式方法采用线性加权法构造虚拟机上的工件加工时间, 虽然易于实现但缺乏灵活性。笔者尝试使用非线性加权以提高结果的质量。这个改进算法加强了RA启发式方法中线性权重函数描述的趋势, 同时平衡了不同工序复杂度工件的优先级, 并且通过引入一个可变参数α使得此方法更具灵活性。针对不同具体问题, 通过优化该参数可以对算法质量进行调整和进一步提高。
改进方法使用指数平滑的方法创建两个虚拟机上的处理时间。改进后的权重定义为
使用改进方法求解表1中的调度排序过程和结果见表3。在此例中, 改进算法得到的结果和原算法相同。
3 实验结果及讨论
该实验使用来自文献的12组不同规模的实例测试改进算法的性能, 实验结果同时与原RA算法进行比较。通过比较不同算例的启发式算法结果与文献中已知最优法得到结果的相对差异百分比来评价改进方法和RA方法的性能优劣。
改进方法和RA方法的比较结果见表4。在进行比较的12组实例中, 算法性能结果最大改进率可以达到29.8%, 平均改进率为12.7%。
4 结束语
改进启发式算法 篇4
目前,相关文献中已提出一些启发式方法,用来解决网络寿命的问题。例如,文献[7]中提出最大化剩余包容量( Maximum Residual Packet Capacity,MRPC ) 最大化WSN寿命方法,它不仅依赖节点的剩余电池能量,且依赖于特定连接上转发包的期望耗能; 文献[8-9]提出基于一段时间内路由消息的数量的容量最大化( Capacity Maximization,CMAX) 方法,启发式的根据链接权重选择每个消息的单路径( 非多路径) ; 文献[10-11]提出启发式在线最大化寿命( Online Maximum Lifetime,OML) 方法,用来计算路由中每个消息的最短路径; 文献[12]提出通过将节点的能量分割为两部分来延长寿命的高效路由协议管理技术( Efficient Routing Protocol Management Technique,ERPMT) 等。大多数启发式能量管理路由方案存在的主要问题是: 它们均通过寻找到最低能耗路由并使用它进行每次通信,但频繁地采用低能耗路径会导致路径上节点的能量消耗过大,尤其是靠近汇聚点处的节点,并且当传感器节点停止运行时会导致网络的分割[13,14],导致网络盲区的存在。
针对上述问题,提出一种基于ERPMT改进启发式方法的无线传感网络寿命最大化算法,并可与其他已有启发式路由算法一起使用。实验结果表明,本文算法在实际应用中较明显地提高了无线传感网络的寿命和覆盖率。
1 WSN数学模型
无线传感器网络可以用一种有向连接图进行表示[15]: G = ( V,E) ,其中V是节点集合,E是节点间边集,如果节点u和v在各自范围内,那么存在节点u到节点v的有向边,如( v,u) ∈E。该模型可用来表示无线传感器网络( WSN) 。对于每个( v,u) ∈E,在传感器u到传感器v的单跳传输情况下, 传感器u现有能量ce( u) 可表示为
式中: ce( u) 是传感器u现有能量,并且满足ce( u) ≥w( u,v) > 0,w( u,v) 是完成传感器u到传感器v的单跳传输所需能量, w( u,v) > 0。同理,假设消息接收过程中,接收节点不消耗能量。因此传感器v现有能量不受u到v传输的影响。这里将能量分为两部分,一种是数据起源节点( α) ,另一种是其他节点( β) 的中继。若数据起源于节点本身,它会使用来自第一部分的能量; 否则它会使用另一部分能量。
一种邻接矩阵可用来表示WSN有向图,n个顶点的确切有向图G的邻接矩阵是n × n阶矩阵,当非对角数字满足 α( i,j) = 1时,表示传感器i到传感器j边的存在。这里的对角线数字 α( i,i) 设置为0,原因是本文假设WSN中没有内部循环存在。
每张图只存在一个唯一的邻接矩阵。例如,图1a为传感器网络S一种简单的表示。使用一种有向图,表示的节点是传感器,边代表传感器节点间存在边。图1b展示了图1a模型化后的传感器网络S的邻接矩阵。很显然图1b描述了一种已经完成的网络,它采用一维来表示传感器。
多数表示传感器的位置和连接性的研究使用了一个来自均匀分布的随机数。在平坦地区环境下使用均匀分布更好, 因为传感器可以按照图2所示来进行分布,但是真实环境通常由地形特征化,如在高山和深海情况下的传感器部署。在这种情况下,均匀分布没有给出能匹配地形变化的一种好的真实感。因此,使用泊松分布更好,因为它最适合非对称环境。图3显示了基于泊松分布的传感器分布,很明显传感器聚集在平均值周围。这种部署模仿了一种S靠近山谷地形、 通过飞机的分布。
一种传感器部署的例子是雪崩预测[3],为了实现全覆盖, 山形地区描绘了传感器部署中所有的挑战。为此,部署策略对于评估一个路由启发式有一个主要影响,这是由于真实环境下的地形变化所引起的。图4描述了典型环境下的风景, 如平原、山顶、悬崖、山谷。为了在不同的路由协议间作公平比较,应该把主要的注意力放在部署策略上,该因素可以通过产生随机图的方式加入考虑,该图同时会仿真位置和连接性, 最后会仿真传感器连接方式。
为决定节点间的连接性,使用一个等于网络节点维数的平均数阈值。当所有网络节点3维( X,Y,Z) 的平均欧几里得维数的3D部署情况下,所有节点通过比较其x,y,z进行递归检查。对于一维情况,仅考虑X维。每个节点的一维值大于或等于相同维数的平均值会认为是连接的,否则认为是未连接的。
2启发式优先级路由算法提出
学者们通常利用CMAX[8,9]和OML[10,11]两种不同的启发式方法来延迟网络的寿命,基于这种思想,本文将ERPMT算法与这两种成熟的启发式方法混合使用。
2.1基于CMAX启发式的ERPMT
第一种启发式方法为基于CMAX的ERPMT,称为ERPMT_C,是与CMAX算法的混合改进。
假设目前每个传感器的能量分为2部分,第1部分是为传感器起源数据( α) 供能,第2部分是其他传感器的中继耗能( β) ,对每个路由有3个步骤。
1) 第1步,初始化
对于每条边的传感器,若没有足够的能量完成单跳传输将会被从图中删除。然后每条剩余的连接根据式( 2) 分配一个权重
式中: λc是启发式参数; a( u) 为已经花费在传感器节点上的百分数,即
2) 第2步,最短路径
计算改进图的源节点到目的节点的路径,如果没有找到路径,则请求失败; 否则,除非路径大于特定阈值 σ 才使用。
3) 第3步,优先级最高的路径选择
分配一个优先级数,它的大小依赖于路径的个数,优先级数的设置取决于路径的平均能量。此外,通过大量的仿真可知,靠近汇聚点的节点耗能较快,因此,将这些节点从计算中去除。因为去掉了那些离汇聚节点只有一跳的节点,所以只选择那些在汇聚节点范围内至少含有一个节点的路径。如果在汇聚节点范围内没有节点,需要加入一跳节点到计算路径中。
2.2基于OML启发式的ERPMT
第二种启发式为基于OML的ERPMT,假设每个传感器的能量分为两部分 α,β。然后对于每个路由请求ri= ( si,ti) , 执行下面两步:
1) 第1步,计算G″
删除G中所有的边以致ce1( u) 或ce1( u) ≤w( u,v) ; 因为这些边对于一个单传输需要更少的能量。结果图是G' = ( V, E') 。决定图G'中从si到ti的最小能是通过一个基于Dijikstra算法的最短路径算法实现的。如果不存在源节点s到目的节点t的路径,则路由请求失败,但是如果路由请求存在, 就利用P'计算剩余能量
接着图G″ = ( V,E″) 可以通过删除E'中所有满足ce1( u) 或ce1( u) - w( u,v) < minRE的边( u,v) 得到。作为一个结果,所有剩余能量低于( minRE) 的边将从图中删除,这样可以避免能量低的传感器的能量减少。
2) 第2步,寻找用来路由请求r的路径
从G″开始,分配权值到E″中的每条边( u,v) ,这样做平衡了最小化总消耗能量的要求和避免传感器能量消耗的要求。
定义e Min( ) 为在图G″中传感器u传输一个消息到最近邻节点所需要的能量
现在,定义( u,v) 如下
其中,符号c是非负常数,它是一个算法参数。在V中每个u的a( u) 定义为a( u) = minRE/ce1( u) 或者ce1( u) ,分配到每条边的权重w″( u,v) 为
其中,λc是另一个非负常数算法参数。
可以看出,通过 ρ 分配高的权重到在路由路径上的边会导致传感器剩余能量降低。
同样,基于此,目前能量比minRE小的传感器散发的所有边将分配高权值。因此,权重函数阻止了在路由路径上的使用,这样会导致一个未来路由的失败。最后,寻找图G″中的最短路径 ρi″,利用它从s到t进行路由。
3实验
实验使用MATLAB7. 0完成,在3. 20 GHz处理器、 2 Gbyte内存的机器上运行,操作系统是Windows XP SP3。
3.1参数设置
OML和CMAX是采用基于均匀分布的新能量管理技术 ( ERPMT) 完成的。在10个网络中,20个传感器是基于均匀分布随机部署。根据文献[16]可知,两个传感器间的距离为d时,两传感器间单跳传输所需能量假定为c = 0. 001 × d3。 若本实验中每个传感器的传输半径和初始能量分别设为5 100。两传感器间距d和传输半径rT存在如下两种关系
即间距超出传输半径,所需传输能量无穷大,信号无法传输。
3. 2实验结果
仿真结果显示了在网络寿命的不同类型上,采用该能量管理技术的效果。
1) 贡献能量少于或等于 α 对应的 β。
即为 α≤β 时的平均寿命,设 α 为50% ,40% ,30% ,20% 和10% 。
随机部署一个有20个传感器的网络。图5描述了OML和ERPMT_O( 基于ERPMT的OML) 启发式的10个含有20个传感器的网络平均寿命。显然当采用ERPMT技术时,网络使用寿命均增加了。
当采用CMAX时,具有相同的变化规律,如图6所示。 正如文献[8]在前期的研究中发现CMAX算法的寿命比OML算法要短。
2) α 相对于 β 消耗更多的能量
即为 α > β 时的平均 寿命,设 α 为60% ,70% ,80% , 90% ,100% 。
图7显示了应用在OML上的ERPMT( ERPMT_O) 的结果。很明显,随着传感器自己产生数据的专有能量升高时,寿命降低。寿命的降低是提高 α 的值超过总能量的50% 的结果。也就是说,一个节点寻找一个到达路由的路径的概率下降时,网络的寿命也降低。
图8显示了相同的实验结果,但是本文使用的是基于CMAX的ERPMT( ERPMT _ C) 。应用相同的结论,但是前面讨论的CMAX更少受到 α 值改变的影响,因为CMAX启发式的稳定性。
3.3比较及分析
表1描述了采用式( 8) 时,OML算法与ERPMT_O算法的寿命百分数差。需要注意的是,如果结果是负的,表示寿命减少,否则寿命增加。当 α≤ β 时,ERPMT_O寿命相对于OML提高了79% 。
表2描述了CMAX与ERPMT_C之间的寿命百分数差。 当 α≤β 时,ERPMT_C寿命相对于CMAX提高了61% ,ERPMT_C相对提高了45% 。
表3显示了OML与ERPMT_O之间的寿命百分数差。 当 α≥β 时,ERPMT_O相对于OML提高了61% ,ERPMT_O相对提高了76% 。当 α = 60% 时,ERPMT_O的寿命优于OML 18. 3% ,当 α = 70% 时OML的寿命优 于ERPMT _ O 17. 9% ,由此可见,α 的升高意味着网络寿命的降低。
表4显示了CMAX与ERPMT_C之间的寿命百分数差。 当时,ERPMT_C寿命相对于CMX提高了47% ,ERPMT_C相对提高了46% 。
基于前面的结果,表5显示了当 α≥β 和 α≤β 时,相对于两种熟知的启发式法( OML和CMAX) ,所提启发式ERPMT的寿命提高率。
很明显,当 α≤ β 时,ERPMT分别胜过OML和CMAX 61% 和78% 。对于 α≤β,它表示其他节点数据传输相对于自己需要消耗更多的能量。通过分别采用OML和CMAX的大量仿真实验,可以看出贯穿WSN寿命N1,N2,…,Nm跳节点的能量值,其中Ni是离该节点i跳的传感器节点,m表示节点的总个数。总之,WSN生命的终结是因为离汇聚节点只有一跳的节点能量耗尽。当使用ERPMT时就转换了转发聚集数据到中间节点的负担( 如N1< l < Nm - 1,其中l是到汇聚点的跳数) 和使用高优先级的Pi是一样的。
4结束语
针对WSN的应用中传感器节点电池容量限制导致的网络寿命较低的问题,基于常用的启发式在线最大寿命算法和容量最大化算法,提出了一种基于启发式路由能量管理的高效优先级算法。实验结果表明,所提算法在性能上与CMAX及OML算法相比,寿命百分比差分别提高59% 和43% 以上, 并且CMAX和ERPMT混合算法比OML和ERPMT混合算法,使用寿命提高47% 以上,显示了所提算法的有效性及可融合性。
启发式库存-路径问题求解算法 篇5
集成化物流管理ILM(integrated logistics management)是一种近年来才发展起来的新的物流战略管理模式,其主张将所有的物流活动整合在一起视为一个完整的系统,并在理想的客户服务水平下追求总成本最低[1]。
库存-路径问题IRP(inventory routing problem)是在如何联合优化配送和库存这两个往往被独立考虑的物流环节的现实需求推动下成为崭新的研究领域,是企业节能增效的重要途径。库存路径问题是对一系列已知需求量的客户,组织适当的行车线路进行服务,在不违反任何约束条件下,优化路线使得总成本达到最小。有效地解决该问题可以提高车辆的利用率,降低配送成本,提高配送时间的准确率,从而提高物流服务水平。由于库存路径问题是典型的NP难题,使用传统的优化方法很难得到问题的最优解或满意解,因此构造高质量的启发式算法成为研究该问题的主要发展方向[2]。
国外IRP研究最早出现在20世纪70年代。2000年以前的IRP文献主要研究单周期、一对多、单品种、确定需求情况,通常给定车辆数或不限,决策方式则集中在确定固定的配送频率,目标只考虑客户库存成本(一般不考虑中心库存成本)。求解时,采用“分区—路径” 分解问题或者沿用EOQ(Economic Order Quantity)思路占绝大多数,寻找合适的求解方法一直是研究热点、重点和难点。2000年以来,在继续构建高效率求解方法的同时,IRP本身的研究得到了深入,随机需求IRP、三层级IRP、取送结合IRP受到更多研究的重视[3]。
SPERANZA等运用实例证明了建立混合整数规划模型较建立纯整数规划模型的优越性[4]。
CHIEN等也讨论了单周期的IRP,他们所研究的配送系统包括一个有固定供应能力的中心仓库和多个有确定需求的客户,供方可以不满足部分客户的需求,但必须对未被满足的需求支付惩罚费用,建立了一个混合整数规划模型,采用基于拉格朗日松弛的求解过程来获得理想的上界[5]。
DROR等则研究了多周期IRP,侧重于如何将长时段(如每年)的多周期问题简化为短时段(如每天)的单周期问题。通过引入惩罚因子和激励因子来反映相邻周期决策的相互影响,并且建立了相应的混合整数规划模型[6]。
BLANCHINI等在建立随机动态规划模型时将单品种、多对多的物流系统看成是一个网络[7]。
国内IRP研究文献出现在2001年以后,但论文数不多,研究工作尚处于起步阶段。
奚飞等人通过综合考虑零售商订货周期与供应商订货周期之间的大小关系,最终寻求一种最优的IR策略,从而使整个供应链的成本最小[8]。
武秀焕等人将随机IRP描述为一个马尔可夫过程MDP(Markovian decision process),根据客户数量将问题分解成N个子问题进行MDP描述,接着对状态转移矩阵进行模拟,并对每一个MDP子问题进行求解,然后运用非线性背包问题的求解方法得到IRP的初始策略来构成直接配送路线,并在此基础上构造了一种基于搜索算法的启发式算法对初始策略进行优化,得到最终的优化解[9]。
沈飞等人将IRP问题分成两个子问题:一个能够使库存储存费用最小的线性规划和在基于模拟退火理论下生成并评估可选择性组合路线的分路线排除约束函数(the route perturbation routine)。一旦确定运货车的路线,混合整数规划(MIP)就转化为相对容易解决的线性规划,这样便能在给定的路线组合中寻找到解决库存问题的最优方案[10]。
目前国内对IRP的研究都是假设产品为单一品种。本文考虑多品种、多供应商对多客户的IRP问题,使用启发式算法选择最优的可选择的组合线路,逐步生成满意解。
1模型的建立
1.1模型假设
(1) 所有产品都能在1天内送到,即不考虑配送时间。
(2) 运输成本以整车为单位计算。通常运输成本包括:过路费、油费、人工工资、各种损耗。对于确定的运输线路和运输工具,则过路费、人工工资、其他损耗可以估算出来,油费与运输距离、货车自重、载货量成正比。
(3) 只考虑产品重量,忽略产品体积,是否易燃易爆等因素对运输费用的影响。
(4) 不考虑产品装卸费用和库存成本。
(5) 货车可以有多种类型,每种货车的自重、最大载货量、固定费用不同。
(6) 只考虑点对点运输,即货车到达目的地之后,必须将所有产品全部卸下。货车数量不受限制。
(7) 任意2节点之间存在直达线路。节点之间直达线路长度为最短,比经过任何节点中转都要短。
(8) 货车必须在当天返回出发点。即货车运输路线形成汉密尔顿圈。
1.2模型的建立
设有n个节点ai,m种产品Bj,节点之间直达距离为Dij,节点产品库存为Sij,节点产品需求为Eij。
设运输费用为:
其中,F为固定费用(与货车类型有关),d为运输距离,Z为货车自重,w为载货量,u为费用系数(需事先估计)。
每辆货车的运输路线形成汉密尔顿圈,设运输路线经过k个节点,则该运输线路可表示为:L(a1,a2,…,ak,a1)。
1.3目标函数
令恰好满足所有节点产品需求的货车运输路线集合为Q={L},相应的总运输费用为:
P=∑c(Li) Li∈Q (2)
则系统目标函数为求总运输费用最低的集合Q′,即:
P(Q′)=min{P(Q)} (3)
约定:
di,t=时间段t内配件i的需求量,i=1,2,…,m;
t=1,2,…,T;
K0=仓库和装配车间的距离;
K1=仓库和最近供应商间的距离;
K2=装配车间和供应商间的距离;
K=K0+1/2K1+1/2K2;
Ci,j=供应商i与j之间的行车距离,i和j=0,1,…,m+1;
hi=配件i的库存存储成本i=1,2,…,m;
Ii=配件i的初始库存量i=1,2,…,m;
C=货车的装运量;
L=线路的最大长度。
设:
qi,t=时间段t内在供应商i处的装运量;
si,t=时间段t内在配件i的库存水平。
于是有:
s.t
qi,t≥yi,t ∀i,∀t (5)
pi,t≤qi,t ∀i,∀t (6)
si,t+1=si,t+pi,t-di,t ∀i,∀t (10)
si,0=Ii ∀i∈{1,2,…,m} (11)
si,t≥0 ∀i,∀t (12)
yi,k,t,pi,k,t∈{0,1} ∀i,j∈{0,1,…,m+1},∀k,∀t (13)
因此,目标函数(4)包括的成本项目有访问供应商的成本之和,库存存储成本,出行设置成本。而约束条件式(5)至式(7)将变量yi,t与装运数量联系起来,约束函数(9)限定了每条线路都小于或等于最长线路L,约束条件式(10)为库存平衡等式,约束函数式(14)对一辆货车能够装运的载运量进行了限定。
2启发式求解算法
Q′为汉密尔顿运输路线集合,根据贪婪法则,总能找到当前单位运输成本最低的汉密尔顿运输路线,则有算法如下:
(1) 系统初始化。
(2) 根据需求计划及库存,找出所有可能的点对点运输线段。
(3) 找出使运输线段连接成汉密尔顿圈的所有组合。
(4) 对于p种货车,分别计算汉密尔顿运输线路及其成本。
(5) 找出运输成本最低的汉密尔顿运输线路,记录该线路。
(6) 根据该线路选择具体的运输方案,并在运输源节点的库存中减去已计划运输的产品,及在目标节点的需求中减去已计划运输的产品。
重复(2)—(6),直到没有任何可能的点对点运输线段。得到的配送方案集合即为最优运输方案。
3算例分析
为验证算法的可行性与有效性,编制程序验证本文所提出的模型与算法。
算例来源于模拟现实生活。基本数据为9个节点,9种货物,货车自重1500千克,最大载货量4000千克,固定费用200元,费用系数为4500,节点之间平均间距为153.3千米,每个节点存有多种产品,平均每个节点存有4.89种产品,节点平均库存量为4137.4千克。节点的产品需求数随机产生,多次运行算例结果如表1所示。
由表1可以看出:单位产品运输成本平均为0.06883元/千克,货车平均载货量为2416.99千克,平均货车运输效率为60.425%,空驶率平均为14.785%。而我国物流运输车辆的空驶率达37%[11]。
为验证算法的可行性与有效性,本文将应用所提出的模型与算法所得出的计算结果与其他启发式算法进行比较。
若利用集合覆盖型等式,由于该等式限制了路线的长度,能够最优解决的IRP 的最大容量是6 个供应商和7 个时间段。最优总成本是1354.70 元(存货成本=97.80 元,运输成本=1256.90 元)。
若利用本文所提出的启发式算法程序解决相同的问题,总的成本是1370.43元(存货成本=118.2 元,运输成本=1252.23元)。最优解和利用启发式解法得到的解的直接数值间隙是1.15%。同时即使供应商的数量大于100 和多个时间段的问题时也是有效的。因此本文提出的模型与算法不仅具有可行性而且在所求解问题的规模上具有先进性。
通过对比可知,本文提出的启发式多产品库存路径算法大大降低了货车的空驶率,有效地提高了货车运输效率,从而降低了运输成本。
4结语
(1) 本文重点介绍了库存路径问题的启发式算法研究,分析了关于库存路径问题的模型建立和解决过程。
(2) 探讨了以贪婪法为基础的启发式算法,采用的策略是每次选取平均运输成本最低的汉密尔顿运输路线。
(3) 模型仿真结果表明,本文提出的启发式多产品库存路径求解算法生成的物流运输方案高效,成本低廉,有广泛的应用前景。
参考文献
[1]Kenderdine D J,Larson P D.Quality and Lo-gistics:A Framework forStrategic Integration[J].International Journal of Physical DistributionandMaterials Management,1988,18(7):5-10.
[2]陈雪瑛.基于启发式算法的库存路径优化问题研究[D],北京交通大学,2008.
[3]傅成红,符卓.库存路径问题及其最新进展[J].计算机应用,2010(2):453-457.
[4]Speranza M G,Ukovich W.MinimizingTransportation and InventoryCosts for Several Products on A Single Link[J].Operations Re-search,1994,42(5):879-894.
[5]Chien W,Balakrishnan A,Wong R.An Integrated Inventory Alloca-tion and Vehicle Routing Problem[J].Transportation Science,1989,23(2):67-76.
[6]Dror M,Ball M.Inventory Routing:Reduction From an Annual to AShort-period Problem[J].Naval Research Logistics,1987,34(6):891-905.
[7]Blanchini F,Queyranne M,Rinaldi F,et al.A Feedback Strategy forPeriodic Network Flows[J].Networks,1996,27(1):25-34.
[8]奚飞,周永务.基于固定分割的库存路径问题最优策略[J].系统工程与电子技术,2009(10):2389-2993.
[9]武秀焕,李延晖.马氏过程的随机库存路径问题模型与算法[J].工业工程与管理,2009(1):66-70.
[10]沈飞,管小俊,于雅岑,等.基于模拟退火理论求解库存路径问题的模型与算法研究[J].物流技术,2009,(2):74-76.
改进启发式算法 篇6
在物流中心的各项活动中,分拣是最为重要的一项活动, 其成本约是整个中心运营成本的50% ~ 65%[1],分拣的效率不仅关系到整个运营的成本还直接影响到客户服务水平。而订单分批通过将多个订单合成一个批次或更大的订单以提升拣选设备的利用率并减少工作量,使得分拣过程得以更有效的实施。随着订单数目的增加,可行批次的数量以及决策变量的数量呈指数增长,许多基于最优化算法的研究都具有比较大的局限性,所以采用启发式算法解决订单分批问题得到了广泛的共识。早期的研究主要凭借以往的经验对订单分批过程进行优化。例如对客户订单按照某种事先确定好的优先级进行分批,先到先服务( First Come First Serve,FCFS) 准则是其中最常用的一种。Elsayed[2]在1981年提出种子算法的概念,该算法对每个批次选定一个种子订单,余下的订单将按照某种配对原则添加到批次中。Ho和Tseng[3,4]等对种子的选取规则以及订单配对原则的选取进行了深入的研究。李诗珍对种子算法以及节约算法进行了初步的探讨[5,6]。Elsayed和Unal[7]在节约算法的基础上提出了一种有效的算法用于求解订单分批问题,通过比较每两个客户订单合并后的路程节约量进行分批,从节约量最大的订单对开始,余下的订单对按照节约量非增的顺序被分配到下一批次中,每次分配订单的时候都重新计算节约量。
综上所述,订单分批问题的求解方法是国内外研究的重点,一些经典的启发式方法如先到先服务,种子算法,节约算法在实际中得到了广泛的应用,这些算法的特点是直观易行并且计算快速,常用来求得问题的初始解或作为检验新算法有效性的基准。本文提出一种降批次启发式方法,并与经典的算法进行比较。
2问题描述和模型建立
订单拣选可以说是物流中心最耗费时间的作业,根据以往的经验,减少拣选所花费的时间能够有效节约人力成本。 同时,拣选时间是交付提前期的重要组成部分,减少拣选作业时间能减少客户订货周期从而提升客户服务水平。
当客户订单到达,为了完成客户订单所指定的物品的拣选,拣货人员需要花费的时间也被称作订单处理时间,其中行走时间对整个订单处理时间的影响最大。假设拣货人员在拣货过程中采用匀速行走,减少行走时间可以等效为减少总的拣选路程。
订单分批是这样一个过程: 待拣选的物品被安排到每一次往返于仓库的行走过程中,每次往返拣选一方面受限于拣选设备的容量,另一方面也取决于订单所包含品项占用的空间大小。客户订单尽量被安排到一次拣选路程中直到拣选设备的容量被用尽为止,这些需要在一次往返路程中完成的订单为一个批次。许多文献中拣选设备容量有不同的意义,即可以指订单的数目也可以是物品的数目,本文指的是物品的数目。综上,订单分批问题可以描述如下:
对于给定的拣选设备容量以及路径策略,如何将客户订单以及所要求的有固定储位的待拣选物品分批在一次往返拣选中完成从而使得所行走的路程最短?
本文采用Gademann和van de Velde[8]提出的订单分批模型,该模型具有简洁直观的特点非常适合用来进行订单分批问题的探讨,该模型明确考虑到每个可行的批次,设订单集合O有n个订单需要拣取,每个订单中含有一定数量的物品,并设B为可行的批次集合,可以建立如下数学优化模型:
目标函数:
约束条件:
式中
O———客户订单的集合,O={1,2,…,n};
C———拣货车的容量;
B———所有可行批次的集合;
cj———第j个订单中所有品项的数量;
di———拣取第i批次订单中的所有物品所行走的总的路径值;
xi———二进制决策变量,如果第i个批次被选中则xi= 1, 否则xi= 0;
ai= { ai1,ai2,…,ain} 表示第i批订单的订单组成,aij= 1表示第j个订单在第i个批次中。
该模型要求每批次订单在一次往返拣选路径中完成,以使得所有批次总的拣选路程最短。约束条件( 2) 保证了每批订单所包含的品项数不超过拣货设备的容量,约束条件( 3) 和( 4) 则保证了每个订单必须且只能被分配一次。
3路径策略下的计算方法
上述优化模型的目标是最小化拣选路径,对于启发式算法的评估依赖于相应的路径策略,由于具体选择哪种路径策略并不会对评价分批结果的好坏产生影响,本文的算法采用S型路径策略。在实际应用中,S型路径策略是最为常见的,采用S型路径策略计算拣选路程不仅直观而且易于实现。本节讨论一种S型路径的计算方法,该方法灵活易于扩展,而且最为重要的是不影响我们对订单分批问题的讨论。一个典型的单区型无交叉走道的货架摆放如图1所示:
则捡货人员在拣选过程中通过的路程可近似计算如下:
其中:
LENGTH_OF_RACK:货架(走道)的长度;
WIDTH:货架的宽度;
CONER:拣货人员到达通道尽头的转角距离;
Nl:人员通过的走道数目;
Nc: 拣选设备转过拐角的数目;
Nw: 拣选设备通过货架两侧的次数即通过货架宽度的次数;
Last: 拣选设备通过的最远的通道数。
λ 的取值取决于需要穿过的通道的数目,当需要穿过的通道数目为奇数时,拣货人员需要多穿越一次。值得注意的是,当拣货员通过的最远通道数为一即只有第一个通道有货物需要拣选时,最好拣选方法是返回策略即拣完最后一个货物就返回,本文在此进行了简化,认为此时拣货员需要通过整个通道再返回,即:
D = LENGTH_OF_RACK + CORNER。图2表示当Nl = 2, last = 3时路程的计算情况,蓝色的方块表示拐角被计算一次, 红色的方块表示货架宽度被计算一次,粉色的区域表示走道被通过。
4启发式分批算法
4. 1根据优先级规则进行分批
通常拣货员在进行拣选作业之前会对订单进行简单的分类,比如按照时间顺序,品项数目多少的顺序等,然后对这些订单按照某种规则制定拣选的优先级,先到先服务( FCFS) 是最常用的一种基于优先规则的分批算法,FCFS按照订单到达的顺序对订单进行分批。
4. 2种子算法
种子算法自从1981年被Elsayed提出,种子含有“最初” 的意思,即种子订单是每个批次的初始订单。种子算法是一种连续生成订单批次的方法,因此,初始批次的选取对后面的分批有很大影响,种子算法进行分批主要有两个过程: 一是种子订单的选取; 二是根据订单的相似度进行配对。使用种子算法进行订单分批,首先对初始批次选择一个种子订单,然后按照配对原则从剩余订单中选出一些订单加入该批次,加入时要考虑拣选设备的容量,如果当前批次无法容纳更多的订单,则考虑一个新的批次直到所有订单都在某个批次内。
4. 3节约算法
种子算法忽略了与具体目标函数的联系,使得算法性能具有某种不确定性,节约算法通过计算每两个订单合并后路径的节约量来匹配订单,所有订单间的路径节约量被存放在一个被称为节约矩阵的矩阵里,其行和列均代表订单的编号, 索引为( i,j) 的元素表示第i个订单与第j个订单合并产生的节约量。节约算法的思想来自于Clark和Wright对车辆调度问题的研究,每次将订单安排进某个批次就对节约矩阵进行更新,使得批次中的订单与剩余订单重新计算节约量,这样剩余订单更可能选择那些能获得最大节约量的批次加入。
4. 4降批次启发式算法
本节根据订单分批问题的特点提出一种降批次算法用于求解分批问题。在分批问题中,订单的分批数量是影响优化结果的一个关键性的指标,分批数量越少则结果可能越好,每个批次在一次拣选路径中完成,则越少的批次意味着越少的拣选次数,拣选的总路程也相应更少。受拣选设备容量的限制,理论的最小批次数为订单集合的物品总数与拣选设备容量的比值,一般要在理想情况下才能取到这个值。降批次算法正是出于上述考虑提出的,该算法的过程如下所述: 首先将一系列订单进行排序,排序将订单按品项数从大到小排列。然后依次将订单放入每个批次中,第i个订单放入第i个批次,批次的数量等于订单的数量,然后依次对最高的批次进行降批即逐步减少批次数量,将高批次数中的订单放入任意低批次中并检查是否满足约束条件,如果不满足则将其作为一个独立的批次,重复上述过程直到无法再进行降批次操作算法停止。
降批次算法不同于前面几种方法,无论FCFS还是种子算法或是节约算法均是采用连续产生批次的方法,降批次算法采用一种逆向的思路,先将订单分成批次,然后对批次的内容进行调整,相当于每个订单都是一个种子,从而减少了选择种子的过程。
5启发式方法求解性能比较
考察上述启发式方法在不同订单集合下的优化性能,通过设置不同的订单数量测试算法的适应性,对FCFS算法、种子算法、节约算法和降批次算法进行了比较,其中种子算法选用最小通道数目的选择策略和随机的匹配策略,节约算法按照节约矩阵选择种子订单对,然后根据随机原则将为分配订单加入到已有批次中。表1显示了在订单数目分别为10、15、 20、25、30、35时各算法平均最小批次数量以及平均路径改善率的情况,这里每个订单品项数均随机产生且均匀分布在[10,30]区间上,拣选设备容量为40,仓储布局为传统的单区型仓库拥有6条纵向走道240个储位,采用S型路径策略和随机存储策略,表中的值为10次试验所取平均值。算法路径改善率随订单数目变化情况图4所示。由图4可看出在随机产生订单的情况下不同的算法得到的结果的优异程度,节约算法的路径改善率是四种算法中最大的,降批次算法则具有几种算法中最少的分批数量。种子算法则显得中规中矩, FCFS的结果最糟糕。然而并不能据此得出某个算法比另一个更好的结论。
表2显示了在同等条件下拣选设备容量为60时的情况。 算法路径改善率随订单数目变化情况如图3所示。
表中节约算法的批次数量最大,但是仍然获得了很好的路径改善率,可见批次数量少并非是路径改善率高的必要条件,种子算法在这种情形下的表现最好。当拣选设备容量为60而订单品项数均匀分布于[10,50]区间上,其结果如表3所示。算法路径改善率随订单数目变化情况如图4所示。
可见,算法的性能受拣选设备容量以及订单品项分布情况共同的影响,当品项数分布接近拣选设备容量上限时,节约算法和降批次算法具有更好的性能,当品项分布远小于容量的限制,FCFS和种子算法则较以往有更好的表现。综合来看,在两种情况下节约算法和降批次算法都提供了更好的分批结果,尤其是节约算法,这与以往的研究结果一致。降批次算法在一些拣选设备有限的情形则可能有更好的表现。
6结论
本文分析了订单分批问题及其求解思路,然后介绍了三种启发式分批算法,并在此基础上提出了一种旨在减少批次数量启发式算法—降批次算法,最后对上述四种算法进行了比较,发现在最小化路径模型的分批问题中节约算法和降批次算法具有比较好的性能。启发式方法还受到订单品项分布和拣选设备容量限制共同的影响,采用不同的启发式算法的性能具有差异性。
摘要：订单分拣是物流中心最为关键的环节,其成本占到整个物流中心成本的50%以上。文中通过制定合理的订单分批策略以改善人工拣选系统中拣选作业的工作效率,在以往研究的基础上提出了降批次启发式算法,算法考虑到拣选过程中批次数量对于结果的影响。并且利用matlab仿真软件进行仿真实验,与经典的启发式算法进行了比较,实验结果显示降批次算法有较经典的启发式算法更好的求解结果。
改进启发式算法 篇7
对于订单式的钢结构项目生产来说, 后一种排料要求更加符合实际情况, 即利用若干规格和数量的钢板, 为指定尺寸、指定数量和指定纹理的零件下料, 在满足配套和切割便利的前提下, 使板材的利用率最高, 同时又使钢板原料的需求最少。
1 排料方法分析
在钢结构实际生产中矩形零件占一部分, 还有一部分零件是不规则零件, 其中对钢板料耗影响最大的就是不规则零件, 不同的组合次序、旋转角度都可能导致不同的排料结果。钢板排料的数学理论除了常用的遗传算法外, 启发式包络算法也是一种较为简易的方法。
1.1 启发式排料原理
启发式方法是根据板件的轮廓特征先求取最小包络矩形, 再求出聚合矩形。通过对零件外轮廓多边形进行操作, 分别求得与多边形平行或重合的最小矩形, 找出其中的最小者即为零件最小包络矩形;将原零件复制一个并旋转180°;将复制件沿原零件的四周依次移动到若干个位置, 再分别与原零件进行组合, 每次组合均求一次最小包络矩形, 面积最小的矩形即为零件聚合体的最小包络矩形。如果聚合后的聚合矩形的面积小于两个零件的最小包络矩形面积之和, 则聚合成功;反之则自动放弃聚合。
1.2 启发式排料流程
启发式排料先要对待排料板件进行简化预处理, 将不规则的二维图形简化为二维矩形, 即用板件的最小包络矩形代替板件进行排料。
单个或多个不规则零件的组合找出其最小包络矩形, 然后化为矩形件的排料问题。
(1) 单个零件的矩形替代。
采用穷举法求取板件的最小矩形包络。只有当零件的包络矩形与零件的外轮廓多边形中的一条边平行或重合时, 此包络矩形才有可能是最小包络矩形。
求解包络矩形的过程是:零件外轮廓的顶点连线形成封闭图形 (凸多边形) , 然后以凸多边形的每一边假设与所求矩形中的一边重合, 根据顶点位置即可得出此时的包络矩形, 其中面积最小者为最佳包络矩形。
(2) 多个零件的矩形替代。
当单个零件经矩形替代后, 若矩形面积较零件面积大的较多, 即又较多的面积冗余。为了提高材料利用率, 可将两个合适的零件聚合在一起, 再按单个零件的矩形替代方法求出其最小矩形包络。一般情况下, 两个同类零件相对180°转角聚合是较为理想的。
(3) 冗余域最小原则。
单 (多) 个零件的矩形替代与零件边界间的空白部分成为冗余域。
为了提高材料的利用率, 进行矩形替代预处理时, 要将适当的小零件矩形替代填充到冗余域中。
(4) 排料优化算法的描述。
假设母板编号为Bm, 每块矩形件编号为An。首先将矩形件按面积大小排序, 面积大的在前, 面积小的在后, 母板的面积为S (Bm) , 将排序后的矩形件排到母板上, 对某一个矩形件An, 它总是被排到第1个能排下它的母板Bm上, 也就是说, 矩形件An被排到已排入的矩形件面积不超过S (Bm) -S (A n) 。
其中, C (Bk) 为第k块母板上排入的矩形件的总面积。
2 注意问题
2.1 绘制排料图的注意事项
为简化排料图的绘制, 排料前应先将零件分类, 一般可分为以下三类。
(1) 零件长边大于钢板短边的一类。此类零件在钢板上只有一种排法, 对材料利用率影响较大, 应注意利用余料安排其他尺寸较小零件。
(2) 零件两边均小于钢板短边一类。此类零件排料组合情况多样, 应注意不同零件的搭配。
(3) 零件尺寸较小, 或某边长与钢板某边长成倍比关系的一类。此类零件单一下料利用率高。
绘制排料图时, 应先考虑第1类零件, 其次搭配好第2类零件, 最后将第3类零件作为余料的填充料。数量较大的第3类零件还应绘制单一排料图。
2.2 简化模型的方法
在下料问题的模型中, 每种零件对应一个约束条件, 当一批下料任务中零件品种较多时, 不尽会使排料工作复杂化, 而且模型也相应复杂, 会使计算量急剧增加。此时可采用以下方法处理。
(1) 对尺寸不大且数量较少的零件, 在排料和建模时可暂不考虑, 它们通常可在最终方案的余料中安排, 或在取整修整阶段一起解决。
(2) 对数量相同或相近, 且某边长也相同或相近的两种或多种零件, 可组合成一“新零件”进行排料和建模。
(3) 若经上述处理后零件品种仍过多时, 可将各零件适当分组。对各组零件分别排料和建模, 可将一个大的问题化为几个较小的问题来求解。这不仅可大大减少运算量, 还可简化排料工作。
3 结语
启发式包络算法对于数量不是很多、轮廓较为规则的零件效果较为明显, 但是对于轮廓不规则 (尤其是凹多边形) 、数量较多的零件排料效果不是非常理想。遗传式排料方法是对不规则零件排料的有益补充, 但是对于零件较多的时候, 排料同样非常耗时, 并且对计算机硬件要求较高。对一个钣金CAD/CAM系统而言, 如何将这两种排料算法有效的结合起来, 并尽可能在优化排料方案基础上提高排料过程自动化程度, 这是钣金CAD需要研究的新领域。
摘要：在钢结构生产中, 钢板排料是一项既重要又繁琐的工作。如何使排料更加优化、降低钢板的采购成本, 而且效率更高, 本文基于启发式包络算法对钢板排料进行了阐述。
关键词：钢板,包络,排料
参考文献
[1]黄宜军, 施德恒, 许启富.钣金CAD中一个较优的排料算法[J].计算机辅助设计与图形学学报, 2000, 5 (5) :380～383.
改进启发式算法 篇8
齿轮类零件是机械加工中的主要零件,齿轮生产正逐步从大批量连续生产向多品种、小批量生产转型。一个制造型企业的竞争能力基本上取决于产品制造过程中的调度能力。从上个世纪末到现在,学者们在不断追寻调度问题解决方案的过程中发明了很多实用的算法,启发式算法就是为了解决复杂调度问题而发明的一种新思路和新方法,其中比较经典的算法如遗传算法、蚁群算法、粒子群优化算法等对求解车间调度问题起到了很大的推动作用。本文应用启发式算法理论对齿轮生产车间的调度问题进行研究。
1齿轮生产调度问题描述
设需要加工零件的数量为n,加工机床的数量为m,每个加工零件包含多道固定顺序的加工工序,每道工序可以在不同的机器上进行加工,在不同的机器上工序的加工时间也不同。调度的任务是安排最合适的机床完成每道工序的加工,计划每台机床上各工序的最佳加工顺序以及开工时间,使生产中需要达到的交货期、库存数量、生产延迟等性能指标达到最优。
2算法的求解步骤
齿轮生产车间寻找最小化制造期的调度Fm‖Cmax问题,可以看成是否能够得到使一个零件的加工工序贯穿整个系统的排列。实际上,需要加工的零件在队列中等待忙碌机器的时候越过另一项工作先进行加工是可能的,机器不一定要按照先到先加工的规则进行加工,这样在不同机器上各零件的加工顺序可能发生变化。改变相邻两台机器间各等待加工工作的加工顺序有时能得到更短的制造期。
对有m台机器的流水车间给出一个排列调度j1,j2,…,jn,在机器i上工作的jk完成时间为:
Ci,jk=max(Ci-1,jk,Ci,jk-1)+pi,jki=1,2,3,…,m;k=1,2,3,…,n。
其中:Ci-1,jk为在机器i-1上工作jk的完成时间;Ci,jk-1为在机器i上第k-1项工作的完成时间;pi,jk为工作jk在机器i上的加工时间。
给定排列调度下的制造期可由有向图的关键路径计算得到,给定序列的有向图构造如图1所示。
对每道在机器i上进行的工序jk,存在一个节点(i,jk),其权重等于jk在机器i上的加工时间。节点 (i,jk)有弧连接到节点(i+1,jk)和(i,jk-1),与机器m相关的节点只有一条弧,这和对应工作jn的节点相同。节点(m,jn)没有出弧(见图1)。从(1,j1)到(m,jn)的最大权重路径的总权重对应于排列调度j1,j2,…,jn的制造期。
3应用实例
结合理论研究,本文设计开发了齿轮生产车间的调度系统,下面以某齿轮加工车间的实际需求为背景,验证该系统的可用性和有效性。
齿轮生产车间的生产线类型属于流水线,其基本的工艺流程为:齿轮毛坯预处理→热处理→齿轮端面加工→齿形加工→热处理→表面处理。现有3个订单生产任务,3种齿轮的型号不一样。通过数据管理模块将新工件添加到系统中,如图2所示。该模块的主要工作是对工件信息进行管理,包括新建、修改和删除等。工件信息包含工件编号、工件名称、开始加工时间、交货期、数量、状态、优先级等。
在对调度问题建模完成后,点击“调度执行”按钮,操作者可根据自己的要求相应地进行参数设置,在确认各项参数后,点“确定”就可以进行调度计算。经验证,运行结果符合实际生产情况,可用来指导实际生产。
4结束语
启发式算法在调度问题中的应用可以很好地解决复杂的调度优化问题。随着研究的不断深入,调度模型和调度算法与生产实践的结合必定会更加紧密,调度系统必定向着集成化、动态化、高效化、实用化和智能化的方向发展。
参考文献
[1]何霆,刘飞,马玉林.车间生产调度问题研究[J].机械工程学报,2000,25(5):14-18.
[2]黄友锐.智能优化算法及其应用[M].北京:国防工业出版社,2008.
[3]孙志峻,朱剑英.具有柔性加工路径的作业车间智能优化调度[J].机械科学与技术,2001,20(6):931-935.