基于重要度的矩形工件优化填充排样算法

大规模矩形件优化排样是一个典型的组合优化问题,属于NP2hard问题。矩形件优化排样已广泛应用于板材切割、瓷砖铺设、服装裁剪等行业。在实际排样工作中发现,决策者对工件的选择不仅要考虑大小、工件费用、铺设利用率等诸多因素,往往还需要考虑颜色、花式、铺设方式等因素。基于这种状况,引入排样属性重要度的概念,提出了基于重要度的矩形工件优化填充排样算法,使用计算机辅助排样。通过实例排样表明了该算法的有效性和实用性。     

基于离散粒子群优化算法求解矩形件排样问题

改进了一种近似排样算法,并将改进的近似排样算法与离散粒子群优化算法结合求解矩形件排样问题.设计了应用离散粒子群优化算法求解矩形件排样问题的相关操作和定义,给出了离散粒子群优化算法求解矩形件排样问题的详细步骤,最后通过实验测试,验证了算法的有效性.     

基于模拟退火剩余矩形算法的矩形件排样

针对矩形件优化排样问题,讨论了用模拟退火算法结合剩余矩形法求解问题。首先阐述了矩形件排样问题的数学模型,然后给出了模拟退火剩余矩形算法求解问题的步骤和方法,最后用实例进行了算法验证。实例分析表明,采用模拟退火剩余矩形算法求解矩形件排样问题是适合的。     

基于蚁群优化算法求解矩形件排样问题

布局问题来源于生产实际,优秀的布局可以提高原料利用率,降低成本,提高经济效益,对许多行业有重要意义。矩形件优化排样是一类具有NP完全难度的组合优化问题。人工蚁群算法是对蚂蚁群体行为的模拟抽象,该算法具有分布计算、信息正反馈和启发式搜索等特点。本文将蚁群算法和剩余矩形法结合用于解决矩形排样问题,首先用蚁群算法将矩形件排样问题转化为一个排列问题;然后通过剩余矩形排样算法排出每一个排列所对应的排样图;最后用算法对文献[9]中的两个算例进行了验证,表明了其有效性。     

一种快速的有约束矩形件优化排样模型

为了有效地解决有约束的矩形件优化排样问题,提出一种快速的求解算法;通过比较待排样矩形件的不同排样模式,选择最优排样方案。算法完全基于解析计算,虽不能寻找理论最优解,但相比于各种启发式算法大大提高了排样速度。实验结果表明,算法能够在较短的计算时间内获得满意的排样效果,是一种效率较高的有约束矩形件排样算法。     

基于最优子段的矩形优化排样

为有效解决企业实际生产中的矩形优化排样问题,对矩形优化排样算法进行研究, 给出基于最优子段的矩形优化排样算法,有效解决了企业实际生产中的长板矩形优化排样问题。 首先基于动态规划算法求出所有小于剪床刀刃长度的最优子段的最佳排样方式,然后以所求的最 优子段作为可用子段在长板上进行优化排样,并将矩形优化排样问题转化为完全背包问题。最后 基于分支定界技术的整数规划算法对其进行求解。企业应用实例表明该算法在解决长板矩形优化 问题方面优于其他算法。     

基于遗传模拟退火算法的矩形件优化排样

为了探索更高效的矩形件优化排样方法,提出了一种改进的自适应遗传模拟退火算法。设计了基于矩形件的排样次序及旋转变量的两层染色体编码方法,并采用基于临界多边形的BL定位策略实现矩形件的布局;通过构造启发式算法生成排样初始种群,然后各个种群之间通过相互竞争实现优秀个体的迁移与共享,最终搜索到最优解。标准测试问题的实验结果验证了所提算法的可行性与有效性。     

矩形件排样优化的一种近似算法

本文对理论上属于ＮＰ－完备问题的二维矩形件优化排样问题，构造了一个效率高、速度快、可令人满意的一种近似算法，该算法的主要思想是在排样过程中根据一种局部最优原则不断地动态产生一些较小的矩形，然后对这些小矩形区域排样，同时也消去一些已排过的矩形区域，直至所有的矩形件被排完，根据本文算法我们开发了一个矩形件排样系统。     

基于两段排样方式的矩形件优化下料算法

针对矩形件下料问题,提出一种基于两段排样方式的优化下料算法。首先构造一 种约束排样算法,生成矩形件在板材上的两段排样方式。然后采用列生成算法依据矩形件剩余 需求量迭代调用上述约束排样算法生成一个虚拟下料方案,按照不产生多余矩形件原则选取虚 拟下料方案中的部分排样方式加入到实际下料方案中,更新矩形件剩余需求量;重复上述步骤 直到矩形件剩余需求量为零。采用文献中基准例题将该算法与2 种文献算法进行比较,数值实 验结果表明该算法下料利用率比2 种文献算法分别高1.61%和0.78%。     

矩形件排样问题的遗传算法求解

本文研究了求解矩形件正交排样优化问题的遗传算法。同时，将矩形件正交排样问题转化为一个排列问题，提出了求一个排列所对应的排样图的下台阶算法（改进的ＢＬ算法）将下台阶算法与遗传算法相结合，用于矩形件排样问题的求解，给出了该算法的实现。用该算法对文献中的两个算例进行了求解，结果表明该算法获得了比ＢＬ算法更好的解，是一种较为行之有效的方法。     

ACS算法在矩形件优化排料中的应用

矩形件优化排料是一类具有NP完全难度的组合优化问题。有关的优化问题可用与或树来描述,这样就把矩形件优化排料问题变换为寻找一棵面积比率最大的二叉树。用ACS算法实现这种树搜索,是把一定数量的人工蚂蚁分布在与或树的根节点,人工蚂蚁间通过使用信息素相互交流,完成从与或树到二叉树的选择,从而得到矩形件优化排料问题的优化解。     

Multi-objective layout optimization of a satellite module using the Wang-Landau sampling method with local search

The layout design of satellite modules is considered to be NP-hard. It is not only a complex coupled system design problem but also a special multi-objective optimization problem. The greatest challenge in solving this problem is that the function to be optimized is characterized by a multitude of local minima separated by high-energy barriers. The Wang-Landau (WL) sampling method, which is an improved Monte Carlo method, has been successfully applied to solve many optimization problems. In this paper we use the WL sampling method to optimize the layout of a satellite module. To accelerate the search for a global optimal layout, local search (LS) based on the gradient method is executed once the Monte-Carlo sweep produces a new layout. By combining the WL sampling algorithm, the LS method, and heuristic layout update strategies, a hybrid method called WL-LS is proposed to obtain a final layout scheme. Furthermore, to improve significantly the efficiency of the algorithm, we propose an accurate and fast computational method for the overlapping depth between two objects (such as two rectangular objects, two circular objects, or a rectangular object and a circular object) embedding each other. The rectangular objects are placed orthogonally. We test two instances using first 51 and then 53 objects. For both instances, the proposed WL-LS algorithm outperforms methods in the literature. Numerical results show that the WL-LS algorithm is an effective method for layout optimization of satellite modules.     

基于遗传算法的大规模矩形件优化排样

大规模矩形件优化排样是一个典型的组合优化问题，属于NP-hard问题．实际工程中对一个排样方案一般有满足“一刀切”的工艺要求，“一刀切”要求增加了对排样的约束．提出的优化算法，将矩形匹配分割算法作为遗传算法染色体的解码器实现一个排样方案，用遗传算法进行排样方案的全局搜索．算例比较表明，该算法可以求得满足“一刀切”约束的最优解．     

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

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

矩形件无约束二维板材剪切的4块排样算法

针对矩形件无约束二维板材剪切排样问题,提出一种新的4块排样方式及其生成算法.该排样方式将板材划分成4个块,对每个块,按照递归方式进行排样.选择一行同种矩形件放置在块的左下角,沿着这行矩形件的上边界和右边界将该块剩余部分划分成两个更小的子块以待进一步递归考察.首先,构造动态规划算法一次性生成所有可能尺寸的块中矩形件的递归...     

An optimal layout methodology for cold forming rectangular parts using genetic algorithms

Cold forming is widely used in manufacturing processing, and the layout of rectangular parts in the strip is manually accomplished, which is a time-consuming task and may be a major bottleneck in effectively improving the utilization ratio of material and the productivity. The mathematical model for optimal layout of cold forming is first developed, and then the constrained optimal layout problem is transformed to an unconstrained optimal one with penalty function strategy. A simple genetic algorithms for this optimal layout is proposed, and an example is examined to show the validity of this proposed genetic methodology. Although the simple genetic algorithms is employed, a higher material utilization ratio and productivity is achieved.     

基于CASE推理的排样算法

优化排料的目的是根据给定待排样品对板材进行最优切割使得板材的利用率尽可能的高。提出了一种基于case推理的优化排样算法,基本思想是对每块板材的布局都进行case推理,选取CASE中的最佳布局,若没有相应的Case,则调用启发式算法搜索。算法不但避免了组合爆炸,加快了排料速度,而且具有满意的材料利用率。目前算法已集成了作者研制的《布局之星》切割系统,实际应用表明算法是成功的。     

A digital equipment identifier system

This study proposes an innovative information resource and service, a digital equipment identifier (DEI) system. The DEI system is a new identification scheme that assigns each piece of equipment a unique identification, based on which various applications can be practiced. When users employ the DEI system to access the data of a piece of equipment by using its DEI, they are directly led to the most up-to-date information about the equipment. The DEI is also useful for establishing a facility layout online because the pictures and other basic data of each piece of equipment in the facility layout can be referenced through the DEI system. A virtual capacity network containing possible vendors and factories of an equipment piece is established according to the DEI of the equipment. An optimal capacity allocation plan is then derived to maximize the average satisfaction levels of factories; therefore, an integer-nonlinear programming problem is solved. The planning results become crucial inputs in establishing a dynamic virtual factory that embodies the changes in capacity over time.