Cutting stock problems with nondeterministic item lengths: a new approach to server consolidation

John Martinovic (), Markus Hähnel (), Guntram Scheithauer (), Waltenegus Dargie () and Andreas Fischer ()
Additional contact information
John Martinovic: Technische Universität Dresden
Markus Hähnel: Technische Universität Dresden
Guntram Scheithauer: Technische Universität Dresden
Waltenegus Dargie: Technische Universität Dresden
Andreas Fischer: Technische Universität Dresden

4OR, 2019, vol. 17, issue 2, No 3, 173-200

Abstract: Abstract 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.

Keywords: Cutting and packing; Server consolidation; Normal distribution; Nondeterministic item lengths; Integer programming; HAEC; 90C10; 90C90; 90B36; 68M07 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10288-018-0384-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:aqjoor:v:17:y:2019:i:2:d:10.1007_s10288-018-0384-4

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-018-0384-4

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().