求解矩形布局问题的自适应算法

矩形布局问题属于NP-Hard问题,其求解算法多为启发式算法。该文侧重于构造布局求解算法中定位函数(规则)的优化,将模拟退火算法的思想融入到遗传算法中,提出了求解矩形布局问题的自适应算法,其利用自适应交叉、变异及接收劣质解的概率等方法对定位函数中各参数进行优化。算法通过两种方式确定初始种群的数目,具有较强的适应性。在算法搜索的后期,利用差异性较大的个体进行交叉操作,从而保持种群的多样性。最后通过实例证明了该算法能够很好的应用于矩形布局问题的求解。     

一种基于蜜蜂进化选择算子的布局遗传算法

三维矩形布局问题属于NP难问题,对于三维矩形布局问题的求解大多依赖于各种启发式算法.该文以布局物体体积递减为定序规则,结合布局物体在布局空间中的几何可行域,以吸引子法为定位规则,利用蜜蜂进化型遗传算法优化吸引子函数中的参数来求解三维矩形布局问题（BEGA）,得到新型布局遗传算法.最后对不同的算例进行了计算,并与以标准比例选择作为选择算子的传统布局遗传算法（SPGA）等对比证明了该算法的有效性.     

基于蒙特卡罗方法的矩形布局问题研究

根据蒙特卡罗方法产生的随机步长,控制矩形在布局空间中移动。矩形移动时,自动满足边界约束条件,简化了矩形可行域边界的计算过程。结合定位函数,得到的可行域可用于完成矩形的布局。测试结果表明,使用该方法求解矩形布局问题,布局空间90%以上被矩形占据。     

单一规格物体二维矩形条带装箱问题解法研究

为了克服用启发式算法及智能搜索法解决单一规格物体二维矩形条带装箱问题耗时过长的缺陷,提出了新的解法和思路.用线性规划法分别在2个维度求最优解,以最好的方案作为近似最优解,可大幅度缩短求解时间,获得满意的近似最优解.     

基于序列模型的三维矩形布局算法

针对三维矩形布局问题进行了研究。在三元序列的基础上,结合布局物体的几何可行域,提出了三元序列结合几何可行域的布局算法。并且利用遗传算法对布局算法进行优化,得到了三元序列结合可行域布局遗传算法。分析和实例证明,三元序列结合几何可行域的改进算法有效地提高了布局效率。     

面向远程布局的分布式虚拟车间研究

提出了面向透视关系一致性的图像插值策略和基于敏感视野的渲染精度分配策略,采用基于图像的柱面纹理映射方法实现了基于Web的分布式虚拟车间系统,解决了面向宜人化水平的车间异地布局评价存在的主要难点问题。     

基于改进粒子群算法的制造单元设施布局问题研究

为避免单元系统布局和单元内设施布局分开孤立研究所导致的问题解空间损失,利用并行工程的思想对单元布局的两个环节集成考虑,对单元系统布局、单元内设施布置、设施摆放方向进行同时描述,并建立多目标集成优化模型。针对模型的复杂性,设计了改进粒子群算法,算法吸收了遗传算法中的交叉操作算子,具有跳出局部最优解的能力。最后通过求解单元设施布置实例,验证模型和算法的有效性。     

基于启发式搜索策略的测试选择问题研究

测试选择是测试性设计的最基本步骤之一，本文通过对其数学模型的研究，构造了衡量测试集优劣程度的启发式函数，并由此实现了一种用于测试选择的遗传搜索算法。实例验证表明了该启发式函数的有效性，为测试性设计提供了一个简单有效的方法。     

面向快递同城运输的车辆路径问题研究

为降低运输成本,研究了快递同城运输中的车辆路径问题。建立多车型,含时间窗约束、容量约束、车辆限行约束,并考虑错峰交货的,以最小化运输成本为目标的混合整数规划模型。提出以点到点集的距离之和作为邻域搜索优先指标的构造性启发式算法,设计了基于“路径−车型对”的列生成算法,初始列由启发式算法求得。实验结果显示,对于120个点的大规模问题,列生成算法只需175秒就能得到近似最优解,验证了该算法的有效性及对一定规模内快递同城运输问题的适用性。     

可重构制造系统的布局规划技术研究

分析了可重构制造系统的内涵,提出了制造系统重构的三种分类(逻辑型RMS、改进型RMS和创新型RMS)并给出了制造系统重构的流程.在利用UML对制造系统建模的基础上,建立了统一的面向改进型RMS和创新型RMS布局规划的多目标规划数学模型.提出了启发式算法和遗传算法相结合的混合遗传算法,解决了创新型RMS布局规划问题.实例验证了算法的可行性和有效性.     

Global optimization for the three-dimensional open-dimension rectangular packing problem

This article addresses the three-dimensional open-dimension rectangular packing problem (3D-ODRPP), which aims to pack a given set of unequal-size rectangular boxes within an enveloping rectangular space such that the volume of the occupied space is minimized. Even though the studied 3D-ODRPP is NP hard, the development of sophisticated global optimization methods has been stimulated. The mathematical programming formulation for the 3D-ODRPP has evolved into an effective and efficient mixed-integer linear programming (MILP) model. This study proposes an advanced exact scheme yielding a guaranteed global optimal solution given that all the instance data are non-negative rational numbers. The developed MILP retains not only fewer variables but also fewer constraints than the state-of-the-art models. The superior effectiveness and efficiency of the developed scheme are demonstrated with numerical experiments, where two sets of benchmark instances from references, real-world instances and instances with rational data are included.     

改进的最低水平线搜索算法求解矩形排样问题

矩形优化排样问题是一个在制造业领域生产实践中普遍遇到的问题,采用了一种改进的最低水平线搜索算法求解此类问题.首先分析了原始的最低水平线搜索算法在排样中存在的缺陷,并针对该缺陷为其设计了一个评价函数,排样时对所有未排零件进行评价,选择评价值最高的零件排入当前位置,从而克服了算法在搜索过程中的随机性,优化了算法的搜索方向.实验仿真的结果表明,提出的算法可以得到较好的排样效果,并且其解决问题的规模越大,优化性能越好,适合于求解大规模排样问题.     

A recursive algorithm for the rectangular guillotine strip packing problem

This article presents a recursive heuristic algorithm to generate cutting patterns for the rectangular guillotine strip packing problem in which a set of rectangular items must be cut from the strip such that the consumed strip length is minimized. The strip is placed with its length along the horizontal direction, and is divided into several segments with vertical cuts. The length of a segment is determined by the item placed at the bottom. Orthogonal cuts divide the segments into blocks and finished items. For the current block considered, the algorithm selects an item, puts it at the bottom-left corner of the block, and divides the unoccupied region into two smaller blocks with an orthogonal cut. Rotation of the items by 90 is allowed. Both lower and upper bounds are used to prune unpromising branches. The computational results indicate that the algorithm performs better than several recently published algorithms.     

Optimisation of a multi-objective two-dimensional strip packing problem based on evolutionary algorithms

This paper considers a real-world two-dimensional strip packing problem involving specific machinery constraints and actual cutting production industry requirements. To adapt the problem to a wider range of machinery characteristics, the design objective considers the minimisation of material length and the total number of cuts for guillotinable-type patterns. The number of cuts required for the cutting process is crucial for the life of the industrial machines and is an important aspect in determining the cost and efficiency of the cutting operation. In this paper we propose the application of evolutionary algorithms to address the multi-objective problem, for which numerous approaches to its single-objective formulation exist, but for which multi-objective approaches are almost non-existent. The multi-objective evolutionary algorithms applied provide a set of solutions offering a range of trade-offs between the two objectives from which clients can choose according to their needs. By considering both the length and number of cuts, they derive solutions with wastage levels similar to most previous approximations which just seek to optimise the overall length.     

An iterative bidirectional heuristic placement algorithm for solving the two-dimensional knapsack packing problem

This article presents an efficient heuristic placement algorithm, namely, a bidirectional heuristic placement, for solving the two-dimensional rectangular knapsack packing problem. The heuristic demonstrates ways to maximize space utilization by fitting the appropriate rectangle from both sides of the wall of the current residual space layer by layer. The iterative local search along with a shift strategy is developed and applied to the heuristic to balance the exploitation and exploration tasks in the solution space without the tuning of any parameters. The experimental results on many scales of packing problems show that this approach can produce high-quality solutions for most of the benchmark datasets, especially for large-scale problems, within a reasonable duration of computational time.     

Solving non-oriented two dimensional bin packing problem using evolutionary particle swarm optimisation

The non-oriented two-dimensional bin packing problem (NO-2DBPP) deals with a set of integer sized rectangular pieces that are to be packed into identical square bins. The specific problem is to allocate the pieces to a minimum number of bins allowing the pieces to be rotated by 90° but without overlap. In this paper, an evolutionary particle swarm optimisation algorithm (EPSO) is proposed for solving the NO-2DBPP. Computational performance experiments of EPSO, simulating annealing (SA), genetic algorithm (GA) and unified tabu search (UTS) using published benchmark data were studied. Based on the results for packing 3000 rectangles, EPSO outperformed SA and GA. In addition; EPSO results were consistent with the results of UTS indicating that it is a promising algorithm for solving the NO-2DBPP.     

Advanced scatter search approach and its application in a sequencing problem of mixed-model assembly lines in a case company

Mixed-model assembly line sequencing is significant in reducing the production time and overall cost of production. To improve production efficiency, a mathematical model aiming simultaneously to minimize overtime, idle time and total set-up costs is developed. To obtain high-quality and stable solutions, an advanced scatter search approach is proposed. In the proposed algorithm, a new diversification generation method based on a genetic algorithm is presented to generate a set of potentially diverse and high-quality initial solutions. Many methods, including reference set update, subset generation, solution combination and improvement methods, are designed to maintain the diversification of populations and to obtain high-quality ideal solutions. The proposed model and algorithm are applied and validated in a case company. The results indicate that the proposed advanced scatter search approach is significant for mixed-model assembly line sequencing in this company.