An exact algorithm for the N-sheet two dimensional single stock-size cutting stock problem.
Saved in:
| Title: | An exact algorithm for the N-sheet two dimensional single stock-size cutting stock problem. |
|---|---|
| Authors: | Steyn, T.1 tjaart.steyn@nwu.ac.za, Hattingh, J. M.2 |
| Source: | Orion. 2015, Vol. 31 Issue 2, p77-94. 18p. 8 Charts. |
| Subjects: | Algorithm research, Stock-flow analysis, Integers, Optimal control theory, Quality control, Mathematical models |
| Abstract: | The method introduced in this paper extends the trim-loss problem or also known as 2D rectangular SLOPP to the multiple sheet situation where N same size two-dimensional sheets have to be cut optimally producing demand items that partially or totally satisfy the requirements of a given order. The cutting methodology is constrained to be of the guillotine type and rotation of pieces is allowed. Sets of patterns are generated in a sequential way. For each set found, an integer program is solved to produce a feasible or sometimes optimal solution to the N-sheet problem if possible. If a feasible solution cannot be identified, the waste acceptance tolerance is relaxed somewhat until solutions are obtained. Sets of cutting patterns consisting of N cutting patterns, one for each of the N sheets, is then analysed for optimality using criteria developed here. This process continues until an optimal solution is identified. Finally, it is indicated how a given order of demand items can be totally satisfied in an optimal way by identifying the smallest N and associated cutting patterns to minimize wastage. Empirical results are reported on a set of 120 problem instances based on well known problems from the literature. The results reported for this data set of problems suggest the feasibility of this approach to optimize the cutting stock problem over more than one same size stock sheet. The main contribution of this research shows the details of an extension of the Wang methodology to obtain and prove exact solutions for the multiple same size stock sheet case. [ABSTRACT FROM AUTHOR] |
| Copyright of Orion is the property of Operations Research Society of South Africa and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. 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.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 111392356 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: An exact algorithm for the N-sheet two dimensional single stock-size cutting stock problem. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Steyn%2C+T%2E%22">Steyn, T.</searchLink><relatesTo>1</relatesTo><i> tjaart.steyn@nwu.ac.za</i><br /><searchLink fieldCode="AR" term="%22Hattingh%2C+J%2E+M%2E%22">Hattingh, J. M.</searchLink><relatesTo>2</relatesTo> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Orion%22">Orion</searchLink>. 2015, Vol. 31 Issue 2, p77-94. 18p. 8 Charts. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Algorithm+research%22">Algorithm research</searchLink><br /><searchLink fieldCode="DE" term="%22Stock-flow+analysis%22">Stock-flow analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Integers%22">Integers</searchLink><br /><searchLink fieldCode="DE" term="%22Optimal+control+theory%22">Optimal control theory</searchLink><br /><searchLink fieldCode="DE" term="%22Quality+control%22">Quality control</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+models%22">Mathematical models</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: The method introduced in this paper extends the trim-loss problem or also known as 2D rectangular SLOPP to the multiple sheet situation where N same size two-dimensional sheets have to be cut optimally producing demand items that partially or totally satisfy the requirements of a given order. The cutting methodology is constrained to be of the guillotine type and rotation of pieces is allowed. Sets of patterns are generated in a sequential way. For each set found, an integer program is solved to produce a feasible or sometimes optimal solution to the N-sheet problem if possible. If a feasible solution cannot be identified, the waste acceptance tolerance is relaxed somewhat until solutions are obtained. Sets of cutting patterns consisting of N cutting patterns, one for each of the N sheets, is then analysed for optimality using criteria developed here. This process continues until an optimal solution is identified. Finally, it is indicated how a given order of demand items can be totally satisfied in an optimal way by identifying the smallest N and associated cutting patterns to minimize wastage. Empirical results are reported on a set of 120 problem instances based on well known problems from the literature. The results reported for this data set of problems suggest the feasibility of this approach to optimize the cutting stock problem over more than one same size stock sheet. The main contribution of this research shows the details of an extension of the Wang methodology to obtain and prove exact solutions for the multiple same size stock sheet case. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Orion is the property of Operations Research Society of South Africa and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. 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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=111392356 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.5784/31-2-527 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 18 StartPage: 77 Subjects: – SubjectFull: Algorithm research Type: general – SubjectFull: Stock-flow analysis Type: general – SubjectFull: Integers Type: general – SubjectFull: Optimal control theory Type: general – SubjectFull: Quality control Type: general – SubjectFull: Mathematical models Type: general Titles: – TitleFull: An exact algorithm for the N-sheet two dimensional single stock-size cutting stock problem. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Steyn, T. – PersonEntity: Name: NameFull: Hattingh, J. M. IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 07 Text: 2015 Type: published Y: 2015 Identifiers: – Type: issn-print Value: 0259191X Numbering: – Type: volume Value: 31 – Type: issue Value: 2 Titles: – TitleFull: Orion Type: main |
| ResultId | 1 |
