An algorithm for a cutting stock problem on a strip
- PDF / 285,812 Bytes
- 7 Pages / 595 x 842 pts (A4) Page_size
- 66 Downloads / 250 Views
#1997 Operational Research Society Ltd. All rights reserved. 0160-5682/97 $12.00
An algorithm for a cutting stock problem on a strip S Benati UniversitaÁ di Trento, Italy A cutting stock problem is formulated as follows: a set of rectangular pieces must be cut from a set of sheets, so as to minimize total waste. In our problem the pieces are requested in large quantities and the set of sheets are long rolls of material. For this class of problems we have developed a fast heuristic based on partial enumeration of all feasible patterns. We then tested the effectiveness on a set of test problems ranging from practical to random instances. Finally, the algorithm has been applied to check the asymptotic behaviour of the solution when a continuous stream of pieces is requested and cutting decisions are to be made while orders are still arriving. Keywords: cutting stock problem; heuristics
Problem formulation The bidimensional cutting stock problem consists of cutting a number of pieces from a sheet of material in order to minimize waste. This problem is frequently met in many industrial applications and may involve materials such as rolls of paper, sheets of iron, planks of wood and so on. Furthermore, it has applications in pallet loading, memory share in large computers, as well as in other areas (for a general discussion see Dyckhoff1). The problem is NP-hard since it includes one dimensional cutting problems as a special case. It can be solved either by exact algorithms whose spatial or temporal complexity is exponential or by heuristic procedures whose solutions can be very far from the optimal one. The speci®c problem we are interested in concerns a paper factory and can be stated in the following way. Requests are made for pieces (or items) of rectangular shape. Each piece j, j 1, . . . , n, has a height hj and a width wj and is requested in a certain quantity dj, where dj is usually a very large number, more than one hundred. Each of these pieces can be rotated and cut from a set of very long rolls, where each roll i, i 1, . . . , m, has a width Wi and virtually in®nite height. However, due to technological constraints, a ®rst guillotine cut must be made where the height is at most H from the base, and every successive cut must be both orthogonal and guillotine. An orthogonal cut means that the corners between successive cuts can only be of 90 ; a guillotine cut means that each cut must go from one side of a rectangle straight to the opposite side. In this setting it is not explicitly requested that cuts should have a maximum number of stages although it is reported in the literature that a low number of stages is most preferred in practice, since it is important to limit the rotation of material. Our algorithm will generate at most two stage cuts. Correspondence: S. Benati, UniversitaÁ degli studi di Trento I 38100 Trento-Via Inama, 5 Italia.
This problem is related to an application in the paper industry, where at a certain phase of the production plan, a large number of white papers are requested. Solut
Data Loading...
