A one-pass heuristic for nesting problems
Journal Title: Operations Research and Decisions - Year 2019, Vol 29, Issue 1
Abstract
A two-dimensional cutting (packing) problem with items of irregular shape and rectangular sheets is studied. Three types of problems are considered: single-sheet problems without restrictions on the number of elements, single-sheet problems with restrictions on the number of elements, and cutting stock problems (restricted number of items and unrestricted number of sheets). The aim of the optimization is to maximize the total area of the elements cut from a single plate or to minimize the number of sheets used in cutting. A one-pass algorithm is proposed which uses the popular concept of a no-fit polygon (NFP). The decision on whether an item is cut from a sheet in a given step depends on the value of a fitting function. The fitting function depends on the change in the NFP of individual items. We test eight different criteria for the evaluation of partial solutions. On the basis of numerical experiments, the algorithm that generates the best solution for each of the considered problem types is selected. The calculation results for these algorithms are compared with results obtained by other authors.
Authors and Affiliations
Igor KIERKOSZ, Maciej ŁUCZAK
Keywords
Related Articles
- EP ID EP632203
- DOI 10.5277/ord190103
- Views 39
- Downloads 0
A study on the influence of the discretisation unit on the effectiveness of modelling currency exchange rates using the binary-temporal representation
An exchange rate can be expressed in the form of a binary-temporal representation. Such a representation is based on a discretization of movements in the exchange rate, in which to each change in the value - equal to a g...
Equilibrium strategies in a fiscal-monetary game. A simulation analysis
The results from a simulation analysis of the policy-mix have been presented, carried out in a fiscal-monetary game, in which fiscal and monetary authorities make decisions from the point of view of realizing their own r...
A multi-level decision making model for the supplier selection problem in a fuzzy situation
Supplier selection plays a vital role in evolving an effective supply chain and the overall performance of organisations. Choosing suppliers may involve different levels arranged in a hierarchical structure. Decisions ar...
Innovation management in Polish enterprises
The modern enterprise operates in a turbulent, demanding and unstable environment. Technical and technological progress as well as socioeconomic development create new opportunities but, at the same time, they force ente...
Forecast value added (FVA) analysis as a means to improve the efficiency of a forecasting process
A praxeological approach has been proposed in order to improve a forecasting process through the employment of the forecast value added (FVA) analysis. This may be interpreted as a manifestation of lean management in for...