J. Martinovic, M. Hähnel , G. Scheithauer, W. Dargie, A. Fischer
Cutting Stock Problems with Nondeterministic Item Lengths: A New Approach for Multiprocessor Scheduling
Based on a particular application in the field of multiprocessor scheduling, 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 introduce two heuristics to obtain approximate solutions, either by a related (ordinary) cutting stock problem or by an adaptation of the first fit decreasing heuristic to the given stochastical context. 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.
(Preprint MATH-NM-04-2017, TU Dresden, July 2017, 20 p.)