A constructive bin-oriented heuristic for the two-dimensional bin packing problem with guillotine cuts

A new heuristic algorithm for solving the two-dimensional bin-packing problem with guillotine cuts (2DBP|?|G)$(2\mathrm{DBP}|?|\mathrm{G})$ is presented. The heuristic constructs a solution by packing a bin at a time. Central to the adopted solution scheme is the principle of average-area sufficiency proposed by the authors for guiding selection of items to fill a bin. The algorithm is tested on a set of standard benchmark problem instances and compared with existing heuristics producing the best-known results. The results presented attest to the efficacy of the proposed scheme.     

单规格一刀切矩形排样问题的启发式搜索算法

针对单规格一刀切二维矩形排样问题,提出了一种启发式搜索算法,称为大小工件分治择优匹配(bigitem smallitem divide-and-conquer best-fit,简称BSDBF)启发式算法.该算法基于组化规则,提出了大小工件分治策略和组块快速举荐算法,是对组化策略的关键补充,这对优解获得至关重要.然后,择优选择适应度高的组块进行递归排样,贪心获得各块板材的排样方案.最后,基于设计的工件拆分方法,对初始解进行后处理小规模重排,进一步提升解的质量.因为没有随机因素,其获得的优解可复现,也是BSDBF算法区别于其他算法的典型特征.大量Benchmark案例的实验结果表明,BSDBF算法求解质量优于其他算法报道结果.     

二维离线非旋转装箱问题的一个混合算法

针对二维离线非旋转装箱问题,在凹角和适应值的思想的基础上,提出了一个改进型的Best-Fit启发式算法,并结合基于自然数编码的遗传算法构建了混合算法。同时在遗传迭代过程中,引入二维装箱问题的下界思想作为迭代的终止条件之一,减少了遗传算法无效迭代次数,另外根据问题自身特点,有效地降低了染色体长度,提高了整体的计算速度。在36个标准测试案例的测试基础上与一些经典的算法进行了比较,实验结果表明该算法在工业生产可接受的时间内与其他经典的算法相比能够获得更为满意的结果。     

一种带剪切约束的启发式二维装箱算法

提出一种满足剪切约束的启发式二维装箱算法,通过价值修正策略提高箱的空间利用率,进而减少箱的使用数量。该启发式算法将较难装箱的物品赋予较高的价值及装箱优先权;并通过延展或融合剩余零散空间,将未用的空间合并到剩余相邻空间,以改进空间利用率。基于标杆测试数据集的仿真实验证明了该算法的有效性和相较于其他二维装箱算法的优越性。     

矩形件优化排样的混合启发式方法

提出一种启发式递归与遗传算法相结合的混合启发式算法求解矩形件优化排样问题。首先给出一种启发式递归算法,利用该算法逐个从待排矩形件中生成局部利用率高的条料,直到所有待排矩形件均生成条料;利用遗传算法全局搜索能力强的特点,对这些条料序进行搜索重组,使其所用的板材数最少;最后再次利用遗传算法,对条料生成之前的矩形件种类序进行全局最优搜索,使总的板材利用率达到了最大。对两个典型实际算例进行计算,并与相关文献比较,结果表明了该算法的有效性。     

基于启发式遗传算法的QoS组播路由问题求解

研究了带宽、延时抖动和包丢失率约束以及费用最小的QoS组播路由问题,并提出一种启发式遗传算法。该算法有以下特点：（1）预处理机制;（2）树结构编码;（3）启发式交叉策略;（4）指导性变异过程,最后通过仿真实验证明该算法快速有效。     

电信网可靠性建模与评估综述

本文从电信网的抗毁性、生存性、有效性等三个方面对电信网的可靠性研究现状进行综述,提出了电信网可靠性研究的主要发展趋势,即新技术对可靠性或有效性的影响、可靠性综合方法的研究、大型系统的可靠性模型的建立与化简方法的研究等。     

带有一刀切约束的二维非规则装箱算法

针对切割下料领域的二维非规则一刀切装箱问题,首先给出了最小移动距离的定义,然后给出了一种基于最大移动距离的启发式算法.该算法通过计算一个凸多边形滑动至另一个凸多边形内部所允许的最大移动距离,对待排件的摆放位置进行一次性定位,避免使用传统的NFP(Not-Fit-Polygon)预判交方法,极大地缩短了排样的整体时间,最...     

约束入库问题模型与算法研究

对某冷轧厂冷卷约束入库问题建立数学模型,归结为有约束的装箱问题 (binpacking),设计带匹配权值的bestfit算法实现优化入库.该算法简便易行,效果良好,是求解一类约束入库问题的有效算法.计算实例说明了模型的合理性与算法的有效性.     

金属板材三维装箱的启发式算法

针对直方体金属板材装箱问题,提出一种模仿人装箱过程的启发式算法,该算法对木箱进行分层装箱,从最底层开始一层层往上装载,对每层出现的不平整的层进行智能填充,从而提高木箱的空间利用率,采用人工智能方法处理待装金属板材得出装箱结果,实验结果表明,该算法是行之有效的,并具有一定的通用性.     

一个扩展的以QoS为指向的网格任务调度算法

在对网格计算的研究中,有人考虑了计算资源中服务质量(QoS)因素,在对传统的Min-Min算法加以改进的基础上,提出了QoS Guided Min-Min算法。在此基础上,本文提出一种新的扩展型算法,以进一步提高网格资源的利用率。最后,本文对以上三种算法的实验结果进行了比较分析。     

集装箱装载的一种启发式算法

多约束条件下的三维装箱问题是一个复杂的组合优化问题,属于NP-HARD问题,其求解是很困难的．所以在实际应用中,往往采用一些启发式算法来求解．本文在考虑一些实际应用中的约束条件下,提出了一种三维集装箱装载的启发式算法．此算法采用了三空间分割、平均高度装载、货物合并、空间合并等策略,考虑了方向、重量、优先顺序、货物的配置位置等约束条件．通过逐步淘汰差的装载方案,最后达到满意的装载．实例仿真说明了该算法的有效性和实用性,能够直接用于实际应用中．     

多箱型三维装箱问题及其优化研究

对多箱型三维装箱问题进行了描述,提出了求解该问题的禁忌算法。算法基于自然数编码,设计了货物的摆放规则和序列生成方式,采用三种邻域,利用邻域操作控制集装箱数量限制,采用惩罚函数处理集装箱重量约束和重心约束。介绍了算法的原理,给出了具有代表性算例实验结果并且进行了分析。实验结果表明了提出的禁忌算法对优化多箱型三维装箱问题的有效性。     

半在线入库堆垛问题的动态求解算法

堆场垛位优化问题一直是仓储管理的难点和焦点之一,垛位优化可以保证物料装卸和出入库的高效率,同时对保证合同交货期也起着至关重要的作用。针对仓储和生产一体化下的入库堆垛问题,本文通过分析将其归结为一类半在线的A型装箱问题,并依据问题的特点,建立了最小化总倒垛次数的优化模型。根据货场天车在相邻入库过程中存在空闲作业量的特点,设计了一种前序货物允许移动的动态堆垛策略,结合堆垛约束后嵌入到经典装箱启发式算法中,最后通过仿真算例验证了该策略的有效性。     

冷卷入库的数学模型及算法

讨论某冷轧厂热处理车间冷卷入库堆垛问题,并将其归结为装箱问题进行研究.通过建立数学模型,设计在线算法,达到了优化堆垛、提高生产效率、加快冷卷周转的目的.同时,通过数值实验,比较了多种算法的计算效果,得到了冷卷入库问题合理而有效的算法.     

基于网络带宽约束的网格任务调度算法研究

在对网格计算任务调度算法的研究中,分析一般适应性调度启发算法即最小一最小(Min-min)算法的不足,在最小一最小(Min-min)算法的基础上,加入考虑QoS方面主要是网络带宽因素的任务调度算法.对以上算法做了实验并指出下一步的研究方向.     

三维装箱问题的组合启发式算法

通过组合拟人启发式和模拟退火算法,提出了三维装箱问题的组合启发式算法.拟人启发式算法的主要思想来源于日常砌墙中的策略.利用找点法以及水平和垂直参考线规则来控制装填过程.用模拟退火算法改进拟人启发式.经过一些数据的测试,实验结果表明,该算法能够同文献中的优秀算法竞争.     

钢坯入库堆垛问题模型及其动态求解算法

通过对钢坯入库堆垛问题进行深入研究,建立了以最小化钢坯出库倒垛数为目标的数学模型,并设计了一种可以动态调整垛位顶层钢坯的堆放位置的DIBF(Dynamic and Improved Best Fit)算法。算法主要分为2个阶段,首先通过聚类算法将辊道上暂存钢坯形成入库批次;然后对入库批次通过DIBF算法进行批次指派垛位。通过钢厂实际生产数据对DIBF算法、IBF(Improved Best Fit)算法和传统手工计算方法进行验证。结果表明,相对于IBF算法和传统手工计算方式,DIBF算法不仅能够在限制可用垛位数的前提下减少倒垛次数,而且也能提高垛位的空间利用率,模型及算法可行、有效。     

同一尺寸货物三维装箱问题的一种启发式算法

给出了集装箱装载同一尺寸长方体货物问题的一种启发式算法.该算法解决了许多三维装箱算法计算量大、排列不规则等缺点,同时用计算机编程实现该算法,并与国内主要装箱软件作了对比,最后给出了该算法的可行性与优势.