矩形毛坯最优三块排样的新算法

针对矩形毛坯二维下料问题,提出采用三块排样的下料算法,以达到最小化板材消耗量和简化切割工艺的目标。该算法将列生成法和排样方式生成算法相结合,生成一个含多个排样方式(排样图)的集合,然后通过解整数规划问题获得各个排样方式的使用次数。排样方式生成算法通过构造并求解整数规划模型,求出最优三块排样。采用的三块排样,切割工艺简单,能有效提高切割效率。实验结果表明,该算法可以明显减少板材消耗。     

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

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

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

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

矩形件三阶段带排样问题的遗传算法

采用混合遗传算法求解矩形件带排样问题,采用三阶段排样方式以满足特定的约束或简化切割工艺。改进遗传算子,在变异操作之后使用调整操作,以进一步简化得到的排样方案。在初始种群构造时,根据矩形件的特性采用一些简单有效的方法,使结果更好更快地收敛。实验结果表明方法对解决这类问题是有效的。     

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

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

结合批量问题的多目标矩形件优化排样

设计多目标启发式进化算法,研究了一种考虑批量问题的二维矩形件排样问题,建立了含有原材料成本最小化和零件库存成本最小化的多目标优化模型。先用启发式算法初始化下料方式,再用改进的快速非支配排序算法进行优化求解,确定下料方案。通过实验结果以及与其他算法的对比表明,在中等规模的矩形件排样问题中,该算法能够在较快的时间内既保证较高的原料利用率,又能降低该问题的总成本,证明了该算法的有效性。     

遗传算法在矩形件优化排样中的应用

遗传算法是一种全局优化的数值计算方法。与传统优化算法相比,它对函数的要求不高,一般不会陷入局部最优解,更适应于求解大规模离散化问题。该文将遗传算法应用于工程问题的一个典型离散优化问题矩形件优化排样。通过该算法可以找出高效率的排样加工方法。设计结果能广泛应用于各零件的排样加工实例。     

基于五块模式的单一矩形件排样算法

如何在一个大矩形里排入尽可能多的单一规格小矩形件是广泛出现在制造业领域 的板材分割、物流业领域的集装箱装载中的问题。采用五块模式将大矩形划分为五个块,求解 每个块里面矩形件的排样方式。首先,采用动态规划算法一次性生成所有块中矩形件排样方式, 然后,采用隐式枚举法考虑所有可能的五块组合,选择包含矩形件个数最多的五块组合作为最 终的排样方案。使用算例对算法进行了测试,并与另外4 种单一排样算法进行了比较。实验结 果表明,该算法在排样利用率和切割工艺两方面都有效,而且计算时间合理。     

基于排样矩形的直角边零件下料算法

针对实际操作中直角边零件下料利用率不高的问题,导入排样矩形的概念,将直角边零件下料问题分解为若干优化子问题,在此基础上,基于动态规划思想通过求解子问题构建全局最优解.实验表明,与传统的直角边零件板材切割相比,使用本文算法能够使板材的利用率提高30％-50％;与其他几种典型算法相比,本算法板材利用率提高显著,并且排样方案...     

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

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

一维下料问题的AB分类法

为了解决大规模的一维下料问题的计算困难, 根据一维下料问题的特点,把贪心算法和随机搜索技术有机地结合起来,利用随机搜索技术对贪心算法进行了有效的改进,提出了一种简单实用的AB分类法。 实验表明,该算法对规模较大的问题也能较快地获得问题最优解或精度较高的近似最优解。     

一维下料的改进遗传算法优化

针对一维下料优化问题,在对一维下料方案数学模型分析的基础上,提出了基于改进遗传算法的优化求解方案。主要思想是把零件的一个顺序作为一种下料方案,定义了遗传算法中的关键问题:编码、解码方法、遗传算子和适应度函数的定义。该算法设计了一种新颖的遗传算子,包括顺序交叉算子、线性变异算子、扩展选择算子。根据这一算法开发出了一维下料方案的优化系统。实际应用表明,该算法逼近理论最优值,而且收敛速度快,较好地解决了一维下料问题。     

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

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

Using Wang's two-dimensional cutting stock algorithm to optimally solve difficult problems

P. Y. Wang's classic bottom-up two-dimensional cutting stock algorithm generates cutting patterns by building rectangles both horizontally and vertically. This algorithm uses a parameter β ₁ to tradeoff the number of rectangles generated by the algorithm and hence the quality of the cutting pattern solution obtained versus the amount of computer resources required. Several researchers have made relatively straightforward modifications to Wang's basic algorithm resulting in improved computational times. However, even with these modifications, Wang's approach tends to require large amounts of computer resources in order to optimally or near-optimally solve difficult two-dimensional guillotine cutting stock problems. In this paper, we present an iterative approach that judiciously uses Wang's basic algorithm (with some previously defined modifications) to obtain optimal cutting patterns to difficult two-dimensional cutting stock problems in reasonable computer run times.     

A least wasted first heuristic algorithm for the rectangular packing problem

The rectangular packing problem is to pack a number of rectangles into a single large rectangular sheet so as to maximize the total area covered by the rectangles packed. The paper first presents a least wasted first strategy which evaluates the positions used by the rectangles. Then a random local search is introduced to improve the results and a least wasted first heuristic algorithm (LWF) is further developed to find a desirable solution. Twenty-one rectangular-packing instances are tested by the algorithm developed, the experimental results show that the presented algorithm can achieve an optimal solution within reasonable time and is fairly efficient for dealing the rectangular packing problem. LWF still performs well when it is extended to solve zero-waste and non-zero-waste strip packing instances.     

Heuristics for two-dimensional knapsack and cutting stock problems with items of irregular shape

In this paper, the two-dimensional cutting/packing problem with items that correspond to simple polygons that may contain holes are studied in which we propose algorithms based on no-fit polygon computation. We present a GRASP based heuristic for the 0/1 version of the knapsack problem, and another heuristic for the unconstrained version of the knapsack problem. This last heuristic is divided in two steps: first it packs items in rectangles and then use the rectangles as items to be packed into the bin. We also solve the cutting stock problem with items of irregular shape, by combining this last heuristic with a column generation algorithm. The algorithms proposed found optimal solutions for several of the tested instances within a reasonable runtime. For some instances, the algorithms obtained solutions with occupancy rates above 90% with relatively fast execution time.     

Bin packing and related problems: General arc-flow formulation with graph compression

We present an exact method, based on an arc-flow formulation with side constraints, for solving bin packing and cutting stock problems—including multi-constraint variants—by simply representing all the patterns in a very compact graph. Our method includes a graph compression algorithm that usually reduces the size of the underlying graph substantially without weakening the model.Our formulation is equivalent to Gilmore and Gomory׳s, thus providing a very strong linear relaxation. However, instead of using column-generation in an iterative process, the method constructs a graph, where paths from the source to the target node represent every valid packing pattern.The same method, without any problem-specific parameterization, was used to solve a large variety of instances from several different cutting and packing problems. In this paper, we deal with vector packing, bin packing, cutting stock, cardinality constrained bin packing, cutting stock with cutting knife limitation, bin packing with conflicts, and other problems. We report computational results obtained with many benchmark test datasets, some of them showing a large advantage of this formulation with respect to the traditional ones.     

New heuristics for one-dimensional bin-packing

Several new heuristics for solving the one-dimensional bin packing problem are presented. Some of these are based on the minimal bin slack (MBS) heuristic of Gupta and Ho. A different algorithm is one based on the variable neighbourhood search metaheuristic. The most effective algorithm turned out to be one based on running one of the former to provide an initial solution for the latter. When tested on 1370 benchmark test problem instances from two sources, this last hybrid algorithm proved capable of achieving the optimal solution for 1329, and could find for 4 instances solutions better than the best known. This is remarkable performance when set against other methods, both heuristic and optimum seeking.Scope and purposePacking items into boxes or bins is a task that occurs frequently in distribution and production. A large variety of different packing problems can be distinguished, depending on the size and shape of the items, as well as on the form and capacity of the bins (H. Dyckhoff and U. Finke, Cutting and Packing in Production and Distribution: a Typology and Bibliography, Springer, Berlin, 1992). Similar problems occur in minimising material wastage while cutting pieces into particular smaller ones and in the scheduling of identical processors in order to minimise total completion time. This work addresses the basic packing problem, known as the one-dimensional bin packing problem, where it is required to pack a number of items into the smallest possible number of bins of pre-specified equal capacity. Even though this problem is simple to state, it is NP hard, i.e., it is unlikely that there exists an algorithm that could solve every instance of it in polynomial time. Solution of more general realistic packing problems is probably contingent upon the availability of effective and computationally efficient solution procedures for the basic problem. In this work we present several heuristics capable of doing that. Extensive computational testing attests to the power of these heuristics, as well as to their computational efficiency.     

An Innovative Genetic Algorithm for a Multi-Objective Optimization of Two-Dimensional Cutting-Stock Problem

This paper addressed an important variant of two-dimensional cutting stock problem. The objective was not only to minimize trim loss, as in traditional cutting stock problems, but rather to minimize the number of machine setups. This additional objective is crucial for the life of the machines and affects both the time and the cost of cutting operations. Since cutting stock problems are well known to be NP-hard, we proposed an approximate method to solve this problem in a reasonable time. This approach differs from the previous works by generating a front with many interesting solutions. By this way, the decision maker or production manager can choose the best one from the set based on other additional constraints. This approach combined a genetic algorithm with a linear programming model to estimate the optimal Pareto front of these two objectives. The effectiveness of this approach was evaluated through a set of instances collected from the literature. The experimental results for different-size problems show that this algorithm provides Pareto fronts very near to the optimal ones.     

Exact Solution of Cutting Stock Problems Using Column Generation and Branch-and-Bound

This paper describes an attempt to solve the one-dimensional cutting stock problem exactly, using column generation and branch-and-bound. A new formulation is introduced for the one-dimensional cutting stock problem that uses general integer variables, not restricted to be binary. It is an arc flow formulation with side constraints, whose linear programming relaxation provides a strong lower bound. In this model, a cutting pattern, which corresponds to a path, is decomposed into single arc variables. The decomposition serves the purpose of showing that it is possible to combine the branch-and-bound method with variable generation. Computational times are reported for one-dimensional cutting stock instances with a number of orders up to 30.