Search

This paper addresses the one-dimensional cutting stock problem, focusing on minimizing total stock usage. Most procedures that deal with this problem reside on linear programming methods, heuristics, metaheuristics, and hybridizations. These methods face drawbacks like handling only low-complexity instances or requiring extensive parameter tuning. To address these limitations we develop a Petri-net model to construct cutting patterns. Using the filtered beam search algorithm, the reachability tree of the Petri net is constructed level by level from its root node to find the best solution, pruning the nodes that worsen the solution as the search progresses through the tree. Our algorithm is compared with the Least Lost Algorithm and the Generate and Solve algorithm over five datasets of instances. These algorithms share some characteristics with ours and have proven to be effective and efficient. Experimental results demonstrate that our algorithm effectively finds optimal and near-optimalsolutions for both low and high-complexity instances. These findings confirm that Petri nets are suitable for modeling and solving the one-dimensional cutting stock problem. [ABSTRACT FROM AUTHOR]

Packing problems are classical optimization problems with wide-ranging applications. With the advancement of robotic manipulation, there are growing demands for the automation of packing tasks. However, the simultaneous optimization of packing and the robot’s motion planning is challenging because these two decisions are interconnected, and no previous study has addressed this optimization problem. This paper presents a framework to simultaneously determine the robot’s motion planning and packing decision to minimize the robot’s processing time and the container’s volume. This framework comprises three key components: solution encoding, surrogate modeling, and evolutionary computation. The sequence-triple representation encodes complex packing solutions by a sequence of integers. A surrogate model is trained to predict the processing time for a given packing solution to reduce the computational burden. Training data is generated by solving the motion planning problem for a set of packing solutions using the rapidly exploring random tree algorithm. The Non-Dominated Sorting Genetic Algorithm II searches for the Pareto solutions. Experimental evaluations are conducted using a 6-DOF robot manipulator. The experimental results suggest that implementing the surrogate model can reduce the computational time by 91.1%. The proposed surrogate-assisted optimization method can obtain significantly better solutions than the joint angular velocity-based estimation method.

The efficient arrangement of patterns on a substrate surface is of paramount importance across diverse domains, including manufacturing, design, nanotechnology, and printed electronics. This paper introduces three distinct strategies for pattern arrangement within the realm of two-dimensional cutting and packing challenges. Firstly, for irregular patterns, we have developed a modified genetic algorithm that effectively determines the spatial relationships between patterns, facilitating subsequent packing processes. Secondly, we present the “MaxiRectPack” method designed for rectangular patterns. This method utilizes partitioning techniques and a variety of orientation schemes to maximize pattern packing efficiency. Lastly, we propose a technique based on normalized 2-D cross-correlation for patterns of diverse shapes, allowing precise placement while accounting for variations in substrate and pattern energy. These methodologies are adaptable, catering to irregular, rectangular, and diverse pattern shapes, offering versatile solutions for pattern placement in the context of two-dimensional cutting and packing. With a strong emphasis on resource conservation and spatial efficiency, this research equips practitioners and researchers with practical tools for optimizing material utilization and pattern arrangement on substrates.

This paper addresses the one-dimensional cutting stock problem, focusing on minimizing total stock usage. Most procedures that deal with this problem reside on linear programming methods, heuristics, metaheuristics, and hybridizations. These methods face drawbacks like handling only low-complexity instances or requiring extensive parameter tuning. To address these limitations we develop a Petri-net model to construct cutting patterns. Using the filtered beam search algorithm, the reachability tree of the Petri net is constructed level by level from its root node to find the best solution, pruning the nodes that worsen the solution as the search progresses through the tree. Our algorithm is compared with the Least Lost Algorithm and the Generate and Solve algorithm over five datasets of instances. These algorithms share some characteristics with ours and have proven to be effective and efficient. Experimental results demonstrate that our algorithm effectively finds optimal and near-optimalsolutions for both low and high-complexity instances. These findings confirm that Petri nets are suitable for modeling and solving the one-dimensional cutting stock problem.

A convex geometric graph G $G$ is said to be packable if there exist edge‐disjoint copies of G $G$ in the complete convex geometric graph Kn ${K}_{n}$ covering all but o(n2) $o({n}^{2})$ edges. We prove that every convex geometric graph with cyclic chromatic number at most 4 is packable. With a similar definition of packability for ordered graphs, we prove that every ordered graph with interval chromatic number at most 3 is packable. Arguments based on the average length of edges imply these results are the best possible. We also identify a class of convex geometric graphs that are packable due to having many "long" edges. [ABSTRACT FROM AUTHOR]

We present a novel learning framework to solve the transport-and-packing (TAP) problem in 3D. It constitutes a full solution pipeline from partial observations of input objects via RGBD sensing and recognition to final box placement, via robotic motion planning, to arrive at a compact packing in a target container. The technical core of our method is a neural network for TAP, trained via reinforcement learning (RL), to solve the NP-hard combinatorial optimization problem. Our network simultaneously selects an object to pack and determines the final packing location, based on a judicious encoding of the continuously evolving states of partially observed source objects and available spaces in the target container, using separate encoders both enabled with attention mechanisms. The encoded feature vectors are employed to compute the matching scores and feasibility masks of different pairings of box selection and available space configuration for packing strategy optimization. Extensive experiments, including ablation studies and physical packing execution by a real robot (Universal Robot UR5e), are conducted to evaluate our method in terms of its design choices, scalability, generalizability, and comparisons to baselines, including the most recent RL-based TAP solution. We also contribute the first benchmark for TAP which covers a variety of input settings and difficulty levels. [ABSTRACT FROM AUTHOR]

Packing a designated set of shapes on a regular grid is an important class of operations research problems that has been intensively studied for more than six decades. Representing a d-dimensional discrete grid as Zd, we formalise the generalised regular grid (GRG) as a surjective function from Zd to a geometric tessellation in a physical space, for example, the cube coordinates of a hexagonal grid or a quasilattice. This study employs 0-1 integer linear programming (ILP) to formulate the polyomino tiling problem with adjacency constraints. Rotation & reflection invariance in adjacency are considered. We separate the formal ILP from the topology & geometry of various grids, such as Ammann-Beenker tiling, Penrose tiling and periodic hypercube. Based on cutting-edge solvers, we reveal an intuitive correspondence between the integer program (a pattern of algebraic rules) and the computer codes. Models of packing problems in the GRG have wide applications in production system, facility layout planning, and architectural design. Two applications in planning high-rise residential apartments are illustrated.

This article is about the current agricultural scenario, where large‐scale production causes large amounts of food to be transported to various points of consumption, causing substantial emissions of so‐called greenhouse gases and increasing the carbon footprint. Land use optimization and land parcel allocation are essential areas of agriculture research that currently represent relevant challenges and are classified as combinatorial optimization problems. In this context, the Selection and Allocation of Land Parcels Problem (SA‐LPP) is proposed; its goal is to optimize the selection and allocation of land parcels with rectangular shapes in small areas available for food production. We propose a reformulation of the SA‐LPP as a variant of the two‐dimensional orthogonal packing problem (2OPP), called Group‐2OPP. This problem was solved through a Mixed‐Integer Linear Programming (MILP) model, but due to the model complexity, we also propose a Greedy Randomized Adaptive Search Procedure metaheuristic approach. Some sensitivity analyses were performed as well to evaluate the impact of parameters on the solutions. Computational results show that the proposed metaheuristic outperforms the MILP model in terms of solution quality and computational times. [ABSTRACT FROM AUTHOR]

Sangaku problem is one of Japanese Temple Geometry problems which was studied in Hidetoshi Fukugawa[1]. One of the Sangaku problem is packing 6 equal circles in rectangle of 1:1.934798 size. We examine the problem from a view point of optimization theory and algorithm. We show that Sangaku optimization problem belongs to a class of nonconvex optimization and propose a penalty method for solving the problem numerically. In numerical expirements, we consider equal and unequal 6 circles. Computational results obtained on Python Jupyter Notebook are provided. [ABSTRACT FROM AUTHOR]

Copyright of China Sciencepaper is the property of China Sciencepaper and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The development of new information technologies at the beginning of the 21st century allows the integration between the physical and the virtual world. In Engineering, an emerging technology called digital twins is presented as the mechanism to virtualize the operation of devices, machines and processes. In industrial engineering and specifically in supply chains there is a growing interest in the development of digital twins. For this reason, this paper proposes the integration of large-scale optimization problems in a digital platform that allows the solution of these problems for decision-making in real time. Bin-Packing and Vehicle Routing problems are addressed through the interface of a commercial supply chain management platform and heuristic optimization algorithms. We use technology based on simulation of discrete events to achieve the periodic decisions that make up the Digital Supply ChainTwin engine. A hypothetical case solution is presented to verify the performance of the proposed development. [ABSTRACT FROM AUTHOR]

This paper addresses a two-dimensional rectangular cutting problem with guillotine constraint, applied to the transformer industry. The problem requires a set of rectangular items to be cut from larger and variable-sized rectangles, known as bins. The goal is to minimize the number of bins used to cut all required items. An effective discrete artificial bee colony is proposed to solve the problem. The approach uses a decimal encoding method where each integer represents a type of bin or item, and decodes the list of integers by a constructive heuristic to generate cutting patterns with guillotine-cut constraint. In addition, a copy strategy is designed to improve the solution quality. The approach's performances and the effectiveness of the strategy are evaluated by three datasets generated from real-world data. The experimental results show that the discrete artificial bee colony is superior to other competitive algorithms, and that the copy strategy can produce higher quality solutions. • A cutting problem with guillotine arisen in reality is studied. • A creative heuristic algorithm is proposed to generate cutting pattern. • A discrete artificial bee colony is proposed to solve the problem. • The performance of approach is assessed by datasets obtained from factory. [ABSTRACT FROM AUTHOR]

A concept for a millimetre-wave (MMW) heat exchanger (HX) featuring AlN:Mo ceramic composite structures as electromagnetic absorbing elements (susceptors) has been recently introduced as a receiving device in power beaming applications. Earlier computational studies of electromagnetic and thermal processes have shown reasonable energy efficiency and exceptional uniformity of MMW-induced temperature fields in a single cubic susceptor with concentration of Mo doping on the level of 3–4% by volume. As part of ongoing research, a MMW HX comprised of an array of cylindrical susceptors is proposed to potentially enable increased robustness against thermal stress and reduced manufacturing cost. In this paper, we computationally study the effects driven by such a change and demonstrate feasibility of the designs based on multiple cylinders. We present the output of electromagnetic and coupled electromagnetic-thermal simulations of a prospective physical prototype of a HX with five cylinders on a square metal base plate. Three alternative layouts with four, nine, and sixteen cylindrical elements that are suggested by the highest density packing of equal circles in a square are also analyzed. It is shown that, in comparison with the previously studied case of a single cubic susceptor, energy efficiency of all systems with Mo = 3–4% is down from 50–55% to 35–45%. While temperature distribution within each individual cylinder remains highly uniform, maximum temperatures of different cylinders may be different by up to 30–40 °C; when the angle of incidence deviates from normal, this difference further increases: e.g. when the angle is 10°, in the sixteen-cylinder system, it may reach 120–130 °C. [ABSTRACT FROM AUTHOR]

The article is devoted to problems related with the development of algorithms for creating, optimizing and placing of orthogonal polyhedrons of arbitrary dimension. Under N-dimensional orthogonal polyhedron is understood a composite object represented as a set of N-dimensional parallelepipeds with a fixed position relative to each other, which is considered as a whole. The need to solve the problem of placing a set of objects in the form of orthogonal polyhedrons of arbitrary dimension arises when solving a large number of practical problems in the automation of design and production. In particular, solving the layout problems of equipment and space, problems of cutting materials, problems of designing very large-scale integrated circuits, and optimizing the distribution of resources in computing and production systems, as well as many other actual problems, can be reduced to solving the problem of packing orthogonal polyhedrons. To create a new N-dimensional orthogonal polyhedron, the operations of addition, subtraction and multiplication of orthogonal objects are implemented. With the aim to increase the placement speed of orthogonal polyhedrons which were created with using the voxel model, an algorithm for partitioning of an orthogonal polyhedron into many non-overlapping each other as large as possible large orthogonal objects is proposed. In the scientific literature, there are no solutions to the problem of partitioning an orthogonal polyhedron of arbitrary dimension. The proposed partitioning algorithm is based on the usage of a model of potential containers developed to solve the orthogonal packing problems of arbitrary dimension. To obtain a container of arbitrary shape, a possibility of setting its geometric constraints with an orthogonal polyhedron is implemented. The article presents an algorithm developed for packing an N-dimensional orthogonal polyhedrons inside containers of arbitrary geometric shape, based on the application of multiplication orthogonal polyhedrons operations to obtain the set of points of permissible placement of each considered object. The examples of solving the problems of cutting the industrial materials into objects of irregular shapes, as well as solving the problems of placement complex objects created with using the voxel model into containers of various geometric shapes (including sphere and cone) are given. The effectiveness of the application of the developed algorithms is shown on the example of solving the problem of generation a dense layout of details on a 3D printer platform. [ABSTRACT FROM AUTHOR]

We study several consequences of the packing problem, a conjecture from combinatorial optimization, using algebraic invariants of square-free monomial ideals. While the packing problem is currently unresolved, we successfully settle the validity of its consequences. Our work prompts additional questions and conjectures, which are presented together with their motivation. [ABSTRACT FROM AUTHOR]

Production planning in 3D printing factories brings new challenges among which the scheduling of parts to be produced stands out. A main issue is to increase the efficiency of the plant and 3D printers productivity. Planning, scheduling, and nesting in 3D printing are recurrent problems in the search for new techniques to promote the development of this technology. In this work, we address the problem for the suppliers that have to schedule their daily production. This problem is part of the LONJA3D model, a managed 3D printing market where the parts ordered by the customers are reorganized into new batches so that suppliers can optimize their production capacity. In this paper, we propose a method derived from the design of combinatorial auctions to solve the nesting problem in 3D printing. First, we propose the use of a heuristic to create potential manufacturing batches. Then, we compute the expected return for each batch. The selected batch should generate the highest income. Several experiments have been tested to validate the process. This method is a first approach to the planning problem in 3D printing and further research is proposed to improve the procedure.

This article proposes a novel discrete grey wolf optimization for the packing problem, called the two-dimensional strip packing (2DSP) problem without guillotine constraint. The 2DSP involves cutting pieces from a stock sheet with the objective of minimizing waste. To solve the 2DSP problem by the discrete grey wolf algorithm, many strategies are originally proposed. The searching and attacking operators in the algorithm are redesigned to guarantee coding effectiveness. A novel approach to measure the distance between the wolves is presented. In addition, an improved best-fit strategy is developed to solve this packing problem. The best-fit strategy divides the situation into five cases based on the width and length of the rectangle. Computational results on widely used benchmark instances show that the novel discrete grey wolf algorithm can solve the 2DSP problem effectively, and surpasses most of the previously reported meta-heuristic algorithms.

For large power systems, a continual challenge is to display wide-area data in a way that maximizes human users’ situational awareness. This paper describes a new visualization technique that draws a mosaic of colored tiles to represent multiple data fields for electric grid objects, arranged to preserve geographic context. The key problem in creating these diagrams is packing the tiles onto the display space, minimizing the total displacement while forbidding overlaps. This paper formulates that problem and presents a horizontal-packing algorithm which is able to produce a feasible, quality solution at an interactive time scale. Illustrative examples are shown for using mosaics to monitor wide-area generator status and dispatch, bus voltages, and line and transformer limits. Mosaics can be customized in numerous ways to show different aspects of the system state, providing for human users a simultaneous sense of the wide-area summary, regional trends, and prominent outliers.

We study online secretary problems with returns in combinatorial packing domains with n candidates that arrive sequentially over time in random order. The goal is to determine a feasible packing of candidates of maximum total value. In the first variant, each candidate arrives exactly twice. All 2n arrivals occur in random order. We propose a simple 0.5‐competitive algorithm. For the online bipartite matching problem, we obtain an algorithm with ratio at least 0.5721 − o(1), and an algorithm with ratio at least 0.5459 for all n ≥ 1. We extend all algorithms and ratios to k ≥ 2 arrivals per candidate. In the second variant, there is a pool of undecided candidates. In each round, a random candidate from the pool arrives. Upon arrival a candidate can be either decided (accept/reject) or postponed. We focus on minimizing the expected number of postponements when computing an optimal solution. An expected number of Θ(n log n) is always sufficient. For bipartite matching, we can show a tight bound of O(r log n), where r is the size of the optimum matching. For matroids, we can improve this further to a tight bound of O(r′ log(n/r′)), where r′ is the minimum rank of the matroid and the dual matroid. [ABSTRACT FROM AUTHOR]

In this paper, the authors present a new algorithm efficient solution to the packing problem in two dimensions. The authors propose a new heuristic using the value of the electromagnetic field to determine the best position to place a circular object in a configuration of other circular objects previously packed. Also, this algorithm simulates two processes to compact objects already placed, inspired by gravitational forces, to minimize the empty space in the container and maximizing the number of objects in the container. To determine the efficacy of this algorithm, the authors carried out experiments with twenty-four instances. Parallel computing can contribute to making decision processes such as optimization and prediction more agile and faster. Real-time decision making involves the use of solution methodologies and algorithms. For this reason the present manuscript shows an alternative for the solution of a classic industry problem that must be solved quickly. Packaging optimization can help reduce waste of container material. The material used to transport the products can reduce its environmental impact due to an efficient packaging process. Light-weighting can also be accomplished by reducing the amount of packaging material used. [ABSTRACT FROM AUTHOR]

This paper introduces a faster and more efficient algorithm for solving a two-dimension packing problem. This common optimization problem takes a set of geometrical objects and tries to find the best form of packing them in a space with specific characteristics, called container. The visualization of nanoscale electromagnetic fields was the inspiration for this new algorithm, using the electromagnetic field between the previously placed objects, this paper explains how to determine the best positions for to place the remaining ones. Two gravitational phenomena are also simulated to achieve better results: shaken and gravity. They help to compact the objects to reduce the occupied space. This paper shows the executions of the packing algorithm for four types of containers: rectangles, squares, triangles, and circles. [ABSTRACT FROM AUTHOR]

We introduce the transport-and-pack (TAP) problem, a frequently encountered instance of real-world packing, and develop a neural optimization solution based on reinforcement learning. Given an initial spatial configuration of boxes, we seek an efficient method to iteratively transport and pack the boxes compactly into a target container. Due to obstruction and accessibility constraints, our problem has to add a new search dimension, i.e., finding an optimal transport sequence, to the already immense search space for packing alone. Using a learning-based approach, a trained network can learn and encode solution patterns to guide the solution of new problem instances instead of executing an expensive online search. In our work, we represent the transport constraints using a precedence graph and train a neural network, coined TAP-Net, using reinforcement learning to reward efficient and stable packing. The network is built on an encoder-decoder architecture, where the encoder employs convolution layers to encode the box geometry and precedence graph and the decoder is a recurrent neural network (RNN) which inputs the current encoder output, as well as the current box packing state of the target container, and outputs the next box to pack, as well as its orientation. We train our network on randomly generated initial box configurations, without supervision, via policy gradients to learn optimal TAP policies to maximize packing efficiency and stability. We demonstrate the performance of TAP-Net on a variety of examples, evaluating the network through ablation studies and comparisons to baselines and alternative network designs. We also show that our network generalizes well to larger problem instances, when trained on small-sized inputs. [ABSTRACT FROM AUTHOR]

Genetic Algorithms (GAs) are introduced to tackle the packing problem. The scheduling in Additive Manufacturing (AM) is also dealt with to set up a managed market, called "Lonja3D". This will enable to determine an alternative tool through the combinatorial auctions, wherein the customers will be able to purchase the products at the best prices from the manufacturers. Moreover, the manufacturers will be able to optimize the production capacity and to decrease the operating costs in each case. [ABSTRACT FROM AUTHOR]

Production planning in 3D printing factories brings new challenges among which the scheduling of parts to be produced stands out. A main issue is to increase the efficiency of the plant and 3D printers productivity. Planning, scheduling, and nesting in 3D printing are recurrent problems in the search for new techniques to promote the development of this technology. In this work, we address the problem for the suppliers that have to schedule their daily production. This problem is part of the LONJA3D model, a managed 3D printing market where the parts ordered by the customers are reorganized into new batches so that suppliers can optimize their production capacity. In this paper, we propose a method derived from the design of combinatorial auctions to solve the nesting problem in 3D printing. First, we propose the use of a heuristic to create potential manufacturing batches. Then, we compute the expected return for each batch. The selected batch should generate the highest income. Several experiments have been tested to validate the process. This method is a first approach to the planning problem in 3D printing and further research is proposed to improve the procedure. Key words: additive manufacturing, production planning, packing problem, optimization, nesting. [ABSTRACT FROM AUTHOR]