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

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

二维多阶段矩形剪切排样算法

讨论有需求约束的二维剪切矩形排样问题:将一张板材剪切成一组已知尺寸的毛坯,使排样价值(板材中包含的毛坯总价值)最大,约束条件是排样方式中包含每种毛坯数量都不能超过其需求量。采用普通条带多阶段排样方式,每次剪切都从板材上产生一根水平或者竖直的普通条带,条带中可以包含不同尺寸毛坯。引入分支限界与贪婪策略,以提高算法效率。实验结果表明,该算法可以有效提高排样价值。     

矩形毛料无约束二维剪切排样的递归算法

将板材分成一系列的板块.对于每一板块,通过优化选择一个毛料放在其左下角,并确定剪切线的方向;沿着该毛料的上边界或右边界将剩余区域分成2个更小的板块以待进一步排样.实验结果表明：该算法的时间效率可满足实际应用的需要,与其他算法相比,所给出的排样方式材料利用率较高.     

一种实用的二维不规则零件排样算法

模拟人排样的排样过程,提出了排样问题的计算和过程模型,实现了直接对多边形进行排样,在实现每重零件的最优的基础上实现排样的近优,实现了快速高效的排样.     

一种实用的二维不规则零件排样算法

模拟人排样的排样过程,提出了排样问题的计算和过程模型,实现了直接对多边形进行排样,在实现每重零件的最优的基础上实现排样的近优,实现了快速高效的排样。     

用于求解二维圆形排样问题的自适应混合算法

针对二维圆形版面不等圆排样问题,在最小局部距离定位布局策略的基础上,引入紧凑度和适应度,提出基于拟矩形排样的自适应启发式算法,并与以自然数编码的遗传算法相结合构建混合算法。该混合算法发挥两者的全局搜索能力与局部寻优能力。在标准测试算例上,与一些经典算法进行比较,结果表明,该算法能够在更短的时间内获得更为满意的结果。     

一种高效的矩形套裁排样的带填充排样算法

提出一种带填充排样算法,实现矩形毛坯套裁排样。该算法首先用水平剪切线将板材分层,每层的宽度和板材宽度相同,高度和层最左端的主毛坯高度相同;通过调用两个递归过程确定最优排样方式,第一个过程确定每层左端的主毛坯,第二个过程确定层右端区域的毛坯排列方式。采用分支定界技术缩小搜索空间。实验计算结果说明所述算法比文献中最近报道的几种算法都有效。     

基于两阶段排放算法的矩形件排样优化方法

针对矩形件排样问题,经典的最下左填充(BLF)算法易于出现区域浪费、原材料利用率低的缺点。对此,提出一种改进的两阶段排放算法。第一阶段利用BLF算法,第二阶段设计一个改进BLF排放算法以减小区域的浪费。再以矩形件排放顺序进行编码,利用两阶段排放算法解码,设计邻域搜索算法寻找最优解。通过已有文献的多个案例,对改进的算法进行实验验证,结果与BLF算法相比,原材料利用率能提高14%,证实了改进算法的有效性。     

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

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

一种卷板填充分层递归排样的优化算法

研究了卷板填充排样问题,提出了一种分层递归排样的优化算法。算法使用水平剪切线将卷板分层,每层的宽度和卷板宽度相同,高度和层最左端的主毛坯高度相同;通过调用递归过程确定卷板中层的排列,为各层选定主毛坯,并确定毛坯的排列方式;采用分支定界技术缩小搜索空间。实验结果说明该算法比文献中最近报道的几种算法都有效。     

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

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

Sequential value correction heuristic for the two-dimensional cutting stock problem with three-staged homogenous patterns

A sequential value correction heuristic is presented for the two-dimensional cutting stock problem with three-staged homogenous patterns, considering both input-minimization and simplicity of the cutting process. The heuristic constructs many cutting plans iteratively and selects the best one as the solution. The patterns in each cutting plan are generated sequentially using simple recursive techniques. The values of the item types are corrected after the generation of each pattern to diversify the cutting plans. Computational results indicate that the proposed heuristic is more effective in input minimization than published algorithms and commercial stock cutting software packages that use three-staged general or exact patterns.     

The multiperiod two‐dimensional non‐guillotine cutting stock problem with usable leftovers

A mixed integer linear programing model for the two‐dimensional non‐guillotine cutting problem with usable leftovers was recently introduced by Andrade et al. The problem consists in cutting a set of ordered items using a set of objects of minimum cost and, within the set of solutions of minimum cost, maximizing the value of the usable leftovers. Since the concept of usable leftovers assumes they can potentially be used to attend new arriving orders, the problem is extended to the multiperiod framework in this work. In this way, the decision at each instant does not minimize in a myopic way the cost of the objects required to attend the orders of the current instant; but it aims to minimize the overall cost of the objects up to the considered time horizon. Some variants of the proposed model are analyzed and numerical results are presented.     

Arc-flow model for the two-dimensional guillotine cutting stock problem

We describe an exact model for the two-dimensional cutting stock problem with two stages and the guillotine constraint. It is an integer linear programming (ILP) arc-flow model, formulated as a minimum flow problem, which is an extension of a model proposed by Valério de Carvalho for the one dimensional case. In this paper, we explore the behavior of this model when it is solved with a commercial software, explicitly considering all its variables and constraints. We also derive a new family of cutting planes and a new lower bound, and consider some variants of the original problem. The model was tested on a set of real instances from the wood industry, with very good results. Furthermore the lower bounds provided by the linear programming relaxation of the model compare favorably with the lower bounds provided by models based on assignment variables.     

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.     

An exact dynamic programming algorithm for large-scale unconstrained two-dimensional guillotine cutting problems

In the unconstrained two-dimensional cutting problems (U2DCP) small rectangular objects have to be extracted from a large rectangular sheet, with no limits on the number of small objects.The exact U2DCP solving approaches present in literature show some limits in tackling very large size instances, due to the high memory requirements.In this work we propose five improvements, three original and two derived from the literature, in order to overcome these limits and to reduce the computational burden of the knapsack function based U2DCP solving approaches. These improvements, based on proofed theoretical results, allow to reduce the search space and to avoid redundant solutions without loss of the feasible ones.The presented improvements, together with several computational refinements, are integrated in a new dynamic programming algorithm, which modifies the one by Russo et al. (2013 [16]). The proposed algorithm has been experienced on test instances present in literature and compared with the best U2DCP solving approaches. The obtained results show that it significantly outperforms them and it determines the optimal solution of unsolved very large size instances.     

Hybrid heuristic algorithm for two-dimensional steel coil cutting problem

This paper is concerned with the problem of two-dimensional cutting of small rectangular items, each of which has its own deadline and size, from a large rectangular plate, whose length are more than one thousand times its width, so as to minimize the trim loss and the reduction of the times of clamping and changing speed are also concerned. This problem is different with the classical two-dimensional cutting problem. In view of the distinguishing features of the problem proposed, we put forward the definition of non-classical cutting, that is to say, put a series of items on the rectangular plates in their best layout, so as to enhance utility and efficiency at the same time. These objectives may be conflicting and a balance should be necessary, so we present a Hybrid Heuristic Algorithm (HHA), consisting of clustering, ordering, striping and integer programming etc. We demonstrate the efficiency of the proposed algorithm through the comparison with the algorithm we studied before.     

Heuristic for the two-dimensional arbitrary stock-size cutting stock problem

A heuristic is presented for the two-dimensional arbitrary stock-size cutting stock problem, where a set of rectangular items with specified demand are cut from plates of arbitrary sizes that confirm to the supplier’s provisions, such that the plate cost is minimized. The supplier’s provisions include: the lengths and widths of the plates must be in the specified ranges; the total area of the plates with the same size must reach the area threshold. The proposed algorithm uses a pattern-generation procedure with all-capacity property to obtain the patterns, and combines it with a sequential heuristic procedure to obtain the cutting plan, from which the purchasing decision can be made. Practical and random instances are used to compare the algorithm with a published approach. The results indicate that the trim loss can be reduced by more than half if the algorithm is used in the purchasing decision of the plates.     

Improved Tabu search heuristics for the dynamic space allocation problem

The dynamic space allocation problem (DSAP) presented in this paper considers the task of assigning items (resources) to locations during a multi-period planning horizon such that the cost of rearranging the items is minimized. Three tabu search heuristics are presented for this problem. The first heuristic is a simple basic tabu search heuristic. The second heuristic adds diversification and intensification strategies to the first, and the third heuristic is a probabilistic tabu search heuristic. To test the performances of the heuristics, a set of test problems from the literature is used in the analysis. The results show that the tabu search heuristics are efficient techniques for solving the DSAP. More importantly, the proposed tabu search heuristic with diversification/intensification strategies found new best solutions using less computation time for one-half of all the test problems.     

应用精确两阶段排样图的板材下料算法

求解基于精确两阶段排样图的二维下料问题,用最小的板材成本,生产出所需要的全部毛坯。将顺序启发式算法和排样图生成算法相结合,顺序生成排样方案中的各个排样图;采用顺序价值修正策略,在生成每个排样图后修正其中所含各种毛坯的价值。经过多次迭代生成多个排样方案,从中选择最好者。实验计算时与商业软件和文献算法相比较,结果表明所述算法可以更为有效地减少板材消耗。