Return to search

Cutting stock problems with nondeterministic item lengths

Based on an application in the field of server consolidation, we consider the one-dimensional cutting stock problem with nondeterministic item lengths. After a short introduction to the general topic we investigate the case of normally distributed item lengths in more detail. Within this framework, we present two lower bounds as well as two heuristics to obtain upper bounds, where the latter are either based on a related (ordinary) cutting stock problem or an adaptation of the first fit decreasing heuristic to the given stochastical context. For these approximation techniques, dominance relations are discussed, and theoretical performance results are stated. As a main contribution, we develop a characterization of feasible patterns by means of one linear and one quadratic inequality. Based on this, we derive two exact modeling approaches for the nondeterministic cutting stock problem, and provide results of numerical simulations.

Identiferoai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:85479
Date17 May 2023
CreatorsMartinovic, John, Hähnel, Markus, Scheithauer, Guntram, Dargie, Waltenegus, Fischer, Andreas
PublisherSpringer
Source SetsHochschulschriftenserver (HSSS) der SLUB Dresden
LanguageEnglish
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/acceptedVersion, doc-type:article, info:eu-repo/semantics/article, doc-type:Text
Rightsinfo:eu-repo/semantics/openAccess
Relation1614-2411, 10.1007/s10288-018-0384-4

Page generated in 0.0019 seconds