模拟退火算法求解矩形物体布局问题

介绍了矩形物体布局问题,提出了基于布置点的改进思想,在引入了新的个体表达方式和物体布局规则的基础上,提出了一种模拟退火算法求解矩形物体布局问题的新思路.实例表明该算法快速有效.     

矩形物体布局的并行算法

分析了矩形物体布局串行算法的计算复杂性，设计出基于ＳＩＭＤ－ＣＲＥＷ共享存储模型的矩形物体布局的并行算法，通过比较和实例分析验证了该并行算法的有效性和快速求解能力。     

基于空间分解的二维布局问题的启发式算法

一种基于空间分解的解决矩形物体布局问题的启发式方法。按照深度优先的原则将布局空间逐步分解，每次放入相对于当前布局空间来说是满足特定条件的最优布局块，并将该布局块定位于当前布局空间的左上角来不同大小矩形物体的布局方案。通过调整调序因子ＫＡ和ＫＢ的值，可得到满足不同要求的优化布局方案，所得布局方案均满足工业上一刀切的要求。实验结果及与其他算法的比较证明了该算法的灵活性和有效性。     

针对目标的布局启发式算法

为解决二维矩形布局问题，在广泛研究各种启发式方法的基础上，提出了基于目标的启发式算法．该算法在布局开始时确定布局目标，布局过程中综合运用多种策略，让每个局部最优解达到布局目标值，得到稳定的、可靠的全局解；并且简要分析了矩形正交布局的空间分解方法，提出了群组的基本策略以及布局的定序规则和定位规则、实验结果表明，算法具有较强实用性，布局效率提高2％以上．     

布局调度问题的聚合算法

在分析布局调度问题的基础上，建立了布局调度问题的数学模型，利用重复匹配算法，聚合算法等启发式方法，提出了布局调度操作的启发式规则及相应的启发式算法，算例表明该算法能较好地解决布局调度问题，所得布局结果是令人满意的。     

求解布局问题的混合萤火虫群优化算法

为了充分发挥萤火虫算法的优点,将人工萤火虫群优化算法与启发式策略相结合,设计了一个新的求解布局问题的高效萤火虫优化算法.实例测试和实验对比结果表明:相对于已有文献中的算法,提出的混合布局方法更加有效.     

求解三维矩形布局的最大穴度算法

针对三维矩形布局问题提出了一种新的启发式算法--最大穴度算法,其主要思路是通过现代的数学工具,将人类几千年来形成的智慧予以形式化和确切化.该算法以最大穴度的动作优先放入为原则,使装入容器的长方体尽可能紧凑,从而可装入尽可能多的长方体.计算了OR-Library中无方向约束的全部47个算例,实验结果表明:该算法在合理的时间内取得了平均体积利用率为94.31 %的结果,比此前报道的最好结果高3.31 %.     

单机总误工问题的分解启发式算法

为了解决单机总误工问题,提出了一种分解启发式算法。该算法是将解决这一问题最好的优化方法(Lawler分解算法)和非常有效的启发式算法(MDD)有机结合,在每一次迭代过程中均利用MDD算法估计Lawler分解算法中不同分解位置对应的误工,确定具有最大加工时间的工件在获得最小总误工的分解位置处加工。从理论上证明了该算法得到的排序结果优于MDD排序,仿真实验也表明该算法得到的结果99%以上为最优排序,而且可以求解多达1000个工件的问题。该算法以较短的时间获得了接近最优排序的结果,算法性能优良。     

求解带平衡约束矩形布局问题的混合算法

以卫星舱布局为背景,针对二维带平衡约束的矩形集在圆容器内的布局问题,提出了一种混合算法,即带压缩策略的动态匹配算法,并与粒子群优化算法结合起来.对于给定的圆容器,将整个布局过程分为4个阶段,相应地将圆容器分成8个区域.每次放置矩形时,动态匹配算法先根据系统质心动态选择装填区域,然后在该装填区域中根据排序函数选择待布矩形.压缩策略用来压缩圆容器,粒子群优化算法用来优化排序函数的参数.在测试集上的计算结果表明:相对于已有算法,提出的混合算法更加有效.     

空间物体断面图的多视区显示算法

本文提出的算法,可用在土木工程、矿山和油田等CAD系统中。该算法利用(?)、ψ映射及α、β变换,把任意大小的物体空间切平面完整地显示或绘制在相应的视区内。一个屏幕可同时交互式地显示多幅断面图,以便设计人员直观地进行比较。     

具有优先权的自由作业时间表问题研究

研究了具有优先权的自由作业时间表问题，在工件具有准备时间的条件下，给出一种新的启发式算法，其最坏性能比不超过2，猜想该算法的紧界是2—2／(m 1)，其中m是机器的台数，证明在3台机器的情况下，该算法的最坏性能比为3／2，且上界是紧的。     

圆饼装填问题的并行算法

圆饼装填是一个将多个芯片设计组合到一个圆饼上，构造费用通过几个设计分担而减少的过程。本文在ＳＩＭＤ－ＣＲＥＷ并行计算模型下，通过修改Ｐｒｅｐａｒａｔａ并行排序算法及其用到的Ｖａｌｉａｎｔ并行归并算法，给出了分配２个设计到一个包的基本圆饼装填问题ＢＷＰＰ的并行算法，在Ｏ（ｎ＾１．５）台处理机上，算法的时间复杂性是Ｏ。     

基于构造的布局启发方法

布局问题属于ＮＰ完全问题已知被研究多年,关于它的求解方法多为启发式方法,本文在分析了布局问题特性的基础上,提出了一种基于构造的布局启发方法,该方法既考虑到布局总问题的不干涉的约束及又考虑了其它的布局约束,从而更加全面,准确地指导布局求解的进行,本文还首次提出了“虚容器”的概念,从而使定序函数和定位函数的计算易于进行。     

基于遗传算法的布局求解法

在分析布局问题的基础上,对编码方式,交叉操作等做了改进,提出一种基于遗传算法的布局求解方法,计算结果表明,算法具有良好的全局搜索能力和较快的收敛速度。     

线性分式运输问题的一个解法

线性分式运输问题是线性分式规划的一种特殊情况．本文针对分式运输问题的特点给出了一种简便的解法     

约束优化问题和互余问题的同伦算法

把约束优化问题转化为互余问题,然后用分段光滑同伦间接地解决了约束优化问题和互余问题,并给出了数值例子。     

Flow Shop成组排序问题的调度算法设计及其界的估计

讨论Flow Shop成组排序问题F2│prmu,s,pkij=pij,GT│∑ωjcj.基于WSPT规则,给出求解该问题的一个启发式算法,并证明2是该算法的一个上界.