Publications of Dr. Guntram Scheithauer
2017
G. Scheithauer
Introduction to Cutting and Packing Optimization

J. Martinovic, A. Fischer, E. Jorswieck, G. Scheithauer
Integer Linear Programming Formulations for Cognitive Radio Resource Allocation
IEEE Wireless Communication Letters, vol. 6, no. 4, pp. 494497, 2017

J. Martinovic, M. Hähnel , G. Scheithauer, W. Dargie, A. Fischer
Cutting Stock Problems with Nondeterministic Item Lengths: A New Approach for Multiprocessor Scheduling

J. Martinovic, G. Scheithauer, V. de Carvalho
A Comparative Study of the Arcflow Model and the OneCut Model for onedimensional Cutting Stock Problems
EJOR 266/2, 458471
(online DOI10.1016/j.ejor.2017.10.008,November 2017)

J. Martinovic, G. Scheithauer
The Skiving Stock Problem and its Relation to Hypergraph Matchings

J. Martinovic, G. Scheithauer
Combinatorial Investigations on the Maximum Gap for Skiving Stock Instances of the Divisible Case
(
online , Annals on OR, January 2018)

J. Martinovic, G. Scheithauer
An Upper Bound of $ \Delta(E)<3/2 $ for Skiving Stock Instances of the Divisible Case
(
online , June 2017)
 Discrete Applied Mathematics, Volume 229, Pages 161167, Okt. 2017

T. Buchwald, G. Scheithauer
Creating worstcase instances for lower bounds of the 2D
Strip Packing Problem,
Operations Research Proceedings 2016, 103109,

J. Martinovic, E. Jorswieck, G. Scheithauer
On the solution of generalized spectrum allocation problems
Operations Research Proceedings 2016, 133138,
2016

T. Buchwald, G. Scheithauer
A 5/9 Theorem on Packing Squares into a Square

J. Martinovic, G. Scheithauer
New Theoretical Investigations on the Gap of the Skiving Stock Problem

J. Martinovic, E. Jorswieck, G. Scheithauer
The Skiving Stock Problem and its Application to Cognitive Radio Networks,
IFACPapersOnLine, 49/12 (2016) 99–104
(klick here)

J. Martinovic, G. Scheithauer
Integer Rounding and Modified Integer Rounding for the Skiving Stock Problem,
Discrete Optimization, 21 (2016) 118130

J. Martinovic, G. Scheithauer
The Skiving Stock Problem and its Application to Resource
Allocation

Yu. Stoyan, G. Scheithauer, G. Yaskov
Packing nonequal spheres into containers of different shapes
Cybernetics and Systems Analysis, 2016, Vol. 52, No.3, p.
419426 (engl.) and p. 97105 (russ.)

T. Buchwald, G. Scheithauer
Upper Bounds for Heuristic Approaches to the Strip Packing Problem
Int. Trans. in Oper. Res. 23/12, 93119

J. Martinovic, G. Scheithauer
The Proper Relaxation and the Proper Gap of the Skiving Stock Problem
Mathematical Methods of Operations Research, 84/3 (2016) 527548
(online
DOI: 10.1007/s0018601605522, June 2016)

T. Buchwald, G. Scheithauer
Creating WorstCase Instances for Upper and Lower Bounds
of the TwoDimensional Strip Packing Proble
Operations Research Proceedings 2015, 5562,

J. Martinovic, G. Scheithauer
On the solution of generalized spectrum allocation problems
Operations Research Proceedings 2015, 6370,

I. Friedow, G. Scheithauer
Using Contiguous 2DFeasible 1D Cutting Patterns for the
2D Strip Packing Problem
Operations Research Proceedings 2015, 7178,

I. Friedow, G. Scheithauer
New Inequalities for 1D Relaxations of the 2D Rectangular Strip Packing Problem,
Operations Research Proceedings 2014, 151157,
(klick here)

T. Buchwald, G. Scheithauer
Upper Bounds for Heuristic Approaches to the Strip Packing Problem,
Operations Research Proceedings 2014, 6570,
(klick here)
2015

A. Fischer, G. Scheithauer,
Cutting and Packing Problems with Placement Constraints
in: Optimized Packings with Applications, Eds. G. Fasano and J. Pinter, Springer, 119156.
(klick here)

P. Stetsyuk, T. Romanova, G. Scheithauer
On the global minimum in a balanced circular packing problem,
Optimization Letters,
(online DOI 10.1007/s1159001509379, August 2015)

J. Martinovic, G. Scheithauer
Improved Upper Bounds for the Gap of the Skiving Stock Problem

V. M. Kartak, A. V. Ripatti, G. Scheithauer, S. Kurz
Minimal proper nonIRUP instances
of the onedimensional Cutting Stock Problem
Discrete Applied Mathematics 187 (2015) 120–129

T. Buchwald, G. Scheithauer
Improved Performance Bounds of the COMB3D Heuristic
for the threedimensional Strip Packing Problem
2014

J. Martinovic, G. Scheithauer
ILP models for the skiving stock problemr
(appeared in
EJOR, Nov 2015,
and EJOR 251/2, 1 June 2016, 356  368)

T. Buchwald, K. Hoffmann, G. Scheithauer
Relations between capacity utilization, minimal bin size and bin number
Annals of Oper. Res.,
June 2014, Volume 217, Issue 1, pp 5576

J. Bennell, G. Scheithauer, Y. Stoyan,T. Romanova, A. Pankratov
Optimal clustering of a pair of irregular objects,
J. of Global Opt.,
online April 2014)

F. Heinicke, A. Simroth, G. Scheithauer and A. Fischer
On a Railway Maintenance Scheduling Problem with
Customer Costs and MultiDepots
,
EURO Journal on Transportation and Logistics
(online December 24, 2014)
2013
2012

T. Buchwald, G. Scheithauer
A note on ''Relations between capacity utilization and minimal bin number''

K.~Hoffmann, G. Scheithauer
Relations between capacity utilization and minimal bin number

G. Scheithauer, Y. Stoyan, J. Bennell, T. Romanova, A. Pankratov
Containment of a pair of rotating objects within a container of minimal area or perimeter

M. A. Mesyagutov, G. Scheithauer , G. Belov,
New Constraint Programming Approaches for 3D Orthogonal Packing

M. A. Mesyagutov, G. Scheithauer , G. Belov,
LP Bounds in Various Constraint Programming Approaches for
Orthogonal Packing
Computers & Operations Research, 39(10): 24252438, (2012)
( online Dec 2011) )
2011

G. Belov, V. Kartak, H. Rohling, G. Scheithauer
Conservative scales in packing problems
(
online Dec 2011)

G. Belov, G. Scheithauer
Gaps between optimal values of some packing and scheduling problems

G. Belov, M. A. Mesyagutov, E. A. Mukhacheva, and G. Scheithauer.
Packing of onedimensional bins with contiguous selection of identical items: An exact method of optimal solution
Automation and Remote Control 72 (1):141159, 2011.
 G. Scheithauer, Y. G. Stoyan, T. Romanova, A. Krivuly
Covering a polygonal region by rectangles
Computational Optimization and Applications 48 (2011) 675695.
(
online May 2009)
2010

J. Bennell, G. Scheithauer, Y. G. Stoyan, T. Romanova,
Tools of mathematical modelling of arbitrary object packing problems
Ann. Oper. Res., (2010) 179:343368
(published online 7.11.08)
here
2009
2008
2007
 G. Belov, G. Scheithauer
LowerDimensional Bounds and a New Model for HigherDimensional
Orthogonal Packing
Preprint MATHNM092007, TU Dresden
 G. Belov, G. Scheithauer
Setup and Open Stacks Minimization
in OneDimensional Stock Cutting
INFORMS J. on Computing 19/1 (2007) 2735
 G. Scheithauer, T. Romanova, Y. Stoyan
Translational polygon containment
Journal of Mechanical Engineering 10/3, 6775 (2007)
 B. Ristau, G. Fettweis, G. Scheithauer, A. Fischer
Linear Programming in Embedded Systems
ECMI Newsletter, No. 41, 29  31, March 2007
 G. Belov, G. Scheithauer, E.A. Mukhacheva
OneDimensional Heuristics Adapted for TwoDimensional Rectangular Strip Packing
Journal of Operat. Res. Soc. (2007) 110
2006
2005
 G. Scheithauer, Yu.G. Stoyan, T. Romanova
Mathematical Modeling of Interactions of Primary
Geometric 3D Objects
Cybernetics and Systems Analysis 41/3 (2005) 332 342
 G. Belov, Chiglintsev A.V., Filippova A.S., Mukhacheva E.A., G. Scheithauer, Shirgazin R.R.
The twodimensional strip packing problem:
a numerical experiment with wastefree instances
using algorithms with block structure
Preprint MATHNM012005 TU Dresden,
 Y. Stoyan, N. Gil, G. Scheithauer,
A. Pankratov, I.Magdalina
Packing of convex polytopes into a parallelepiped
Optimization 54/2 (2005) 215236
 G. Scheithauer, G. Belov
A New Model and Lower Bounds for Oriented NonGuillotine TwoDimensional Strip Packing
Proceedings of the Workshop WSCSP2005, Miercurea Ciuc, Rumania 15.18.9.2005, pp. 1928
 G. Scheithauer, Y. Stoyan and T. Romanova
Mathematical modelling of interaction of a circular segment and primary objects
Proceedings of the Workshop WSCSP2005, Miercurea Ciuc, Rumania 15.18.9.2005, pp. 3746
2004
2003
G. Belov, G. Scheithauer

Models with Variable Strip Widths for TwoDimensional
TwoStage Cutting
Preprint MATHNM172003, TU Dresden,
 G. Belov, G. Scheithauer
The number of Setups (Different Patterns)
in OneDimensional Stock Cutting
Preprint MATHNM152003, TU Dresden
 G. Scheithauer, Y. Stoyan, N. Gil, T. Romanova
Phifunctions for circular segments
Preprint MATHNM072003, TU Dresden
 G. Belov, G. Scheithauer
A branchandcutandprice algorithm for
one and twodimensional twostaged cutting (stock) problems
Preprint MATHNM032003, TU Dresden
 Y. Stoyan, G. Yaskov, G. Scheithauer
Packing of various radii solid spheres
into a parallelepiped
CEJOR 11/4 (2003) 389408
2002
2001
2000
1999
1998
1997
1996
1995
1994
1993
1992
1991
1990
1989
1988
1987
1986
1985
1982
Back
Abstracts
2002
Construction of a Phifunction
for two convex polytopes
Authors: Y. Stoyan, J. Terno, G. Scheithauer, N. Gil,
T. Romanova,
Applicationes Mathematicae 29.2 (2002) 199  218.
In this paper, the analytical description of $\Phi $functions for two
convex polytopes is investigated. These $\Phi $functions can be used for
mathematical modelling of packing problems in the threedimensional space.
Only translations of the polytopes are considered. The approach consists of
two stages. At first the 0level surface of a $\Phi $function is
constructed, and secondly, the surface is extended to get the $\Phi $%
function. The method for constructing the 0level surface is described in
detail, and therefore also for computing a $\Phi$function.
Preprint version:
Postscript,
PDF
Back
Phifunctions for primary 2Dobjects
Authors: Y. Stoyan, J. Terno, G. Scheithauer, N. Gil,
T. Romanova,
Studia Informatica Universalis 2.1 (2002) 1  32.
Within the field of Cutting and Packing problems the placement or
allocation of smaller objects within a larger region has
high importance.
In order to develop efficient solution approaches, the interaction of two
placed objects has to be modelled in a suitable manner.
In this paper we
follow the concept of Phifunctions.
A comprehensive investigation of
all mutual positions of two socalled primary objects is given
and corresponding Phifunctions are presented
for each suitable pair of two such primary objects.
Preprint version:
Postscript,
PDF
Back
Tighter bounds for the gap and nonIRUP
constructions in the onedimensional cutting stock problem
Authors: Jürgen Rietz and Guntram Scheithauer,
Optimization 51.6 (2002) 927  963.
The onedimensional cutting stock problem is investigated with respect to the
difference between the optimal function value of the discrete problem and its
continnuous relaxation. A tighter bound for this gap is presented, followed
by some nonIRUP constructions. Finally, instances with gap 7/6 are
constructed, the largest gap known so far.
Preprint version:
Postscript,
PDF
Back
Phifunctions for primary 3Dobjects
Authors: Y. Stoyan, G. Scheithauer, D. Pridatko,
T. Romanova, N. Gil
Preprint MATHNM152002, TU Dresden, November 2002.
Within the field of packing problems the placement of 3D objects is of
great importance.
In order to develop efficient solution approaches, the
interaction of two placed objects has to be modelled in a suitable manner.
In this paper we follow the concept of Phifunctions.
Phifunctions are presented for each suitable pair of
socalled primary 3D objects from the collection of objects with
spherical, parallelepipedal or cylindrical frontiers.
Postscript,
PDF
Back
Families of NonIRUP instances
of the onedimensional cutting stock problem
Authors: Juergen Rietz, Guntram Scheithauer and
Johannes Terbo
Discrete Appl. Math. 121 (2002) 229245.
In case of the onedimensional cutting stock problem (CSP)
one can observe for any instance a very small gap
between the integer optimal value and the continuous relaxation
bound.
These observations have initiated a series of investigations.
An instance possesses the integer roundup property (IRUP)
if its gap is smaller than 1.
It is wellknown that there exist instances of the CSP having
a gap greater than 1 but there is not known any instance
with gap at least 2.
In this paper, families of nonIRUP instances are presented
and methods to construct such instances are given.
Especially, an instance with gap equal to 10/9 is obtained.
Furthermore, an equivalence relation for instances of the CSP is considered
to become independent from the real size parameters.
Preprint version:
Postscript,
PDF
Back
A Cutting Plane Algorithm
for the OneDimensional Cutting Stock Problem with
Multiple Stock Lengths
Authors: Gleb Belov and Guntram Scheithauer
EJOR 141/2 (2002) 274294.
A cutting plane approach combining ChvatalGomory
cutting planes with column generation is generalized for the case of
multiple stock lengths in the onedimensional
cutting stock problem. Appropriate modifications of the column
generation procedure and the rounding heuristic are proposed.
A comparison with the
branchandprice method for the problem with one stock type and
representative test results are reported.
Preprint version:
Postscript,
PDF
Back
Phifunctions for complex 2Dobjects
Authors: Y. Stoyan, M. Gil, T. Romanova and G. Scheithauer
4OR 2/1 (2004) 6984.
Within twodimensional cutting and packing problems with irregular shaped
objects, the concept of Phifunctions has been proven to be very helpful
for several solution approaches. In order to construct such Phifunctions
a previous work, in which socalled primary objects are considered, is
continued. Now Phifunctions are constructed for pairs of objects which
can be represented as a finite combination (union, intersection, complement)
of primary objects which allows the handling of arbitrary shaped objects by
appropriate approximations of sufficient accuracy.
Postscript,
PDF
Back
Solving OneDimensional Cutting Stock Problems
with Multiple Stock Material Lengths
Using Cutting Plane Approach
Authors: G. Scheithauer and G. Belov
Operations Research Proceedings 2001,
SpringerVerlag Berlin Heidelberg, 285292, 2002.
For exactly solving the onedimensional cutting stock problem (CSP)
with several stock material lengths,
a cutting plane approach (CPA) is proposed.
This work is a continuation of [12] where firstly
column generation technique and CPA have been combined
for the CSP with identical stock material pieces.
In order to ensure efficient implementation
of the generation problems in case of no and of additional cutting planes,
some modifications of known methods
have been performed.
The efficiency of the algorithm is demonstrated by extensive numerical
results.
Postscript
Back
2001
Solving onedimensional cutting stock
problems exactly with a cutting plane algorithm
Authors: Guntram Scheithauer, Johannes Terno,
Antje Müller and Gleb Belov,
JORS 52 (2001) 13901401
When solving the onedimensional cutting stock problem (CSP) as
an integer linear programming problem
one has to overcome computational difficulties
arising from the integrality condition
and the huge number of variables.
In the usual solution approach the continuous relaxation is solved via
column generation technique followed by an appropriate rounding
of the in general noninteger solution.
Obviously, in this way an optimal solution cannot be obtained
for any instance.
In order to compute a proved optimal solution,
techniques like branchandbound have to be applied.
In this paper we present another exact solution approach for the CSP
which is based on the cutting plane method.
We investigate how to compute and how to use
suitable cutting planes in an algorithm
which is based on column generation.
Results of extensive computational experiments are reported.
Preprint version:
Postscript,
PDF
Back
Packing of various radii solid spheres
into a parallelepiped
Authors: Y. Stoyan, G. Yaskov, G. Scheithauer,
Preprint MATHNM172001, TU Dresden.
CEJOR 11/4 (2003) 389408.
The paper considers the optimization problem of packing
various solid spheres into a parallelepiped with minimal height. Based on a
corresponding mathematical model the peculiarities of the problem are
investigated. Regarding these peculiarities a solution method is offered.
The method includes three stages: searching for some approximations (extreme
points) to local minima; improving the approximations by a neighborhood
search; computing local minima using these approximations as starting
points. Preliminary numerical results for examples with up to 60 spheres are
also given.
Postscript,
PDF
Back
2000
Solving onedimensional cutting stock
problems exactly with a cutting plane algorithm
Author: Guntram Scheithauer,
Inderfurth, K. (ed.) et al., Operations research proceedings 1999.
Selected papers of the symposium (SOR '99), Magdeburg, Germany,
September 13, 1999. Berlin: Springer. 8691 (2000).
Postscript
Back
Facetdefining inequalities for the cutting
stock problem
Authors: Guntram Scheithauer and Johannes Terno
Pesquisa Operational 19/2 (2000) 131144
In this paper the polyhedron of the cutting stock problem is
investigated with respect to facetdefining inequalities. For some classes
of valid inequalities this property is proved.
Preprint version:
Postscript,
PDF
Back
An Efficient Approach for the MultiPallet
Loading Problem
Authors: Guntram Scheithauer, Johannes Terno, Uta Sommerweiss
and Jan Riehme
EJOR 123/2 (2000) 372381
The Distributor's or MultiPallet Loading Problem
is considered in this paper.
This problem is to load a set of distinct products with given
quantities on pallets (or in containers)
and to minimize the number of pallets needed.
The theoretical objective of finding the best space utilization is
restricted by a list of practical aspects
(technological constraints, weight distribution over the pallet,
stability aspects, etc.).
Keeping in mind a general branch and bound framework an efficient
heuristic for the considered multipallet loading problem is
developed.
The threedimensional solution approach uses in the kernel a
layerwise loading strategy with optimal twodimensional
loading patterns.
Computational experiments show the efficiency of the proposed
algorithms.
Preprint version:
Postscript,
PDF
Back
Class of 0level $\Phi$functions of point
sets which have circumferential or polygonal frontiers (in Russian),
Authors: Y.Y. Stoyan, G. Scheithauer, N.I. Gil, T.E. Romanova
and I.V. Magdalina
J. of Mech. Engineering 3 (2000) 12, 117123.
A structural approach for constructing the 0level surface of Phifunctions
of point sets in twodimensional space which have circumferential or
polygonal frontiers is considered.
The approach can be used for solving optimization problems of geometric
design for constructing Phifunctions of a pair of geometric objects
having arbitrary spatial shapes.
Back
1999
Tighter Relaxations for the Cutting
Stock Problem
Authors: Christiph Nitsche, Guntram Scheithauer and
Johannes Terno
EJOR 112 (1999) 654663
In the cutting stock problem (CSP) a given order for smaller
pieces has to be cut from larger stock material
in such a way
that the number of stock material needed is minimal.
Based on the classical integer linear
programming model the common solution technique consists of
solving the corresponding continuous relaxation problem
followed by several heuristics which construct
integer solutions.
In many cases an optimal solution can be obtained quickly in this way.
But for instances which do not possess the
integer roundup property the optimality of the
solution obtained cannot be verified by means
of the LP bound.
In order to overcome this nonsatisfactory situation,
two tighter relaxations of the CSP are proposed,
and results of theoretical and numerical investigations
are presented.
PDF
Back
Numerical investigations on the MIRUP of
the 2stage guillotine cutting stock problem
Authors: Jan Riehme, Guntram Scheithauer and Johannes Terno
J. of Math. Eng. 2 (1999) 3/4, 101107
The MIRUP (Modified Integer RoundUp Property) leads to an upper bound
for the gap between the optimal value of the integer problem and that of
the corresponding continuous relaxation rounded up. This property is known
to hold for many instances of the onedimensional cutting stock problem
but there are not known so far any results with respect to the twodimensional
case.
In this paper we investigate numerically three variants of the socalled
2stage guillotine cutting stock problem with respect to the MIRUP. The
variants differ by allowing either only horizontal or only vertical or
horizontal and vertical guillotine cuts in the first stage.
Within a sample of 900 randomly generated instances there did not arise
any instance with gap larger than 1. Moreover, for more than 60% of the
instances an optimal solution was found.
Postscript
Back
LPbased bounds for the Container
and MultiContainer Loading Problem
Author: Guntram Scheithauer
Int. Trans. in Op. Res. 6 (1999) 199213
In this paper we develop new bounds for problems of optimal packing
of small (rectangularshaped) pieces within one or several larger
containers, that are bounds for the
Container Loading Problem (CLP) and the
MultiContainer Loading Problem (MCLP).
We propose new relaxations for the CLP and MCLP which lead to
linear programming problems.
We discuss a solution approach based on a column generation technique.
Results of computational tests are also given.
Postscript
Back
Optimale Positionierung beim Vollholzzuschnitt
durch automatisierte Fehlererkennung
Authors: Guntram Scheithauer und Johannes Terno
Wiss. Z. TU Dresden 46 (1999) 2, 7881.
The progress in automatic defect detection in the wood industry allows
now the usage of improved optimization models and solution methods in order
to get a higher yield in cutting processes.
Since the wooden material contains defects, quality restrictions of
the products are of high importance which have to be fulfilled in the rip
and/or crosscutting process.
This is done traditionally by human labour.
By using automated defect detection and corresponding image analysis,
now it is possible to integrate this quality control into the optimization
process.
In this paper, the modelling of one and twodimensional cutting problems
is considered as well as efficient solution
approaches are discussed.
Postscript
Back
1998
4Block Heuristic for the Rectangle Packing
Problem
Authors: Guntram Scheithauer and Uta Sommerweiss
EJOR 108 (1998), 509526
In this paper the rectangle packing problem (RPP) is considered. The
RPP consists in finding a packing pattern of small rectangles within a
larger rectangle such that the area utilization is maximized.
We develop new heuristics for the RPP which are based on the G4heuristic
for the pallet loading problem. In addition to the general RPP we take
also into account further restrictions which are of practical interest.
PDF
Back
New Cases of the Cutting Stock Problem Having
MIRUP
Authors: Christoph Nitsche, Guntram Scheithauer and
Johannes Terno
Math. Meth. of OR (ZOR) 48.1 (1998) 105116.
The modified integer roundup property (MIRUP) for a linear integer
minimization problem means that the optimal value of this problem is not
greater than the optimal value of the corresponding LP relaxation rounded
up plus one.
In earlier papers the MIRUP was shown to hold for the socalled divisible
case and some other subproblems of the onedimensional cutting stock problem.
In this paper we extent the results by using special transformations,
proving the existence of nonelementary patterns in the solution, and involving
more detailed greedy techniques.
PDF
Back
Families of NonIRUP instances of the onedimensional
cutting stock problem
Authors: Guntram Scheithauer, Johannes Terno and
Jürgen Rietz
Preprint MATHNM091998, TU Dresden 1998
In case of the onedimensional cutting stock problem (CSP) one can
observe for any instance a very small gap between the integer optimal
value and the continuous relaxation bound. These observations have initiated
a series of investigations. An instance possesses the integer roundup
property (IRUP) if its gap is smaller than 1. It is wellknown that there
exist instances of the CSP having a gap greater than 1 but there
is not known any instance with gap at least 2.
In this paper we present families of nonIRUP instances and give methods
to construct such instances. Furthermore, an equivalence relation for instances
of the CSP is considered to become independent from the real size parameters.
Postscript
Back
1997
Equivalence and Dominance for Problems of Optimal
Packing of Rectangles
Author: Guntram Scheithauer
Ricerca Operativa 27 (1997) 83, 334.
In this paper we consider the problem of optimal packing of small rectangles
within a larger rectangle.
The topic consists of a comprehensive investigation of equivalence
and dominance of packing patterns. Using suitable kinds of equivalence
and dominance, the goal is to develop an efficient branch and bound algorithm
with which problems of practical interest may be solved exactly.
Postscript
Back
A Heuristic Approach for Solving the
MultiPallet Packing Problem
Authors: Guntram Scheithauer and Johannes Terno
Decision making under conditions of uncertanty (cuttingpacking problems),
Ufa State Aviation Technical Univ. 1997, 140154.
We consider the Distributer's Pallet Packing Problem.
This problem is to pack a set of distinct products with given
quantities in greater volumes (pallets, containers)
and to minimize the number of used volumes.
The theoretical objective of finding the best space utilization is
restricted by a list of practical aspects
(technological constraints, weight distribution over the pallet,
stability aspects, etc.).
Keeping in mind a general branch and bound framework an efficient
heuristic for the considered multipallet packing problem is
developed.
The threedimensional solution approach uses in the kernel a
layerwise packing strategy with optimal twodimensional
packing patterns.
Linear Programming lower bounds for the number of pallets needed
to pack the total consignment are developed.
Computational experiments show the efficiency of the proposed
algorithms.
Postscript
Back
The Properties IRUP and MIRUP for the Cutting
Stock Problem
Authors: Guntram Scheithauer and Johannes Terno
Decision making under conditions of uncertanty (cuttingpacking problems),
Ufa State Aviation Technical Univ. 1997, 1632.
The integer roundup property (IRUP) holds for an integer linear
minimization problem if, for any instance, the optimal
value equals the linear programming (LP) relaxation lower bound rounded up,
and the modified integer roundup property (MIRUP) holds
if the optimal value is not
greater than the optimal value of the corresponding LP relaxation rounded up
plus one.
In recent years, the well known cutting stock problem gets a growing
interest with respect to investigations for IRUP and MIRUP.
In this paper we summarize work done and discuss open questions.
Postscript
Back
The value correction method for packing of
irregular shapes
Authors:
Guntram Scheithauer, Oksana Y. Sergeyeva and Johannes Terno
Decision making under conditions of uncertanty (cuttingpacking problems),
Ufa State Aviation Technical Univ. 1997, 261269.
We consider the packing of irregular shapes in a strip of given width such
that the length of the occupied part is minimized. Starting
with a first allocation of
the objects with a greedylike technique the placement of every object is
evaluated and with respect to the evaluation a new packing pattern is
generated. Continueing this foregoing we select the best pattern. Numerical
experience show a good performance of the algorithm.
Postscript
Back
Cutting and Packing: An Annotated Bibliography
Authors: Harald Dyckhoff (RWTH Aachen), Guntram Scheithauer
and Johannes Terno
in: Annotated Bibliographies in Combinatorial Optimization,
M. Dell'Amico, F. Maffioli, S. Martello (eds.), Wiley 1997, 393412.
In drawing up this bibliography, we have concentrated on publications
that appeared in 1990 or later (with some exceptions). For the literature
prior to 1990 we refer to the books and surveys listed in the first section,
especially to the book of Dyckhoff/Finke(1992).
In this paper we have included more than 130 annotated references.
A BiBTeX data base containing more than 1100 entries related to C&P
can be obtained from the authors.
Postscript
Back
Theoretical Investigations on the Modified
Integer RoundUp Property for the OneDimensional Cutting Stock Problem
Authors: Guntram Scheithauer and Johannes Terno
Oper. Res. Lett. 20 (1997) 93100.
Many numerical computations show a small difference only between the
optimal value of the onedimensional cutting stock problem and that of
its corresponding linear programming relaxation.
In this paper we investigate the onedimensional cutting stock problem
with respect to the modified integer roundup property (MIRUP) and present
some results on subproblems having the MIRUP.
PDF,
Postscript
Back
LPbounds for the container and
multicontainer loading problem
Author: Guntram Scheithauer
Zimmermann, Uwe (ed.) et al., Operations research proceedings 1996.
Selected papers of the symposium, SOR'96, Braunschweig, Germany,
September 36, 1996. Berlin: Springer. 123128 (1997).
Postscript
Back
1996
The G4Heuristic for the Pallet Loading Problem
Authors: Guntram Scheithauer and Johannes Terno
JORS 47 (1996) 511522
A new heuristic to the wellknown (twodimensional orthogonal) pallet
loading problem (PLP) is proposed in this paper. This heuristic referred
to as G4heuristic is based on the definition of the socalled G4structure
of packing patterns. The G4structure is a generalization of the common
used block structure of packing patterns which requires the same orientation
of packed boxes within each block.
The G4heuristic yields in approximately 99% of the test instances
an optimal solution and solves all instances exactly where at most 50 boxes
are contained in an optimal packing.
Although the algorithm is pseudopolynomial the computational experiments
reported show that also instances with more than 200 packed boxes in an
optimal solution can be handled with a small amount of computational time.
Moreover, so far there is not known any instance where the gap between
optimal value and the value obtained by the G4heuristic is larger than
1 box.
Postscript
Back
The Solution of Twostage Guillotine Cutting
Stock Problems Having Extremely Varying Order Demands
Authors: Jan Riehme, Guntram Scheithauer and
Johannes Terno
EJOR 91 (1996) 543552
In this paper the solution of twostage guillotine cutting stock problems
is considered. Especially such problems are under investigation where the
sizes of the order demands differ in a large range.
We propose a new approach dealing with such situations and compare
it with the classical Gilmore/Gomory approach. We report results of extensive
numerical experiments which show the advantages of the new approach.
Postscript
Back
A new heuristic for the Pallet Loading Problem
Authors: Guntram Scheithauer and Johannes Terno
Operations Research Proceedings 1995, SpringerVerlag
Berlin Heidelberg (1996) 8489
In this paper we analyse the structure of optimal packing patterns
and we introduce the denotation of G4structure. Then we propose a new
heuristic for solving the PLP. Since the algorithm is based on dynamic
programming it is of pseudopolynomial type. The computational experiments
show that instances having more than 200 items in an (optimal) packing
pattern can be handled with small computational amount of time.
Postscript
Back
Auftragsoptimierung bei Zuschnitt und Packungsproblemen
als ganzzahliges lineares Optimierungsmodell
Authors: Guntram Scheithauer and Johannes Terno
Wiss. Z. TU Dresden, 45 (1996) 6, 4448.
The paper deals with the modelling of various cutting and packing problems
as an integer linear programming problem. For this the column generation
method is an efficient solution method especially to get a socalled residual
problem. An integer feasible solution for the initial problem is found
with a greedysolution of the residual problem. Thereby the introduced
Modified Integer RoundUp Property is helpful. The general framework is
illustrated by results for various special problems.
Postscript
Back
Dreidimensionale Packungsprobleme (Auftragsoptimierung
auf Europaletten) (in German)
Authors:
Johannes Terno, Guntram Scheithauer, Jan Riehme und Uta Sommerweiss
Working Paper 1996, Dresden University of Technology
We consider the MultiPallet Loading Problem. This problem is to pack
a set of distinct products with given quantities in greater volumes (pallets,
containers) and to minimize the number of used volumes.
The theoretical objective of finding the best space utilization is
restricted by a list of practical aspects (technological constraints, weight
distribution over the pallet, stability aspects, etc.).
Keeping in mind a general branch and bound framework, an efficient
heuristic for the considered multipallet loading problem is developed.
The threedimensional solution approach uses in the kernel a generalized
layerwise packing strategy with optimal twodimensional packing patterns.
Computational experiments show the efficiency of the proposed algorithms.
Back
A New Heuristic Approach for Solving the
MultiPallet Packing Problem
Authors: Guntram Scheithauer and Johannes Terno
Preprint MATHNM031996, Dresden University of Technology
We consider the Distributer's Pallet Packing Problem. This problem
is to pack a set of distinct products with given quantities in greater
volumes (pallets, containers) and to minimize the number of used volumes.
The theoretical objective of finding the best space utilization is
restricted by a list of practical aspects (technological constraints, weight
distribution over the pallet, stability aspects, etc.).
Keeping in mind a general branch and bound framework an efficient heuristic
for the considered multipallet packing problem is developed.
The threedimensional solution approach uses in the kernel a layerwise
packing strategy with optimal twodimensional packing patterns.
Linear Programming lower bounds for the number of pallets needed to
pack the total consignment are developed. Computational experiments show
the efficiency of the proposed algorithms.
Postscript
Back
1995
A branch and bound algorithm for solving onedimensional
cutting stock problems exactly
Authors: Guntram Scheithauer and Johannes Terno
APLICATIONES MATHEMATICAE 23, 2 (1995) 151167
Many numerical computations reported in the literature show an only
small difference between the optimal value of the onedimensional cutting
stock problem (1CSP) and that of its corresponding linear programming relaxation.
Moreover, theoretical investigations have proven that this difference is
smaller than 2 for a wide range of subproblems of the general 1CSP.
In this paper we give a branch and bound algorithm to compute optimal
solutions for instances of the 1CSP. Numerical results are presented of
about 900 randomly generated instances with up to 100 small pieces and
all of them are solved to optimality.
Postscript
Back
Numerical investigations on the MIRUP
of the 2stage guillotine cutting stock problem
Authors:Jan Riehme, Guntram Scheithauer and Johannes Terno
Preprint MATH  NM  17  1995, TU Dresden.
The MIRUP (Modified Integer RoundUp Property)
leads to an upper bound for the gap between the optimal value
of the integer problem and that of
the corresponding continuous relaxation rounded up.
This property is known to hold for many instances of the onedimensional
cutting stock problem but there are not known so far any results
with respect to the twodimensional case.
In this paper we investigate numerically
three variants of the socalled 2stage guillotine
cutting stock problem with respect to the MIRUP.
The variants differ by allowing either only horizontal
or only vertical or horizontal and vertical guillotine cuts in the
first stage.
Within a sample of 900 randomly generated instances there did not arise any
instance with gap larger than 1.
Moreover, for more than 60 percent of the instances an optimal solution
was found.
PDF,
Postscript
Back
The solution of packing problems with pieces of
variable length and additional allocation constraints
Author: Guntram Scheithauer
Optimization 34 (1995) 8196
In this paper onedimensional partitioning and packing problems of
the following type are investigated. The pieces, which are to be packed,
are assumed to have a variable length in a given range. Furthermore, the
placement of any packed piece has to fulfill additional allocation constraints.
The value of a piece is dependent affine linearly on its length. Find a
feasible partition or packing, resp., with maximum total value.
For these problems mixedinteger optimization models with linear constraints
are developed and suitable solution methods are discussed. Especially,
a branch and bound algorithm and an algorithm based on the socalled forward
state strategy are proposed.
Postscript
Back
The Modified Integer RoundUp Property of the
OneDimensional Cutting Stock Problem
Authors: Guntram Scheithauer and Johannes Terno
EJOR 84 (1995) 562571
A linear integer minimization problem (IP) has the modified integer
roundup property (MIRUP) if the optimal value of any instance of IP is
not greater than the optimal value of the corresponding LP relaxation problem
rounded up plus one.
The aim of this paper is to investigate numerically whether the MIRUP
holds for the onedimensional cutting stock problem. The computational
experiments carried out with a lot of randomly generated instances of the
onedimensional cutting stock problem show, that for all instances an integer
solution fulfills the MIRUP. Moreover, in most cases the optimal value
equals the roundup optimal value of the corresponding LP relaxation.
Similarly, the approach proposed to verify the MIRUP is usable as a
new heuristic procedure for solving onedimensional cutting stock problems.
This heuristic always leads to very good solutions being optimal in the
most cases.
PDF,
Postscript
Back
1994
A Polynomial Time Algorithm for the Guillotine
Pallet Loading Problem
Authors: Alexander G. Tarnowski, Johannes
Terno and Guntram Scheithauer
INFOR 32 (1994) 275287
A polynomial time algorithm is presented for solving the twodimensional
guillotine cutting stock problem where all small rectangles are of the
same dimensions (generating pallet loading patterns). It is based on the
initial problem decomposition into three subproblems. Two of these subproblems
are solved by dynamic programming recurrence in polynomial time and the
third subproblem is solved during constant time. This algorithm requires
the minimization of linear modulo functions. A polynomial time algorithm
is used for this purpose.
Postscript
Back
On the MAXGAP Problem for Cutting Stock Problems
Author: Guntram Scheithauer
J.Inform.Process.Cybernet.(EIK) 30 (1994) 2, 111117
The MAXGAP problem of a linear integer optimization problem P
consists in determining the maximum difference (gap) d(P) between
the optimal value z*(E) of an instance E in P. and
the LP bound z_c(E) with respect to all E in P.
In the case of the onedimensional cutting stock problem (1D CSP)
it is known that d(1D CSP)>= 1 + 5/132 but there is also a conjecture
that d(1D CSP) <= 2.
In this paper we show that in the case of the restricted exact 2stage
twodimensional cutting stock problem (RE2 CSP) the maximum gap
increases at least linearly in the number m of pieces. It holds
d(RE2 CSP)> m/3.
For the (nonrestricted) exact 2stage twodimensional cutting stock
problem (E2 CSP) an example is given such that d(E2 CSP)>= 2
(1 + 5/132 )> 2.075 follows which yields also a lower bound for the
general twodimensional cutting stock problem.
Furthermore some consequences for higherdimensional cutting stock
problems and with respect to applications are discussed.
Postscript
Back
1993
Theoretical Investigations on the Modified
Integer RoundUp Property for the OneDimensional Cutting Stock Problem
Authors: Guntram Scheithauer and Johannes Terno
Preprint MATH  NM  12  1993, TU Dresden.
Many numerical computations show a small difference only between the
optimal value of the onedimensional cutting stock problem and that of
its corresponding linear programming relaxation.
In this paper we investigate the onedimensional cutting stock problem
with respect to the modified integer roundup property (MIRUP) and present
some results on subproblems having the MIRUP.
PDF,
Postscript
Back
Modelling of Packing Problems
Authors: Guntram Scheithauer and Johannes Terno
Optimization 28 (1993) 6384
In this paper we develop linear optimization models with continuous
and 0/1variables for packing problems with convex and nonconvex polygons.
The number of 0/1variables is essentially reduced in comparison to
Beasley (1985). This reduction is based on the use of very helpful tools
 the socalled (outer) hodograph and the inner hodograph of two polygons.
The hodograph can be used to handle the nonoverlapping condition of two
packed objects. The containment of a polygon in an other polygon can be
characterized by using the inner hodograph.
Postscript
Back
Computation of optimal phisimple
guillotine cutting patterns
Authors: Guntram Scheithauer
J. Inf. Process. Cybern. 29, No.2, 115128 (1993).
Postscript
Back
1992
Algorithms for the container loading problem
Author: Guntram Scheithauer
Operations Research Proceedings 1991, SpringerVerlag
Berlin Heidelberg (1992) 445452
In this paper we consider the threedimensional problem of optimal
packing of a container with rectangular pieces. We propose an approximation
algorithm based on the "forward state strategy" of dynamic programming.
A suitable description of packings is developed for the implementation
of the approximation algorithm, and some computational experience is
reported.
Postscript
Back
About the gap between the optimal values of the
integer and continuous relaxation onedimensional cutting stock problem
Authors: Guntram Scheithauer and Johannes Terno
Operations Research Proceedings 1991, SpringerVerlag
Berlin Heidelberg (1992) 439444
The purpose of this paper is to show that the gap is possibly smaller
than 2. Some helpful results are summarized.
PDF,
Postscript
Back
1991
A new branch and bound algorithm for product scheduling
with ressource constraints
Authors: Guntram Scheithauer and Johannes Terno
Applicationes Mathematicae 21 (1991) 273282
Back
A note on handling residual lengths
Author: Guntram Scheithauer
Optimization 22 (1991) 3, 361366
PDF
Back
A threedimensional bin packing algorithm
Author: Guntram Scheithauer
J. Inf. Process. Cybern. EIK 27 (1991) 5/6, 263271
PDFt
Back
1990
Optimaler Zuschnitt trapezf"ormiger Teile
Author: Guntram Scheithauer
Wiss. Z. TU Dresden 39 (1990) 1, 191195
PDFt
Back
1989
On the stochastic complexity of
the asymmetric traveling salesman problem
Authors: H.U.Dost, G. Scheithauer and J.Terno
EJOR 43 (1989) 313316
Back
1988
Guillotine cutting of defective boards
Authors: Guntram Scheithauer and Johannes Terno
Optimization 19 (1988) 1, 111121
PDF
Back
The partition of a square in rectangles with equal areas
Authors: Guntram Scheithauer and Johannes Terno
J. Inf. Process. Cybern. EIK 24 (1988) 189200
PDF
Back
1987
Zuschnittprobleme und ihre praktische L"osung
Authors: Johannes Terno, Rudolf Lindemann und Guntram Scheithauer
Fachbuchverlag Leipzig und
Verlag Harry Deutsch Thun und Frankfurt/Main 1987
Back
Zur Ermittlung eines restringierten k"urzesten Weges
Author: Guntram Scheithauer
Seminarberichte der HU Berlin, Nr. 90 (1987) 107114
PDF
Back
1986
Complexity investigations on the ellipsoid algorithm
Authors: Johannes Terno und Guntram Scheithauer
Optimization 17 (1986) 2, 203207
Back
Effektive L"osung von GuillotineZuschnittproblemen
Authors: Guntram Scheithauer und Johannes Terno
Wiss. Z. TU Dresden 35 (1986) 4, 3540
Back
1985
On recursive computation of minimum spanning trees
for special partial graphs
Author: Guntram Scheithauer
Optimization 16 (1985) 1, 4149
Back
On recursive computation of minimum spanning trees
for special partial and subgraphs
Author: Guntram Scheithauer
Graphs, hypergraphs and applications, Proc. Conf. Graph Theory,
Eyba/GDR 1984, TeubnerTexte Math. 73, 141144 (1985).
Back
Rekursive Berechnung von Minimalger"usten f"ur spezielle Subgraphen
Author: Guntram Scheithauer
J. Inf. Process. Cybern. EIK 21 (1985) 12, 613624
PDF
Back
1982
A new extension principle algorithm for the traveling salesman problem
Authors: Guntram Scheithauer and Johannes Terno
Optimization 13 (1982) 2, 231245
Back
This page is under construction and is subject to change.
Last modified: January 19, 2015
Impressum