An Improved Upper Bound for the Gap of Skiving Stock Instances of the Divisible Case

John Martinovic () and Guntram Scheithauer ()
Additional contact information
John Martinovic: Institut für Numerische Mathematik, Technische Universität Dresden
Guntram Scheithauer: Institut für Numerische Mathematik, Technische Universität Dresden

A chapter in Operations Research Proceedings 2017, 2018, pp 179-184 from Springer

Abstract: Abstract The 1D skiving stock problem (SSP) is a combinatorial optimization problem being of high relevance whenever an efficient utilization of given resources is intended. In the classical formulation, (small) items shall be used to build as many large objects (specified by some required length) as possible. Due to the NP-hardness of the SSP, the performance of the LP relaxation (measured by the additive gap of the related optimal values) and/or heuristics are of scientific interest. In this paper, theoretical properties of the best fit decreasing heuristic (for the SSP) are investigated and shown to provide a new and improved upper bound for the gap of the so-called divisible case.

Keywords: Cutting and packing; Skiving stock problem; Divisible case; Gap; Best fit decreasing (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-89920-6_25

Ordering information: This item can be ordered from
http://www.springer.com/9783319899206

DOI: 10.1007/978-3-319-89920-6_25

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().