求解平衡约束圆形Packing问题的快速启发式并行蚁群算法

带平衡约束圆形Packing问题属于NP-hard问题,求解困难.提出一种求解该问题的快速启发式并行蚁群算法.首先提出一种启发式方法:在轮盘赌选择定序的概率公式中增加质量因子和外围逆时针排列定位待布圆,并用它构造出多样性种群个体(相交圆数不超过3的布局方案).然后将蚁群优化与并行搜索相结合,使种群个体快速收敛到最优解或迭代出存在少量干涉的近似最优解(1～3个相交圆).若为后者,则基于物理模型用最速下降法将其快速调整成最优解.所采用的启发式方法、并行蚁群搜索机制和快速调整策略有机结合提高了算法的搜索精度和效率.数值实验表明该算法在性能指标上优于已存在的算法.

开放式频谱系统中启发式动态频谱分配算法

在回顾了现有的开放式频谱系统中的动态频谱分配算法后,基于快速收敛和公平性两方面的性能因素并兼顾系统总带宽性能,提出了两种易于实现且具有良好收敛性能的启发式频谱动态分配算法——兼顾最大化系统总带宽的快速收敛算法(fast convergency algorithm with maximum bandwidth,简称FCMB)和兼顾最大化系统总带宽的启发式公平性分配算法(heuristic fairness algorithm with maximum bandwidth,简称HFWB).通过大量的仿真实验,就系统总带宽、公平性以及收敛性能3个方面,与现有的协调式最大化系统总带宽(collaboration max-sum-bandwidth,简称CMSB)算法、随机分布式算法(randomized distributed algorithm,简称RAND)以及以最大化系统总带宽为目标的理论最优(theoretical max-bandwidth optimal,简称OPTL)算法进行了比较,并针对主、次用户数目变化、系统中信道数目以及次用户干扰区域半径大小变化等不同系统参数情况下各种算法的性能进行了对比分析.仿真结果表明,在综合考虑系统总带宽的基础上,FCMB算法和HFWB算法在快速收敛和兼顾系统带宽的公平性能上分别表现突出,尤其是FCMB算法,其在收敛速度上远远优于其他算法(和与其在系统吞吐性能上表现相近的CMSB算法相比,在收敛性能上至少有300%的提高).

求解带动不平衡约束的卫星舱布局问题的启发式算法

以卫星舱中承载板上物件的三维布局为背景,研究一类带动不平衡约束的圆柱体形和长方体形待布物的混合布局问题.采用两阶段法进行求解,首先引入基面分配策略,将待布物分配到承载板上、下基面上;然后采用禁忌搜索算法对每一基面上的待布物进行布局优化:对传统禁忌搜索算法中的邻域格局提出启发式的产生策略,并对禁忌对象和格局接受原则进行有效改进,将改进的禁忌搜索算法与局部搜索的梯度下降法相结合,提出一种启发式的布局方法——基于梯度下降的禁忌搜索算法.最后通过算例验证了文中算法的高效性.

双边装配线平衡的启发式算法

针对目前研究较少的双边装配线平衡问题,分析、研究了双边装配线平衡的特点,建立了问题的数学模型,并提出一种有效的启发式算法.在该算法中,采用基于位置的任务分配策略,运用多个启发式规则,如具有操作方位约束的任务将被优先分配,来进行任务的选择与分配;通过综合考虑E型任务在装配线双边的状况,确定其分配的具体方位,最大化E型任务的调节作用.大量实例运算结果表明,该算法具有较好的性能.

解二维分配问题的行列启发式算法

二维 (2 D)分配算法在实际中具有广泛的应用 ,本文提出求解该问题的一种新的算法———行列启发式算法。该算法采用交替消去代价矩阵行与列中多余元素的方法得到分配问题的最优解。算法简单易懂 ,避免了其它 2 D分配算法中存在的算法实现难、处理速度慢的不足。给出相关原理的理论证明及算法的具体步骤 。

启发式算法在网络计划多资源平衡中的应用

多资源平衡问题是项目管理网络资源优化的一个基本问题,论文提出一种在工期一定的情况下多资源平衡问题的启发式算法。由于项目的某项活动总是可以在最早开始时间和最晚开始时间确定的范围内开始,所以,通过时差管理采用不同的分配方式,就可以达到较高的资源利用率和降低项目的成本支出。论文编制了相应的程序并进行了仿真,得到了较优的结果。

一种改进的启发式任务分配算法

文中首先分析了分布式任务分配中启发式算法的基本思想、特点、不足和算法复杂度，以及可进一步改进之处．然后给出了一种启发式算法的改进算法，并简单讨论了其特点和性能．最后指出了分布式任务分配的发展方向．

随机型双边装配线平衡问题的一种启发式算法

为有效求解随机型双边装配线第Ⅰ类平衡问题(STALBP-1),在分析双边装配线平衡特点的基础上,考虑各任务操作时间的随机性,提出了一种启发式算法。在该启发式算法中,假定各任务的操作时间服从正态分布,运用具有操作方位约束的任务优先分配等规则来进行任务的选择和分配,通过改变预设超限概率,在不同生产节拍下,分别得到不同的平衡方案。实例验证了算法的有效性。

基于Monte Carlo和启发式算法的网络可靠性分配

在AGREE分配法的基础上,提出一种基于Monte Carlo仿真和启发式算法的网络可靠性分配方法,实现了对网络部件重要度和网络可靠性的仿真计算,并采用启发式算法迭代实现了网络可靠性分配.该方法适合对拓扑结构复杂的网络进行可靠性分配工作,可有效解决网络部件重要度计算复杂性问题.以中国教育网(CERNET)骨干网为案例,应用本方法实现了75%网络节点连通可靠性指标的分配,并通过与基于解析计算得出结果的对比分析,证明了本方法的有效性和实用性.

共享单车再平衡问题及其容差插入启发式算法

共享单车再平衡问题是一类NP-难问题,已有启发式求解算法随着问题规模扩大求解速度显著变慢。本文先讨论了该问题的线路可行变换性质,推导证明了插入构造可行解时,被插入位置允许插入客户点的容量区间。在此基础上,提出容差概念,设计了容差插入启发式算法,对该算法应用标准算例测试表明,算法速度快,参数设置简单;算法找到11个测试算例的当前最好解,其中1个为新的当前最好解;算法求解大容量问题的质量优于中、小容量问题。

基于启发式算法的可重构性指标分配

串联有约束条件下的可重构性指标分配问题,针对考虑部件故障的系统给出了可重构度的概念和计算方法,并论证了其合理性.结合最优冗余分配理论和可重构度定义给出了可重构度最大化的冗余分配模型,在此基础上提出了基于启发式算法的可重构性指标分配方法,该方法可解决约束条件内资源优化配置问题,并得到系统最大可重构度的解.直接寻查法作为以往具有代表性的最优冗余分配方法,用作系统可重构性指标分配仿真,与所提方法作比较,结果显示基于启发式算法的可重构性指标分配方法较前者有更高的有效性.

基于启发式算法与仿真分析的混合流水线平衡优化

为快速求解混合流水线平衡问题,提出一种将启发式算法和仿真分析相结合的方法。首先将多产品的作业优先次序图转化为单一产品的综合作业优先次序图,然后利用基于关键路径的双向启发式算法求得初始平衡方案,接着根据混合流水线运行特点建立仿真模型,通过仿真分析,辨识存在的问题并进行改进,得到优化平衡方案。最后通过一个案例验证了所提方法的有效性。

求解连续平衡网络设计问题近似解的启发式算法

采用双层规划模型描述连续平衡网络设计问题，设计了求解问题近似解的启发式求解算法，并给出了一个简单的算例．本算法使用不需求导数的简单的求解方法，通过和以前的几种求解算法相比较，计算结果准确，但相应的计算量增加．

带静不平衡约束的矩形装填问题的启发式算法

卫星舱布局问题不仅是一个复杂的耦合系统设计问题,也是一个特殊的优化问题,具有NP难度性.解决这类问题最大的挑战在于需要优化的目标函数具有大量被高能势垒分隔开的局部极小值点.Wang-Landau(WL)抽样算法是一种改进的蒙特卡罗方法,已被成功地运用于蛋白质结构预测等优化问题.以卫星舱布局优化问题为背景,将WL抽样算法引入矩形装填问题的求解.针对矩形装填物的特点,提出了启发式格局更新策略,以引导抽样算法在解空间中进行有效行走.为了加速搜索全局最优解,每次蒙特卡罗扫描生成新的布局时,就执行梯度法进行局部搜索.通过将局部搜索机制、启发式格局更新策略与WL抽样算法相结合,提出了一种用于解决带静不平衡约束的任意矩形装填问题的启发式布局算法.在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项并采用质心平移的方法,使布局系统的静不平衡量达到约束要求.为了改进算法的搜索效率,还提出了改进的有限圆族法,用于装填物之间的干涉性判断和干涉量计算.通过对文献中两组共10个有代表性的算例进行实算,计算结果表明,所提出的装填算法是一种求解带静不平衡性能约束的任意矩形装填问题的有效算法.

分布式系统中任务分配的启发式算法

本文系统地介绍了分布式系统任务分配的几种启发式算法。其中包括Efe提出的启发式算法,Lo提出的基于网络流的算法,Shen和Tsai提出的基于A~*算法的图匹配方法,和本文作者提出的一种通用启发式算法。文中指出了Shen和Tsai的方法中存在的两个错误。对以上各种算法进行了分析和比较,所采用的标准是算法的适应性,即算法对于不同的网络构造的适应能力。

项目鲁棒调度的资源分配启发式算法研究

合理的资源配置是提高项目调度鲁棒性一种有效的方法。本文针对项目鲁棒调度问题,提出了Max-PRUA资源分配启发式算法,以期通过生成鲁棒性高的资源分配方案来提高调度计划的鲁棒性。本算法设计了最大化利用优先关系和不可避免弧传递资源的资源分配两项策略来传递最大资源量,以减少由额外约束传递的资源量,降低对项目调度鲁棒性的影响。为寻优最优资源分配方案,配合局部搜索算法,本算法构建了动态活动组GRA,通过对组内活动顺序重排以生成多种资源分配方案,以利于从解空间中寻优出最佳的鲁棒性方案。最后通过大量的仿真实验验证和与其它算法进行比较,结果表明本算法对于不同规模和不同因素影响的项目均有较好的适应性,生成的资源分配方案对调度计划鲁棒性影响较小,是一种有效的算法。

启发式算法的装配线的平衡改善应用

装配线是普遍存在的一种制造系统,装配线的均衡与否直接关系到生产体系的生产率。通过对某空调主控制板装配线工序的时间研究,利用动作经济原则、"5W1H"的方法对生产线进行优化改善,制定一个合理的操作方法和标准作业时间,采用启发式算法原理对装配线的平衡计算,达到劳动强度的降低和运行时间最小化,提高生产线的均衡率,从而能适应产品消费市场的变化。

基于ECRS和启发式算法的涡轮增压器装配线平衡研究

装配线的均衡与否直接关系到生产体系的生产率,通过对某厂废气涡轮增压器装配线工序的时间研究,利用5W1H提问和"ECRS"四大原则,对生产线进行优化改善,采用启发式算法原理对装配线进行平衡计算,使装配线的平衡率由49.5%提升到了78.6%;使得劳动强度降低和运行时间最小化,提高了装配线的的作业绩效。

集装箱堆场箱位启发式分配算法研究

考虑集装箱堆场出口箱箱位分配问题的动态性,文中建立了预分配和实分配两个阶段模型,根据翻箱和起吊设备行驶发生规律开发了一种基于规则的启发式算法,来降低龙门吊大车行驶距离和翻箱量。模拟实验表明算法能够有效降低作业成本,改善分配效果。

一种启发式多传感器任务实时动态分配算法

传感器任务的分配是传感器管理的重要问题。为提高任务分配的实时性和实效性,基于紧急任务优先、最早完成任务优先、复用能力最小优先和随机分配四条原则,提出了一种启发式多传感器任务实时动态分配算法。计算机模拟仿真表明:该算法既能保证优先级任务较早的执行,又能探测到任务的失败,还能维持传感器负载平衡,是一种快捷、高效的分配算法。