Optimizing the placement of irregular shapes

Placement is part of the cutting problem encountered whenever a manufactured object is produced by transforming the material. As such, it concerns a wide range of industries, including metal, wood, glass, garment and leather.

The manufacture of an object is often carried out with the aim of reducing production costs by cutting material consumption. This trend is linked in particular to rising raw material prices. In general, the optimal use of resources is a growing concern in the manufacturing industry.

An industrial formulation of the two-dimensional cutting problem might be as follows: "Given a raw material presented in the form of several units of possibly different sizes and shapes, how to produce a quantity of parts, according to demand and stock levels, using the minimum amount of material, and doing so in a time compatible with the deadlines set by the customer."

The quantity of parts to be produced may or may not be known in advance. While the main objective is to minimize raw material consumption, it is also topical to produce quickly to meet increasingly tight delivery deadlines, on a "just-in-time" basis to avoid storage costs.

A request based on a list of parts and a certain quantity of raw material is the initial input to the process. Constraints are defined as restrictions imposed on the process to take account of material properties, part quality, cutting method, stock levels, etc.

The placement problem consists in finding the best amalgam in the sense of the placement objectives, while the cutting problem involves finding a set of amalgams to satisfy the demands. An amalgam is a way of cutting a unit of raw material. Placement is the most important part of the cutting problem, and you can't effectively solve a cutting problem without effectively solving the placement problem.

Placement is one of the most interesting combinatorial optimization problems. Despite the considerable progress made by computer tools, enumeration methods, whether exhaustive or partial, are still unsatisfactory in terms of execution time or efficiency. As these problems often contain many solutions of acceptable practical interest, research is focused on the development of heuristic methods. The aim is to find a solution of satisfactory quality in a reasonable computation time, especially as for real problems, it is not always imperative to find the optimum solution, but solutions whose quality and time taken to obtain them remain acceptable.