Jose
Oliveira
Professor,
Department
of
Industrial
Engineering
University
of
Porto
Porto,
Portugal
jfo
@fe.up.pt
Abstract
Cutting and Packing problems are hard combinatorial optimization problems that arise in the context of several manufacturing and process industries or in their supply chains. These problems occur whenever a bigger object or space has to be divided into smaller objects or spaces, so that waste is minimized. This is the case when cutting paper rolls in the paper industry, large wood boards into smaller rectangular panels in the furniture industry, irregularly shaped garment parts from fabric rolls in the apparel industry, but also the case when packing boxes on pallets and these inside trucks or containers, in logistics applications. All these problems have in common the existence of a geometric sub-problem, which deals with the small object non-overlap constraints.
The resolution of these problems is not only a scientific challenge, given its intrinsic difficulty, but has also a great economic impact as it contributes to the decrease of one of the major cost factors for many production sectors: the raw-materials. In some industries raw-material may represent up to 40% of the total production costs. It has also a significant environmental repercussion as it leads to a less intense exploration of the natural resources from where the raw-materials are extracted, and decreases the quantity of garbage generated, which frequently has also important environmental impacts. In logistics applications, minimizing container and truck loading space waste directly leads to less transportation needs and therefore to smaller logistics costs and less pollution.
In this talk the several Cutting and Packing problems will be characterized and exemplified, based on Gerhard Wäscher’s typology (2007), allowing non-specialists to have a broad view over the area. Afterwards, as geometry plays a critical role in these problems, the geometric manipulation techniques more relevant for Cutting and Packing problems resolution will be presented. Finally, aiming to illustrate some of the most recent developments in the area, some approaches based on heuristics and metaheuristics, for the container loading problem, and based on mathematical programming models, for the irregular packing problem, will be described.
Biographical Sketch
Dr. Oliveira’s main area of scientific activity is Operations Research and Management Science. Within Operations Research his main application area are the Cutting and Packing Problems, while from the techniques viewpoint his research is centered in the use and development of Metaheuristics approaches and their hybridization with Mathematical Programming based methods.
Cutting
and
Packing
problems
are
hard
combinatorial
optimization
problems
that
arise
under
several
practical
contexts,
whenever
big
pieces
of
raw-material
have
to
be
cut
into
smaller
items,
or
small
items
have
to
be
packed
inside
a
larger
container,
so
that
waste
is
minimized.
These
problems
include
hard
geometric
constraints
when
dealing
with
the
optimization
layer.
Dr.
Oliveira
has
also
worked
on
Vehicle
Routing
Problem,
especially
in
the
integration
of
route
definition
with
the
container
loading
problem.
His
research
on
Lotsizing
and
Scheduling
problems
in
industrial
contexts
mainly
builds
on
his
expertise
on
Metaheuristics
and
optimization.
Dr.
Oliveira
has
been
giving
special
attention
in
the
last
years
to
several
problems
arising
in
the
Transportation
sector,
in
particular
freight
transportation.
Therefore,
new
frameworks
to
assess
and
enforce
cargo
stability,
both
static
and
dynamic,
weight
distribution
and
other
relevant
goals
in
road
transportation,
have
been
developed,
implemented
and
tested.
Another
important
line
of
research
is
related
to
the
car
rental
industry,
where
integration
of
pricing
and
capacity
planning
decisions
has
been
approached,
under
a
revenue
management
framework.
Dr.
Oliveira
has
also
worked
on
the
use
of
the
quantitative
methods,
provided
by
Operations
Research
and
Management
Science,
to
support
decision
making
in
Higher
Education
institutions
management,
which
includes
workload
models,
sustainability,
institutional
benchmarking
and
assessment
and
evaluation
of
institutions
and
teaching
staff.
*Light refreshments will be served at 12 noon