基于临界多边形的不规则件启发式排样算法

为提高不规则件启发式排样的材料利用率,提出一种基于重心临界多边形和边适应度的不规则件启发式排样算法GEFHNA。首先,定义了边适应度以衡量排样过程中原材料与不规则件间贴合程度,在此基础上给出了将边适应度与重心NFP（GNFP）相结合的排放策略以减少排样过程中可能产生的空隙面积;其次,给出了基于Weiler-Atherton多边形裁剪算法的剩余原材料求解方法,重用排样过程中产生的孔洞,减少孔洞面积;最后,给出了基于上述排样策略和材料重用策略的启发式排样算法GEFHNA,给出了与智能算法和同类软件的实验比较。对欧洲排样问题兴趣小组提供的基准测试用例的实验结果表明,GEFHNA的耗时约为基于智能算法的排样方法的千分之一,同时在与两款商业软件NestLib和SigmaNest的11个基准测试的对比中,GEFHNA获得了7/11个相对最优的排样面积利用率。     

用启发算法和神经网络法解决二维不规则零件排样问题

本文提出一种用启发算法和神经网络法相结合的算法解决二维不规则零件的排料问题。此算法具有优化效果好、自动化程度高、并且速度快等特点。     

New approaches to nesting rectangular patterns

In this study, two approaches are explored for the solution of the rectangular stock cutting problem: neuro-optimization, which integrates artificial neural networks and optimization methods; and genetic neuro-nesting, which combines artificial neural networks and genetic algorithms. In the first approach, an artificial neural network architecture is used to generate rectangular pattern configurations, to be used by the optimization model, with an acceptable scrap. Rectangular patterns of different sizes are selected as input to the network to generate the location and rotation of each pattern after they are combined. A mathematical programming model is used to determine the nesting of different sizes of rectangular patterns to meet the demand for rectangular blanks for a given planning horizon. The test data used in this study is generated randomly from a specific normal distribution. The average scrap percentage obtained is within acceptable limits. In the second approach, a genetic algorithm is used to generate sequences of the input patterns to be allocated on a finite width with infinite-length material. Each gene represents the sequence in which the patterns are to be allocated using the allocation algorithm developed. The scrap percentage of each allocation is used as an evaluation criterion for each gene for determining the best allocation while considering successive generations. The allocation algorithm uses the sliding method integrated with an artificial neural network based on the adaptive resonance theory (ART1) paradigm to allocate the patterns according to the sequence generated by the genetic algorithm. It slides an incoming pattern next to the allocated ones and keeps all scrap areas produced, which can be utilized in allocating a new pattern through the ART1 network. If there is a possible match with an incoming pattern and one of the scrap areas, the neural network selects the best match area and assigns the pattern. Both approaches gave satisfactory results. The second approach generated nests having packing densities in the range 95–97%. Improvement in packing densities was possible at the expense of excessive computational time. Parallel implementation of this unconventional approach could well bring a quick and satisfactory solution to this classical problem.     

Solution for textile nesting problems using adaptive meta-heuristics and grouping

 An optimal packing problem of non-convex polygons on a sheet is considered and applied to a textile nesting problem. We propose a procedure of grouping objects and adaptive meta-heuristics. The grouping procedure classifies objects into groups which are then allocated on the sheet using adaptive meta-heuristics. As a result, effectiveness of the meta-heuristics is improved. The performance of the proposed method is compared with other meta-heuristics using simulation experiments. The result shows that the present method is superior to cases where adaptive meta-heuristics without grouping are used.     

Sequential optimization approach for nesting and cutting sequence in laser cutting

The economy of the laser cutting process depends on two productivity issues: (i) nesting, a classic problem of finding the most efficient layout for cutting parts with minimum material waste; (ii) cutting sequence, which targets the optimal sequence of edges of the parts to be cut for minimum cycle time. This paper presents a two stage sequential optimization procedure for nesting and cutting sequence for the objectives of maximizing material utilization and minimization of ideal (non-cut) travel distance of laser cut tool. However, the focus of this paper is the development of solution technique for optimal cutting sequence to any given layout. Simulated annealing algorithm (SAA) is considered to evolve the optimal cutting sequence. The proposed SAA is illustrated with the optimal material utilization layout obtained using sheet cutting suite software, a professional rectangular nesting software package. The robust test carried out with five typical problems shows that the SAA proposed for cutting sequence is capable of providing near optimal solutions. The performance comparison with two literature problems reveals that the proposed SAA is able to give improved result than GA and ACO algorithms.     

Facility layout problems: A survey

Layout problems are found in several types of manufacturing systems. Typically, layout problems are related to the location of facilities (e.g., machines, departments) in a plant. They are known to greatly impact the system performance. Most of these problems are NP hard. Numerous research works related to facility layout have been published. A few literature reviews exist, but they are not recent or are restricted to certain specific aspects of these problems. The literature analysis given here is recent and not restricted to specific considerations about layout design.

We suggest a general framework to analyze the literature and present existing works using such criteria as: the manufacturing system features, static/dynamic considerations, continual/discrete representation, problem formulation, and resolution approach. Several research directions are pointed out and discussed in our conclusion.     

A hybrid algorithm for the two-dimensional layout problem: the cases of regular and irregular shapes

The two-dimensional layout (TDL) optimization problem consists of finding the minimal length layout of a set of both regular and irregular two-dimensional shapes on a stock sheet of finite width but infinite length. The layout should not contain any overlap. In this paper, we solve the TDL problem by proposing two approximate algorithms. The first one is a new heuristic based on a constructive approach specifically designed for irregular shapes, but that works well with regular ones. The second is a hybrid method in which the constructive approach displays the layouts corresponding to the chromosomes yielded by the genetic algorithm. The resulting algorithm yields satisfactory results in relatively short computational times as shown by the extensive computational testing on problems from the literature.     

Employing subgroup evolution for irregular-shape nesting

This paper introduces a new method to solve the irregular-shape, full-rotation nesting problem by a genetic algorithm. Layout patterns are evolved in hierarchical subgroups to facilitate the search for an optimal solution in such a complex solution space. The genotype used in the genetic algorithm contains both the sequence and rotation for each shape, requiring new genetic operators to manipulate a multi-type genetic representation. A lower-left placement heuristic coupled with matrix encoding of the shapes and plate prevents overlap and constrains the solution space to valid solutions. This new method is able to efficiently search the solution space for large problems involving complex shapes with 360 degrees of freedom. The algorithm generates better solutions than previously published evolutionary methods.     

A hybrid heuristic to reduce the number of different patterns in cutting stock problems

We propose a hybrid procedure to obtain a reduced number of different patterns in cutting stock problems. Initially, we generate patterns with limited waste that fulfill the demands of at least two items when the patterns are repeatedly cut as much as possible but without overproducing any of the items. The problem is reduced and the residual problem is solved. Then, pattern reduction techniques (local search) are applied starting with the generated solution. The scheme is straightforward and can be used in cutting stock problems of any dimension. Variations of the procedure are also indicated. Computational tests performed indicated that the proposed scheme provides alternative solutions to the pattern reduction problem which are not dominated by other solutions obtained using procedures previously suggested in the literature.     

A global constraint for nesting problems

Nesting problems are particularly hard combinatorial problems. They involve the positioning of a set of small arbitrarily-shaped pieces on a large stretch of material, without overlapping them. The problem constraints are bidimensional in nature and have to be imposed on each pair of pieces. This all-to-all pattern results in a quadratic number of constraints. Constraint programming has been proven applicable to this category of problems, particularly in what concerns exploring them to optimality. But it is not easy to get effective propagation of the bidimensional constraints represented via finite-domain variables. It is also not easy to achieve incrementality in the search for an improved solution: an available bound on the solution is not effective until very late in the positioning process. In the sequel of work on positioning non-convex polygonal pieces using a CLP model, this work is aimed at improving the expressiveness of constraints for this kind of problems and the effectiveness of their resolution using global constraints. A global constraint “outside” for the non-overlapping constraints at the core of nesting problems has been developed using the constraint programming interface provided by Sicstus Prolog. The global constraint has been applied together with a specialized backtracking mechanism to the resolution of instances of the problem where optimization by Integer Programming techniques is not considered viable. The use of a global constraint for nesting problems is also regarded as a first step in the direction of integrating Integer Programming techniques within a Constraint Programming model.     

A PTAS for Cutting Out Polygons with Lines

We present a simple O(m+n ⁶/ε ¹²) time (1+ε)-approximation algorithm for finding a minimum-cost sequence of lines to cut a convex n-gon out of a convex m-gon.     

A heuristic algorithm for group scheduling

Group technology is a rapidly developing productivity improvement tool that can have a significant impact on the development of totally integrated manufacturing facilities and flexible manufacturing systems. Production scheduling associated with group technology is called “Group Scheduling”. There are many heuristic algorithms developed for general job shop applications based on unrealistic hypothesis, complicated computations etc., which are not addressed to group scheduling. In this paper, from the existing algorithms for group scheduling, a heuristic algorithm has been developed and programmed for computer/microcomputer applications. The developed algorithm has been used to determine the optimal group and the optimal job sequence for a batch type production process with functional layout. The developed algorithm is far simpler and easier to compute, compared to the other similar heuristic algorithms and certainly in comparison to other optimization methods such as branch and bound method.     

A heuristic procedure for the integrated facility layout design and flow assignment problem

We present an efficient iterative heuristic procedure for solving the integrated layout design and product flow assignment problem. The layout design decisions involve planar location of unequal-area machines with duplicates. The product flows are assigned to machines according to the product processing routes. The integrated decision problem is a nonlinear mixed integer model which cannot be efficiently solved using classical methods for large problems. We propose a novel integrated heuristic procedure based on the alternating heuristic, a perturbation algorithm and sequential location heuristic. Since the alternating heuristic between facility layout design and product-machine assignment sub-problems terminates with local optima, we developed a perturbation algorithm based on assignment decisions. The results of an experimental study show that proposed procedure is both efficient and effective in identifying quality solutions for small to very large-sized problems.     

A Fast Quartet tree heuristic for hierarchical clustering

The Minimum Quartet Tree Cost problem is to construct an optimal weight tree from the weighted quartet topologies on n objects, where optimality means that the summed weight of the embedded quartet topologies is optimal (so it can be the case that the optimal tree embeds all quartets as nonoptimal topologies). We present a Monte Carlo heuristic, based on randomized hill-climbing, for approximating the optimal weight tree, given the quartet topology weights. The method repeatedly transforms a dendrogram, with all objects involved as leaves, achieving a monotonic approximation to the exact single globally optimal tree. The problem and the solution heuristic has been extensively used for general hierarchical clustering of nontree-like (non-phylogeny) data in various domains and across domains with heterogeneous data. We also present a greatly improved heuristic, reducing the running time by a factor of order a thousand to ten thousand. All this is implemented and available, as part of the CompLearn package. We compare performance and running time of the original and improved versions with those of UPGMA, BioNJ, and NJ, as implemented in the SplitsTree package on genomic data for which the latter are optimized.     

A fault-tolerant parallel heuristic for assignment problems

This paper presents a new approach for parallel heuristic algorithms based on adaptive parallelism. Adaptive parallelism was used to dynamically adjust the parallelism degree of the application with respect to the system load. This approach demonstrates that high-performance computing using a hundred of heterogeneous workstations combined with massively parallel machines is feasible to solve large optimization problems with respect to the personal character of workstations. The fault-tolerant algorithm allows a minimal loss of computation in case of failures. The proposed algorithm exploits the properties of this class of applications in order to reduce the complexity of the algorithm in terms of the checkpoint files size and the control messages exchanged. The parallel heuristic algorithm combines different search strategies: simulated annealing and tabu search. Encouraging results have been obtained in solving the quadratic assignment problem. We have improved the best known solutions for some large real-world problems.     

A general heuristic for vehicle routing problems

We present a unified heuristic which is able to solve five different variants of the vehicle routing problem: the vehicle routing problem with time windows (VRPTW), the capacitated vehicle routing problem (CVRP), the multi-depot vehicle routing problem (MDVRP), the site-dependent vehicle routing problem (SDVRP) and the open vehicle routing problem (OVRP).     

A heuristic iterated-subspace minimization method with pattern search for unconstrained optimization

Recently, an increasing attention was paid on different procedures for an unconstrained optimization problem when the information of the first derivatives is unavailable or unreliable. In this paper, we consider a heuristic iterated-subspace minimization method with pattern search for solving such unconstrained optimization problems. The proposed method is designed to reduce the total number of function evaluations for the implementation of high-dimensional problems. Meanwhile, it keeps the advantages of general pattern search algorithm, i.e., the information of the derivatives is not needed. At each major iteration of such a method, a low-dimensional manifold, the iterated subspace, is constructed. And an approximate minimizer of the objective function in this manifold is then determined by a pattern search method. Numerical results on some classic test examples are given to show the efficiency of the proposed method in comparison with a conventional pattern search method and a derivative-free method.     

一种不规则零件排样的新粒子群优化策略

基于图形扫描转换的启发式底左（Heuristic Bottom-Left,HBL）算法,把一种最大速度收缩策略（Maximal Velocity Contractile Strategy,MVCS）的粒子群优化（Particle Swarm Optimization,PSO）算法应用于不规则零件的优化排样,给出了新的排样组合优化算法（MVCS-PSO）的粒子构造方法和零件排样过程,通过实例把该算法与模拟退火遗传算法（Simulated Annealing Genetic Algorithms,SAGA）进行优化排样比较,实验结果表明,具有良好的非线性和动态搜索性能的MVCS-PSO算法是求解排样问题的一种高效算法。     

A heuristic for the skiving and cutting stock problem in paper and plastic film industries

This paper investigates the skiving and cutting stock problem (SCSP) encountered in the paper and plastic film industries, in which a set of nonstandard reels generated from previous cutting processes are used to produce finished rolls through the skiving and cutting process. First, reels are skived together lengthwise to form a reel‐pyramid (a polygon), and then the reel‐pyramid is cut into finished rolls of small widths. Depending on if a reel can be divided lengthwise into subreels to form the reel‐pyramid, the problem can be classified into divisible SCSP (DSCSP) and indivisible SCSP (ISCSP). In this paper, two integer programming (IP) models are proposed for DSCSP and ISCSP, respectively. A sequential value correction procedure combined with the two IP models (SVCTIP) is developed to solve the two SCSPs. The effectiveness of the SVCTIP is demonstrated through extensive computational tests.     

一种有效的求解一维下料问题的启发式算法

使用了一种改进的顺序启发式算法,在排样方式的生成过程中不断修正当前排入毛坯的价值,使之趋于合理,依次选取求解背包函数获得的最大单位价值的排样方式组成当前排样方案,迭代调用该过程多次,最终选取最优的排样方案。在保证较高材料利用率的同时考虑减少排样方式,增加最后一根材料余料长度等多个优化目标。通过多组实验结果比较,证实了算法的有效性。