This paper focuses on the study of the two-dimensional cutting or packing problem of irregular polygons with free rotation that must be organized within a set of identical plates with fixed dimensions. The main objective is to minimize the number of plates that can fit a specific demand of objects. Given the constraint of non-overlapping, the possibility of free rotations and the irregular shape of the objects, this is a combinatorial problem with NP-Hard complexity. A column generation procedure was proposed, in which the master problem will be in charge of selecting the subset of plates that will compose the solution, while the auxiliary problem will create each of the proposed plates to be given to the master problem as columns. For this, the auxiliary problem will use a two phased procedure with a constructive algorithm and a local search enhanced with swapping and insertion operators, made using Unity engine. To test the proposed algorithms, known instances for the cutting stock problem were selected. The solutions and computational times achieved were compared by benchmarking with the available work in the literature, obtaining satisfactory results. Further work will include the sequential use of the shown algorithms that produce good performance in order to produce a more specialized algorithm.

This book investigates in detail the two-dimensional packing and cutting problems in the field of operations research and management science. It introduces the mathematical models and intelligent solving algorithms for these problems, as well as their engineering applications. Most intelligent methods reported in this book have already been applied in reality, which can provide reference for the engineers. The presented novel methods for the two-dimensional packing problem provide a new way to solve the problem for researchers interested in operations research or computer science. This book also introduces three new variants of packing problems and their solving methods, which offer a different research direction. The book is intended for undergraduate and graduate students who are interested in the solving methods for packing and cutting problems, researchers investigating the application of intelligent algorithms, scientists studying the theory of the operations research and CAM software developers working on integration of packing and cutting problem.

"There are different variants for the Cutting and Packing Problems (CPP), i.e. nesting problems consist of placing irregular small objects inside a bigger plate with fixed dimensions. This paper aims to solve a Two-dimensional Cutting Stock Problem (CSP) with irregular polygons that must be packed inside a set of identical plates with fixed dimensions. The main objective is to minimize the number of plates needed to pack all the polygons. This is a combinatorial problem with NP-hard complexity, as the main problem is based on a non-overlapping arrangement of the polygons. We used a column generation (CG) approach to find a good solution, and a simulation engine, Unity, to generate the columns. This simulation tool allowed us to verify and satisfy the non-overlapping constraints to get the final cutting patterns. The final solution is tested with the shapes1 instance found in the ES-ICUP website and then compared to one similar paper from literature. We did obtain similar results in terms of plates needed to pack all polygons but achieving a better computational time." -- Tomado del Formato de Documento de Grado.

This conference, organized jointly by UTC and INRIA, is the biennial general conference of the IFIP Technical Committee 7 (System Modelling and Optimization), and reflects the activity of its members and working groups. These proceedings contain a collection of papers (82 from the more than 400 submitted) as well as the plenary lectures presented at the conference.

Seminar paper from the year 2020 in the subject Business economics - Operations Research, grade: 1,3, University of Kaiserslautern, language: English, abstract: The Cutting Stock Problem (CSP) appears when a material has to be cut into smaller pieces and occurs in many branches of industry. On the one hand, the CSP belongs to the earliest studied problems through methods of Operational Research and on the other to the most intensively studied problems in combinatorial optimization. In the one-dimensional Cutting Stock Problem (1DCSP), there are typically identical pieces of a single standard length, called rolls, that need to be cut into smaller pieces lengthwise. Examples, where the cutting process is performed in one single dimension, can be found in the steel industry and the paper industry . The two-dimensional CSP (2DCSP) is classified into cutting of regular and irregular shapes and is often found in clothing and shoe-leather industries. A real-world application of a three-dimensional CSP (3DCSP) lies in the production of mattresses, where rubber blocks are cut into different types of orthogonal rectangular prisms. Methods of finding an optimal solution exist for the 1DCSP. Often in large problem instances, the required time for finding an optimal solution proliferates, and heuristics may turn out to be the more sensible option in this case. Nowadays, there are countless different ways to find acceptable solutions in a fast manner of time, among others, the column generation approach, which is the central component of the present work. This work is organized as follows. In Chapter 2, a brief overview of different formulations for the CSP is given. Furthermore, some known extensions of the classic CSP are presented, e.g., raw material, that consists of various sizes at the same time. CSP has many relatives, the closest is the Bin Packing Problem (BPP), where items are packed into bins as efficiently as possible. The third chapter shows the column generation technique for solving the CSP and provides the connection between a solution for the relaxed problem and an integer solution. In Chapter 4, different test instances of the CSP are compared using a column generation implementation solved in three different MIP solvers. The conclusion is provided in Chapter 5.