Abstract
Local Search Algorithms for the Rectangle Packing Problem with General Spatial Costs
S. Imahori, M. Yagiura and T. Ibaraki
We propose local search algorithms for the rectangle packing problem to
minimize a general spatial cost associated with the locations of rectangles.
The problem is to pack given rectangles without overlap in the plane
so that the maximum cost of the rectangles is minimized.
Each rectangle has a set of modes, where each mode specifies the width and
height of the rectangle and its spatial cost function.
The spatial costs are general piecewise linear functions which
can be non-convex and discontinuous.
Various types of packing problems and scheduling problems can be formulated
in this form. To represent a solution of this problem,
a pair of permutations of n rectangles is used to determine their horizontal
and vertical partial orders, respectively.
We show that, under the constraint specified by such a pair of permutations,
optimal locations of the rectangles can be efficiently determined by
using dynamic programming.
The search for finding good pairs of permutations is conducted by
local search and metaheuristic algorithms.
We report computational results on various implementations using
different neighborhoods, and compare their performance.
We also compare our algorithms with other existing heuristic algorithms
for the rectangle packing problem and scheduling problem.
These computational results exhibit good prospects of the proposed algorithms.
Keywords:
rectangle packing,
sequence pair,
general spatial cost,
dynamic programming,
metaheuristics.
[Full Version : PS file/PDF file]
Improved Local Search Algorithms for the Rectangle Packing Problem with General Spatial Costs
S. Imahori, M. Yagiura and T. Ibaraki
The rectangle packing problem with general spatial costs is to pack given
rectangles without overlap in the plane so that the maximum cost of the
rectangles is minimized. This problem is very general, and various types
of packing problems and scheduling problems can be formulated in this form.
For this problem, we have previously presented local search algorithms
using a pair of permutations of rectangles to represent a solution.
In this paper, we propose speed-up techniques to evaluate solutions
in various neighborhoods. Computational results for the rectangle
packing problem and a real-world scheduling problem exhibit
good prospects of the proposed techniques.
Keywords:
packing,
sequence pair,
general spatial cost,
dynamic programming,
local search.
[Full Version : PS file/PDF file]
Local Search Algorithms for the Two-Dimensional Cutting
Stock Problem with a Given Number of Different Patterns
S. Imahori, M. Yagiura, S. Umetani, S. Adachi and T. Ibaraki
We consider the two-dimensional cutting stock problem
which arises in many applications in industries.
In recent industrial applications, it is argued that the setup cost
for changing patterns becomes more dominant and it is impractical to
use many different cutting patterns.
Therefore, we consider the pattern restricted two-dimensional
cutting stock problem, in which the total number of applications
of cutting patterns is minimized while the number of different cutting
patterns is given as a parameter n.
For this problem, we develop local search algorithms.
As the size of the neighborhood plays a crucial role in determining
the efficiency of local search,
we propose to use linear programming techniques for the purpose of
restricting the number of solutions in the neighborhood.
In this process, to generate a cutting pattern, it is required
to place all the given products (rectangles) in the stock sheet
(two-dimensional area) without mutual overlap.
For this purpose, we develop a heuristic algorithm using an existing
rectangle packing algorithm with the sequence pair coding scheme.
Finally, we generate random test instances of this problem
and conduct computational experiments, to see the effectiveness
of the proposed algorithms.
Keywords:
two-dimensional cutting stock problem,
linear programming,
rectangle packing,
neighborhood,
local search.
[Full Version : PS file/PDF file]